how to solve $rem(8^{5}+9^{5},17)$ & $rem(3^{8}-4^{8},10)$

Question

I am trying to solve $rem(8^{5}+9^{5},17)$ & $rem(3^{8}-4^{8},10)$ but don't know how to start with

Answer 1

One way to address the first problem: Observe that

$$ 8^5+9^5 = (8+9)(8^4-8^3\cdot9+8^2\cdot9^2-8\cdot9^3+9^4) $$

and the right side is divisible by $8+9$, of course!

Another way: Follow André Nicolas's hint and note that

$$ 8^5+9^5 \equiv 8^5+(-8)^5 = 8^5-8^5 = 0 $$

modulo $17$.

One way to address the second problem: The last digits of $3^k$ run $3, 9, 7, 1, 3, 9, 7, 1, \ldots$ and the last digits of $4^k$ run $4, 6, 4, 6, 4, 6, \ldots$. Taking the difference modulo $10$ amounts to subtracting the last digits (and adding $10$ as necessary).

Another way: Observe that

$$ 3^8-4^8 = (3^4+4^4)(3^2+4^2)(3+4)(3-4) $$

Of those terms, the second is an odd multiple of $5$, and the rest are all odd, so $\ldots$

Answer 2

Here is one:

For $17$, use Little Fermat first: $8^5=2^{15}\equiv2^{-1}\mod17$. So you have to find the inverse of $2$ modulo $17$.

Note that, as $2^{16}\equiv 1$, we have a chance $2^4=\pm 1$. Indeed $2^4=16\equiv -1$. So $\;-2^4=(-2^3)2=1$, which proves $$2^{-1}\equiv -8=9\mod 17.$$

On the other hand, $9^5=3^{10}$. Also, $3^4=81\equiv -4\mod17$, so that $3^8\equiv (-4)^2=16\equiv -1\mod 17$, and finally $$3^10\equiv -3^2=-9.$$ Thus $\;8^5+9^5\equiv 9-9=0\mod17.$

Congruence modulo 10:

It is easy to check $4^k\equiv\begin{cases}4\mod 10 &\text{if }k\text{ is odd},\\ 6\mod10 &\text{if }k\text{ is even}.\end{cases}$

On the other hand, $\varphi(10)=4$, and $3$ is coprime to $10$, so by Euler's theorem, $3^4\equiv 1$, hence $3^8\equiv 1\mod10$.

Thus, $\;3^8-4^8\equiv 5\mod10$.