Answer to Question #199455 in Combinatorics | Number Theory for Curly

Question

Find the remainder when 7^21+49^21+343^21+2401^21 is divided by 7^20+1

Answer 1

1) $7^{21} + 49^{21} + 343^{21} + 2401{21} =$

$7^{21} + (7\cdot7)^{21}+(7\cdot7\cdot7)^{21} + (7\cdot7\cdot7\cdot7)^{21} =$

$7^{21} +{(7^{21})}^2+{(7^{21})}^3 + {(7^{21})}^4;$

2) $7^{21} = 7\cdot(7^{20})=7\cdot({7^{20} + 1})-7$

3) $Rem[7^{21} / (7^{20} + 1)] = -7$

We have represented 7²¹ as 7⋅(7²⁰+1)−7 (look step 2)

7⋅(7²⁰+1)−7 mod (7²⁰+1) = -7 because

$\frac{7\cdot(7^{21}+1) -7}{7^{21}+1} = \frac{7\cdot(7^{21}+1)}{7^{21}+1}+\frac{-7}{7^{21}+1} = 7+\frac{-7}{7^{21}+1}$

where is -7 is our reminder.

For steps 4, 5, 6 We have to raise our reminder to a power.

4) $Rem[{(7^{21})}^2/(7^{20} + 1)] = (-7)^{2}$

5) $Rem[{(7^{21})}^3/(7^{20} + 1)] = (-7)^3$

6) $Rem[{(7^{21})}^4/(7^{20} + 1)] = (-7)^4$

$Answer: -7+(-7)^2+(-7)^3+(-7)^4 = 2100$