Euler criterion

For an odd prime $p$,For $p\nmid a$, write $a=g^m$ using a primitive root $g$; then the left side is $(-1{)}^m$, which is one exactly when $m$ is even and $a$ is a square.

Euler's criterion at $a=-1$ gives

For every odd prime,

If $q_1,\dots ,q_r$ listed all primes congruent to seven modulo eight, then for $n=8q_1\cdots q_r$ the odd number $(n^2-2)/2$ is seven modulo eight. Every prime factor is one or seven modulo eight, at least one is seven, and none is among the $q_i$, a contradiction.

Let ${\pi }_k(x)$ count primes at most $x$ congruent to $k$ modulo eight. Bounding the prime-power divisibility ofabove and its size below gives, for all sufficiently large $x$,

For an integer matrix $A$ and prime $p$, the commuting-matrix binomial theorem and divisibility of $\left(\genfrac{}{}{0ex}{}{p}{j}\right)$ for $0<j<p$ give