Using Fermat’s Little Theorem to compute $3^{649} \bmod{85}$

Question

I am confused about the steps to solve it. I know that $\mbox{gcd}(3,85) = 1$. I got

$$\phi(85) = 85 \left( 1 - \frac15 \right) \left( 1 - \frac{1}{17} \right) = 64$$

and then, by Euler's theorem, $3^{64} \equiv 1 \bmod{85}$. What would be the next step?

Answer 1

Hint: How does $649$ compare to $64$?

Can you finish?

Answer 2

Since $\varphi(85)=64$ we have that $3^{649}\equiv 3^{9}\pmod{85}$. Now it is very practical to invoke the Chinese remainder theorem. $85=5\cdot 17$ and $3^9\equiv 3\pmod{5}$ while by taking $p=17$ $$ 3^9 \equiv 3\cdot 3^{\frac{p-1}{2}} \equiv 3\left(\frac{3}{17}\right) \equiv 3\left(\frac{17}{3}\right)\equiv -3\pmod{17} $$ so the wanted remainder is the first element in $\{17k-3\}_{k\geq 1}$ which ends with a $3$ or an $8$, so $14\to 31\to \color{green}{48}$.

Answer 3

$649= 10 \times 64 + 9$ so it follows that $$3^{649} = (3^{64})^{10} \times 3^9$$ by standard exponent rules.

So modulo $85$ we get (as the left hand becomes a power of $1$):

$$3^{649} = 3^9 \pmod{85}$$

which will make it easier...

Answer 4

$3^{4}\equiv 1\pmod 5$ and $3^{16}\equiv 1\pmod {17}$ together imply By CRT, that $3^{16}\equiv 1\pmod {85}$ so $3^{649=16\cdot 40+9}\equiv 3^9\cdot {85}$ which you can then easily solve.