19
$\begingroup$

If $p$ is prime, then $(x+y)^p=x^p+y^p$ holds in any field of characteristic $p$. However all the proofs I have seen use induction and some relatively nasty algebra despite how fundamental this fact seems.

What is the nicest, "highest level proof" you know?

$\endgroup$
  • $\begingroup$ This section may at least be of some interest: en.wikipedia.org/wiki/Freshman%27s_dream#Prime_characteristic $\endgroup$ – nathan.j.mcdougall Apr 17 '15 at 4:17
  • 1
    $\begingroup$ It holds in any commutative ring of characteristic $p$. Many would consider the theory of finite fields - determining their existence and uniqueness and thus their classification, and knowing how to construct them - to be nasty algebra despite how fundamental the topic seems. Moreover, what kind of high-level math do you expect to have something to say about finite fields while simultaneously not assuming any knowledge of them? Certainly I would count the binomial theorem in that category! Do you expect any other "high-level math" to be supported by less nasty algebra than that? $\endgroup$ – whacka Apr 17 '15 at 13:08
  • 2
    $\begingroup$ for $p \neq 0$, right? In $\mathbb R$, $(x + y)^0 = 1$, but $x^0 + y^0 = 1 + 1 = 2$ (for $x, y, x + y \neq 0$). $\endgroup$ – wchargin Apr 17 '15 at 20:25
15
$\begingroup$

Let $F$ be a field of characteristic $p$. Let $f = (1 + x)^p \in F[x]$. We want to show that $f = 1 + x^p$.

Take the formal derivative: $f' = p(x+1)^{p-1} = 0$

Now we know that $f$ has degree $p$, and its derivative is $0$, so $f$ must be in the form $A + Bx^p$ with $A$, $B \in F$.

$f(0) = 1$ so $A = 1$.

A product of monic polynomials is always monic so $B = 1$.

Q.E.D.

The "freshman's dream" is a corollary of this fact.

The fact that the binomial coefficient $\binom p i$ is divisible by $p$ for $1 \leq i \leq p-1$ is also a corollary.

The binomial theorem itself can be proved by taking derivatives of $(1 + x)^n$.

Fermat's little theorem follows easily: $\left( \sum_{i=1}^n 1 \right)^p = \sum_{r=1}^n (1^p) = \sum_{r=1}^n 1$

$\endgroup$
  • 1
    $\begingroup$ This requires proving the power-chain rule $(u(x)^e)'=eu(x)^{e-1}u'(x)$ for the formal derivative, which initially might seem to involve a lot of algebra. There is a clever definition of the formal derivative (not just the artificial $(x^n)':=nx^{n-1}$ one) that allows us to only use the geometric series formula to prove it, and it's elegant in my opinion. The definition is that $f'(x)$ equals the two-variable polynomial $\frac{f(x+h)-f(x)}{x-h}$ simplified to an element of $K[x,h]$ first and then evaluated at $h=0$ second. $\endgroup$ – whacka Apr 17 '15 at 13:13
  • 1
    $\begingroup$ @whacka: that should be divided by $h$, not $x - h$ $\endgroup$ – jkabrg Apr 17 '15 at 13:22
  • 1
    $\begingroup$ Oops, yes, that's what I meant. $\endgroup$ – whacka Apr 17 '15 at 13:23
  • $\begingroup$ A really nice way to do it is to map $F[X]$ into $F[X][Y]/Y^2$. then $f(X + aY) = f(X) + af'(X)Y$ where $a \in F[X]$. the chain rule falls out with no effort. $\endgroup$ – jkabrg Apr 17 '15 at 13:49
  • $\begingroup$ I suppose computing $(f(X)+f'(X)Y)^n=f(X)^n+nf(X)^{n-1}f'(X)Y$ mod $Y^2$ is "easier" than computing $(x+y)^p$ mod $p$, but perhaps the OP could disagree with that. $\endgroup$ – whacka Apr 17 '15 at 13:53
31
$\begingroup$

The binomial coefficient $\binom p i$ is divisible by $p$ for $1 \leq i \leq p-1$

One way of seeing this is Legendre's formula on the power of a prime dividing some factorial, http://www.cut-the-knot.org/blue/LegendresTheorem.shtml

and http://en.wikipedia.org/wiki/Factorial#Number_theory

From the formula, $p$ divides $p!$ with exponent exactly $1,$ but $p$ does not divide $i!$ or $(p-i)!$ when $1 \leq i \leq p-1.$

$\endgroup$
  • $\begingroup$ Do we also need to prove this? Or is this considered well-known? $\endgroup$ – justhalf Apr 17 '15 at 6:12
  • 5
    $\begingroup$ @Asvin: The point is that you are using the action of the integers on the elements of the finite field. There is no reason why we should or could expect not to use the integers in the proof, since the very statement of field characteristic requires "using something from outside the finite field". $\endgroup$ – user21820 Apr 17 '15 at 7:32
  • 5
    $\begingroup$ @justhalf: the proof is trivial once you believe that $\binom{p}{i} = \frac{p!}{i!(p-i)!}$, and also believe that the integers have unique prime factorisations, and also that $p$ is prime, since then there's no factor of $p$ on the bottom when $i < p$ and $p-i < p$. You can give elementary proofs of all three of those, but hopefully don't need to every time you use them ;-) $\endgroup$ – Steve Jessop Apr 17 '15 at 9:30
  • 7
    $\begingroup$ @Asvin Let me convince you it's not inelegant, doesn't require induction to understand (only counting with symmetry, which is beautiful), and is germane to the problem at hand. Expanding $(x+y)^p$ yields all possible words in the letters $x$ and $y$; every one of these words can get its letters cyclically shifted to the right and wrapped back around yielding $p$ different words all of which are like terms and cancel - except for $xx\cdots x$ and $yy\cdots y$. The theorem may not be about finite fields, but it is about binomials, which is what we're talking about so it's perfectly germane. $\endgroup$ – whacka Apr 17 '15 at 12:58
  • 1
    $\begingroup$ Also, Asvin, you have to use induction to say that any ring homomorphism is finitely additive, that is not at all specific to finite fields. But it's perfectly intuitive and obvious so who cares? | BTW, @SteveJessop, the full factorial formula for binomial coefficients is unnecessary to prove $p\mid\binom{p}{i}$ for $0<i<p$. There is a combinatorial argument using symmetry that also works; see my comment above to Asvin. (The argument can also be cast in terms of groups actions and the orbit-stabilizer theorem, but I decided to keep it simple and focused on binomial expansions.) $\endgroup$ – whacka Apr 17 '15 at 13:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.