# how to prove $a^{p-1} + \frac{p-1}{2\cdot 1}a^{p-2} + \frac{(p-1)(p-2)}{3\cdot 2\cdot 1}a^{p-3} + … + a \in \mathbb{Z}$?

I'm reading "Journey Through Genius, the great theorems of mathematics" by William Dunham. During the introduction of Fermat's little theorem, it explains how Euler first proved it in 1736. However I couldn't understand one step of it.

It says, given $p$ a prime, $a \in \mathbb{Z}$, let $$b = a^{p-1} + \frac{p-1}{2\cdot 1}a^{p-2} + \frac{(p-1)(p-2)}{3\cdot 2\cdot 1}a^{p-3} + ... + a$$ , then one also has $b\in \mathbb{Z}$

This conclusion is given with only a few examples but no proof. How could it be proved?

Of course there are other proofs, but I'm particularly interested to figure out Euler's way.

please notice that $p$ is a prime is a must.

For example if $p=4$, $$b = a^3 + \frac{3}{2\cdot 1}a^2 + \frac{3\cdot 2}{3\cdot 2\cdot 1}a$$ is not an integer, chosen a = 13.

-
$\binom{p}{k} \equiv 0 \pmod{p}$ for a prime $p$ and $1 \leqslant k \leqslant p-1$. – Daniel Fischer Sep 14 '13 at 0:34
is this another theorem? – athos Sep 14 '13 at 2:02
@DanielFischer: Why not add an answer? – Aryabhata Sep 14 '13 at 2:30

One way is to look at the expression $\displaystyle \frac{p(p-1)(p-2)\cdots(p-n+1)}{1.2.\cdots.n}$ combinatorially as $\displaystyle \binom pn$. This represents the number of ways that you can choose $n$ objects out of $p$ objects when the order does not matter. Therefore it must be a natural number. Now, just by expanding $\displaystyle \binom pn$ for $n=1,\cdots,p-1$ you can factor out $p$ and obtain your expression by using the binomial theorem as $\displaystyle (a+1)^p - a^p$

EDIT: I guess you don't have a clear idea of what is happening here. Binomial coefficients, denoted by $\displaystyle \binom kn$ are always positive integers for the reasons that I said. Primality of $p$ comes into the play when you want to factor $p$ out of $\displaystyle \binom pn$. Since $n<p$ and $p$ is prime, $n!$ does not contain $p$ in its product. Therefore, the $p$ in the numerator does NOT get canceled and you can factor it out. That's why Fermat's little theorem is not correct for other natural numbers (A generalization exists due to Euler which uses Euler's totient function). This proof is actually using mathematical induction on $a$. You prove that if its true for $a$, then it must be true for $a+1$ as well.

-
please notice $p$ is a prime is a must. – athos Sep 14 '13 at 1:59
@athos: Nope. $p$ being a prime is not necessary for $\binom kn$ to be an integer. $p$ being prime is however a must for Fermat's little theorem to be true. – some1.new4u Sep 14 '13 at 2:05
pls see my edited post. – athos Sep 14 '13 at 2:26
thanks, now i got it. yes since $p>n$ and $p$ is a prime, it can factor out. – athos Sep 14 '13 at 2:33

Expand $(a+1)^{p}=\sum_{k=0}^{p}{p\choose k}a^k$ and note that ${p\choose k}=\frac{(p)!}{k!(p-k)!}=\frac{p(p-1)(p-2)...(p-k+1)}{k!}$ and note that $p$ and the denominator are comprime.

-
${p-1\choose k}=\frac{(p-1)!}{k!(p-1-k)!}=\frac{(p-1)(p-2)...(p-k)}{k!}$ the last one item in the numerator is $(p-k)$, not $(p-k+1)$ – athos Sep 14 '13 at 2:00
of course, thanks it should be ${p\choose k}$ instead, I fixed it. – leshik Sep 14 '13 at 2:11
then the problem is, the coefficient, is not ${p\choose k}$, but ${p\choose k}/p$ – athos Sep 14 '13 at 2:28
you do know the identity ${p\choose k}={p\choose p-k}$ – leshik Sep 14 '13 at 2:30
yes that's my difficulty. thanks for elaborating it! – athos Sep 14 '13 at 2:35

One simple proof is to use the following theorem:

If $r$ is a real number such that $ra$ and $rb$ are both integers for integers $a,b$ which are relatively prime (i.e. $(a,b) = 1$), then $r$ is an integer.

Now $\displaystyle r = \frac{(p-1)(p-2)\dots (p-k)}{(k+1)!}$ has the property that $pr$ and $(p-k-1)r$ are both binomial coefficients, and so are integers. Thus $r$ is an integer, by the above theorem.

To prove the above theorem, since $(a,b) = 1$, we have $ax + by = 1$ for some integers $x,y$. Multiplying by $r$ gives the result.

-
Okay. I see it. Thanks. – some1.new4u Sep 14 '13 at 4:25