Find the remainder when $140^{67}+153^{51}$ is divided by $17$

Question

Find the remainder when $$140^{67}+153^{51}$$ is divided by $17$.

$$140\equiv 4 \pmod {17}$$ $$67\equiv 16 \pmod{17}$$ $$153 \equiv 0 \pmod{17}$$ $$51\equiv 0 \pmod{17}$$

$$\Rightarrow 140^{67}+153^{51}\equiv 4^{16}+0 \equiv 1\pmod{17}$$

Solution should be $13$. What's wrong?

Answer 1

You're right to discard the $153$ term as divisible by $17$, so not affecting the remainder, and also right to reduce the $140\bmod 17$, changing the question to just find $4^{67}\bmod 17$. However ${67}$ is an operation count, not a value that can be reduced by the same modulus (and nor could the $51$, but it became irrelevant when applied to zero).

Repeated exponentiation in modular arithmetic produces cycles, which (it's easy to grasp) cannot be longer than the modulus itself, and in fact must divide the totient function for the modulus, $\phi(17)$ in this case. For prime numbers $\phi(p)=p-1$, so we know that the exponent cycle here divides $16$.

This gives us $4^{67}\equiv 4^3 \equiv 64 \equiv \fbox{13} \bmod 17$, which is our remainder.

Answer 2

What is wrong is that

$$x^y \mod n \neq (x \mod n)^{y \mod n}$$

It is true however that,

$$x^y \mod n=(x \mod n)^{y}$$

So my hint on how to proceed would be to notice $4^2=16=17-1$.

Answer 3

One of the rules for you are using is correct the other one is wrong.

Suppose $p$ is a prime then

If $a \equiv b \ (\bmod p)$ then $a^n\equiv b^n (\bmod p)$

However

If $m \equiv n (\bmod p) \not\Rightarrow a^m \equiv a^n (\bmod p)$.

To see why this is so you need to look at the multiplicative group modulo $p$. Notice that it has a different structure than additive group modulo $p$. You cannot mix the two.

Answer 4

FLT says $a^{p-1} \equiv 1\mod p$

So $67 \equiv 16 \mod 17$ ($p=17$) is irrelevent.

You need $67\equiv 3 \mod 16$ ($p-1=16$)

So $4^{67} \equiv 4^3 \equiv 13 \mod 17$.

Answer 5

$140^{67}+153^{51}\equiv 4^{67} + 0^{51}$

Now $4^{67} \equiv 4^3 \equiv 13 \mod 17$

Answer 6

One has $140\equiv 4\pmod{17}$. Now $4^4=256\equiv 1\pmod{17}$ and $67=16\cdot 4+3$ so

$$140^{67}\equiv (4^4)^{16}\cdot 4^3\equiv 4^3\equiv13 \pmod{17}$$

Similarly one has $153\equiv 0\pmod{17}$ and so $153^{51}\equiv 0\pmod{17}$.

So the answer is indeed $13$