last two digits of $14^{5532}$?

Question

This is a exam question, something related to network security, I have no clue how to solve this!

Last two digits of $7^4$ and $3^{20}$ is $01$, what is the last two digits of $14^{5532}$?

Answer 1

By the Chinese remainder theorem, it is enough to find the values of $14^{5532}\mod 4$ and $\bmod25$.

Now, clearly $\;14^{5532}\equiv 0\mod 4$.

By Euler's theorem, as $\varphi(25)=20$, and $14$ is prime to$25$, we have: $$14^{5532}=14^{5532\bmod20}=14^{12}\mod25.$$ Note that $14^2=196\equiv -4\mod25$, so $14^{12}\equiv 2^{12}=1024\cdot 4\equiv -4\mod25$.

Now use the C.R.T.: since $25-6\cdot4=1$, the solutions to $\;\begin{cases}x\equiv 0\mod 4\\x\equiv -4\mod 25\end{cases}\;$ are: $$x\equiv \color{red}0\cdot25-6\cdot{\color{red}-\color{red}4}\cdot 4= 96\mod 100$$ Thus the remainder last two digits of $14^{5532}$ are $\;96$.

Answer 2

Finding the last two digits necessarily implies $\pmod{100}$

As $(14^n,100)=4$ for $n\ge2$

Let use start with $14^{5532-2}\pmod{100/4}$ i.e., $14^{5530}\pmod{25}$

As $14^2\equiv-2^2\pmod{25}$

Now $2^5\equiv7,2^{10}\equiv7^2\equiv-1\pmod{25}$

$\implies14^{10}=(14^2)^5\equiv(-2^2)^5=-2^{10}\equiv-1(-1)\equiv1$

As $5530\equiv0\pmod{10},14^{5530}\equiv14^0\pmod{25}\equiv1$

Now use $a\equiv b\pmod m\implies a\cdot c\equiv b\cdot c\pmod {m\cdot c} $

$\displaystyle14^{5530}\cdot14^2\equiv1\cdot14^2\pmod{25\cdot14^2}$

As $100|25\cdot14^2,$

$\displaystyle14^{5530+2}\equiv14^2\pmod{100}\equiv?$

Answer 3

${\rm mod}\,\ \color{#c00}{25}\!:\, \ 14\equiv 8^{\large 2}\Rightarrow\, 14^{\large 10}\equiv \overbrace{8^{\large 20}\equiv 1}^{\rm\large Euler\ \phi}\,\Rightarrow\, \color{#0a0}{14^{\large 1530}}\equiv\color{#c00}{\bf 1}$

${\rm mod}\ 100\!:\,\ 14^{\large 2}\, \color{#0a0}{14^{\large 1530}} \equiv 14^{\large 2} (\color{#c00}{{\bf 1}\!+\!25k}) \equiv 14^{\large 2} \equiv\, 96$

Answer 4

The OP quickly realizes that we can't write $14^k \equiv 1 \pmod{100}$ with $k \gt 0$, but there are still relations to be found in (multiplicative) semigroups.

If the last digit of integers $a$ and $b$ end in $6$, then the last digit of the product ends in $6$. This motivates us to write

$\quad 14^2 \equiv 96 \equiv -4 \pmod{100}$

and

$\quad 96^2 \equiv 16 \pmod{100}$
$\quad 96^3 \equiv 36 \pmod{100}$
$\quad 96^4 \equiv 56 \pmod{100}$
$\quad 96^5 \equiv 76 \pmod{100}$
$\quad 96^6 \equiv 96 \pmod{100}$

and

$\quad 96^{36} \equiv 96 \pmod{100}$
$\quad 96^{216} \equiv 96 \pmod{100}$
$\quad 96^{1296} \equiv 96 \pmod{100}$

So

$\; 14^{5532} = (14^2)^{2766} \equiv 96^{2766} \equiv (96^{1296})^2 (96^{174}) \equiv 96^{176} \equiv (96^{36})^4 (96^{32}) \equiv 96^{36} \equiv 96 \pmod{100}$

Answer 5

Consider the following class of exam questions:

If $n$ is even find the last two digits of $n^k$.

There is a quick way of cranking out the answers by giving the multiplicative semigroup,

contained in $\mathbb {Z} / \text{100} \mathbb {Z}$, a central/absorbing role.

We know that $76 \times 76 \equiv 76 \pmod{100}$ and more generally that for any $a$ in the semigroup

$\quad 76 \times a \equiv a \pmod{100}$

(we actually have a group with the identity being $76$)

We know that there is an easy calculation algorithm that can be used to multiply any two of these residue numbers.

Example: For $56 \times 96 \pmod{100}$ the tens digit is equal to the residue $5 + 9 + 3 \pmod{10}$:

$\quad 56 \times 96 \equiv 76 \pmod{100}$

We know that given an even integer $n$ such that $n \not\equiv 0 \pmod{10}$, at least one of the residue classes

$\quad [n], [n^2], [n^4] \quad \pmod{100}$

belongs to our semigroup.

We know that given an even integer $n$ such that $n \not\equiv 0 \pmod{10}$,

$\quad n^{20} = 76 \pmod{100}$

Now with these preliminaries we can mentally turn the crank (recall that $14^2 = 196$) ,

$\; 14^{5532} \equiv 76 \times 14^{12} \equiv 76 \times (14^2)^6 \equiv 76 \times (96)^2 \times (96)^2 \times (96)^2 \equiv$
$\quad \quad \quad \quad 76 \times 16 \times 16 \times 16 \equiv 96 \pmod{100}$

Answer 6

The following calculations can be easily done by hand on scrap paper, but we organized this preparatory work on a google sheet.

The outputs from these formulas

are

With this done we can mentally write out

$\quad 14^{5532} \equiv (16) (56) (36) (56) (36) (16) (36) \equiv$

$\quad\quad\quad\quad (56) (56) (36) (56) (36) (36) \equiv$

$\quad\quad\quad\quad (36) (36) (56) (36) (36) \equiv$

$\quad\quad\quad\quad (96) (56) (96) \equiv$

$\quad\quad\quad\quad (16) (56) \text{ mod 100} $

Since $(10 + 6)(50 + 6) = 500 + 60 + 300 + 36$, we can write

$\quad 14^{5532} \equiv 96 \text{ mod 100} $