2
$\begingroup$

Suppose that you are asked to find the last $2$ digits of $5312^{442}$.

  • We need to find what number between $0$ and $99$ that is congruent to our number modulo $100$.

  • My first guess would be to check to see if I can use Euler's Theorem, but since $5312$ and $100$ are not coprime it would not be useful.

  • Would it be possible to convert the exponent to binary and use the successive squaring algorithm to solve: $5312^{442} \mod 100$? Are there any other (better) ways to go about this?

$\endgroup$
  • $\begingroup$ To start, you can immediately reduce $5312$ modulo $100$ so that you're solving $12^{442}$ instead. $\endgroup$ – Kaj Hansen Oct 4 '16 at 1:20
3
$\begingroup$

As $5312\equiv12\pmod{100},5312^{442}\equiv12^{442}\pmod{100}$

Now as $(12,100)=4$ let us find $12^{442-1}\pmod{100/4}$

As $(12,25)=1,$ by Euler Theorem, $$12^{20}\equiv1\pmod{25}$$

As $441\equiv1\pmod{20},12^{441}\equiv12^1\pmod{25}$

$$\implies12\cdot12^{441}\equiv12\cdot12^1\pmod{12\cdot25}$$ $$\equiv144\pmod{300}\equiv144\pmod{100}\equiv44\pmod{100}$$

$\endgroup$
1
$\begingroup$

[quote] To start, you can immediately reduce 5312 modulo 100 so that you're solving $12^{442}$ instead.

Then, you solve this (mod 4) and (mod 25)

  • (mod 4), it is pretty clear what the result would be

  • (mod 25), you can use Euler's Theorem.

Then, combine the results back to (mod 100).

$\endgroup$
  • $\begingroup$ I think it's a bad custom (and growing in this portal) qualify as the best answer without having mediated others to compare. $\endgroup$ – Piquito Oct 4 '16 at 2:55
  • $\begingroup$ What do you mean? $\endgroup$ – Alex Oct 4 '16 at 2:56
  • 2
    $\begingroup$ First, dear friend, nothing against your good answer. What I do is give a simple declaration concerning ownership of lenguaje. One thing is to accept as the best answer and another thing is to accept it as satisfactory. "The best" implies comparison. Many beginners lately in StackExchange mark "the best answer" to see only the first one. Regards. $\endgroup$ – Piquito Oct 4 '16 at 11:36
0
$\begingroup$

Well, you actually can use Euler's Theorem. $\phi(100) = 40$ and so $12^{41} \equiv 12 \pmod{100}$:

$$5312^{442} \equiv (12^{41})^{10}12^{32} \equiv 12^{10}12^{32} \equiv 12^{42}\equiv 12^{41}12 \equiv 12^2 \equiv 44 \pmod{100}.$$

$\endgroup$
  • $\begingroup$ Two things: 1. The answer to your question is "no." See, e.g. arxiv.org/ftp/math/papers/0610/0610607.pdf. 2. In 1980, your bigotry against autistic people prevented at least one ESG student from graduating MIT, set him back two years and caused the waste of thousands of dollars. Please be so kind as to never speak to me again. $\endgroup$ – B. Goddard Oct 4 '16 at 18:05
  • 1
    $\begingroup$ As $(12,100)\ne1,$ we can not apply Euler's Totient Theorem here $\endgroup$ – lab bhattacharjee Oct 5 '16 at 16:08
  • 1
    $\begingroup$ @labbhattacharjee Again, there are extensions to Euler's Theorem, so, you can, in fact, apply it here. See the link in my comment above. Take $s=1$. $\endgroup$ – B. Goddard Oct 5 '16 at 16:10
0
$\begingroup$

Note $\ \ ca\bmod cn\,=\, c\,(a\bmod n)\ $ as explained here, $ $ so

$\! \begin{align} 5312^{\large 442}\!\bmod 100\, &=\, 4\,(\color{}{12}^{\large 442}/4\bmod 25)\\ &=\,4\,(\color{}{12}^{\large 2}/\,2^{\large 2}\, \bmod 25)\ \ {\rm by}\,\ 12^{\large 440}\!\equiv (12^{\large\color{#c00}{20}})^{\large 22}\!\equiv 1^{\large 22}\rm \ by\ Euler\ \phi(25)\!=\!\color{#c00}{20}\\ &=\,4\,(6^{\large 2} \bmod 25)\\ &=\, 4\,(11) \end{align}$

$\endgroup$

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.