If a divides b and a divides c, then a divides (b-c)

\(\)In reading about Euclid’s proof of the infinitude of prime numbers, the only part that wasn’t completely clear to me was this:

If \(p\) divides \(P\) and \(q\), then \(p\) would have to divide the difference of the two numbers, which is \( (P + 1) − P\) or just \(1\).

Well, I don’t know…why is that true? Why does a number have to divide the difference of two numbers if it divides each of those numbers separately?

It turns out that my textbook from my introduction to proofs class, Mathematical Proofs by Chartrand, Polimeni, and Zhang (a class that was taught by Dr. Zhang herself at Western Michigan University), contains the proof of a more general statement. (Note: For this theorem, the vertical bar \( \vert \), which looks identical to the absolute value symbol, is used to mean “divides”; that is, \( a ~\vert~ b \) i.f.f. \(a\) is a factor of \(b\), that is, \(a\) “guzzinta” \(b\) an integer number of times, that is, \( b \div a \) equals an integer.)

Theorem: If \( a~\vert~b \) and \( a ~\vert~c \), then \( a ~\vert~ (bx + cy) \) for all integers \(x\) and \(y\).

Proof: Let \( a ~\vert~ b \) and \( a ~\vert~ c \). Then there exist integers \(q_{\scriptscriptstyle 1}\) and \(q_{\scriptscriptstyle 2}\) such that \(b=aq_{\scriptscriptstyle 1}\) and \(c=aq_{\scriptscriptstyle 2}\). Hence, for integers \(x\) and \(y\),

bx + cy = aq_{\scriptscriptstyle 1}x + aq_{\scriptscriptstyle 2}y = a(q_{\scriptscriptstyle 1}x + q_{\scriptscriptstyle 2}y).

Since \( q_{\scriptscriptstyle 1} x + q_{\scriptscriptstyle 2} y \) is an integer, \( a ~\vert~ (bx + cy) \). $$\tag*{$\blacksquare$}$$

The specific case where \( x=1 \) and \(y=-1\) is used in Euclid’s proof of the infinitude of primes.

Aside from this abstract proof, it’s easy to see why the theorem would be true with a simple example. Consider \( a = 5 \) and \(b \) and \(c\) any multiples of \(5\), say \(25\) and \(100\). Since these are both multiples of \(5\), they are some multiple of \(5\) apart from each other, so their difference is also obviously a multiple of \(5\). It’s just counting by fives, or by whatever the factor is in the example you choose. It’s hard to think of a theorem that could be more obvious and intuitive, even to an elementary-schooler.

As a side note, Mathematical Proofs is an extremely good introduction to mathematical proofs. It is one of my favorite textbooks. It is detailed, thorough, and extremely long, with great explanations that they call “proof strategy” before many proofs and summaries that they call “proof analysis” after many proofs. It has chapters on sets, logic, direct proofs, proof by contradiction, mathematical induction, equivalence relations, functions, cardinalities of sets, number theory, calculus, linear algebra, topology, group theory, and ring theory. I love this book and I highly recommend it for anyone who might want to learn or review how to do a lot of basic and important proofs from many fields of mathematics.

This entry was posted in Math, Theorems. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *