\(p\) is a odd prime, then
- there are infinite primes \(q\) such that \(q\) is a quadratic residue modulo \(p\);
- there are infinite primes \(q\) such that \(q\) is a quadratic nonresidue modulo \(p\).
第二件事是容易的. 事实上, 是 \(q>0\) quadratic non-residue modulo \(p\) 的最小正整数, 则 \(p\) 是质数 . 考虑
\[a_0=q, a_1=q+p,a_2=q+pa_1,a_3=q+pa_1a_2,\dotsc, a_n=q+pa_1a_2\dotsb a_{n-1},\dotsc \]
显然, \((a_i,a_j)=1\).
换个做法 假定只有有限个, 不妨设为 \(q_1, q_2, q_3,\dotsc, q_n\), 二次非剩余 modulo \(p\). 因为 \((q_1q_2q_3\dotsm q_n, p)=1\), 因之必有正整数 \(k\), 使得
\[\bigg(\dfrac{kq_1q_2q_3\dotsm q_n+1}p\bigg)=-1.\]
无穷个质数二次剩余的证明要难一些, 关键在于巧妙的使用二次互反律.
在 \(p\equiv1\pmod4\) 的情形, 如果 \(q\) 是奇质数且 \(q \neq p\), 那么
\[\bigg(\frac qp\bigg) = \bigg(\frac pq\bigg). \]
首先选定一个正整数 \(k\) 使得 \(4^k\gt p\). 考虑
\[a_1 = 4^k – p,\]
\[a_2 = 4^ka_1^2 -p,\]
\[ a_3 = 4^ka_1^2a_2^2 -p, \]
\[\dotsc\]
\[a_n = 4^ka_1^2a_2^2\dotsm a_{n-1}^2-p,\]
\[\dotsc\]
显然, \((a_i,a_j)=1\), 并且 \((a_n,p)=1\). 然后, \(a_n\) 的任意一个质因子 \(q\) 都使得 \(\Big(\dfrac{p}q\Big)=1\).
余下的另一种情况, 即 \(p\equiv3\pmod4\), 如果 \(q\) 是奇质数且 \(q \neq p\), 那么
\[\bigg(\frac qp\bigg)=\bigg(\frac {-p}q\bigg).\]
考察
\[a_1 = 4+p, \]
\[a_2 = 4a_1^2 + p, \]
\[ a_3 = 4a_1^2a_2^2 + p, \]
\[a_4 = 4 a_1^2a_2^2 a_3^2 + p, \]
\[\dotsc\]
\[a_n = 4 a_1^2a_2^2\dotsm a_{n-1}^2+ p,\]
\[\dotsc\]
显然, \((a_i,a_j)=1\), 并且 \((a_n,p)=1\). \(a_n\) 的每一个质因子 \(q\) 都使得 \(\Big(\dfrac{-p}q\Big)=1\).