Number theory

Let $\psi(d)$ be the number of elements of order $d$. By Lagrange's theorem every order divides $p - 1$, so $\sum_{d \mid p-1}\psi(d) = p - 1$. Suppose $\psi(d) \ge 1$, and let $a$ have order $d$. Then $1, a, \dots, a^{d-1}$ are $d$ distinct roots of $x^d - 1$. Over the field $\Z/p\Z$ a polynomial of degree $d$ has at most $d$ roots (factor theorem plus no zero divisors), so these are all the roots. Every element of order $d$ is therefore a power $a^k$, and $a^k$ has order $d$ iff $\gcd(k, d) = 1$. Hence $\psi(d) = \varphi(d)$ whenever $\psi(d) \ne 0$, so $\psi(d) \le \varphi(d)$ for all $d$. But $\sum_{d \mid p-1}\varphi(d) = p - 1$ (groups lesson, Proposition 4), so the inequalities are equalities. In particular $\psi(p - 1) = \varphi(p - 1) \ge 1$.

For $k = 3$: $a = 2m + 1$ gives $a^2 = 4m(m + 1) + 1 \equiv 1 \pmod 8$, as $m(m + 1)$ is even. If $a^{2^{k-2}} = 1 + 2^k t$, squaring gives $a^{2^{k-1}} = 1 + 2^{k+1}t + 2^{2k}t^2 \equiv 1 \pmod{2^{k+1}}$. Induct on $k$.

None otherwise. If $n = 2^k$ with $k \ge 3$, use Theorem 2. Otherwise $n = m m'$ with $\gcd(m, m') = 1$ and $m, m' \gt 2$, so $\varphi(m)$ and $\varphi(m')$ are both even. By the Chinese remainder theorem (quotients), $(\Z/n)^\times \cong (\Z/m)^\times \times (\Z/m')^\times$. Every element then has order dividing $\operatorname{lcm}(\varphi(m), \varphi(m')) \le \varphi(m)\varphi(m')/2 \lt \varphi(n)$.

Odd prime powers. Let $g$ be a primitive root modulo $p$. If $g^{p-1} \equiv 1 \pmod{p^2}$, replace $g$ by $g + p$: by the binomial theorem $(g + p)^{p-1} \equiv g^{p-1} + (p-1)g^{p-2}p \not\equiv 1 \pmod{p^2}$. So we may assume $g^{p-1} = 1 + pt$ with $p \nmid t$. By induction, using the binomial theorem and $p$ odd, $(1 + pt)^{p^{j}} = 1 + p^{j+1}t_j$ with $p \nmid t_j$. The order of $g$ modulo $p^k$ divides $\varphi(p^k) = (p - 1)p^{k-1}$ and is a multiple of $p - 1$ (reduce modulo $p$), so it is $(p-1)p^j$ for some $j$. It is not $(p-1)p^{j}$ for $j \lt k - 1$, since $g^{(p-1)p^{k-2}} = 1 + p^{k-1}t_{k-2} \not\equiv 1 \pmod{p^k}$. So $g$ is a primitive root modulo every $p^k$.

$2p^k$, $2$ and $4$. $(\Z/2p^k)^\times \cong (\Z/p^k)^\times$ (the factor $(\Z/2)^\times$ is trivial), and an odd primitive root modulo $p^k$ is a primitive root modulo $2p^k$. Modulo $2$ and $4$, $1$ and $3$ are primitive roots.

If $p \mid a$ both sides are $0$. Otherwise let $g$ be a primitive root (Theorem 1) and $a \equiv g^k$. Then $a$ is a square iff $k$ is even: $g^k = (g^j)^2$ means $k \equiv 2j \pmod{p - 1}$, and $p - 1$ is even. On the other hand $g^{(p-1)/2} \equiv -1$, because it is a root of $x^2 - 1$ other than $1$ (as $g$ has order $p - 1$). So $a^{(p-1)/2} = (g^{(p-1)/2})^k \equiv (-1)^k$. This is $1$ for even $k$ and $-1$ for odd $k$. Exactly half of $k = 0, \dots, p-2$ are even. Multiplicativity follows since $(ab)^{(p-1)/2} = a^{(p-1)/2}b^{(p-1)/2}$, and the values $\pm 1$ are distinct modulo $p \gt 2$.

Let $h = \frac{p-1}{2}$. Write the residues of $a, 2a, \dots, ha$ as $s_1, \dots, s_\lambda$ (those below $\frac p2$) and $t_1, \dots, t_\mu$ (those above). The $h$ numbers $s_1, \dots, s_\lambda, p - t_1, \dots, p - t_\mu$ all lie in $\{1, \dots, h\}$, and they are distinct. The $s$'s are distinct, and so are the $t$'s. If $s_i = p - t_j$, then $ka + la \equiv 0$ for some $1 \le k, l \le h$, so $p \mid k + l$, impossible as $2 \le k + l \le p - 1$. So they are exactly $1, \dots, h$ in some order. Multiplying, $h! \equiv \prod s_i \prod (p - t_j) \equiv (-1)^\mu \prod s_i \prod t_j \equiv (-1)^\mu\, a^h\, h! \pmod p$. Cancel $h!$ and use Euler's criterion.

For $a = 2$, the residues $2k$ with $1 \le k \le h$ are just $2, 4, \dots, p - 1$. Those exceeding $\frac p2$ are the $2k$ with $k \gt \frac p4$, so $\mu = h - \lfloor \frac p4 \rfloor$. Checking $p = 8m + 1, 8m + 3, 8m + 5, 8m + 7$ gives $\mu = 2m, 2m + 1, 2m + 1, 2m + 2$. So $\mu$ is even exactly for $p \equiv \pm 1 \pmod 8$, and $(-1)^\mu = (-1)^{(p^2 - 1)/8}$ in each case.

(Eisenstein, 1844.) Step 1: for odd $a$ with $p \nmid a$, $\mu \equiv \sum_{k=1}^{h} \lfloor \frac{ka}{p} \rfloor \pmod 2$. With the notation of Lemma 6, $ka = p\lfloor\frac{ka}{p}\rfloor + (\text{residue})$. Summing over $k = 1, \dots, h$ gives

From the proof of Lemma 6, $\sum_{k=1}^h k = \sum_i s_i + \sum_j (p - t_j) = \sum_i s_i + p\mu - \sum_j t_j$. Subtracting, $(a - 1)\sum k = p\big(\sum\lfloor\frac{ka}p\rfloor - \mu\big) + 2\sum_j t_j$. Reduce modulo $2$: $a - 1$ is even and $p$ is odd, so $\sum\lfloor \frac{ka}{p}\rfloor \equiv \mu$.

Step 2: count lattice points. Consider the points $(x, y)$ with $1 \le x \le \frac{p-1}{2}$ and $1 \le y \le \frac{q-1}{2}$; there are $\frac{p-1}{2}\cdot\frac{q-1}{2}$ of them. None lies on the line $py = qx$, since that would need $p \mid x$. Below the line, the column at $x$ contains $\lfloor \frac{qx}{p} \rfloor$ points, so there are $\sum_x \lfloor\frac{qx}{p}\rfloor \equiv \mu(q, p)$ points below. Symmetrically, there are $\sum_y \lfloor \frac{py}{q}\rfloor \equiv \mu(p, q)$ points above. By Gauss's lemma,

$(f * g)(n) = \sum_{ab = n} f(a)g(b)$ is symmetric in $f, g$, and $((f * g) * h)(n) = \sum_{abc = n} f(a)g(b)h(c)$ is symmetric in the bracketing. Also $(f * \varepsilon)(n) = f(n)$. If $\gcd(m, n) = 1$, the divisors of $mn$ are exactly the products $d e$ with $d \mid m$, $e \mid n$, each uniquely, and then $\gcd(d, e) = 1$ and $\gcd(m/d, n/e) = 1$. So $(f * g)(mn) = \sum_{d,e} f(d)f(e)g(\frac md)g(\frac ne) = (f * g)(m)(f * g)(n)$. Finally $\mu * \mathbf 1$ is multiplicative, and on a prime power $p^k$ with $k \ge 1$ it is $\mu(1) + \mu(p) = 1 - 1 = 0$.

The first statement says $g = f * \mathbf 1$, the second $f = \mu * g$. If $g = f * \mathbf 1$ then $\mu * g = f * (\mathbf 1 * \mu) = f * \varepsilon = f$. If $f = \mu * g$ then $f * \mathbf 1 = g * (\mu * \mathbf 1) = g$.

Only if. Squares are $0$ or $1$ modulo $4$, so $a^2 + b^2 \not\equiv 3 \pmod 4$.

If. Let $p \equiv 1 \pmod 4$. By Corollary 5 there is an $x$ with $p \mid x^2 + 1 = (x + i)(x - i)$ in the Gaussian integers $\Z[i]$. But $p$ divides neither factor, since $\frac xp \pm \frac 1p i \notin \Z[i]$. So $p$ is not a prime element of $\Z[i]$. Now $\Z[i]$ is a Euclidean domain, hence a UFD in which irreducible elements are prime (rings lesson, Theorems 6–9). So $p$ is not irreducible: $p = \alpha\beta$ with $\alpha, \beta$ non-units. Taking norms, $p^2 = N(\alpha)N(\beta)$ with $N(\alpha), N(\beta) \gt 1$, so $N(\alpha) = p$. Writing $\alpha = a + bi$ gives $p = a^2 + b^2$.

Fix $Q \ge 1$. The $Q + 1$ numbers $\{0\alpha\}, \{1\alpha\}, \dots, \{Q\alpha\}$ (fractional parts) lie in $[0, 1)$. By the pigeonhole principle two of them, say for $0 \le j \lt k \le Q$, lie in the same interval $[\frac iQ, \frac{i+1}Q)$. Then $y = k - j \in [1, Q]$ and $x = \lfloor k\alpha \rfloor - \lfloor j\alpha \rfloor$ satisfy $|y\alpha - x| \lt \frac1Q \le \frac1y$. As $\alpha$ is irrational, $|y\alpha - x| \gt 0$. Taking $Q$ larger than $1/|y\alpha - x|$ produces a new pair each time, so there are infinitely many.

(a) For each pair from Lemma 12 (with $\alpha = \sqrt d$),

So infinitely many pairs give values $x^2 - dy^2$ in a finite set. None is $0$, since $\sqrt d$ is irrational. By the pigeonhole principle infinitely many pairs share the same value $N$ and the same residues of $x$ and $y$ modulo $|N|$. Take two distinct such pairs $(x_1, y_1)$, $(x_2, y_2)$ with positive coordinates, and set

Modulo $|N|$, $x_1x_2 - dy_1y_2 \equiv x_1^2 - dy_1^2 = N \equiv 0$ and $x_2y_1 - x_1y_2 \equiv x_1y_1 - x_1y_1 = 0$, so $u, v \in \Z$. Taking norms, $u^2 - dv^2 = N \cdot N / N^2 = 1$. If $v = 0$ then $u = \pm 1$, and the two positive numbers $x_i + y_i\sqrt d$ would be equal, so the pairs would be equal. Hence $v \ne 0$.

(b) If $\eta = x + y\sqrt d \in U$ and $\eta \gt 1$, then $\bar\eta = \eta^{-1} \in (0, 1)$, so $x = \frac{\eta + \bar\eta}{2} \gt 0$ and $y = \frac{\eta - \bar\eta}{2\sqrt d} \gt 0$. Such $\eta$ exist by (a): replace $(x, y)$ by $(|x|, |y|)$. Among them, the one with the least $x$ (and so the least $y$) is the least element $\varepsilon$ of $U \cap (1, \infty)$. Now let $\eta \in U$ with $\eta \gt 0$, and choose $n$ with $\varepsilon^n \le \eta \lt \varepsilon^{n+1}$. Then $\eta\varepsilon^{-n} \in U \cap [1, \varepsilon)$, so it equals $1$ by minimality, and $\eta = \varepsilon^n$. If $\eta \lt 0$, apply this to $-\eta$.