My Math Forum Solving congruences for large exponents and mods

 Number Theory Number Theory Math Forum

 November 17th, 2009, 08: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, 09: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, 10: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: $x ^ {1477}= 2673 ( 3977 )$ by factoring the modulus 3977 = 41 * 97 The RHS leaves remainders of 2673 = 8 (41) 2673 = 54 (97) So now we have 2 problems: $x ^ {1477}= 8 ( 41 )$ $x ^ {1477}= 54 ( 97 )$ Use Fermat's little theorem: $x^ {p-1}= 1 (p)$ to reduce the exponents: 1477 = 37 (40) 1477 = 37 (96) We're left with 2 smaller equations: $x ^ {37}= 8 ( 41 )$ $x ^ {37}= 54 ( 97 )$ 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: ${x ^ {37} }^ {13}= 8 ^ {13} = 21 ( 41 )$ ${x ^ {37} } ^ {13}= 54 ^ {13} = 43 ( 97 )$ 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

,
,

,

,

,

,

,

,

,

,

,

,

,

,

# solving large exponent modulus

Click on a term to search for related topics.
 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Student444 Abstract Algebra 5 February 17th, 2013 12:41 PM watson Abstract Algebra 2 December 27th, 2012 02:48 PM chanther Algebra 3 December 29th, 2011 07:03 PM h05 Number Theory 2 October 15th, 2008 03:15 PM

 Contact - Home - Forums - Cryptocurrency Forum - Top