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

Home > Numbers
A 2011 Problem (Posted on 2007-03-17) Difficulty: 3 of 5
Determine the remainder when (201156 + 34)28 is divided by 111.

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    
No Rating
Solution: (Hide)
111 = 3*37.

Now, 2011= -1 (mod 3) and, so 2011^56 = (-1)^56 = 1 (mod 3)

Accordingly, 2011^56 + 34 = -1 (mod 3), giving:
(2011^56 + 34)^28 = (-1)^28 (mod 3) = 1 (mod 3)
Now,
2011 = 13 (mod 37); so that:
2011^56 = 13^56 (mod 37)

13^2 = 21(mod 37);
13^3 = 14 (mod 37);
13^4 = 21^2 (mod 37) = -3 (mod 37)
13^7 = (14)*(-3) (mod 37) = -5 (mod 37)
13^14 = 25 (mod 37)
13^28 = 25^2 (mod 37) = -4 (mod 37)
13^56 = 16 (mod 37)

So, (2011^56 + 34)^28
= (16+34)^28 (mod 37)
= 50^28 (mod 37)
= 13^28( mod 37)
= -4 (mod 37)
= 33 (mod 37)

Accordingly, (2011^56 + 34)^28 = 1 (mod 3) = 33 (mod 37)
We observe that 3 and 37 are prime to each other.
Now the only number less than 111 that yields the respective remainders 1 and 33 when divided separately by 3 and 37 is 70.

Consequently, the required remainder is 70.

NOTE: This problem was inspired by the topic Remainder when Dividing Large Numbers inclusive of the Math Forum.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
SolutionsolutionCharlie2007-03-17 14:37:35
SolutionSilly questions get silly answersAdy TZIDON2007-03-17 13:44:14
SolutionIt remains to be said....Dej Mar2007-03-17 12:28:21
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 (3)
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