Mathematics under the Microscope

Atomic objects, structures and concepts of mathematics
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$.

Like this:

Posted in Uncategorized

Responses

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

By: Charles Wells on April 20, 2008
at 1:34 am

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.

By: Alexandre Borovik on April 20, 2008
at 5:22 am

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.

By: Charles Wells on April 21, 2008
at 1:59 pm

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

By: Elusive boundary of proof « Mathematics under the Microscope on February 24, 2009
at 3:05 pm

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

By: Veky on February 25, 2009
at 11:10 am

Cancel
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 48, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9265526533126831, "perplexity_flag": "middle"}