20220913, 07:22  #1 
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 (711)=70, 35 divides 70, so 6^35=1 mod 71 But how to continue the proof? 
20220913, 07:55  #2  
Jul 2022
2^{2}×13 Posts 
Quote:
Maybe this can help, you can simplify: 6^(6+35j)  648 = 0 mod 23004 2*324 *(72*6^35j1) = 0 mod (324*71) 2*324*71*6^35j+2*324*(6^35j1) = 0 mod (324*71) Last fiddled with by User140242 on 20220913 at 07:57 

20220913, 09:30  #3  
Mar 2018
2×269 Posts 
Quote:
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 (711)=0 so this should conclude the proof 

20220914, 00:32  #4 
"特朗普trump"
Feb 2019
大陆China
2^{2}×29 Posts 

20220914, 01:54  #5  
Einyen
Dec 2003
Denmark
2×1,693 Posts 
Quote:
Proof by induction: Each time you increase j by 1, you multiply the previous result by 6^{35} = 5184 (mod 23004) Define: S_{j} = 6^{6} * 6^{35j} (mod 23004) S_{0} = 6^{6} (mod 23004) = 648 (mod 23004) S_{1} = S_{0} * 6^{35} (mod 23004) = 648*5184 (mod 23004) = 648 (mod 23004) S_{j+1} = S_{j} * 6^{35} (mod 23004) = 648 (mod 23004) Q.E.D It works because 648*6^{35} is again 648 (mod 23004). 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Proving, for A > 1, (A+1)^n mod A = 0  MushNine  Number Theory Discussion Group  9  20180104 03:29 
Primality proving of DB factors?  jasonp  FactorDB  3  20111017 18:04 
Primality proving  CRGreathouse  Software  13  20110130 14:30 
New Class of primes  proving algorithm  AntonVrba  Math  2  20081006 00:53 
Countdown to proving M(6972593) is #38 down to less than 10!  eepiccolo  Lounge  10  20030203 05:15 