This was a question which intrigued me when I was a student: is there a meaningful mathematical statement about finite fields which is proven by induction on the characteristic of a field?
Finally and many years later I got a partial answer: a meaningful statement about prime numbers proven by induction on the size of prime number in question.
This is a note A Lemma on Divisibility by Peter Walker in a recent issue of The American Mathematical Monthly 115 no. 4 (2008 ) p. 338:
(*) For all primes , implies or .
His proof uses division with remainder but not Euclidean algorithm for finding the greatest common divisor of two integers.
We say that a prime is genuine if it satisfies (*) for all integers and . We shall prove by induction on that all primes are genuine.
Basis of induction. is a genuine prime number. Indeed if a product of two integers is even then at least one of the multiplicands is even.
Inductive step. Let be the least non-genuine prime number so that but does not divide and does not divide .
Using division with remainder, we can write and where . Of course, . If either or then divides or as required. If not, then both and are at least and can be factorised into primes: and (existence of factorisation can be proved earlier). Now and for some integer we have wher all , are less than and are therefore genuine prime numbers. Since none of , can divide , they divide and can be cancelled out one by one from the equation, leaving an obviously contradictory equality .