Determine the quotient and remainder when 400....001 (100 zeros) is divided by 41.
Provide valid explanation for your answer.
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.