Find the remainder when $3^{89}7^{86}$ is divided by $17$

Question

Find the remainder when $3^{89}7^{86}$ is divided by $17$.

I guess the problem is to be solved by congruencies. But unfortunately, I have no clear conception about it.

Can someone please explain it.

Thank you.

Answer 1

You can check $3$ has order $16$ modulo $17$. This means $3^{16}\equiv 1\mod 17$, but $3^k\not\equiv 1$ for $1\le k<16$ Actually, Little Fermat ensures $a^{16}\equiv 1 \mod 16$ for any $a$ not divisible by $17$, and Lagrange's theorem says the order of $a$ is a divisor of $16$. Also $3^8\equiv -1$.Thus: $$3^{89}=\bigl(3^{16}\bigr)^5\cdot 3^8\cdot 3\equiv 1\cdot(-1)\cdot3=-3\mod 17$$

Similarly $7^2\equiv-2\mod 17$, hence $7^4\equiv(-2)^2=4$, $7^8\equiv4^2\equiv -1$ and finally $17^{16}\equiv 1$. Thus $$7^{86}\equiv 7^4\cdot7^2\equiv-8$$ whence $3^{89}7^{86}\equiv (-3)(-8)=24\equiv 7\mod 17.$

Answer 2

${\rm mod}\ 17\!:\,\ 3^{89} 7^{86}\!\equiv 3^3(\color{#c00}{3\cdot 7})^{86}\equiv 27\cdot \color{#c00}4^{86}\equiv 10 (4^2)^{43}\equiv 10 (-1)^{43}\equiv -10\equiv 7$