Quadratic reciprocity

Let $\left(\dfrac {n}{p}\right)$ denote the Legendre (Jacobi) symbol, defined for $p$ an odd prime and $n$ any number not divisible by $p$ as $\left(\dfrac {n}{p}\right) = 1$ if $n$ is a quadratic residue of $p$ and $\left(\dfrac {n}{p}\right) = -1$ if $n$ is a quadratic non-residue of $p$ (Hardy--Wright, p. 68). The equation

has only one positive root, namely $x=1$.

The equation of degree $162$

has exactly $5$ positive roots which are all simple.

If $p$ and $q$ are odd positive integers with no common divisor, then with

The prime divisors of the polynomial $x^2+1$ are $2,5,13,17,\ldots$, i.e. 2 and the odd prime numbers of the form $4n+1$; the prime numbers of the form $4n+3$ are not prime divisors of $x^2+1$.

Determine the prime divisors of $x^2+15$.

There are infinitely many prime numbers that are not prime divisors of a given irreducible polynomial of second degree with integral coefficients.

Every prime number is a prime divisor of the polynomial

which has no rational zeros.

Let $r$ and $s$ be odd prime numbers, such that

(For definition of the Legendre symbol $\left(\dfrac np\right)$ see Problem 45 of Part V.) Such prime numbers are for example $r=41$ and $s=5$. The polynomial

is irreducible but it is ``reducible'' (it can be expressed as the product of two factors of the 2nd degree) modulo $m$, where $m$ is an arbitrary integer, as can be shown in an elementary manner by formulae (1), (2) and (3).

Let the integers $D$ and $p$ be as in 160. In the power series expansion of $(1-Dz^2)^{-1}$ the coefficients are periodic mod $p$. The length of the period is always a divisor of $2(p-1)$. It is or is not a divisor of $p-1$ according to $\left(\dfrac Dp\right)=+1$ or $-1$.

The number $n=2^h+1$, $h\geq 2$ is a prime number if and only if

The following theorem given by Euler as a conjecture is true: The Diophantine equation

has no solution in positive integers $x,y,z,t$.

If the prime number $q\geq 11$, then there always exist positive odd prime numbers $p_1,p_2,p_3,p_4$, not necessarily distinct, that are all smaller than $q$, and satisfy the equations

respectively. $\left[\left(\dfrac {p_1}{q}\right)\right.$ etc., are Legendre symbols defined in Problem 45 of Part V.]

Let $F$ be a finite field with an odd number $q$ of elements. An element $a \in F^{*}$ is called a quadratic residue in $F$ if the binomial $x^{2}-a$ has a root in $F$.

Prove that:

For an element $a \in F^{*}$, set $\left(\frac{a}{F}\right)$ equal to 1 if $a$ is a quadratic residue in $F$, and $-1$ otherwise.

Prove that:

Let $a$ and $b$ be coprime numbers and $\sigma : x \rightarrow a x$ a permutation of the set of residue classes modulo $b$.

Prove that:

Let $G$ be a finite abelian group of odd order, written additively, $\sigma$ an automorphism of the group $G$, $\left(\frac{\sigma }{G}\right)=\operatorname {sgn} \sigma$, where $\sigma$ is regarded as a permutation of the set $G$. Prove that if $G$ can be represented as a union $\left\{ 0\right\} \cup S \cup \left\{ -S\right\}$ of disjoint subsets, then

Let $\sigma$ be an automorphism of a group $G$ of odd order, $G_{1}$ a subgroup of $G$ invariant under $\sigma$, $G_{2}=G / G_{1}$, and let $\sigma_{1}, \sigma_{2}$ be the automorphisms of $G_{1}$ and $G_{2}$ induced by $\sigma$. Prove that

and deduce from this the statement of problem 68.7, (b)).

Prove that if $N$ is the number of numbers $x$ from the range $1 \leqslant x \leqslant (b-1) / 2$ for which $a x \equiv r(\bmod b)$, $-(b-1) / 2 \leqslant r \leqslant 1$, then

Prove that $\left(\frac{2}{b}\right)=(-1)^{\left(b^{2}-1\right) / 8}$.

Prove that for any coprime odd numbers $a$ and $b$,

Let $V$ be a finite-dimensional space over a finite field $F$ of odd order, $\mathcal{A}$ a nonsingular linear operator on $V$. Prove that

Let $p$ be an odd prime number. If the congruence $x^{2} \equiv a(\bmod p)$ has a solution, then the integer $a$ is called a quadratic residue modulo $p$; otherwise, a quadratic non-residue. The Legendre symbol $\left(\frac{a}{p}\right)$ is defined by the relation

Show that $\left(\frac{a}{p}\right)=1 \Longleftrightarrow a+p \mathbb {Z} \in \left(Z_{p}^{*}\right)^{2}$ and $\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}}(\bmod p)$. Further, $\left(\frac{a b}{p}\right)=\left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$, and the number of quadratic residues in the reduced system $1,2, \ldots , p$ - 1 coincides with the number of non-residues. Verify for small odd prime numbers $p$ and $q$ that the quadratic law of reciprocity

proved in the general case (in many ways) by Gauss, holds. Deduce from Theorem 1 the relation $\left(\frac{-1}{p}\right)=(-1)^{\frac{p-1}{2}}$.

Prove (in the notation of the preceding exercise) that $\left(\frac{2}{p}\right)=(-1)^{\frac{p^{2}-1}{8}}$, i.e., 2 is a square mod $p$ precisely when $p \equiv \pm 1(\bmod 8)$.

Let $q=p^{n}$. Show that for $p=2$ all elements of the field $\mathbb {F}_{q}$ are squares, while for $p>2$ the squares of the group $\mathbb {F}_{q}^{*}$ form in it a subgroup $\mathbb {F}_{q}^{* 2}$ of index 2, with $\mathbb {F}_{q}^{* 2}=\operatorname {Ker}\left(t \mapsto t^{(q-1) / 2}\right)$.

Let $\mathbb {F}_{q}$ be a finite field with an odd number $q=p^{n}$ of elements. If $q$ is not equal to 3 or 5, then on the "circle" $x^{2}+y^{2}=1$ there is a point with coordinates $x, y \in \mathbb {F}_{q}^{*}$. Prove this statement for $p>5$.

Solving this problem and the next one (7.2.5) requires the basic properties of quadratic residues; see [GIM, § 9], [Vi, § 5], [ZSS, Sec. 3.3].

For a prime number $p$, denote $S_{d} = S_{p,d} := \sum \limits_{j \in \mathbb {Z}_{p}} \left(\dfrac {j(j+d)}{p}\right)$ (this is a sum of Legendre symbols).

Solving this problem (along with the previous one, 7.2.4) requires the basic properties of quadratic residues; see [GIM, § 9], [Vi, § 5], [ZSS, Sec. 3.3].

Construct an $n \times n$ Hadamard matrix for