Freshman's Dream
Most people know that
\[ (x+y)^n = x^n + y^n \]
does not hold for all real numbers $x, y \in \mathbb{R}$ for $n > 1$. However, if one works over a characteristic $p$ ring, we do have
\[ (x+y)^p = x^p + y^p \]
The above is called the Freshman's dream and follows from
Lemma
\[p \left | \binom{p}{i} \right . \]
for $0 < i < p$. Let $N = \binom{p}{i}$.
Proof) $N = \frac{p!}{(p-i)! i!}$. This implies that $p! = N (p-i)! i!$. For $0 < i < p$, $p \not| (p-i)!$ and $p \not| i!$. Therefore, $p |N$.
Now we prove some more general result.
Lemma
\[ p \left | \binom{p^r}{i} \right . \]
for $0 < i < p^r$.
Proof) Let $v_p$ be the $p$-adic valuation. Then
\[ v_p(n!) = \sum_{k=1}^r \left \lfloor \frac{n!}{p^k} \right \rfloor \]
\[ v_p(n!) = \sum_{k=1}^r \left \lfloor \frac{n!}{p^k} \right \rfloor \]
Recall that $\left \lfloor \frac{n}{m} \right \rfloor$ is the number of multiples of $m$ less or equal to $n$. By varying $k$, we would count those are divisible by higher $p$ powers of p.
As a lemma, observe that
\[ \lfloor x \rfloor + \lfloor -x \rfloor = \begin{cases} 0 & x \in \mathbb{Z} \\ -1 & x \in \mathbb{R} \backslash \mathbb{Z} \end{cases} \]
This is obvious when $x \in \mathbb{Z}$ as $\lfloor x \rfloor = x$. If $x = z + \alpha$ where $z \in \mathbb{Z}$ and $0 < \alpha < 1$. Then $\lfloor x \rfloor = z$ and $\lfloor -x \rfloor = -z-1$.
\[ \begin{array}{lcl} v_p((p^r-i)!) + v_p(i!) & = & \sum_{k=1}^r \left \lfloor \frac{p^r-i}{p^k} \right \rfloor + \left \lfloor \frac{i}{p^k} \right \rfloor \\ & = & \sum_{k=1}^r p^{n-k} + \left \lfloor \frac{-i}{p^k} \right \rfloor + \left \lfloor \frac{i}{p^k} \right \rfloor \\ & = & (1+ p + \cdots + p^{n-1}) + \sum_{k=1}^r \left \lfloor \frac{-i}{p^k} \right \rfloor + \left \lfloor \frac{i}{p^k} \right \rfloor \\ &= & \frac{p^n-1}{p-1} + \sum_{k=1}^r \left \lfloor \frac{-i}{p^k} \right \rfloor + \left \lfloor \frac{i}{p^k} \right \rfloor \end{array} \]
Let us examine the last part. $\frac{i}{p^k}$ is an integer if and only if $p^k|i$. Hence If $v_p(i) = l$, then $\frac{i}{p^k} \in \mathbb{Z}$ for $1 \leq k \leq l$. Therefore, the sum
\[ \left \lfloor \frac{-i}{p^k} \right \rfloor + \left \lfloor \frac{i}{p^k} \right \rfloor = 0 \]
for $1 \leq k \leq v_p(i)$. In particular,
\[ \sum_{i=1}^r \left \lfloor \frac{-i}{p^k} \right \rfloor + \left \lfloor \frac{i}{p^k} \right \rfloor = -(r - v_p(i)) \]
by the lemma.
\[ v_p((p^r-i)!) + v_p(i!) = \frac{p^r-1}{p-1} - (r-v_p(i)) \]
As
\[ v_p((p^r)!) = \sum_{k=1}^r \left \lfloor \frac{p^r}{p^k} \right \rfloor = p^{r-1} + \cdots + p + 1 = \frac{p^r-1}{p-1} \]
If follows that
\[ v_p \left ( \binom{p^r}{i} \right ) = v_p((p^r)!) - v_p((p^r-i)!) -v_p(i!) = r-v_p(i) \]
Hence unless $i=0$ or $i=p^r$, the RHS is greater than $1$, i.e. $p$ divides $\binom{p^r}{i}$.
Hence unless $i=0$ or $i=p^r$, the RHS is greater than $1$, i.e. $p$ divides $\binom{p^r}{i}$.
Reference:
Comments
Post a Comment