Show that in the sequence $b,2b,3b…,mb$ there are exactly $\gcd(b,m)$ numbers divisible by $m$.

"Where $b$ and $m$ are integers and $m>1$, show that in the sequence $b,2b,3b...,mb$ there are exactly $\gcd(b,m)$ numbers divisible by $m$.

I'm having a real hard time proving that... can anyone help me?

• $m$ needn't be bigger than one: when $m = 1$, in the sequence $b, 2b, 3b, \dots mb$, there is exactly 1 integer, and it is divisible by 1 :) – Ben Millwood Oct 22 '14 at 22:22

The given sequence is the first $m$ multiples of $b$. Scanning from left to right, when will we find the the first multiple of $b$ that is also a multiple of $m$? By definition, this will occur at $\ell = \text{lcm}(b, m)$. Letting $\ell = kb$, notice that $\ell$ is the only multiple of $m$ in the first $k$ multiples of $b$.

Now observe that the next common multiple of $b$ and $m$ will be $2\ell = 2kb$, which shows up after listing out $k$ more multiples of $b$ after $\ell$. Now since $\ell$ divides $mb$, we can continue in this manner so that the list of all common multiples of $b$ and $m$ is: $$\ell, 2\ell, \ldots, g\ell$$ where $g\ell = mb$. [Remark: At this step, we are using the fact that the least common multiple of $m$ and $b$ must divide any common multiple of $m$ and $b$.] But then since: $$\gcd(b, m) \cdot \text{lcm}(b, m) = mb$$ we have that $g = \gcd(b, m)$, as desired.

• oh, interesting, thank you! i'm curious, though, the book i'm using places this question before the question that asks you to prove that gcd(a,b) * lcm(a,b) = |a*b|. i wonder what's the other way to do it... – violeta Oct 22 '14 at 23:02
• also, b can be negative... hmm.. – violeta Oct 22 '14 at 23:31

So the sequence is the following:

$$b,2b,3b,..,mb$$

Let $g= \gcd(b,m)$ , so $ng=m$ and $gd=b$

Lets consider the following members of the sequence:

$$I= \{x \in \mathbb{N} : x=bjn =\frac{bjm}{g}\ \text{ such that } j \in \mathbb{N} \land 0<j\leq g \}$$

So all the members $I$ are divisible by $m$. The number of members is equal to $g$. Now I want to prove that this are the only members of the sequence that are divisible by $m$.

Now all the members that are not in $I$ are of the form:

$$S=\{t \in \mathbb{N} : t=b(jn+c) =\frac{bjm}{g}+bc \ \text{ such that } j \in \mathbb{N} \land 0<j< g \land 0<c<n \}$$

$$m|t \text{ such that } t\in S$$ $$m|b(jn+c)$$

by definition:

$$mk=jbn+bc \tag{1}$$ $$mk=jb\frac{m}{g} + bc$$ $$m(k-\frac{jb}{g})=bc$$ $$k-jd=\frac{bc}{m} \tag{2}$$ $$k=\frac{dc}{n}+jd$$ $$kn=njd+dc$$ $$kn=d(jn+c)$$

Now $d|k$ by the Euclid Lemma, since $(n,d)=1$ . This will be useful in a moment:

Now as $c<n$ we can obtain: $$\frac{c}{m}<\frac{1}{g} \Rightarrow \frac{bc}{m}<d$$

From $(2)$we can obtain:

$$k-jd<d$$ $$k<d+dj$$ $$k<d(1+j) \tag{3}$$

As $d|k$ then $d\hat{k}=k$ , replacing in $(3)$

$$d\hat{k}<d(1+j) \Rightarrow \hat{k}<(j+1)$$

So $\hat{k}\leq j$ then $mk\leq djm$, now in $(1)$

$$djm \geq jbn+bc$$ $$djm \geq djm+bc$$ $$0 \geq bc$$

As $b$ and $c$ are positive, $bc >0$, so contradiction.

So no element of $S$ is divisible by $m$, now only the elements of $I$ are divisible by $m$. As the number of members is $g= \gcd(b,m)$ , the statement is proven.