29
$\begingroup$

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

$\endgroup$
3
  • 23
    $\begingroup$ Remember that $a$ and $a+1$ are relatively prime: this will do it! $\endgroup$
    – damiano
    Aug 23, 2010 at 13:48
  • $\begingroup$ Thanks! Is that... recommended for an exam? $\endgroup$
    – KaliKelly
    Aug 23, 2010 at 14:05
  • 8
    $\begingroup$ I don't understand Chandru1's comment: he shows that $a(a+1)$ divides $m^2$. We want to show that it divides $m$. $\endgroup$ Aug 23, 2010 at 14:49

5 Answers 5

67
$\begingroup$

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

$\endgroup$
3
  • 3
    $\begingroup$ Do the brackets in $[ar]$ have special meaning? $\endgroup$
    – yiyi
    Dec 9, 2013 at 14:55
  • 3
    $\begingroup$ I would have said \begin{array}{rcr} a(a+1)r &=& (a+1)m\\ a(a+1)s &=& am\\ \hline a(a+1)(r-s) &=& m \end{array} $\endgroup$ Apr 11, 2016 at 18:05
  • $\begingroup$ Proof: Suppose that $a \mid m$ and $a + 1 \mid m$, where $a$ and $m$ are integers. Therefore, there exist integers $r$ and $s$ such that (1) $ar = m$ and (2) $(a + 1)s = m$. Multiplying (1) by $a + 1$, we get $a(a + 1)r = (a + 1)m$ (3). Multiplying (2) by $a$, we get $a(a + 1)s = am$ (4). Now subtracting (3) and (4), we get $$a(a + 1)r - a(a + 1)s = (a + 1)m - am$$ $$\Rightarrow a(a + 1)(r - s) = m$$ And Since $r - s$ is an integer, we have that $$a(a + 1) \mid m$$. $Q.E.D.$ $\endgroup$ Aug 26, 2018 at 13:02
31
$\begingroup$

If $\rm\,\ a\mid m,\ a\!+\!1\mid m\ \,$ then it follows that $\rm\ \, \color{#90f}{a(a\!+\!1)\mid m}$

${\bf Proof}\rm\quad\displaystyle \frac{m}{a},\; \frac{m}{a+1}\in\mathbb{Z} \ \,\Rightarrow\,\ \frac{m}{a} - \frac{m}{a\!+\!1} \; = \;\color{#90f}{\frac{m}{a(a\!+\!1)} \in \mathbb Z}.\quad$ QED

${\bf Remark}\rm\ \, \text{More generally, if }\, \color{#c00}{n = bc \:\!-\:\! ad} \;$ is a linear combination of $\rm\, a, b\, $ then

$\rm\text{we have}\quad\,\ \displaystyle \frac{m}{a},\; \frac{m}{b}\in\mathbb{Z} \;\;\Rightarrow\;\; \frac{m}{a}\frac{\color{#c00}{bc}}{b} - \frac{\color{#c00}{ad}}{a}\frac{m}{b} = \frac{m\:\!\color{#c00}n}{a\:\!b} \in \mathbb Z$

By Bezout, $\rm\, \color{#c00}{n = \gcd(a,b)}\, $ is the least positive linear combination, so the above yields

$\rm\qquad\qquad a,b\mid m \;\Rightarrow\; ab\mid m\;gcd(a,b) \;\Rightarrow\; \mathfrak{m}_{a,b}\!\mid m\ \ $ for $\ \ \rm \mathfrak{m}_{a,b} := \dfrac{ab}{\gcd(a,b)}$

i.e. $ $ every common multiple $\rm\, m\,$ of $\,\rm a,b\,$ is a multiple of $\;\rm \mathfrak{m}_{a,b},\,$ so $\rm\, \color{#0a0}{\mathfrak{m}_{a,b}\le m}.\,$ But $\rm\,\mathfrak{m}_{a,b}\,$ is also a common multiple, i.e. $\rm\ a,b\mid \mathfrak{m}_{a,b}\,$ viz. $\displaystyle \,\rm \frac{\mathfrak{m}_{a,b}}{a} = \;\frac{a}{a}\frac{b}{gcd(a,b)}\in\mathbb Z\,$ $\,\Rightarrow\,$ $\rm\, a\mid \frak{m}_{a,b},\,$ and $\,\rm b\mid \mathfrak{m}_{a,b}\,$ by symmetry. Thus $\,\rm \mathfrak{m}_{a,b} = lcm(a,b)\,$ is the $\rm\color{#0a0}{least}$ common multiple of $\rm\,a,b.\,$ In fact we have proved the stronger statement that it is a common multiple that is divisibility-least, i.e. it divides every common multiple. This is the general definition of LCM in an arbitrary domain (ring without zero-divisors), i.e. we have the following universal dual definitions of LCM and GCD, which essentially says that LCM & GCD are $\,\sup\,$ & $\,\inf\,$ in the poset induced by divisibility order $\,a\preceq b\!\iff\! a\mid b$.

Definition of LCM $\ \ $ If $\quad\rm a,b\mid c\,\iff\; d\mid c \ \ \,$ then $\rm\ d\approx lcm(a,b)$
compare: $\, $ Def of $\rm\,\cap\ \ \,$ If $\rm\ \ \ a,b\supset c\iff d\supset c\,\ $ then $\,\ \rm d = a\cap b$

Definition of GCD $\ \ $ If $\quad\rm c\mid a,b \;\iff\; c\mid d \,\ $ then $\,\ \rm d \approx \gcd(a,b)$
compare: $\, $ Def of $\rm\,\cup\ \ \,$ If $\rm\ \ \ c\supset a,b\iff c\supset d\,\ $ then $\,\ \rm d = a\cup b$

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

Above $\rm\,d\approx e\,$ means $\rm\,d,e\,$ are associate, i.e. $\rm\,d\mid e\mid d\,$ (equivalently $\rm\,d = u\!\: e\,$ for $\,\rm u\,$ a unit = invertible). In general domains gcds are defined only up to associates (unit multiples), but we can often normalize to rid such unit factors, e.g. normalizing the gcd to be $\ge 0$ in $\Bbb Z,\,$ and making it monic for polynomials over a field, e.g. see here and here.

Such universal definitions enable slick unified proofs of both arrow directions, e.g.

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

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

The conciseness of the proof arises by exploiting to the hilt the $\:\!(\!\!\iff\!\!)\:\!$ definition of LCM, GCD. Implicit in the above proof is an innate cofactor duality. Brought to the fore, it clarifies LCM, GCD duality (analogous to DeMorgan's Laws), e.g. see here and here.

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 $\ $ If $\;\rm M\subset\mathbb Z \;$ is closed under subtraction and $\rm M$ contains a nonzero element $\rm\,k,\,$ then $\rm M \:$ has a positive element and the least such positive element of $\;\rm M$ divides every element.

Proof $\, $ Note $\rm\, k-k = 0\in M\,\Rightarrow\, 0-k = -k\in M, \;$ therefore $\rm M$ contains a positive element. Let $\rm\, m\,$ be the least positive element in $\rm\, M.\,$ Since $\,\rm m\mid n \iff m\mid -n, \;$ if some $\rm\, n\in M\,$ is not divisible by $\,\rm m\,$ then we may assume that $\,\rm n > 0,\,$ and the least such. Then $\rm\,M\,$ contains $\rm\, n-m > 0\,$ also not divisible by $\rm m,\,$ and smaller than $\rm n$, contra leastness of $\,\rm n.\ \ $ QED

$\endgroup$
5
  • 1
    $\begingroup$ Do I understand it right that $\mathrm{gcd}:\mathbb{Z}\times\mathbb{Z}\to\mathbb{Z}$ is right adjoint of the diagonal function from $\mathbb{Z}$ to $\mathbb{Z}\times\mathbb{Z}$, if $\mathbb{Z}$ is ordered by the `divisibility' relation? $\endgroup$
    – Egbert
    May 21, 2012 at 20:52
  • $\begingroup$ @Egbert That would make a good question. I recommend that you post it, since it wouldn't get much exposure buried here in the comments. Was your question sparked by my recent answer here and/or its link here? $\endgroup$ May 21, 2012 at 20:56
  • $\begingroup$ I added the question. Yes, I followed the links in these answers. I find the approach with the universal property illuminating for both my understanding of adjoints and elementary number theory. $\endgroup$
    – Egbert
    May 21, 2012 at 21:19
  • $\begingroup$ @BillDubuque Can you suggest an article/reference that discusses this category-theoretic view of number theory in detail? $\endgroup$ Jun 2, 2012 at 2:14
  • 2
    $\begingroup$ Note to future readers: The concise (and very nice) proof of the "$\rm\;\; (a,b) = ab/[a,b] \;\;$" theorem requires the implicit understanding that a relation of the form "$u \mid v$" for integer $u$ and rational $v$ means "$v$ is an integer divisible by $u$" (or, equivalently, "$v$ equals $u$ times some an integer"). This matters because the way it is used here, $v$ is not always (a priori) an integer. $\endgroup$ Feb 19, 2019 at 3:47
19
$\begingroup$

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.

$\endgroup$
7
  • $\begingroup$ Thanks, that was fast. I see the logic now :D Just hope I can replicate this in my exam tomorrow! $\endgroup$
    – KaliKelly
    Aug 23, 2010 at 14:04
  • 1
    $\begingroup$ @Pete: I just realized that you removed the tag "divison-algebra" and that probably that tag should be "division-algebra": is there a way to correct the spelling of the tag? $\endgroup$
    – damiano
    Aug 23, 2010 at 14:06
  • $\begingroup$ @damiano: my understanding is that only a moderator can delete tags. But we can certainly add the tag with the correct spelling and make sure that it is the correct tag which actually appears in questions (when appropriate). $\endgroup$ Aug 23, 2010 at 14:52
  • 1
    $\begingroup$ About the Edit: I think Robin shows this. If, in a ring, $m$ and $m+1$ divide $a$ on the left, so does $m(m+1)$. No use of the absence of zero divisors or of the commutativity seems to be made. $\endgroup$ Aug 23, 2010 at 20:13
  • 1
    $\begingroup$ @PYG: Yes, that's true. I just prefer to think of divisibility in the context of integral domains. $\endgroup$ Aug 23, 2010 at 23:55
11
$\begingroup$

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.

$\endgroup$
9
  • 1
    $\begingroup$ Actually it turns out to be simpler to prove by way of GCDs rather than employing the Bezout identity. Namely A,B|M => AB|AM,BM => AB | (AM,BM) = (A,B) M = M. This is merely a very special case of the general LCM, GCD duality identity. See my post here. Note that this proof works whether one interprets (A,B) as a GCD or as an ideal (as in your Bezout proof). Note that it has the advantage of eliminating obfuscatory info such as the irrelevant variables K,L,X,Y in the Bezout proof. $\endgroup$ Aug 25, 2010 at 0:58
  • $\begingroup$ I don't want to get into this forever, but I'll try to justify myself. Let's separate two notions of GCD. GCD1(a,b) is the largest integer that divides a and b. GCD2(a,b) is divisible by any integer which divides a and b. The fact that GCD1=GCD2 has some depth; it is basically as hard as unique factorization. (continued...) $\endgroup$ Aug 25, 2010 at 11:21
  • $\begingroup$ In fact, even the fact that GCD2 is well defined is not obvious. You are clearly using GCD2 when you write ab|am, bm implies ab|(am,bm). (continued) $\endgroup$ Aug 25, 2010 at 11:23
  • $\begingroup$ Now, the point is, suppose that there exist x and y such that ax+by divides a and divides b. Then ax+by is GCD2(a,b). In this case, we know that GCD2(a,b) exists without ever thinking about the division algorithm or general properties of the larger ring. In particular, the result in question is true in any commutative ring, because we have ax+by=1 for an explicit pair (x,y)=(-1,1). The proof is pure algebraic manipulation, not relying on properties of the integers like GCD2 existing. (continued) $\endgroup$ Aug 25, 2010 at 11:27
  • $\begingroup$ I should also add that Robin Chapman makes the same points I do much more clearly. In retrospect, it was an expository error to write x and y in place of -1 and 1. $\endgroup$ Aug 25, 2010 at 11:27
0
$\begingroup$

If $a|m$ and $a+1|m$ then $lcm(a,a+1)|m$. And we know that $lcm(a,a+1)\cdot gcd(a,a+1) = a(a+1)$ . But $a$ and $(a+1)$ are two consecutive numbers so $gcd(a,a+1)$ $=$ $1$, hence $lcm(a,a+1) = a(a+1)$. So $a(a+1)|m$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy