6
$\begingroup$

Question is to find last two digits of $9^{1500}$ (No Euler totient theorem please)

What i have done so far is :

$9^2\equiv 81\pmod{100}$

$9^4 \equiv 61\pmod{100}$

$9^8\equiv 21\pmod{100}$

$9^{16} \equiv 41\pmod{100}$

$9^{32} \equiv 81\pmod{100}$

higher powers of $9$ namely $64,128,256,512,1024$ will be in repeated pattern as above.

$9^{64} \equiv 61\pmod{100}$

$9^{128} \equiv 21\pmod{100}$

$9^{256} \equiv 41\pmod{100}$

$9^{512} \equiv 81\pmod{100}$

$9^{1024} \equiv 61\pmod{100}$

Now,I want to split power of $9$ i.e., $1500$ to powers which i have noted down above. i.e,

$9^{1500}=9^{1024}.9^{476}$

$9^{1500}=9^{1024}.9^{256}.9^{220}$

$9^{1500}=9^{1024}.9^{256}.9^{128}.9^{92}$

$9^{1500}=9^{1024}.9^{256}.9^{128}.9^{64}.9^{28}$

$9^{1500}=9^{1024}.9^{256}.9^{128}.9^{64}.9^{16}.9^{12}$

$9^{1500}=9^{1024}.9^{256}.9^{128}.9^{64}.9^{16}.9^{8}.9^4$

When you multiply two positive integers, the last digit in the product depends on those two integers only through their last digits.

So, I will look only for last two digits of $9$ in above powers.

$9^{1500}=9^{1024}.9^{256}.9^{128}.9^{64}.9^{16}.9^{8}.9^4$

$\equiv 61.41.21.61.41.21.61 \pmod{100} $

$\equiv (61.61).(21.21).(41.41).61\pmod{100}$

(we have already seen above $61.61\equiv 21 \text{mod}100$ and similarly for other cases). So, we would be left with :

$\equiv (21).(41).(81).(61)\pmod{100}$

$\equiv (61)(41)\pmod{100}$

$\equiv (01) \pmod{100}$ I would be happy if someone can verify the procedure I have done and I would be thankful if some one can help me to make this less laborious and more efficient.

$\endgroup$
  • 1
    $\begingroup$ Is it $1000$ or $1500$ in the exponent? $\endgroup$ – TMM Oct 26 '13 at 13:13
  • $\begingroup$ Thank you for pointing out... Error Edited :) $\endgroup$ – user87543 Oct 26 '13 at 13:15
  • $\begingroup$ You could also use the binomial theorem, but I don't know if you consider that as basic. $\endgroup$ – Ivan Loh Oct 26 '13 at 13:23
  • $\begingroup$ @IvanLoh : Thanks for pointing out another possible way.. I have not yet worked out in that way.. I do consider it as basic :) I will try working it out.. Thank You.. $\endgroup$ – user87543 Oct 26 '13 at 13:26
7
$\begingroup$

You have seen that $9^2 \equiv 9^{32} \equiv 81$ mod $100$. As gcd$(81,100) = 1$, this implies $9^{30} \equiv \frac{9^{32}}{9^2} \equiv \frac{81}{81} \equiv 1$, and thus $9^{1500} = (9^{30})^{50} \equiv 1$.

Your method also works, but it is longer.

$\endgroup$
  • $\begingroup$ This does makes perfect sense and Thank You :) $\endgroup$ – user87543 Oct 26 '13 at 13:22
2
$\begingroup$

A similar question has been asked a while back. The whole idea is to exploit the fact that
$9^n=(10-1)^n$ and/or the fact that $9^{2n}=81^n=(8\cdot10+1)^n$, and plug it into Newton's
Binomial Theorem. It will soon become evident that our number is of the form $\mathcal{M}_{100}+1$.

$\endgroup$
1
$\begingroup$

Given the answer above by Arthur, I still would like to add my shorter version.

1: $9^5\equiv49\pmod{100}$

$$9^5=59049$$

2: $9^{10}\equiv1\pmod{100}$

$$9^{10}\equiv49\times49=2401\equiv1\pmod{100}$$

3: $$9^{1500}=(9^{10})^{150}\equiv1\pmod{100}$$

$\endgroup$
1
$\begingroup$

$$ \phi(100)=\phi(5^2)\phi(2^2)=40 $$ where $\phi$ is Euler's Totient function. Then $$ 9^{1500}=9^{20}9^{37*40}=9^{20}=3^{40}=1 $$ Using Fermat's little theorem.

$\endgroup$

Your Answer

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