Show that the odd primes q for which 5 is a square mod q are

Show that the odd primes q for which 5 is a square (mod q) are precisely those of the form 20n+1, 20n+3, 20n+7, and 20n+9. Test this result by showing that -5 is a square mod 41, 23, 7, and 29.

Solution

It is a famous problem of classical number theory which primes can be expressed in the form x 2 + ny2 . For example, if p is prime, then for some n Z we have p = 20n + 1 20n + 3 20n + 7 20n + 9 if and only if p = x ² + 5y ² or p = 2x ² + 2xy + 3y ² . Now we are ready to describe all generators of Pq, where q {2, 3, 5, 6}. Our proof is similar to the proof given by Eckert, where he decomposes the hypothenuse of a right triangle into the product of primes and after that peels off one prime at a time, together with the corresponding sides of the right triangle. His description of prime p 1 (mod 4) is equivalent to the statement that p can be written in the form p = u ² + v ² , for some integers u and v, which is the case of Fermat’s two square theorem.