1
$\begingroup$

I'm trying to find the last two digits of ${2012}^{2012}$. I know you can use (mod 100) to find them, but I'm not quite sure how to apply this. Can someone please explain it?

$\endgroup$
  • $\begingroup$ See: en.wikipedia.org/wiki/Modular_exponentiation This page explains how to get the answer you want. $\endgroup$ – O. S. Dawg Apr 18 '14 at 22:56
  • 1
    $\begingroup$ Here's what happens when you multiply a number by $12$ modulo $100$. The left-most component is a little crowded, but there should be an arrow pointing from each member of the "bouquets" onto the number that's part of the big cycle (eg. 1, 51, and 26 all go to 12). As you can see, 12 is part of a 20 number cycle. $\endgroup$ – Jack M Apr 19 '14 at 0:30
  • $\begingroup$ Related: How do I compute $a^b\,\bmod c$ by hand? $\endgroup$ – punctured dusk Aug 20 '15 at 11:47
2
$\begingroup$

Finding the last two digits of $a$ essentially $\displaystyle a\pmod{100}$

Now as $\displaystyle2012\equiv12, 2012^{2012}\equiv12^{2012}\pmod{100}$

Again as $\displaystyle(12,100)=4$ let us find $\displaystyle12^{2012-1}\pmod{\frac{100}4}$ i.e., $\displaystyle12^{2011}\pmod{25}$

Now using Carmichael function or Totient function $\displaystyle\lambda(25)=\phi(25)=20,2011\equiv11\pmod{20}\implies12^{2011}\equiv12^{11}\pmod{25}$

Method $\#1:$

Again, $\displaystyle12^2=144\equiv-6\pmod{25}\implies12^3\equiv-6\cdot12\equiv3$

$\displaystyle\implies12^9\equiv3^3\equiv2\implies12^{11}\equiv2\cdot(-6)\equiv-12\pmod{25}$

Method $\#2:$

$\displaystyle12^2=144=(145-1)\implies12^{10}=(-1+145)^5$ $\displaystyle=-1+\binom51\cdot145-\binom52145^2+\cdots+145^5$ $\displaystyle12^{10}\equiv-1\pmod{25}\ \ \ \ (1)$ as the rest of terms are divisible by $5^2=25$

As $\displaystyle a\equiv b\pmod m\implies a\cdot c\equiv b\cdot c\pmod{m\cdot c}\ \ \ \ (2)$

Using $(1),(2)$ with $c=12$ $\displaystyle12^{11}=12\cdot12^{10}\equiv-1\cdot12\pmod{12\cdot25}\equiv-12\pmod{300}\equiv-12\pmod{25}$

So, by any of the two methods $\displaystyle12^{11}\equiv-12\pmod{25}$

Using $(2)$ again with $c=12$, $\displaystyle\implies12^{12}\equiv-12\cdot12\pmod{25\cdot12}\equiv-144\equiv156\pmod{300}$

$\displaystyle\implies12^{12}\equiv156\pmod{300}\equiv156\pmod{100}\equiv56$

$\endgroup$
3
$\begingroup$

$\phi(25) = 20$ so $2012^{2012} \equiv 2012^{12} \pmod {25}$.

Then $2012^{12} \equiv 12^{12} \equiv 144^6 \equiv 36^3 \equiv 6 \pmod {25}$.

Then solving the system $N \equiv 6 \pmod {25}, \equiv 0 \pmod 4$ gives $n \equiv 56 \pmod {100}$.

$\endgroup$
  • $\begingroup$ The answer was actually 56, but I'm not sure how to get it. Can you provide some more detail without the Totient function, because I didn't learn that yet. $\endgroup$ – Jason Chen Apr 18 '14 at 22:47
  • $\begingroup$ Fixed it, thanks for the heads up. $\endgroup$ – Sandeep Silwal Apr 18 '14 at 22:50
  • $\begingroup$ Never mind @SandeepSilwal, the totient function means the number of elements in a set of numbers from 0 to x-1 that are relatively prime to x, right? $\endgroup$ – Jason Chen Apr 18 '14 at 22:56
  • $\begingroup$ You're right. Sandeep used the Euler-Fermat theorem: en.wikipedia.org/wiki/Euler's_theorem $\endgroup$ – Ricbit Apr 19 '14 at 0:23

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.