2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If you are programming you can use binary-modular exponentiation. $\endgroup$ – Phicar Jul 22 '14 at 16:43
  • 1
    $\begingroup$ Considering that the last term alone is larger than the number of atoms in the universe, I'm hardly surprised. $\endgroup$ – Semiclassical Jul 22 '14 at 16:44
  • $\begingroup$ It was an aptitude question. Thanks @Phicar I want to know how do one do this kind of questions. $\endgroup$ – WannaBeCoder Jul 22 '14 at 16:46
  • $\begingroup$ 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. $\endgroup$ – mweiss Jul 22 '14 at 16:46
  • $\begingroup$ 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. $\endgroup$ – Emily Jul 22 '14 at 18:00
2
$\begingroup$

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}$$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Fermat's little theorem does not apply; $100$ is neither prime nor a Carmichael number. $\endgroup$ – Omnomnomnom Jul 22 '14 at 16:48
  • $\begingroup$ @Omnomnomnom that's true. My bad. $\endgroup$ – Darth Geek Jul 22 '14 at 16:49
  • $\begingroup$ 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$. $\endgroup$ – NovaDenizen Jul 22 '14 at 19:28
1
$\begingroup$

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} $$

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Rory Daulton Jul 22 '14 at 16:48
  • $\begingroup$ @RoryDaulton yes I did, thank you. $\endgroup$ – Omnomnomnom Jul 22 '14 at 16:51
1
$\begingroup$

These may help you:

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}$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.