Proving every 6^(6+35j)=648 mod 23004

[enzocreti]

How to prove that every 6^(6+35j) for nonnegative j is congruent to 648 mod 23004?

By Fermat litle theorem I can say (71-1)=70, 35 divides 70, so 6^35=1 mod 71

But how to continue the proof?

[User140242]

Originally Posted by enzocreti

How to prove that every 6^(6+35j) for nonnegative j is congruent to 648 mod 23004?

By Fermat litle theorem I can say (71-1)=70, 35 divides 70, so 6^35=1 mod 71

But how to continue the proof?

Maybe this can help, you can simplify:

6^(6+35j) - 648 = 0 mod 23004

2*324 *(72*6^35j-1) = 0 mod (324*71)

2*324*71*6^35j+2*324*(6^35j-1) = 0 mod (324*71)

[enzocreti]

Originally Posted by User140242

Maybe this can help, you can simplify:

6^(6+35j) - 648 = 0 mod 23004

2*324 *(72*6^35j-1) = 0 mod (324*71)

2*324*71*6^35j+2*324*(6^35j-1) = 0 mod (324*71)

the congruence should be equal to

6^6=0 mod 4

6^6=0 mod 81

6^6=9 mod 71

so the least exponent k for which 6^k=1 is k=35 a divisor of (71-1)=0

so this should conclude the proof

[bbb120]

Originally Posted by enzocreti

How to prove that every 6^(6+35j) for nonnegative j is congruent to 648 mod 23004?

By Fermat litle theorem I can say (71-1)=70, 35 divides 70, so 6^35=1 mod 71

But how to continue the proof?

you can use Exhaustive method with the help of computer!

[ATH]

Originally Posted by enzocreti

How to prove that every 6^(6+35j) for nonnegative j is congruent to 648 mod 23004?

6^6+35j = 6⁶ * 6^35j


Proof by induction:

Each time you increase j by 1, you multiply the previous result by 6³⁵ = 5184 (mod 23004)

Define: S_j = 6⁶ * 6^35j (mod 23004)

S₀ = 6⁶ (mod 23004) = 648 (mod 23004)
S₁ = S₀ * 6³⁵ (mod 23004) = 648*5184 (mod 23004) = 648 (mod 23004)
S_j+1 = S_j * 6³⁵ (mod 23004) = 648 (mod 23004)
Q.E.D


It works because 648*6³⁵ is again 648 (mod 23004).