My Math Forum  

Go Back   My Math Forum > College Math Forum > Number Theory

Number Theory Number Theory Math Forum


Reply
 
LinkBack Thread Tools Display Modes
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.
hasu is offline  
 
November 17th, 2009, 09:29 AM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
November 20th, 2009, 10:53 PM   #3
mpf
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)
mpf is offline  
Reply

  My Math Forum > College Math Forum > Number Theory

Tags
congruences, exponents, large, mods, solving



Search tags for this page
Click on a term to search for related topics.
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 12:41 PM
If D is a division ring, why are D-mods semisimple? watson Abstract Algebra 2 December 27th, 2012 02:48 PM
logarithms and exponents of extremely large or small numbers chanther Algebra 3 December 29th, 2011 07:03 PM
Congruences h05 Number Theory 2 October 15th, 2008 03:15 PM





Copyright © 2018 My Math Forum. All rights reserved.