# 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/(2*n*) + ∑_{n≥1} 1/(2*n*) < ∑_{n≥1} 1/(2*n* - 1) + ∑_{n≥1} 1/(2*n*) = *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*^{2} + *b*^{2}: *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*^{2} + *b*^{2})(*c*^{2} + *d*^{2}) = (*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

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