2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ But.... that's it. What more do you need to do? $\endgroup$ – fleablood Jan 5 at 3:59
  • $\begingroup$ @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. $\endgroup$ – Will R Jan 5 at 4:01
  • 2
    $\begingroup$ @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) $\endgroup$ – stressed out Jan 5 at 4:01
5
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.