In a intro-to-math course I was teaching some years ago the question came up if one could do mathematical induction over the set of prime numbers. This is probably a proof strategy we should advise students against since the sequence of primes is notoriously unpredictable. But, already knowing about this unpredictability, I was particularly pleased when I found I could create an example, a new(?) proof of a very old theorem, where it works.
I will post my example as an answer below, but thinking about this proof again (for a different reason) I wondered:
Do you know (or can you come up with) other examples of proofs that use mathematical induction over the set of primes?
Please post your proofs below!
Theorem ('Euclid's Lemma') Let $p$ be a prime number and $a, b \in \mathbb{N}$ such that $p\mid ab$. Then $p \mid a$ or $p \mid b$.
Proof: We proceed by induction on $p$. The basis of the induction is the case $p = 2$. Here the statement boils down (if we define 'even' as divisible by 2 and 'odd' as not even) to the fact that the product of two odd numbers is again odd. While non-trivial, I am confident that all readers have convinced themselves of this fact at a much earlier point in their lives and I won't dwell on it here.
Now for the induction step, assume that the claim has been proven for all primes $q < p$. We will proceed by Fermat descent. That is: we start from an hypothetical counterexample: a pair $(a, b)$ such that $p|ab$ but $p\not|a$ and $p\not|b$ and construct from it a pair $(a', b')$ with the same properties, but such that either $a' < a$ or $b' < b$. Since we then can repeat this procedure for as long as we want, we will eventually hit a pair $(a, b)$ in which one of the members equals zero; this is a contradiction since zero is clearly divisible by $p$. It follows that the original pair $(a, b)$ was not a counterexample to begin with.
To get started, we first notice that the conditions on $a$ and $b$ (that is: $ab \cong 0 \mod p$, $a,b \neq 0 \mod p$) only depend on their congruence class modulo $p$ and hence we may assume without loss of generality that $0 < a, b < p$. It follows that $ab < p^2$ and hence $c := ab/p < p$.
Let $q$ be a prime divisor of $c$. Then $q < p$ as well. ($c$ does indeed have a prime divisor, since if $c = 1$ we would have $ab = p$, which by primality of $p$ means that $a = p$ or $b = p$, a contradiction). Now $q$ divides $ab$ and since $q < p$ the induction hypothesis states that $q|a$ or $q|b$. Let's assume without loss of generality that $q|a$ and that $a = qa'$. Writing $c = qc'$ we find that $qa'b = qc'p$ and hence that $a'b = c'p$. In other words we have that $p \mid (a'b)$, that $p \nmid b$ and moreover that $p \nmid a'$ since $a' \mid a$.
It follows that $(a', b)$ is a pair with the same properties as $(a, b)$ but with $a' < a$. Repeating this procedure we eventually run into a contradiction.