mersenneforum.org Proving every 6^(6+35j)=648 mod 23004
 Register FAQ Search Today's Posts Mark Forums Read

 2022-09-13, 07:22 #1 enzocreti   Mar 2018 2×269 Posts Proving every 6^(6+35j)=648 mod 23004 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?
2022-09-13, 07:55   #2
User140242

Jul 2022

22·13 Posts

Quote:
 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)

Last fiddled with by User140242 on 2022-09-13 at 07:57

2022-09-13, 09:30   #3
enzocreti

Mar 2018

2×269 Posts

Quote:
 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

2022-09-14, 00:32   #4
bbb120

"特朗普trump"
Feb 2019

22·3·11 Posts

Quote:
 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!

2022-09-14, 01:54   #5
ATH
Einyen

Dec 2003
Denmark

2×3×569 Posts

Quote:
 Originally Posted by enzocreti How to prove that every 6^(6+35j) for nonnegative j is congruent to 648 mod 23004?
66+35j = 66 * 635j

Proof by induction:

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

Define: Sj = 66 * 635j (mod 23004)

S0 = 66 (mod 23004) = 648 (mod 23004)
S1 = S0 * 635 (mod 23004) = 648*5184 (mod 23004) = 648 (mod 23004)
Sj+1 = Sj * 635 (mod 23004) = 648 (mod 23004)
Q.E.D

It works because 648*635 is again 648 (mod 23004).

 Similar Threads Thread Thread Starter Forum Replies Last Post MushNine Number Theory Discussion Group 9 2018-01-04 03:29 jasonp FactorDB 3 2011-10-17 18:04 CRGreathouse Software 13 2011-01-30 14:30 AntonVrba Math 2 2008-10-06 00:53 eepiccolo Lounge 10 2003-02-03 05:15

All times are UTC. The time now is 11:15.

Thu Dec 1 11:15:48 UTC 2022 up 105 days, 8:44, 0 users, load averages: 1.15, 0.86, 0.76