# Deducing prime factors through elimination

I recently found this interesting proof technique that uses a combination of deductive reasoning and integer factorization.
The prompt goes something like this: If

Initially, there is a temptation to expand

At this point I gave up, only to find a nifty proof in the solutions:

- Expand the usual
$(\genfrac{}{}{0ex}{}{p}{k})=\frac{p!}{k!(p-k)!}$ - Manipulate it to the more interesting form
$p!=(\genfrac{}{}{0ex}{}{p}{k})k!(p-k)!$ - Given that
is prime, it must present in the prime factorization of$p$ $p!$ - Due to the equality,
must then also be a factor of$p$ $(\genfrac{}{}{0ex}{}{p}{k})k!(p-k)!$ - Of the three terms,
and$k!$ are products of numbers smaller than$(p-k)!$ and therefore cannot contain the prime number$p$ as their factors.$p$ - This leaves us with
as the only possible term with$(\genfrac{}{}{0ex}{}{p}{k})$ in its factorization.$p$ - Therefore,
divides$p$ .$(\genfrac{}{}{0ex}{}{p}{k})$ $\u25fb$

Some notes on the above approach:

- The critical part of the proof is where it uses deductive reasoning and comparison to isolate
as the only possible multiple of$(\genfrac{}{}{0ex}{}{p}{k})$ .$p$ - The form
is also interesting because it does not feature any nasty integer division. This sidesteps the problem of having to prove that any intermediate fractions are integers and also makes way for prime factorization.$p!=(\genfrac{}{}{0ex}{}{p}{k})k!(p-k)!$ - It is a nice example of how prime factorization should be the first thing that comes to mind when discussing prime numbers.

The above problem is sourced from the fourth chapter of the excellent Book of Proof by Richard Hammack.