0
$\begingroup$

Find the last $2$ digits of $2016^{123}$

So you have that $2016^{123} \equiv \pmod{100}$

then $16^{123}\equiv \pmod{100}$

Now the $gcd(16,100)=4$ so I divide everything by 4 $4^{123} \equiv \pmod{25}$

I know $4^{\varphi(25)} \equiv 1 \pmod{25}$ then $(4^{20})^6*4^{3} \equiv 14 \pmod{25}$

Then multiplying that by $4$ to get it in the original mod I get $56$ but the answer is $96$ so I"m not sure where I"m making a mistake or if this is the right process to use.

$\endgroup$
4
  • 5
    $\begingroup$ so I divide everything by 4 That's not what you did on the LHS. $\endgroup$
    – dxiv
    Apr 3, 2017 at 3:52
  • 1
    $\begingroup$ I'll give an image of your mistake: if you divide $(2a)^{100}$ by 2 you get $a^{100}$. This is obviously WRONG ! $\endgroup$
    – QFi
    Apr 3, 2017 at 4:00
  • 1
    $\begingroup$ oh wow thanks I got it I reduced it again and the right hand side was $4^{245}$ $\endgroup$ Apr 3, 2017 at 4:11
  • $\begingroup$ We can also use the Mod Distributive Law to pull out the factor in common with the modulus, e.g. see this answer. $\endgroup$ Apr 3, 2017 at 16:18

1 Answer 1

1
$\begingroup$

There are two ways of simplifying the congruence to get the desired result:

Using your approach:

$$(2^5\cdot3^2\cdot7)^{123} \equiv (4^2)^{123}\pmod{4\cdot25} $$

Factor $4$ out:

$$2^{613}\cdot3^{246}\cdot7^{123} \equiv 4^{245} \equiv 4^5 \equiv 24 \pmod{25}$$

Now $4\cdot24 = 96$, the desired result.

The $5$ of the last exponent is since $245 \equiv 5 \pmod {\varphi(25)}$


The following for me is the standard approach. Simplifying both congruence class and exponent:

$$\begin{cases} 2016 \equiv 16 \pmod{100} \\ 123 \equiv 3 \pmod{\varphi(100)} \\ 16^3 \equiv 96 \pmod{100} \end{cases}$$

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