What is the remainder when the below number is divided by $100$?

What is the remainder when the below number is divided by $100$? $$1^{1} + 111^{111}+11111^{11111}+1111111^{1111111}+111111111^{111111111}\\+5^{1}+555^{111}+55555^{11111}+5555555^{1111111}+55555555^{111111111}$$ How to approach this type of question? I tried to brute force using Python, but it took very long time.

• If you are programming you can use binary-modular exponentiation. – Phicar Jul 22 '14 at 16:43
• Considering that the last term alone is larger than the number of atoms in the universe, I'm hardly surprised. – Semiclassical Jul 22 '14 at 16:44
• It was an aptitude question. Thanks @Phicar I want to know how do one do this kind of questions. – WannaBeCoder Jul 22 '14 at 16:46
• Hint: $55555555^{n} = 55^{n} \mod 100$. In fact for all of those terms, you can simply cross out all digits to the left of the hundreds place in the base. – mweiss Jul 22 '14 at 16:46
• Of course it took a long time in Python.... $55555555^{111111111}$ has approximately 860 million digits... which would take up close to 1.2 gigabytes of memory, if my back-of-the envelope calculation is accurate. – Emily Jul 22 '14 at 18:00

HINT:

$$(1+10n)^{1+10n}=1+\binom{1+10n}1(10n)\pmod{100}\equiv1+10n$$

and $$(5+50n)^{1+10n}=5^{1+10n}+\binom{1+10n}1(50n)5^{10n}\pmod{100}$$

Now, $$5^{m+2}-5^2=5^2(5^m-1)\equiv0\pmod{100}\implies5^{m+2}\equiv25\pmod{100}$$ for integer $m\ge0$

$$\implies5^{1+10n}+\binom{1+10n}1(50n)5^{10n}\equiv25+(1+10n)(50n)25\pmod{100}$$ $$\equiv25+1250n$$ for $n\ge1$

For odd $n,$ $$(5+50n)^{1+10n}\equiv25+50\pmod{100}$$

Hint

If $a \equiv b \pmod{n}$ then $a^k \equiv b^k \pmod{n}$ So for instance $111 \equiv 11 \pmod{100}$ so $111^{111} \equiv 11^{111} \pmod{100}$

Also note that $11^2 = 121 \equiv 21$ so $11^{111} = 11^{2·65 + 1} \equiv 11·21^{65}$. But $21^2 = 441 \equiv 41$ and so forth.

Continue simplifying and repeat for the rest of the numbers.

• Fermat's little theorem does not apply; $100$ is neither prime nor a Carmichael number. – Omnomnomnom Jul 22 '14 at 16:48
• @Omnomnomnom that's true. My bad. – Darth Geek Jul 22 '14 at 16:49
• Also $11^{10} \equiv 1 \mod 100$, so $11111^{11111} \equiv 11^{11111} \equiv 11 \cdot (11^{10})^{1111} \equiv 11 \cdot 1^{1111} \equiv 11$. And for $n \ge 2$, $5^n \equiv 25$. – NovaDenizen Jul 22 '14 at 19:28

Two facts help here:

1. if $a \equiv b \pmod m$, then $a^n \equiv b^n \pmod m$
2. For any $a$ relatively prime to $100$, $a^{40} \equiv 1 \pmod {100}$

So, for example, $$111^{111} \equiv 11^{111} \equiv (11^{40})^2 11^{31} \equiv 11^{31} \pmod{100}$$

• For step 2, I think you mean "for any $a$ relatively prime to 100." If $a$ is divisible by 2 or by 5, no power of $a$ will be congruent to 1. This fact is relevant to the powers of 5, 555, etc. – Rory Daulton Jul 22 '14 at 16:48
• @RoryDaulton yes I did, thank you. – Omnomnomnom Jul 22 '14 at 16:51

Noting that $a^{40} = 1 \pmod {100}~\forall a$ coprime to $100$, (follows directly from Euler's theorem) $$1^1 = 1 \pmod {100}$$ $$111^{111} = 11^{111} = 11^{31} \pmod {100}$$ $$11111^{11111} = 11^{11} \pmod {100}$$ $$1111111^{1111111} = 11^{11} \pmod {100}$$ $$111111111^{111111111} = 11^{11} \pmod {100}$$

To see $11111^{11111} = 11^{11} \pmod {100}$, you may note $11111^{11111} = (10000 + 11)^{11111}$, and in the binomial expansion, all but the last term will contain a multiple of $100$; so $11111^{11111} = 11^{11111} \pmod {100} = 11^{11} \pmod {100}$, since $11111=10000+11$ and $10000$ is a multiple of $40$.

Other results follows in the similar way.

By Fermat's liltle theorem (or Euler's theorem), $11^{11} = 11 \pmod{100}$.

Alternately, note that $11^{11} = 285311670611 = 11\pmod{100}$, so $11^{31} = 11^ 9$ $= 2357947691 =$ $-9 \pmod{100}$.

So, the terms involving $1\ldots$ have remainder $1 - 9 + 3 \times 11 = 25 \pmod{100}$.

For the rest terms, note that $$5^1 = 5 \pmod{100}$$ $$555^{111} =(500+55)^{111} =55^{111} = 75\pmod{100},$$ since $55^2 = 3025 = 25 \pmod{100}$ and $55^{111} = 55^{2\times55 + 1} = 25^{55} \times 55 = 25 \times$ $55 = 1375$ $= 75\pmod{100}$ (note that $25^x =$ $25 \pmod{100}~\forall x$) $$55555^{11111} = 55^{11111} = 75 \pmod{100},$$ since $11111 = 11100 + 11$, and $55^{11100} = 75^{100} = 25 \pmod{100}$ (as $75^x = 25 \pmod{100}~\forall \text{even}~ x$), $55^{11} = 55\times (55^2)^{10} = 55 \times 25 = 75 \pmod{100}$

If you proceed analogously, you can convince yourself that $55555^{11111} = 5555555^{1111111} = 75 \pmod{100}$.

So, the final result is $25+5+75\times4 = 30\pmod{100}$.

• $a$ must be coprime with $100$ to apply Euler's theorem so it works with $11\ldots 11$ but not with $55\ldots 55$ – Darth Geek Jul 22 '14 at 17:12
• @DarthGeek Oh! I forgot. Correcting... – xxx--- Jul 22 '14 at 17:13