This article is translated by AI.

1

Let integer $\alpha \geqslant 1, p$ be an odd prime number, if $p^\alpha \nmid a$, find all solutions of

$$x^2 \equiv a\left(\bmod p^\alpha\right)$$

Solution:

(1) If $\left(\frac{a}{p}\right) = -1$, then $x^2 \equiv a \pmod{p}$ has no solution, so $x^2 \equiv a \pmod{p^\alpha}$ has no solution.

(2) If $\left(\frac{a}{p}\right) = 1$, then $x^2 \equiv a \pmod{p}$ has solutions. By Hensel's Lemma, $x^2 \equiv a \pmod{p^\alpha}$ has exactly two solutions and they are opposite to each other modulo $p^\alpha$.

(3) If $\left(\frac{a}{p}\right) = 0$, let $a = p^k b$, where $1 \leq k < \alpha$ and $p \nmid b$.

1. If $2 \nmid k$, then the equation has no solution.

2. If $2 \mid k$, let $k = 2m$, let $x = p^m y$, then

$$\begin{align} x^2 &\equiv a \pmod{p^\alpha}\\ &\Longleftrightarrow p^{2m} y^2 \equiv p^{2m} b \pmod{p^\alpha}\\ &\Longleftrightarrow y^2 \equiv b \pmod{p^{\alpha-2m}} \end{align}$$

Same as above, if $\left(\frac{b}{p}\right) = 1$, then there are exactly two solutions. Let $y_0^2 \equiv b \pmod{p^{\alpha-2m}}$,

Then $x_1 \equiv p^m y_0 \pmod{p^\alpha}$, $x_2 \equiv p^m(p^{\alpha-2m} - y_0) \pmod{p^\alpha}$.

If $\left(\frac{b}{p}\right) = -1$, then the equation has no solution.

3

Write out all quadratic residues and non-residues of $7,13,29,37$.

Solution:

Prime	Quadratic Residues	Quadratic Non-residues
7	1, 2, 4	3, 5, 6
13	1, 3, 4, 9, 10, 12	2, 5, 6, 7, 8, 11
29	1, 4, 5, 6, 7, 9, 13, 16, 20, 22, 23, 24, 25, 28	2, 3, 8, 10, 11, 12, 14, 15, 17, 18, 19, 21, 26, 27
37	1, 3, 4, 7, 9, 10, 11, 12, 16, 21, 25, 26, 27, 28, 30, 33, 34, 36	2, 5, 6, 8, 13, 14, 15, 17, 18, 19, 20, 22, 23, 24, 29, 31, 32, 35

4

Let $p>2$ be an odd prime number, prove: (1) The necessary and sufficient condition for $\left(\frac{-1}{p}\right)=1$ is $p=4 n+1$; (2) The necessary and sufficient condition for $\left(\frac{2}{p}\right)=1$ is $p=8 n \pm 1$; (3) The necessary and sufficient condition for $\left(\frac{-2}{p}\right)=1$ is $p=8 n+1,8 n+3$; and further prove that for any prime number $p$, one of $-1,-2,2$ must be a quadratic residue of $p$.

Proof:

(1) $\left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}} = 1 \Leftrightarrow p = 4n+1$

(2) $\left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}} = 1 \Leftrightarrow p = 8n \pm 1$

(3) $\left(\frac{-2}{p}\right) = \left(\frac{-1}{p}\right)\left(\frac{2}{p}\right) = (-1)^{\frac{(p-1)(p+5)}{8}}$

$\left(\frac{-2}{p}\right) = 1 \Leftrightarrow p = 8n+1, 8n+3$

Therefore, for any odd prime number $p$, one of $-1, -2, 2$ must be a quadratic residue of $p$.

7

Let $x, y$ be integers, $(x, y)=1$. Question: What form must the prime factors of $x^2+y^2$ greater than 2 have? What form must the prime factors of $x^2+2 y^2$ greater than 2 have?

Solution:

(1)

$$\begin{align} & x^2 \equiv -y^2 \pmod{p}\\ &\Leftrightarrow \left(\frac{-1}{p}\right) = 1\\ &\Leftrightarrow p = 4n+1 \end{align}$$

(2)

$$\begin{align} & x^2 \equiv -2y^2 \pmod{p}\\ &\Leftrightarrow \left(\frac{-2}{p}\right) = 1\\ &\Leftrightarrow p = 8n+1, 8n+3 \end{align}$$

5

Use the previous question to prove: For any prime number $p$, there must be an integer $x$ such that

$$p \mid x^8-16$$

Proof: If $\left(\frac{2}{p}\right)=1$ or $\left(\frac{-2}{p}\right)=1$, then

$$x^2 \equiv 2 \pmod p \text{ or } x^2 \equiv -2 \pmod p$$

So

$$x^8 \equiv 16 \pmod p$$

If $\left(\frac{-1}{p}\right)=1$, then

$$t^2 \equiv -1 \pmod p$$

Let $x=1+t$, we have

$$\begin{align} x^2 &= t^2+2t+1 \equiv 2t \pmod p\\ x^4 &\equiv -4 \pmod p\\ x^8 &\equiv 16 \pmod p \end{align}$$

6

Prove: The solution of the congruence $x^2+1 \equiv 0(\bmod p), p=4 m+1$ is

$$x \equiv(2 m)!(\bmod p) .$$

Proof: By Wilson's Theorem, we know

$$(p-1)! \equiv -1 \pmod p$$

That is

$$\begin{align} [(2m)!]^2 &= 1\times2\times\cdots\times2m\times(-2m)\times\cdots\times(-1)\\ &= 1\times2\times\cdots\times2m\times(2m+1)\times\cdots\times(4m)\\ &= (4m)!\\ &\equiv -1 \pmod p \end{align}$$

8

Calculate: $\left(\frac{-23}{83}\right),\left(\frac{51}{71}\right),\left(\frac{71}{73}\right),\left(\frac{-35}{97}\right)$

Solution:

$$\begin{align*} \left(\frac{-23}{83}\right) &= \left(\frac{-1}{83}\right) \cdot \left(\frac{23}{83}\right)\\ &= (-1)^{\frac{83-1}{2}} \cdot (-1) \cdot \left(\frac{83}{23}\right)\\ &= \left(\frac{83}{23}\right)\\ &= \left(\frac{-9}{23}\right)\\ &= \left(\frac{-1}{23}\right) \cdot \left(\frac{9}{23}\right)\\ &= (-1)^{\frac{23-1}{2}} \cdot (-1) \cdot \left(\frac{23}{9}\right)\\ &= -1 \cdot 1 \end{align*}$$

因此 $\left(\frac{-23}{83}\right) = -1$

$$\begin{align*} \left(\frac{51}{71}\right) &= \left(\frac{3}{71}\right) \cdot \left(\frac{17}{71}\right)\\ &= (-1) \cdot \left(\frac{71}{3}\right) \cdot \left(\frac{71}{17}\right)\\ &= (-1) \cdot \left(\frac{2}{3}\right) \cdot \left(\frac{3}{17}\right)\\ &= (-1) \cdot (-1)^{\frac{9-1}{8}} \cdot \left(\frac{17}{3}\right)\\ &= (-1) \cdot \left(\frac{2}{3}\right)\\ &= -1 \end{align*}$$

$$\begin{align*} \left(\frac{71}{73}\right) &= \left(\frac{73}{71}\right)\\ &= \left(\frac{2}{71}\right)\\ &= (-1)^{\frac{71^2-1}{8}}\\ &= 1 \end{align*}$$

$$\begin{align*} \left(\frac{-35}{97}\right) &= \left(\frac{-1}{97}\right) \cdot \left(\frac{35}{97}\right)\\ &= \left(\frac{-1}{97}\right) \cdot \left(\frac{97}{35}\right)\\ &= (-1)^{\frac{97-1}{2}} \cdot (\frac{-1}{35}) \cdot (\frac{2}{35}) \cdot (\frac{4}{35})\\ &= (-1)^{\frac{35-1}{2}} \cdot (-1)^{\frac{35^2-1}{8}} \cdot 1 \\ &= (-1) \cdot (-1) \cdot 1\\ &= 1 \end{align*}$$

9

Let $p>3$ be a prime number, prove:

1. The necessary and sufficient condition for $\left(\frac{3}{p}\right)=1$ is $p=12 n \pm 1$;
2. The necessary and sufficient condition for $\left(\frac{-3}{p}\right)=1$ is $p=6 n+1$.

Proof:

1. $$\left(\frac{3}{p}\right) \left(\frac{p}{3}\right) = (-1)^{\frac{p-1}{2} \frac{3-1}{2}} = (-1)^{\frac{p-1}{2}}$$

Thus

$$\left(\frac{3}{p}\right) = (-1)^{\frac{p-1}{2}} \left(\frac{p}{3}\right)$$

Where

$$\begin{align} \left(\frac{p}{3}\right)=1 &\iff p \equiv 1 \pmod 3 \\ \left(\frac{p}{3}\right)=-1 &\iff p \equiv 2 \pmod 3 \end{align}$$

So

$$\begin{align} &\left(\frac{3}{p}\right)=1 \\ &\iff p \equiv 3 \pmod 4 \land p \equiv 2 \pmod 3 \\ &\text{or } p \equiv 1 \pmod 4 \land p \equiv 1 \pmod 3 \\ &\iff p \equiv \pm 1 \pmod{12} \\ &\iff p = 12n \pm 1 \end{align}$$

$$\begin{align*} \left(\frac{-3}{p}\right) &= \left(\frac{-1}{p}\right)\left(\frac{3}{p}\right)\\ &= (-1)^{\frac{p-1}{2}} \cdot (-1)^{\frac{p-1}{2}}\left(\frac{p}{3}\right)\\ &= (-1)^{p-1} \left(\frac{p}{3}\right) \end{align*}$$

Thus

$$\begin{align} \left(\frac{-3}{p}\right) = 1 &\Leftrightarrow p \equiv 1 \pmod{2} \land p \equiv 1 \pmod{3} \\ &\lor p \equiv 0 \pmod{2} \land p \equiv 2 \pmod{3} \\ &\Leftrightarrow p \equiv 1 \pmod{6} \\ &\Leftrightarrow p = 6n+1. \end{align}$$

12

Let $p>2$ be a prime number, $(a, p)=1$, then

$$\sum_{x=1}^p\left(\frac{a x+b}{p}\right)=0 .$$

Proof:

$$\sum_{x=1}^p\left(\frac{ax+b}{p}\right) = \sum_{y=1}^p\left(\frac{y}{p}\right) = \frac{p-1}{2} - \frac{p-1}{2} + 0 = 0$$

References

• https://zhuanlan.zhihu.com/p/543010816

• https://zhuanlan.zhihu.com/p/544792225

• https://zhuanlan.zhihu.com/p/545595129

• https://zhuanlan.zhihu.com/p/546385318

• https://zhuanlan.zhihu.com/p/547333984

• https://zhuanlan.zhihu.com/p/548061254

Contributors: Ming Wei

Previous pagePan Chengdong "Number Theory Foundation" Selected Solutions: Chapter 2

Next pageManga Resource Navigation