All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Numbers
A 2006 Problem (Posted on 2006-07-27) Difficulty: 3 of 5
Determine the remainder when 612006 is divided by 2006.

Can you do this in a short time using pen and paper, and eventually a hand calculator, but no computer programs?

  Submitted by K Sengupta    
Rating: 3.3333 (3 votes)
Solution: (Hide)
The required remainder is 145.

EXPLANATION:
Both 61 and 17 are prime numbers and since (17,61)=1, by Fermatís Little Theorem, 61^16=1 (Mod 17) giving, 61^2000=1 (Mod 17). We observe that, 61=10 (Mod 17), so that 61^6=(-7)^6 (Mod 17)= 7^6 (Mod 17). Now, 7^2= -2 (Mod 17); so that 7^6= - 8 (Mod 17). Hence, 61^6= -8 (Mod 17), giving 61^2006= (61^2000)(61^6)= 1*(-8) (Mod 17)= - 8 Mod(17))= 9 Mod(17).

Again, 61^58 = 1(Mod 59), giving, 61^1972 = 1(Mod 59).Now, 61=2(Mod 59), so that, 61^34 = 2^34(Mod 59).Now, 2^6 = 5 (Mod 59); while 5^3=7 (Mod 59), giving 5^5 = 175 (Mod 59)= 57 (Mod 59), so that, 2^30 = 57 (Mod 59)= (-2)(Mod 59).Therefore, 2^34 = (-2)(2^4)= -32 (Mod 59)= 27 (Mod 59).Consequently, 2^2006 = (2^1972)(2^34)=1*27(Mod 59)= 27(Mod 59), so that, 61^2006 = 27(Mod 59)

Since, 61 is odd, it follows that 61^2006 is also odd. odd.Accordingly:

61^2006 = 27 Mod (59) = 9(Mod 17)= 1 Mod(2).---------(#)

Let, us denote 61^2006 by x, and the required remainder by r.
So, x-r is divisible by 2006 = 2*17*59; and since 2,17 and 19 are pairwise coprime, it follows that (x-r) is divisible by each of 2,17 and 59.

From the first congruence, we obtain,

x = 59*L + 27 = 9(Mod 17)
or, r = 9 (mod 17) giving, 59L + 18 = 0 (Mod 17); or, 8L + 1 = 0 (Mod 17); giving L = 2 (Mod 17) or, L = 17*M + 2, for some M.

Consequently, r = 59(17*M + 2)+ 27 = 1003*M + 145. For M=0, we obtain r = 145.

For, M greater than or equal to 2,we obtain r > = 2151 > 2006, which is not feasible.

For M=1, we obtain r = 1148, which is even and thus contradicts (#)

Consequently, it follows that the required remainder must be 145.

--------------------------------------------------------------------------------

Also refer to Nick Hobson's methodology given in this location.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
SolutionAnother approachNick Hobson2006-08-30 20:36:58
re: HowtoFederico Kereki2006-07-29 11:49:36
re: CORRECTIONFederico Kereki2006-07-29 11:48:22
CORRECTIONAdy TZIDON2006-07-29 01:56:19
re: A solutionRichard2006-07-28 00:14:36
SolutionA solutionDej Mar2006-07-27 17:36:48
SolutionHowtoe.g.2006-07-27 16:05:50
Advice (Read only if you are really stuck)Richard2006-07-27 13:54:30
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information