Fun proofs

The harmonic series diverges

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

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

s = ∑ 1/(2n) + ∑ 1/(2n) < ∑ 1/(2n - 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.

Proof. 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 inclusion-exclusion,

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 global 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). ∎