I am reading "An introduction to algebraic systems" by Kazuo Matsuzaka.
There is the following problen without a solution in the book.
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}$
Best Answer
Since $31$ is prime, by Fermat's Little Theorem, $3^{30}\equiv 1 \pmod{31}$. Thus, $3^{30}-1$ is a multiple of $31$. Now, let's consider $\frac{3^{30}-1}{31} \pmod{31}$:
$$\frac{3^{30}-1}{31}=(3^{15}-1)\frac{3^{15}+1}{31}=(3^{15}-1)(3^5+1)\frac{1-3^5+3^{10}}{31}$$
Now, this requires some computation, but $3^5=243=8\cdot 31-5$ (In particular, $3^5 \equiv -5 \pmod {31}$). Therefore:
$$\frac{1-3^5+3^{10}}{31}=\frac{1+5-8\cdot 31+(8\cdot 31-5)^2}{31}=\frac{1+5-8\cdot 31+25-80\cdot 31+64\cdot 31^2}{31} \\ =1-8-80+64\cdot 31=-87+64\cdot 31 \\ \implies \frac{1-3^5+3^{10}}{31}\equiv -87\equiv-3\cdot 31+6\equiv 6\pmod{31}$$
Then, since $3^5\equiv -5\pmod{31}$, we have: $$3^5+1\equiv -4\pmod{31}$$ $$3^{15}-1=(3^5)^3-1=(-5)^3-1=-125-1=-126=-4\cdot 31-2\equiv -2\pmod{31}$$ Thus: $$\frac{3^{30}-1}{31}\equiv -2\cdot -4\cdot 6\equiv48\equiv 17\pmod{31}$$
In other words: $$\frac{3^{30}-1}{31}=17+31k \text{ for some integer } k$$
Multiply both sides by $31$ and then add $1$: $$3^{30}=1+17\cdot 31+31^2k \text{ for some integer } k$$
This can be converted into a statement with $\pmod{31^2}$: $$3^{30}\equiv 1+17\cdot 31\pmod{31^2}$$