If $a | m$ and $(a + 1) | m$, prove $a(a + 1) | m$.

Question

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

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

Answer 1

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.

Answer 2

The other answers put this in a general context, but in this example one can be absolutely explicit. If $a\mid m$ and $(a+1)\mid m$ then there are integers $r$ and $s$ such that $$m=ar=(a+1)s.$$ Then $$a(a+1)(r-s)=(a+1)[ar]-a[(a+1)s]=(a+1)m-am=m.$$ As $r-s$ is an integer, then $a(a+1)\mid m$.

Answer 3

PROOF $\;\rm\quad\displaystyle \frac{m}{a},\; \frac{m}{a+1}\in\mathbb{Z} \;\;\Rightarrow\;\; \frac{m}{a} - \frac{m}{a+1} \; = \;\frac{m}{a(a+1)} \in \mathbb Z\quad\;\;$ QED

NOTE $\ $ More generally, for $\:\rm n = bc \:-\; ad \;$ a linear combination of $\rm a, b$

we have $\rm\quad\quad\quad\displaystyle \frac{m}{a},\; \frac{m}{b}\in\mathbb{Z} \;\;\Rightarrow\;\; \frac{m}{a}\frac{bc}{b} - \frac{ad}{a}\frac{m}{b} = \frac{mn}{ab} \in \mathbb Z$

By Bezout's identity, $\rm\ n = gcd(a,b)\ $ is the least positive linear combination, so the above yields

$\rm\quad\quad\quad\quad\quad\quad\quad\quad\ a,b|m \;\Rightarrow\; ab\:|\:m\;gcd(a,b) \;\Rightarrow\; \mathfrak{m}_{a,b} |\:m\;\;\;$ for $\;\;\rm \mathfrak{m}_{a,b} := \frac{ab}{gcd(a,b)}$

i.e. $\:$ every common multiple $\rm m$ of $\rm a,b$ is a multiple of $\;\rm \mathfrak{m}_{a,b}. \;$ But $\rm\:\mathfrak{m}_{a,b}\:$ is also a common multiple, i.e. $\rm\ a,b|\mathfrak{m}_{a,b} \;$ viz. $\rm \frac{\mathfrak{m}_{a,b}}{a} = \;\frac{a}{a}\frac{b}{gcd(a,b)}\in\mathbb Z \;\Rightarrow\; a|\mathfrak{m}_{a,b} \;$. By symmetry, also $\rm\ b|\mathfrak{m}_{a,b} \;.\ $ Therefore $\rm \mathfrak{m}_{a,b} = lcm(a,b)$ since it's a common multiple of $\rm a,b$ that's divisibility-least, i.e. that divides every common multiple. This is the general definition of LCM in an arbitrary domain (ring without zero-divisors), namely we make the following universal dual definitions of LCM and GCD:

DEFINITION of LCM $\quad$ If $\quad\rm a,b|c \;\iff\; [a,b]\:|\:c \quad\;$ then $\quad\rm [a,b] \;$ is an LCM of $\;\rm a,b$

DEFINITION of GCD $\quad$ If $\quad\rm c|a,b \;\iff\; c\:|\:(a,b) \quad$ then $\quad\rm (a,b) \;$ is an GCD of $\;\;\rm a,b$

Note: that $\;\rm a,b\:|\:[a,b] \;$ follows by putting $\;\rm c = [a,b] \;$ in the definition. Dually $\;\rm (a,b)|\:a,b \;$

Such $\iff$ definitions provide slick unified proofs of both arrow directions, e.g. the fundamental

THEOREM $\rm\;\; (a,b) = ab/[a,b] \;\;$ if $\;\rm\ [a,b] \;$ exists.

Proof: $\rm\quad\quad d|\:a,b \;\iff\; a,b\:|\:ab/d \;\iff\; [a,b]\:|\:ab/d \;\iff\; d\:|\:ab/[a,b] \quad\;\;$ QED

The conciseness of this proof arises by exploiting to the hilt the $\iff$ definition of LCM and GCD. Compare this slick proof to many obfuscated proofs found in elementary number theory textbooks!

By the theorem, GCDs exist if LCMs exist. But common multiples clearly comprise an ideal, being closed under subtraction and multiplication by any ring element. Hence in a PID the generator of an ideal of common multiples is clearly an LCM. In Euclidean domains this can be proved directly by a simple descent, e.g. in $\:\mathbb Z \;$ we have the following high-school level proof of the existence of LCMs (and, hence, of GCDs), after noting the set $\rm M$ of common multiples of $\rm a,b$ is closed under subtraction and contains $\:\rm ab \ne 0\:$:

LEMMA $\ $ Suppose $\;\rm M\subset\mathbb Z \;$ is closed under subtraction and that $\rm M$ contains a nonzero element.
Then $\rm M \:$ has a positive element and the least such positive element of $\;\rm M$ divides every element.

Proof $\rm\ \ 0 \ne m\in M \Rightarrow m-m = 0\in M\Rightarrow 0-m = -m\in M, \;$ so $\rm M$ has a positive element.
Let $\rm m$ be the least positive element in $\rm M$. Since $\rm m|n \iff m\;|-n, \;$ if some $\rm n\in M$ isn't divisible by $\rm m$ then we may assume this $\rm n$ is positive, and the least such element. But $\rm\: n-m \:$ is a positive element of $\rm M$ not divisible by $\rm m$ and smaller than $\rm n$, contra leastness of $\rm n\:$. Hence $\rm m$ divides every element of $\rm M.\;\;$ QED

Answer 4

An alternate route: We show that, if $ax+by=1$ and $m$ is divisible by $a$ and $b$ then $m$ is divisible by $ab$. (Then apply this with $b=a+1$, $x=-1$ and $y=1$.)

Proof: Let $m=ak=bl$. Then $ab(xl+ky)=(ax+by)m=m$. QED

The point here is that the hypothesis $\exists_{x,y}: ax+by=1$ is often easier to use than $GCD(a,b)=1$. The equivalence between these two is basically equivalent to unique factorization, and you can often dodge unique factorization by figuring out which of these two you really need.