I recently found this interesting proof technique that uses a combination of deductive reasoning and integer factorization. The prompt goes something like this: If is prime and for which , then divides .
Initially, there is a temptation to expand to some expression , where . This is natural given the goal of . However, we soon realize that being prime is not significant in this approach. This should be enough to ward us off and look elsewhere.
At this point I gave up, only to find a nifty proof in the solutions:
- Expand the usual
- Manipulate it to the more interesting form
- Given that is prime, it must present in the prime factorization of
- Due to the equality, must then also be a factor of
- Of the three terms, and are products of numbers smaller than and therefore cannot contain the prime number as their factors.
- This leaves us with as the only possible term with in its factorization.
- Therefore, divides .
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 .
- 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.
- 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.