"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?

  • $\begingroup$ $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 :) $\endgroup$ – 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.

  • $\begingroup$ 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... $\endgroup$ – violeta Oct 22 '14 at 23:02
  • $\begingroup$ also, b can be negative... hmm.. $\endgroup$ – violeta Oct 22 '14 at 23:31

So the sequence is the following:


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 \}$$

By contradiction

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


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.