
Number Theory Number Theory Math Forum 
 LinkBack  Thread Tools  Display Modes 
November 17th, 2009, 07:55 AM  #1 
Newbie Joined: Nov 2009 Posts: 1 Thanks: 0  Solving congruences for large exponents and mods
I am being asked to solve for x in the following: x^1477 = 2673 mod 3977. Additionally, I'm being asked to show what my p, q, and ?(3977) is that I used to solve. ?(3977) = 40 * 96 = 3840. Normally my first step would be to use Euler's theorem to reduce the large power (in this case 1477), but I'm always at a loss of what to do when the ? of the modulus is larger than the exponent. Any help is appreciated. 
November 17th, 2009, 08:29 AM  #2 
Global Moderator Joined: Nov 2006 From: UTC 5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms  Re: Solving congruences for large exponents and mods
I suppose you could solve x^1477 = 2673 mod 41 and x^1477 = 2673 mod 97 and then CRT the results together.

November 20th, 2009, 09:53 PM  #3 
Newbie Joined: Oct 2009 Posts: 20 Thanks: 0  Re: Solving congruences for large exponents and mods
As CRGreatHouse suggests, break down the problem: by factoring the modulus 3977 = 41 * 97 The RHS leaves remainders of 2673 = 8 (41) 2673 = 54 (97) So now we have 2 problems: Use Fermat's little theorem: to reduce the exponents: 1477 = 37 (40) 1477 = 37 (96) We're left with 2 smaller equations: Notice 37 * 13 = 1 (40) 37 * 13 = 1 (96) ( is it an accident that 13 is the same number for both? ) Raise both LHS and RHS to the 13th power, and use Fermat's little theorem again: This gives: x = 21(41) x = 43(97) Calculate: 97 * 11 = 1 (41) 41 * 71 = 1 (97) for the chinese remainder theorem: x = 21 * 97 * 11 + 43 * 41 * 71 + k*41*97 x = 431 (3977) 

Tags 
congruences, exponents, large, mods, solving 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Solving a System of Congruences  Student444  Abstract Algebra  5  February 17th, 2013 11:41 AM 
If D is a division ring, why are Dmods semisimple?  watson  Abstract Algebra  2  December 27th, 2012 01:48 PM 
logarithms and exponents of extremely large or small numbers  chanther  Algebra  3  December 29th, 2011 06:03 PM 
Congruences  h05  Number Theory  2  October 15th, 2008 02:15 PM 