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

Home > Numbers
Forty-one's Forte (Posted on 2022-08-27) Difficulty: 3 of 5
Determine the quotient and remainder when 400....001 (100 zeros) is divided by 41.
Provide valid explanation for your answer.

See The Solution Submitted by K Sengupta    
Rating: 5.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Pencil and Paper | Comment 3 of 5 |
Lets start with the remainder, since that will be a pretty straightforward exercise in modular arithmetic. 
The big number can be written as 4*10^101 + 1, and we want this mod 41. 
4*10^101 + 1 
= 2^103 * 5^101 + 1 
= 2^4*(2^7)^14 * 5^2*(5^3)^33 + 1.

2^7=128=5 mod 41 and 5^3=125=2. So working in mod 41: 
2^4*(2^7)^14 * 5^2*(5^3)^33 + 1 
= 2^4*5^14 * 5^2*2^33 + 1
= 2^37 * 5^16 + 1
= 2^2*(2^7)^5 * 5*(5^3)^5 + 1
= 2^2*5^5 * 5*2^5 + 1 
= 2^7 * 5^6 + 1
= 2^7 * (5^3)^2 + 1
= 5 * 2^2 + 1
= 41 = 0 mod 41.

The remainder is 0. So our big number is a multiple of 41.  Onto the quotient.
4*10^101 + 1 = 41*10^100 - 999....999 (a number composed of 100 9's)
41*10^100 is obviously a multiple of 41 and because 999....999 (100 9's) is the difference of two multiples of 41, it is also a multiple of 41.

By Fermat's Little Theorem we know 10^40 = 1 mod 41, thus 99...99 (40 9's) is a multiple of 41.  But there may be a smaller number of 9's that is divisible by 41.  Fermat's Little Theorem also tells us that number of 9's is a factor of 40.

So we have candidates starting with 9, 99, 9999, 99999, 99999999 etc.  Fortunately the fourth candidate gives us 99999/41 = 2439.
Then 999....999 (100 9's) divided by 41 will be 20 blocks of 02439 concantenated.

Then (4*10^101 + 1)/41 
= (41*10^100 - 999....999)/41 
= 1 + 99999...99999 - 0243902439....02439 (20 blocks each of 99999 and 02439)
= 1 + 97560....97560 (20 blocks)
= 97560....9756097561 (19 blocks of 97560 followed by 97561)
This is our quotient.

  Posted by Brian Smith on 2022-08-30 10:58:23
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (1)
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 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information