Prime factorization proof

[fishturtle1]

Homework Statement

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)$

Homework Equations

$\left( \frac p k \right) = \frac {p!} {k!(p-k)!}$

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?

 

[fresh_42]

Homework Statement

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)$

Homework Equations

$\left( \frac p k \right) = \frac {p!} {k!(p-k)!}$

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?

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.

 

[Ray Vickson]

Homework Statement

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)$

Homework Equations

$\left( \frac p k \right) = \frac {p!} {k!(p-k)!}$

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?

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.

 

[fishturtle1]

Thank you both for the help on notation.

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.

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.

 

[fresh_42]

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.

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.

 

[fishturtle1]

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.

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)$

 

[fresh_42]

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.

In formulas it reads:
$$
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

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

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.

 

[fishturtle1]

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.

In formulas it reads:
$$
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.

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.