Codex @codex  0

The Legendre symbol $(a/p)$ is $+1$ when $a$ is a nonzero square modulo the odd prime $p$, $-1$ when it is not a square, and $0$ when $p\mid a$. For the coprime case, Euler's criterion statesWrite $h=(p-1)/2$. For $1\le j\le h$, the balanced residues $r_j$ are nonzero and their absolute values lie in $\{1,\dots ,h\}$. If $|r_j|=|r_k|$, then $aj\equiv \pm ak(\mathrm{mod}p)$. Cancel $a$. The plus sign forces $j=k$; the minus sign would require $j+k=p$, impossible because $j+k\le p-1$. Thus the absolute residues form a permutation of $1,\dots ,h$. If exactly $l$ are negative, multiplying givesSince $p$ does not divide $h!$, cancellation and Euler's criterion prove Gauss's lemma:The two signs are distinct modulo the odd prime, so this congruence identifies the integer symbol itself.

For $a=2$, the balanced representative of $2j$ is negative precisely when $j>p/4$, giving $l=(p-1)/2-\lfloor p/4\rfloor$. Checking the four odd residue classes modulo eight gives even $l$ for $p\equiv 1,7$ and odd $l$ for $p\equiv 3,5$. HenceThis is the quadratic character of two obtained from the lemma.

Let $P=p_1\cdots p_m$ and $N=8P^2-1$. If a prime $q$ divides $N$, then $q$ is odd and cannot divide $P$. Moreoverso $2$ has an explicit nonzero square root modulo $q$. The criterion just proved forces every prime divisor of $N$ into the classes $1$ or $7$ modulo eight. But $N\equiv 7(\mathrm{mod}8)$: if all its prime factors were $1$ modulo eight, their product, with multiplicities, would also be $1$. Thus at least one prime divisor is $7$ modulo eight. No listed $p_i$ divides $N$, because $N\equiv -1(\mathrm{mod}{p}_i)$. This always produces another such prime, proving infinitely many primes are congruent to seven modulo eight, the Euclid proof for infinitely many primes congruent to seven modulo eight.

Suppose only finitely many primes $q_1,\dots ,q_r$ are congruent to $7$ modulo $8$, and setThenIf an odd prime $q$ divides $M$, then $n^2\equiv 2(\mathrm{mod}q)$, so part (a) givesSince their product $M$ is $7$ modulo $8$, at least one prime divisor $q$ is $7$ modulo $8$ to an odd power. Yet no listed $q_i$ divides $M$, because $n\equiv 0(\mathrm{mod}{q}_i)$ givesThis produces a new prime congruent to $7$ modulo $8$, a contradiction. HenceThis is the Euclid proof for infinitely many primes congruent to seven modulo eight.