Let 1 <= k <= p−1, where p is prime. Show that p choose k is a multiple of p. What if p is not prime?
I think here when we expand p choose k and then input few prime numbers then we always get a multiple of p .
And same with when p is not prime.
To show that p choose k (written as "pCk") is a multiple of p when 1 <= k <= p−1, we can use the definition of pCk:
pCk = p! / (k!(p-k)!)
To determine if pCk is a multiple of p, we need to show that p is a factor of the numerator, p!. We can do this by examining the prime factorization of p!.
Prime factorization of p!:
p! = 1 * 2 * 3 * ... * (p-1) * p
Since p is prime, all the numbers from 1 to (p-1) do not have p as a factor. Thus, p only appears once in the prime factorization of p!.
Since p is a factor of p!, it means that pCk is a multiple of p. This holds for any 1 <= k <= p−1.
Now, let's consider the case when p is not prime. In this case, the prime factorization of p! will have multiples of p appearing more than once. If k is such that k is not a multiple of p, then the p's occurring multiple times in the prime factorization of p! will still cancel out in both the numerator and denominator of pCk. Therefore, pCk will still be a multiple of p.
However, if k is a multiple of p (i.e., p divides k), then the p's occurring multiple times in the prime factorization of p! will not fully cancel out in the denominator (k!(p-k)!) and will leave a remaining p as a factor. Thus, pCk will not be a multiple of p.
In summary:
- When p is prime and 1 <= k <= p−1, pCk is always a multiple of p.
- When p is not prime and 1 <= k <= p−1:
- If k is not a multiple of p, pCk is still a multiple of p.
- If k is a multiple of p, pCk is not a multiple of p.