Posted by: Alexandre Borovik | April 18, 2008

Induction over prime numbers

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 p, p \mid ab implies p \mid a or p \mid b.

His proof uses division with remainder but not Euclidean algorithm for finding the greatest common divisor of two integers.

We say that a prime p is genuine if it satisfies (*) for all integers a and b. We shall prove by induction on p that all primes p are genuine.

Basis of induction. 2 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 p be the least non-genuine prime number so that p \mid ab but p does not divide a and does not divide b.

Using division with remainder, we can write a = mp+c and b = np+d where 0 \le c, d < p. Of course, p \mid cd. If either c=0 or d=0 then p divides a or b as required. If not, then both c and d are at least 1 and can be factorised into primes: c = p_1\cdots p_k and d = q_1\cdots q_l (existence of factorisation can be proved earlier). Now p \mid cd and for some integer u we have up = p_1\cdots p_kq_1\cdots q_l wher all p_i, q_j are less than p and are therefore genuine prime numbers. Since none of p_i, q_j can divide p, they divide u and can be cancelled out one by one from the equation, leaving an obviously contradictory equality vp =1.


  1. 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 (*)?

  2. (*) if ab is even then one of a and b are even.

    Sketch of a proof: if a is odd and b is odd then a = 2k+1 and b = 2l+1. Then

    ab = 2(2kl +k+l)+1

    is also odd.

  3. 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.

  4. […] 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 […]

  5. @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).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s


%d bloggers like this: