Intereting Posts

obtain a three-term asymptotic solution
A sufficient condition for a function to be of class $C^2$ in the weak sense.
Inductive Proof for Vandermonde's Identity?
How to prove $\frac{1}{x}=\frac{1}{a}+\frac{1}{b}+\frac{1}{c}+2\sqrt{\frac{1}{ab}+\frac{1}{ac}+\frac{1}{bc}}$
Definition of $K$-conjugacy classes
How to construct isogenies between elliptic curves over finite fields for some simple cases?
Demostration of ∀x ∈ ∅ p(x) is always true
Representation of the dual of $C_b(X)$?
Integrating $\int \frac{\sqrt{\cos 2x}}{\sin x} dx$
Does the abstract Jordan decomposition agree with the usual Jordan decomposition in a semisimple Lie subalgebra of endomorphisms?
Interpretation of limsup-liminf of sets
Gaussian Integral using contour integration with a parallelogram contour
$\int_0^{\infty } \frac{\log (x)}{e^x+1} \, dx = -\frac{1}{2} \log ^2(2)$ How to show?
Number of 5 letter words with at least two consecutive letters same
Intuition Building: Visualizing Complex Roots

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

- Representability as a Sum of Three Positive Squares or Non-negative Triangular Numbers
- In how many ways can a number be expressed as a sum of consecutive numbers?
- Do these inequalities regarding the gamma function and factorials work?
- Transcendental number
- Curves triangular numbers.
- Divisibility of sum of powers: $\ 323\mid 20^n+16^n-3^n-1\ $ for which $n?$

- Claim: $a$ has $90 \% $ primes less than $n$ If $n!= 2^s \times a \times b $ and $\lfloor{\frac{a}{b}}\rfloor = 2^{s-2}$
- Quartic polynomial taking infinitely many square rational values?
- How to show that $1,\alpha,\alpha^2/2$ is an integral basis of $R=\mathcal{O}\cap \mathbb{Q}$
- Ramanujan theta function and its continued fraction
- Proving $\mathbb{Z}$, $\mathbb{Z}$, $\mathbb{Z}$, and $\mathbb{Z}$ are euclidean.
- Can an odd perfect number be divisible by $165$?
- Intuition in studying splitting and ramification of prime ideals
- Problem : Permutation and Combination : In how many ways can we divide 12 students in groups of fours.
- Irrationality of Two Series
- Asymptotic divisor function / primorials

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.

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

${\bf 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**

${\bf Remark}\rm\ \, \text{More generally, if }\, 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{bc}{b} – \frac{ad}{a}\frac{m}{b} = \frac{mn}{ab} \in \mathbb Z$

By Bezout, $\rm\, 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}. \;$ But $\rm\,\mathfrak{m}_{a,b}\,$ is also a *common* multiple: $\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}.\,$ $\rm\, b\mid \mathfrak{m}_{a,b}\,$ by symmetry. Thus $\,\rm \mathfrak{m}_{a,b} = lcm(a,b)\,$ since it’s a common multiple of $\,\rm a,b\,$ that’s divisibility-least, i.e. 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:

**Definition** of **LCM** $\ \ $ If $\quad\rm a,b\mid c \;\iff\; [a,b]\mid c \quad$ then $\,\quad\rm [a,b] \;$ is an **LCM** of $\;\rm a,b$

**Definition** of **GCD** $\ \ $ If $\quad\rm c\mid a,b \;\iff\; c\mid (a,b) \quad$ then $\quad\rm (a,b) \;$ is an **GCD** of $\;\rm a,b$

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

Such $\iff$ 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**

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.

- What converges this series?
- Class number computation (cyclotomic field)
- How to write down formally number of occurences?
- How to prove that $\lVert \Delta u \rVert_{L^2} + \lVert u \rVert_{L^2}$ and $\lVert u \rVert_{H^2}$ are equivalent norms?
- Injective and Surjective Functions
- A proof for the inequality $\sum_{i=0}^{t-2}{\frac{1}{t+3i}} \leq \frac{1}{2} $ for all $t \geq 2$
- Conditions for Schur decomposition and its generalization
- Countable or uncountable set 8 signs
- Given dividend and divisor, can we know the length of nonrepeating part and repeating part?
- Limit of matrix powers.
- Intuitive explanation of Nakayama's Lemma
- If M is a non-orientable closed connected 3 manifold prove H1(M) is an infinite group.
- Basis for adjoint representation of $sl(2,F)$
- Clarify definitions of relation and 0-ary relation
- Can we construct Sturm Liouville problems from an orthogonal basis of functions?