Fun proofs

Back to main page.

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 ≔ {a2 + b2: 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 (a2 + b2)(c2 + d2) = (ac + bd)2 + (ad - bc)2, 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

TN ≔ ℕ ∖ pN(pℕ ∖ p)

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

d(TN) = ∏pN(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 KF[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𝔓′/KD𝔓′/F is an equality. In particular, D𝔓′/FH.

Since H is a proper subgroup of G, there must exist some conjugacy class CG 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). ∎