3
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ CRT is overkill since $\, -4\equiv 0\pmod 4\, $ so $\ x\equiv -4\pmod{100}\ $ is a solution. We can simplify even further noting $\,14\,$ is a square mod $\,25,\,$ see my answer. $\endgroup$ – Bill Dubuque Dec 15 '16 at 2:12
  • $\begingroup$ @Bill Dubuque: Yes, but I think the question the general way to solve. Your comment is useful to show students they can, and certainly should, think before applying any general solution. $\endgroup$ – Bernard Dec 17 '16 at 0:08
  • $\begingroup$ OP makes no mention of that. In fact the OP says it's an exam question, so speed is important, so widely applicable optimizations such as this CRT constant case optimization are surely of interest; i.e. above $\,x\equiv \color{#c00}{-4}\pmod{\!4\ \&\ 25}\iff x\equiv \color{#c00}{-4}\pmod{4\cdot 25}.\,$ Ditto for the complete elimination of CRT as in my answer. But of course I do agree that one should know both the general / mechanical results as well as the special cases / optimizations, shortcuts, and detours. $\endgroup$ – Bill Dubuque Dec 17 '16 at 0:26
4
$\begingroup$

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

$\endgroup$
2
$\begingroup$

${\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$

$\endgroup$
  • $\begingroup$ The prior line essentially uses a generalization of the mod distributive law below $$\large ca\,\bmod\, cn\, =\, c\,(a\bmod n)$$ See this answer for more on this viewpoint. To be clear, you don't need to know about this to understand the above answer. It's merely a tangential remark for enrichment. $\endgroup$ – Bill Dubuque Dec 17 '16 at 1:02

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.