I have to show that $(a+b)^p=a^p+b^p$ in $\mathbb Z/p\mathbb Z$ for $p$ prime. In other word that $p$ divide $\binom{p}{k}$ for $0<k<p$. I tryied many thing but impossible to conclude algebraically. But can I do like this: $$\binom{p}{k}=\frac{p!}{k!(p-k)!}=\frac{(p-k+1)(p-k+2)... (p-1)p}{k!}\in\mathbb N$$ Since $p$ is prime, not in $1\leq i\leq k$ divide $p$ and thus $\frac{(p-k+1)...(p-1)}{k!}\in\mathbb N$ therefore $$\frac{(p-k+1)(p-k+2)... (p-1)p}{k!}=mp$$ for $m\in\mathbb N$ and thus $p$ divide $\binom{p}{k}$.

Do you think it work ? The problem is i'm not sure that (if $m<n$) $$\frac{a_1\cdot ...\cdot a_n}{b_1\cdot ...\cdot b_m}\in\mathbb N\implies \forall a_i, \exists b_j: b_j\mid a_i.$$

What do you think ?

  • 1
    $\begingroup$ Here is another, Proving prime $p$ divides $p\choose k$ for $k\in\{1,\dots,p−1\}$. $\endgroup$ – user249332 Dec 20 '15 at 20:58
  • $\begingroup$ Ok thank you. By the way, do you have a link of the proof that $\frac{n!}{k!(n-k)!}$ is really an integer ? I also have difficulties to prove it. And more generally that if $n-p> k$ that $\frac{n(n-1)...(n-p)}{k!}$ is also an integer ? $\endgroup$ – MSE Dec 20 '15 at 21:09
  • $\begingroup$ By definition ${n\choose k}$ is an integer, it's the number of subset of $\{1,\ldots,n\}$ of cardinality $k$. From there, if you manage to proove that ${n\choose k}=\frac{n!}{k!(n-k)!}$, you are done. $\endgroup$ – C. Falcon Dec 20 '15 at 21:17

Somehow you have to use that $p$ is prime. Either you use the decomposition into prime factors ( $p$ appears in the numerator but not in the denominator, so it can't disappear) or, more formally:

Let $N = \binom{p}{k} = \frac{p!}{(p-k)! k!}$. Then $(p-k)! k! \cdot N = p!$ clearly divisible by $p$. However, $p \not \mid (p-k)! k! $, since it does not divide any number from $1$ to $p-1$ so neither their product ( here we use the fact that $p$ is prime). Now, if since $p$ does not divide $(p-k)! k!$ then the gcd $(p, (p-k)! k!) = 1$ (again we use that $p$ is prime), so $u p + v(p-k)! k! = 1$. Multiply this by $N$ and get $$ u pN + v(p-k)! k!N = N$$ The first term is clearly divisible by $p$, and so is the second, being $p!$.

Thus $p \mid N$.

Obs: In general, if $p$ divides $b \cdot N$ and $(p,b)=1$ then $p$ divides $N$. Or : if $N=\frac{a}{b}$ integer, $p$ divides $a$ and $(p,b) = 1$ then $p$ divides $N$.


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