# Prime factorization proof

1. Jul 19, 2017

### fishturtle1

1. The problem statement, all variables and given/known data
The book wants me to use direct proof.

if p is a prime and k is an integer for which 0 < k < p, then p divides $\left( \frac p k \right)$
2. Relevant equations
$\left( \frac p k \right) = \frac {p!} {k!(p-k)!}$

3. The attempt at a solution
the fraction line in $\left( \frac p k \right)$ isn't supposed to be there, but i didn't know how to remove it..its supposed to be p choose k.
proof. Suppose p is prime and k $\epsilon$ Z such that 0 < k < p.

$p! = \left( \frac p k \right)k!(p-k)!$
$p!$ has a factor of p.
$k!$ has no factor of p because p > k.
$(p-k)!$ has no factor of p because p > (p-k).

So $\left( \frac p k \right)k!(p-k)! = p\frac {(p-1)!} {k!(p-k)!} k!(p-k)!$
and $p$ must be a factor of $\left( \frac p k \right)$ since $p$ is not a factor of $k!$ nor $(p-k)!$ but how do you show that $\frac {(p-1)!} {k!(p-k)!}$ is an integer?

2. Jul 19, 2017

### Staff: Mentor

The code for the binomial coefficient is \binom{p}{k}.
Do you know that $\binom{p}{k} =: m \in \mathbb{Z}\,$, i.e. may you use it as a given?
If so, you could write $\binom{p}{k} = \frac{p \, \cdot \ldots \cdot \, (p-k+1)}{1\, \cdot \ldots \cdot \, k}=m$ and deal with this fraction together with the definition of a prime.

3. Jul 19, 2017

### Ray Vickson

You can use either "{p \choose k}" or "\binom{p}{k}" (as Fresh_42 suggested).

Alternatively, you can use the older notation "{}^pC_k" (giving ${}^pC_k$) or "C^p_k" (giving $C^p_k$). Sometimes I just use "C(p,k)" in a forum like this when being fancy does not matter very much; however, I would always state what the notation means in every case.

4. Jul 19, 2017

### fishturtle1

Thank you both for the help on notation.
Yes we can use that definition, I didn't think about that though.

Proof.
Suppose p is a prime number and k is an integer such that p > k > 0.
$\binom{p}{k} \epsilon Z$.
therefore $\binom{p}{k}$ must have a prime factorization.

$\binom{p}{k} = \frac {p!}{k!(p-k)!} = p\frac {(p-1)!}{k!(p-k)!}$
p is prime, therefore $\frac {(p-1)!}{k!(p-k)!}$ must also be prime so it is also an integer.

So p | $\binom{p}{k}$ is true.

I think this is what you were suggesting.

5. Jul 19, 2017

### Staff: Mentor

Not really, because it looks as if you would have the same problem as before. I meant to multiply the entire equation with the denominator to get rid of fractions.
What is a prime? (I hope they defined it properly to you.)

However, your approach should work as well, but then you have to use the unique prime factorization of integers, which is a theorem and should be mentioned. I only use the definition of a prime number. You could do both.

6. Jul 19, 2017

### fishturtle1

Here's what they say a prime number is: A natural number $n$ is a prime if it has exactly two positive divisors, 1 and n.

Proof.
Suppose p is a prime number and k is an integer such that p > k > 0.
$\binom{p}{k} \epsilon Z$.

$\binom{p}{k} = \frac {p\cdot ... \cdot(p-k+1)}{1\cdot....\cdot k} = m$

$p\cdot ... \cdot(p-k+1) = m\cdot k!$

$p = \frac {m\cdot k!} {(p-1)\cdot ... \cdot (p-k+1)}$

p is prime and m is an integer, so by definition of a prime number either $m = 1$ and $\frac {k!} {(p-1)\cdot ... \cdot(p-k+1)} = p$ or $m = p$ and $\frac {k!} {(p-1)\cdot ... \cdot(p-k+1)} = 1$.

therefore $\frac {k!} {(p-1)\cdot ... \cdot(p-k+1)}$ must be an integer.

And since $\binom{p}{k} = p\cdot \frac {k!} {(p-1)\cdot ... \cdot(p-k+1)}$ then we can conclude that p divides $\binom{p}{k}$

Would this be a valid proof using the definition of a prime number? I know you said get rid of fractions but I'm not sure what else I could do after the third line except divide by $(p-1)\cdot ... \cdot (p-k+1)$

7. Jul 19, 2017

### Staff: Mentor

But neither is $m=1$ nor $m=p$. I haven't checked whether your claimed integers are really ones (I think you've swapped nominators and denominators). The "get rid of quotients" as an advice makes sense, because all statements of the problem involves integers: "prime", "divides", $0<k<p\, , \,\binom{p}{k}$. Everything in it only makes sense for integers. Therefore $p \cdot a = m \cdot k!$ makes more sense as $\frac{p \cdot a}{k!} = m$ or other quotients do. And here you can use what you know: $p\,\vert \,p \cdot a\,$.

I had a feeling that this would be the definition of a prime number you used. It is wrong. I mean it is accidentally true, but it's not how primes are defined. The real definition goes: $p$ is a prime number, if it has no multiplicative inverse (which in the case of integers is equivalent to say it's neither $+1$ nor $-1$) and - and this is the crucial part - if it divides a product, then it has to divide one of the factors.

$$p \in \mathbb{Z} \text{ is prime } \Longleftrightarrow p \neq \pm 1 \text{ and } (\;p\,\vert \, a\cdot b \Longrightarrow p\,\vert \,a \text{ or } p\,\vert \,b\;)$$
With this (correct) definition the result simply drops out of
But as I said before, you can also use the fundamental theorem of arithmetic and apply it to $m\cdot k!$, which says that integers have a unique factorization into primes. The "unique" part gives another solution.

Last edited: Jul 19, 2017
8. Jul 19, 2017

### fishturtle1

Thanks for the response,

I think I got the proof using this new definition of a prime number. Sorry if it took a while, I was hung up on the definition for a bit.

Proof.
Suppose $p$ is prime and $k$ is an integer such that $p$ > $k$ > 0. $\binom{p}{k} \epsilon Z$.

$\binom{p}{k} = \frac {p((p-1)\cdot...\cdot(p-k+1)} {k!} = m$

$p((p-1)\cdot...\cdot(p-k+1) = m \cdot k!$

p | $p((p-1)\cdot...\cdot(p-k+1)$ therefore p | $m \cdot k!$

p | $m \cdot k!$ so p | m or p | k! but p does not divide k! because p is prime and p > k.

Therefore p | m <-> p | $\binom{p}{k}$ must be true.