The Lumenary · Advanced undergraduate

Number theory

Name: ______________________

Date: ______________________

You will learn to

Prove that $(\Z/p\Z)^\times$ is cyclic for $p$ prime, find primitive roots, and determine which moduli have them
Prove Euler's criterion and the law of quadratic reciprocity, and compute Legendre symbols with them
Use Dirichlet convolution and Möbius inversion to work with arithmetic functions
Characterise the primes that are sums of two squares
Prove that Pell's equation $x^2 - dy^2 = 1$ has infinitely many solutions, all generated by one, and find it with continued fractions

1.
How many primitive roots are there modulo $13$ ?
2.
Use quadratic reciprocity to compute the Legendre symbol $\left(\frac{37}{101}\right)$ . (Enter $1$ or $-1$ .)
3.
For which moduli $n$ does a primitive root exist? (Select all that apply.)
- A. $n = 9$
- B. $n = 8$
- C. $n = 18$
- D. $n = 15$
- E. $n = 50$
- F. $n = 12$
4.
Which of these numbers are sums of two squares of integers? (Select all that apply.)
- A. $29$
- B. $31$
- C. $65$
- D. $21$
- E. $45$
5.
In the proof of Euler's criterion, let $g$ be a primitive root modulo an odd prime $p$ and $a = g^k$ . Why is $a^{(p-1)/2} \equiv 1$ exactly when $k$ is even?
- A. $a^{(p-1)/2} = g^{k(p-1)/2}$ , which is $1$ iff $p - 1$ divides $k(p-1)/2$ , i.e. iff $k$ is even.
- B.Because $a^{p-1} \equiv 1$ by Fermat's little theorem.
- C.Because $g^{(p-1)/2} \equiv 1$ .
- D.Because every even number is a square.
6.
Compute $\sum_{d \mid 60} \mu(d)$ , where $\mu$ is the Möbius function.
7.
The fundamental solution of $x^2 - 2y^2 = 1$ is $(3, 2)$ . Using composition, $(x + y\sqrt2) = (3 + 2\sqrt2)^2$ , find the next solution. What is its $x$ ?
8.
In Lean, legendreSym p a is the Legendre symbol $\left(\frac{a}{p}\right)$ . Which statement is the law of quadratic reciprocity for primes p, q (with [Fact p.Prime] [Fact q.Prime])?
- A.p ≠ 2 → q ≠ 2 → p ≠ q → legendreSym q p * legendreSym p q = (-1) ^ (p / 2 * (q / 2))
- B.legendreSym q p * legendreSym p q = (-1) ^ (p / 2 * (q / 2))
- C.p ≠ 2 → q ≠ 2 → p ≠ q → legendreSym q p = legendreSym p q
- D.p ≠ 2 → q ≠ 2 → p ≠ q → legendreSym q p * legendreSym p q = (-1) ^ (p * q / 4)
9.
Write order(a, n) returning the multiplicative order of $a$ modulo $n$ (assume $\gcd(a, n) = 1$ , $n \ge 2$ ), and primitive_roots(p) returning the sorted list of primitive roots modulo a prime $p$ . Check that there are $\varphi(p - 1)$ of them.
Computational — Practice

Answer key — Number theory

1.
$(\Z/13\Z)^\times$ is cyclic of order $12$ . If $g$ generates it, the generators are the $g^k$ with $\gcd(k, 12) = 1$ , and there are $\varphi(12) = 4$ of them. With $g = 2$ they are $2, 2^5 = 6, 2^7 = 11, 2^{11} = 7$ . In general there are $\varphi(p - 1)$ primitive roots modulo $p$ .
2.
As $101 \equiv 1 \pmod 4$ , $\left(\frac{37}{101}\right) = \left(\frac{101}{37}\right) = \left(\frac{27}{37}\right) = \left(\frac{3}{37}\right)^3 = \left(\frac{3}{37}\right)$ . As $37 \equiv 1 \pmod 4$ , $\left(\frac{3}{37}\right) = \left(\frac{37}{3}\right) = \left(\frac{1}{3}\right) = 1$ . So $37$ is a square modulo $101$ ; indeed $21^2 = 441 = 4 \cdot 101 + 37$ .
3.
Primitive roots exist for $9 = 3^2$ , $18 = 2 \cdot 3^2$ and $50 = 2 \cdot 5^2$ , and not for $8$ , $12$ or $15$ . The obstruction for $15$ and $12$ is the Chinese remainder theorem: $(\Z/15)^\times \cong \Z/2 \times \Z/4$ has exponent $4$ . For $8$ , every unit satisfies $u^2 = 1$ .
4.
$29 = 2^2 + 5^2$ , $65 = 1^2 + 8^2 = 4^2 + 7^2$ and $45 = 3^2 + 6^2$ are sums of two squares; $31$ and $21$ are not. The criterion: $n \ge 1$ is a sum of two squares iff every prime $q \equiv 3 \pmod 4$ divides $n$ to an even power. It follows from Fermat's theorem for primes, the Brahmagupta–Fibonacci identity, and the fact that $q \equiv 3 \pmod 4$ dividing $a^2 + b^2$ forces $q \mid a$ and $q \mid b$ (since $-1$ is not a square mod $q$ ).
5.
Since $g$ has order $p - 1$ , $g^m \equiv 1$ iff $(p - 1) \mid m$ . With $m = k(p-1)/2$ this holds iff $k/2$ is an integer, i.e. $k$ is even. And $g^k$ is a square iff $k$ is even (if $g^k = (g^j)^2$ then $k \equiv 2j \pmod{p - 1}$ , an even modulus). So $a$ is a square iff $a^{(p-1)/2} \equiv 1$ : Euler's criterion.
6.
The square-free divisors of $60 = 2^2 \cdot 3 \cdot 5$ correspond to subsets of $\{2, 3, 5\}$ , and $\mu$ of such a divisor is $(-1)^{\text{size}}$ . So the sum is $\sum_{S \subseteq \{2,3,5\}} (-1)^{|S|} = (1 - 1)^3 = 0$ . In general $\sum_{d \mid n}\mu(d) = 0$ for $n \gt 1$ and $1$ for $n = 1$ : this is the identity $\mu * 1 = \varepsilon$ behind Möbius inversion.
7.
$(3 + 2\sqrt2)^2 = 17 + 12\sqrt2$ , so $(x, y) = (17, 12)$ , and indeed $17^2 - 2 \cdot 12^2 = 289 - 288 = 1$ . The norm $N(x + y\sqrt2) = x^2 - 2y^2$ is multiplicative, so powers of a norm- $1$ element have norm $1$ . Every positive solution is a power of $3 + 2\sqrt2$ : next come $(99, 70)$ and $(577, 408)$ . The ratios $17/12, 99/70, 577/408$ are excellent approximations of $\sqrt2$ .
8.
Option (a), which is Mathlib's legendreSym.quadratic_reciprocity (cited in the lesson). The hypotheses p ≠ 2, q ≠ 2, p ≠ q are essential, and the sign is $(-1)^{\frac{p-1}{2}\frac{q-1}{2}}$ , which is $-1$ exactly when both primes are $\equiv 3 \pmod 4$ .
9.
```
def order(a, n):
    k, x = 1, a % n
    while x != 1:
        x = x * a % n
        k += 1
    return k

def primitive_roots(p):
    return [a for a in range(1, p) if order(a, p) == p - 1]
```
The loop terminates because $a$ has finite order when $\gcd(a, n) = 1$ (Euler's theorem). The counts $\varphi(22) = 10$ for $p = 23$ and $\varphi(40) = 16$ for $p = 41$ reflect the fact that $(\Z/p\Z)^\times$ is cyclic of order $p - 1$ : a cyclic group of order $m$ has exactly $\varphi(m)$ generators.