Prove that if p is prime and 1 <= k < p
that p divides p!/(k!(p-k)!) (this is the binomial coefficient for C(p,k))
k! and (p-k)! only contain prime factors that are smaller than p, so they can't divide p (because p is prime), the binomial coefficient will thus have to contain a factor p in its prime factorization.
Thanks. I was stumped, but in hindsight, that is surprisingly simple
To prove that p divides p!/(k!(p-k)!), we need to show that p is a prime factor of the numerator but not the denominator. In other words, p must appear in the prime factorization of p! but not in the prime factorization of k!(p-k)!. This will ensure that p divides the numerator but not the denominator.
To demonstrate this, let's consider the prime factorization of p!. The prime factorization of p! can be represented as follows:
p! = p * (p-1) * (p-2) * ... * (k+1) * k! * (k-1)! * ... * 2 * 1
Now consider the prime factorization of k!(p-k)!. It can be represented as:
k!(p-k)! = k * (k-1) * ... * 2 * 1 * (p-k) * (p-k-1) * ... * 2 * 1
Comparing these two factorizations, we can observe that p appears as a factor in the numerator (p!) but not in the denominator (k!(p-k)!).
Therefore, p divides p!/(k!(p-k)!), making the binomial coefficient C(p,k) divisible by p when p is a prime number, and 1 ≤ k < p.