I recently found this interesting proof technique that uses a combination of deductive reasoning and integer factorization. The prompt goes something like this: If p is prime and k∈Z for which 0<k<p, then p divides (pk).

Initially, there is a temptation to expand (pk)=p!k!(p−k)! to some expression pa, where a∈Z. This is natural given the goal of p|(pk). However, we soon realize that p 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:

  1. Expand the usual (pk)=p!k!(p−k)!
  2. Manipulate it to the more interesting form p!=(pk)k!(p−k)!
  3. Given that p is prime, it must present in the prime factorization of p!
  4. Due to the equality, p must then also be a factor of (pk)k!(p−k)!
  5. Of the three terms, k! and (p−k)! are products of numbers smaller than p and therefore cannot contain the prime number p as their factors.
  6. This leaves us with (pk) as the only possible term with p in its factorization.
  7. Therefore, p divides (pk). ◻

Some notes on the above approach:

  • The critical part of the proof is where it uses deductive reasoning and comparison to isolate (pk) as the only possible multiple of p.
  • The form p!=(pk)k!(p−k)! 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.