Freshman's Dream (Frobenius): Expanding pth Powers Modulo p

$$(x+1)^p \mod{p} \equiv x^p+1$$

Do a few numerical experiments. What is $(x+1)^2$? Hw about $(x+1)^3$? $(x+1)^5$?

It's 1 3 3 1. For 5 it's "1 5 10 10 5 1". For 7, "1 7 21 35 35 21 7 1". What is going on with the terms between the two $1$s? Not just being symmetrical; all the terms in between are multiples of the prime number.

Anything special with prime numbers? Sure. For 4 it's "1 4 6 4 1", where 6 is not a multiple of 4. For 6, "1 6 15 20 15 6 1". Not much are multiples of 6!

A Proof Using Binomial Theorem

We can expand $(x+1)^p$ with the binomial theorem, such that the coefficient of each term is $\binom{p}{k}$ for some integer $k$. By definition, $$\binom{p}{k} = \frac{p!}{(p-k)!k!}$$ If $0<k<p$, then $0<(p-k)<p$.

Since $p$ is prime, it follows from Euclid's lemma that $(p-k)!k!$ must be coprime with $p$, and $p$ must remain one of the prime factors of $\frac{p!}{(p-k)!k!}$. (There's another perspective using the $p$-adic valuation on rationals, or just integers if you're careful enough.)

$p$ divides into $\dfrac{p!}{(p-k)!k!}$, so all the terms $k$ with $0<k<p$ disappeared as we take modulo $p$.

The only two terms that haven't disappear turns out to be $x^p+1$.

Show that for all $n$, $(x + 1)^{p^n} \equiv x^{p^n} + 1\pmod{p}$

Solution:

It suffices to show that the coefficients of $x^k$ for $k\in(0,p^n)$ for $(x+1)^{p^n}$ is a multiple of $p$. It is obvious since $^{p^n-1}C_k$ is an integer $^{p^n}C_k\ \cdot\frac{p^n}{p^n-k}$ which means it has a higher $p$-order than $^{p^n-1}C_k$.

Taylor expansion derivation of the freshman's dream

The freshman's dream is equivalent to the coefficient-wise congruence $$x^p - 1 \equiv (x-1)^p \pmod{p},$$ meaning when you compare both sides in standard form, the coefficients should be the same modulo $p$.

One way to prove the polynomial congruence above is to re-center $f(x) = x^p - 1$ from $0$ to $1$, using powers of $x-1$ instead of $x-0$. By the binomial theorem applied to $x^p = [(x-1) + 1]^p$, we know $$f(x) = x^p - 1 = a_0 + a_1(x-1) + \dots + a_p(x-1)^p$$ for some integers $a_0,a_1,\dots,a_p$, and we'd like to show that $a_0,a_1,\dots,a_{p-1}$ are divisible by $p$ while $a_p\equiv1\pmod{p}$. In fact, by comparing leading coefficients, $a_p = 1$, so the only difficulty is the divisibility statement.

We can do this using derivatives. First, $f(1) = 0$, so $a_0 = 0$. Next, $$f'(n) = pn^{p-1} \equiv 0\pmod{p}$$ for integers $n$, so $f'(1) \equiv 0\pmod{p}$, meaning $$1! a_1 = f'(1) \equiv 0\pmod{p}.$$

Proceeding in this way, we find that $$k! a_k = f^{(k)}(1) \equiv 0\pmod{p}$$ for all positive integers $k$. Now, $p\nmid k!$ as long as $k\leq p-1$, so we get $a_k \equiv 0\pmod{p}$ by Euclid's lemma, as desired.

Proof of the freshman's dream using $x^p - x$ factorization modulo $p$

From here we know that with coefficients interpreted modulo $p$, the polynomial $x^p - x$ factors as $$A(x) := (x-1)(x-2)\dots(x-p) \pmod{p},$$ meaning when you compare $x^p - x$ and $A(x)$ in standard form, the coefficients should be the same modulo $p$.

But replacing $x$ by $x+1$, that means $(x+1)^p - (x+1)$ factors as $$A(x+1) = x(x-1)\dots(x-(p-1)) \pmod{p}.$$

Yet $x \equiv x-p \pmod{p}$, so $$\begin{align*} A(x+1) &\equiv (x-p)(x-1)\dots(x-(p-1)) \\ &= (x-1)\dots(x-(p-1))(x-p) \\ &= A(x)\pmod{p}, \end{align*}$$ meaning that $$(x+1)^p - (x+1) \equiv A(x+1) \equiv A(x) \equiv x^p - x\pmod{p},$$ which rearranges to $$(x+1)^p \equiv x^p + 1\pmod{p},$$ as desired.

Reflection

The key point in the argument above is that $\{1,2,\dots,p\}$ is a complete residue system modulo $p$, so when we translate it by $\pm1$ it remains the same modulo $p$ (it's still a complete residue system).