\(p\) is a odd prime,  then

1. there are infinite primes \(q\) such that \(q\) is a quadratic residue modulo \(p\);
2. 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\).