Euclid's lemma tells you that this is true for .

Now suppose it true for some , then we have for any prime numbers:

Then by Euclids lemma if then either or . But we already have by assumption that if then divides one of Hence the result if true for is true for , and with the base case we have a proof by induction for all integers

RonL