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
.
How do you know this fact: (*) if ab is even then one of a and b are even.
Of course this follows from unique factorization but the proofs I know of unique factorization require the divisibility lemma. Can you give an independent proof of (*)?
By: Charles Wells on April 20, 2008
at 1:34 am
(*) if
is even then one of
and
are even.
Sketch of a proof: if
is odd and
is odd then
and
. Then
is also odd.
By: Alexandre Borovik on April 20, 2008
at 5:22 am
How do you know that ab might not be both odd and even, without deriving that fact from unique factorization? Well, one answer is that if m and n are integers for which 2m+1 = 2n, then 2(m-n) = 1, a case of the “contradictory inequality vp = 1” that you mentioned. By the way, the impossibility of vp = 1 unless v = p = 1 (for positive integers) follows easily from the Peano axioms and the recursive definition of multiplication.
By: Charles Wells on April 21, 2008
at 1:59 pm
[…] and beautitiful proof of a self-evident statement, like a proof of lemma in my old post Induction over prime numbers? Possibly related posts: (automatically generated)What is deep mathematics?Arwen’s FREE […]
By: Elusive boundary of proof « Mathematics under the Microscope on February 24, 2009
at 3:05 pm
@Charles: You know it from induction “step”. Contrary to popular opinion, induction with total history (if all primes less than p are genuine, then p is genuine) _doesn’t_ need a basis, since it is just a special case of a step: all primes less than 2 _are_ surely genuine (since there are none), so 2 is genuine by induction step.
Only inductions with bounded history (eg, if P(k-1) and P(k), then P(k+1)) need a basis, since you can’t conclude P(0) by the step if P(-1) doesn’t hold or even make sense in the context.
@Alexandre: So the real proof is even shorter, in fact, and the whole even/odd distinction is a special case of what’s going on in the step. Really, in the step we invoke theorem about division with remainder, which obviously answers second Charles’s question as well (when p is 2, remainder can be 0 or 1, and can’t be both).
By: Veky on February 25, 2009
at 11:10 am