Fun proofs

The harmonic series diverges

Theorem. ∑_n≥1 1/n = ∞.

Proof. Suppose, toward a contradiction, that s := ∑_n≥1 1/n is finite. Then

s = ∑_n≥1 1/(2n) + ∑_n≥1 1/(2n) < ∑_n≥1 1/(2n - 1) + ∑_n≥1 1/(2n) = s. ∎

Sums of squares mod p

Theorem. Every element of 𝔽_p is a sum of two squares.

Proof. We may suppose p > 2. Write S ≔ {a² + b²: a,b ∈ 𝔽_p}. Obviously 0 ∈ S. Exactly half of the elements of 𝔽_p^× are squares, and 1 is a square; it follows that #(S ∖ {0}) > (#𝔽_p^×)/2. But S ∖ {0} is a group under multiplication because of the identity (a² + b²)(c² + d²) = (ac + bd)² + (ad - bc)², so it must be all of #𝔽_p^× by Lagrange's theorem. ∎

Density of primes

Euler famously observed that the identity ζ(1) = ∞ (in the Euler expansion) implies the infinitude of primes. But it also implies that there aren't too many primes:

Theorem. Let P be the set of primes. Then d(P) = 0, where d means natural density.

Theorem. For each N, define

T_N ≔ ℕ ∖ ∪_p≤N(pℕ ∖ p)

Clearly P ⊆ T_N for each N. But d(pℕ ∖ p) = 1/p, so by the inclusion-exclusion principle,

d(T_N) = ∏_p≤N(1-1/p) → 1/ζ(1) = 0

as N → ∞. ∎

Roots of irreducible polynomials mod primes

I learned the following proof from Ariana1729.

Theorem. Let F be a number field, and let f ∈ 𝒪_F[t] be a nonlinear irreducible polynomial. Then there are infinitely many primes 𝔭 of F such that f has no roots mod 𝔭.

Proof. Let K ≔ F[t]/f, and let K′/F be the splitting field of f. Set G ≔ Gal(K′/F) and H ≔ Gal(K′/K).

Let 𝔭 be a prime of F which is unramified in K′ and does not divide the conductor of the order 𝒪_F[α] in K, where α is the image of t in K. Assume that f has a root mod 𝔭. Then there exists a prime 𝔓 of 𝒪_K lying above 𝔭 with inertial degree f_𝔓/𝔭 = 1. Let 𝔓′ be a prime of K′ above 𝔓. Since #D_𝔓′/F = f_𝔓′/𝔭 and #D_𝔓′/K = f_𝔓′/𝔓 (where D means "decomposition group"), multiplicativity of the inertial degree implies that the inclusion D_𝔓′/K ⊆ D_𝔓′/F is an equality. In particular, D_𝔓′/F ⊆ H.

Since H is a proper subgroup of G, there must exist some conjugacy class C ⊆ G disjoint from H. By Chebotarev's density theorem, there are infinitely many primes 𝔭 of F such that Frob_𝔭 = C. Then for any prime 𝔓′ of K′ lying above 𝔭, the group D_𝔓′/F contains an element of C, hence cannot be contained in H. Thus 𝔭 cannot satisfy the assumptions of the previous paragraph. Since only finitely many primes ramify or divide the conductor, the theorem follows. ∎

Corollary. Let a ∈ ℤ, and let 𝓁 be a prime number. Then a is an 𝓁th power mod all but finitely many primes if and only if a is an 𝓁th power in ℤ.

Proof. Special case of the Theorem (irreducibility is an exercise). ∎