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

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}$$

• But.... that's it. What more do you need to do? – fleablood Jan 5 at 3:59
• @fleablood: I think his complaint is that if the number 17 were not already given to him, then he would not know how to find it without just trying numbers. – Will R Jan 5 at 4:01
• @fleablood he has proven that $31$ divides $3^{30} - (1+ 17\cdot 31)$. He wants to prove that $31^2$ divides it as well. He hasn't demonstrated the later in his argument. Has he? (I think you missed the exponent $2$ perhaps) – stressed out Jan 5 at 4:01

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}$$

• Thank you very much, Noble Mushtak. – tchappy ha Jan 10 at 12:17