Find the remainder of $40^{314}$ divided by 91.

Question

Here's what I have so far.

$$x \equiv 40^{314} \mod{91}$$

$$\Rightarrow$$

$$x \equiv 40^{314} \mod{7}$$ $$ x \equiv 40^{314} \mod{13}$$

Then by FLT,

$$40^6 ≡ 1 \mod{7}$$ $$40^{12} ≡ 1 \mod{13}$$

Am I on the right track? What should I do from here?

Answer 1

Yes, you are on the right track. Then observe that:

$$40^{314} = (40^6)^{52} \cdot 40^2 \equiv 1 \cdot 40^2 \equiv 4 \mod{7}$$

$$40^{314} = (40^{12})^{26} \cdot 40^2 \equiv 1 \cdot 40^2 \equiv 1 \mod{13}$$

Can you do it from here?

Answer 2

A little help from Excel, you can see the remainders pattern will repeat every 6 terms.

Then \begin{equation} \frac{314}{6}=52+\frac{2}{6}\qquad\text{ or }\qquad(314)\mod 6=2 \end{equation} As you can see in the table, the sequence no. 2 in the table is 53. Hence, $40^{314} \mod 91 =$ 53.

Answer 3

We have $\displaystyle40\equiv-2\pmod7$

$$\implies40^2\equiv(-2)^2\equiv4, 40^3\equiv(-2)^3\equiv-1\implies40^6\equiv(-1)^2\equiv1$$

and $$40^1\equiv1\pmod{13}$$

Following your way like Carmichael Function, $$40^{\text{lcm}(1,6)}\equiv1\pmod7,40^6\equiv1\text{ and }40^6\equiv1\pmod{13}$$

$$\implies40^6\equiv1\pmod{\text{lcm}(13,7)},40^6\equiv1\pmod{91}$$

As $\displaystyle314\equiv2\pmod6,40^{314}\equiv40^2\pmod{91}$