2
$\begingroup$

I decided to prove by induction (though am running into some issues).

(Base case) When $k = 1$, we have $$\binom{p}{1} = \frac{p!}{1! \cdot (p - 1)!} = p \equiv 0 \bmod p.$$ When $k = p - 1$, we have $$\binom{p}{p - 1} = \frac{p!}{(p - 1)! \cdot (p - p + 1)!} = \frac{p!}{(p - 1)! \cdot 1!} = p \equiv 0 \bmod p.$$ (Inductive step) For some $1 < k < p - 1$, assume $\binom{p}{k} \equiv 0 \bmod p$. We will show that $\binom{p}{k + 1} \equiv 0 \bmod p$. By substitution, we obtain $$\binom{p}{k + 1} = \frac{p!}{(k + 1)! \cdot (p - k - 1)!} = \frac{p!}{k!(p - k)!} \cdot \frac{p - k}{k + 1} = \binom{p}{k} \cdot \frac{p - k}{k + 1}$$ Since the inductive hypothesis assumes that $\binom{p}{k} \equiv 0 \bmod p \implies \binom{p}{k} \cdot a \equiv 0 \bmod p \ \forall \ a \in \mathbb{Z}$, I need to somehow show that $\frac{p - k}{k + 1}$ is an integer, but it doesn't seem like it always will be.

Ultimately, I think it may be easier to not use induction, but I think it can be done this way and I just want to see if anyone has a good idea on how to continue my logic.

$\endgroup$
6
  • 3
    $\begingroup$ It's not true that $\frac{p - k}{k + 1} \in \mathbb{Z}$, but you know that $\binom{p}{k+1}$ is integer. $\endgroup$
    – openspace
    Mar 6, 2023 at 21:19
  • 2
    $\begingroup$ Note that $\binom{p}{k+1}=\binom{p}{k}\cdot\frac{p-k}{k+1}\;\;\to\;\;(k+1)\cdot\binom{p}{k+1}=\binom{p}{k}\cdot(p-k)$. Also, your base case of $\binom{p}{1} = \frac{p!}{1! \cdot p!} = 1 \equiv 0 \bmod p$ should be $\binom{p}{1} = \frac{p!}{1! \cdot \color{red}{(p-1)}!} = \color{red}{p} \equiv 0 \bmod p$ instead. $\endgroup$ Mar 6, 2023 at 21:27
  • $\begingroup$ @JohnOmielan Thanks! Is this enough to prove the inductive step? Since this equation is not explicitly saying that $\binom{p}{k} \equiv 0 \bmod p$? Or is the next step to show that $(k + 1)$ has an inverse mod $p$ so $(k + 1) \cdot \binom{p}{k + 1} = \binom{p}{k} \cdot (p - k) \implies (k + 1) \cdot \binom{p}{k + 1} \equiv 0 \bmod p \implies \binom{p}{k + 1} \equiv 0 \cdot (k + 1)^{-1} \equiv 0 \bmod p$? $\endgroup$ Mar 6, 2023 at 21:42
  • 1
    $\begingroup$ You're welcome. Yes, you could show $k+1$ has an inverse. However, an alternative is that since $p\mid\binom{p}{k}\;\to\;p\mid\binom{p}{k}\cdot(p-k)$, then $p\mid(k+1)\cdot\binom{p}{k+1}$. Thus, because $1\le k \lt p-1 \;\;\to\;\;2\le k+1\lt p$, then $p\nmid k+1$, so $p\mid\binom{p}{k+1}$. Also, in case you weren't aware, there's quite a few posts here which solve the problem without induction, e.g., Why is $ {n\choose k} \equiv 0 \pmod n$ if $n$ is prime?. $\endgroup$ Mar 6, 2023 at 21:54
  • 2
    $\begingroup$ The base case is clearly wrong. $\endgroup$
    – Randall
    Mar 6, 2023 at 21:59

1 Answer 1

1
$\begingroup$

You're correct that, for $p$ prime, to prove

$$\binom{p}{k}\equiv 0\bmod{p}\;\;\forall\;\;1\le k\le p-1 \tag{1}\label{eq1A}$$

it's generally easier to not use induction (e.g., such as shown in Why is $ {n\choose k} \equiv 0 \pmod n$ if $n$ is prime?). Nonetheless, you've made a good start with using induction, although there are several issues:

  1. It's unnecessary to include a base case of $k=p-1$. This is because that's already handled in the inductive step where, with $k=p-2$, it's shown that $k+1=p-1$ also satisfies \eqref{eq1A}.

  2. With the inductive step, you wrote "For some $1 < k < p - 1$ ...". However, the inequality should be $1\color{red}{\le}k\lt p-1$ instead, to have the induction start from your base case of $k=1$.

  3. From your result of $$\binom{p}{k + 1} = \binom{p}{k}\cdot\frac{p - k}{k + 1} \tag{2}\label{eq2A}$$ you can't "... somehow show that $\frac{p - k}{k + 1}$ is an integer ..." because it's not true in general, as openspace's comment indicates.

When checking divisibility, it's generally easier to deal with products of just integers rather than with one or more non-integral rational numbers. As such, by multiplying both sides of \eqref{eq2A} by $k+1$, we get

$$(k+1)\cdot\binom{p}{k + 1} = \binom{p}{k}\cdot(p - k) \tag{3}\label{eq3A}$$

Note that $1\le k\lt p-1 \;\;\to\;\;2\le k+1 \lt p$, so $p\nmid k+1$. Thus, as you indicated in your comment, we could state that $k+1$ has a multiplicative inverse modulo $p$ to get that

$$\begin{equation}\begin{aligned} & (k+1)\cdot\binom{p}{k + 1} = \binom{p}{k}\cdot(p - k) \implies (k+1)\cdot\binom{p}{k + 1}\equiv 0\bmod{p} \\ & \implies \binom{p}{k + 1}\equiv 0\cdot(k+1)^{-1}\equiv 0\bmod{p} \end{aligned}\end{equation}\tag{4}\label{eq4A}$$

Alternatively, from \eqref{eq3A}, since $p\mid\binom{p}{k}\;\;\to\;\;p\mid(k+1)\cdot\binom{p}{k + 1}$, but $p\nmid k+1$, then

$$p\mid\binom{p}{k + 1}\;\;\to\;\;\binom{p}{k + 1}\equiv 0\bmod{p}\tag{5}\label{eq5A}$$

With either \eqref{eq4A} or \eqref{eq5A}, the inductive step is completed and, thus, \eqref{eq1A} has been proven to be true.

$\endgroup$
1
  • 1
    $\begingroup$ Great answer, John. I understand now. Thanks for all your help. $\endgroup$ Mar 7, 2023 at 15:44

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .