number theory - If $a mid m$ and $(a + 1) mid m$, prove $a(a + 1) | m$.

Can anyone help me out here? Can't seem to find the right rules of divisibility to show this:

If $a \mid m$ and $(a + 1) \mid m$, then $a(a + 1) \mid m$.

Answer

It is not surprising that you are finding this difficult, because it goes beyond basic divisibility rules -- it rather requires something which is essentially equivalent to the uniqueness of prime factorization. [Edit: Actually this is comment is incorrect -- as Robin Chapman's answer shows, it is possible to prove this using just divisibility rules. In particular it is true in any integral domain.]

I assume $a$ and $m$ are positive integers. The first observation is that $a$ and $a+1$ are relatively prime: i.e., there is no integer $d > 1$ -- or equivalently, no prime number-- which divides both $a$ and $a+1$, for then $d$ would have to divide $(a+1) - a = 1$, so $d = 1$.

Now the key step: since $a$ divides $m$, we may write $m = aM$ for some positive integer $M$. So $a+1$ divides $aM$ and is relatively prime to $a$. I claim that this implies $a+1$ divides $M$. Assuming this, we have $M = (a+1)N$, say, so altogether

$m = aM = a(a+1)N$, so $a(a+1)$ divides $m$.

The claim is a special case of:

(Generalized) Euclid's Lemma: Let $a,b,c$ be positive integers. Suppose $a$ divides $bc$ and $a$ is relatively prime to $b$. Then $a$ divides $c$.

A formal proof of this requires some work! See for instance

http://en.wikipedia.org/wiki/Euclid's_lemma

In particular, proving this is essentialy as hard as proving the fundamental theorem of arithmetic.