## Prove that $3^{30} \equiv 1 + 17 \cdot 31 \pmod{31^{2}}$.

I guess this problem is easy, but I cannot solve it.

Prove that $$3^{30} \equiv 1 + 17 \cdot 31 \pmod{31^{2}}$$

Of course, I can solve the above problem by direct calculation, but I wanna know smarter solution.

I did the following calculation for example, but I was not able to solve this problem.

By Fermat’s little theorem,
$$3^{30} \equiv 1 + 17 \cdot 31 \pmod{31}.$$

$$1 + 17 \cdot 31 \equiv (1 + 31)^{17} \equiv 32^{17} \equiv 2^{85}\pmod{31^2}$$