Prove que se d=(a, b), então d é o número de inteiros na sequência a, 2 a, 3 a, \ldots, b a que são divisíveis por b.

Passo 1

Resumindo o enunciado, temos dois inteiros a e b e definimos
d = \gcd(a,b).
Queremos mostrar que, na sequência
a,\;2a,\;3a,\;\dots,\;b\,a,
exatamente d termos são divisíveis por b. Para isso vamos usar propriedades básicas de divisibilidade e o fato de que
\gcd\bigl(\tfrac{a}{d},\,\tfrac{b}{d}\bigr)=1.

Passo 2

Seja k um inteiro com 1\le k\le b. Note que
b \mid k\,a \quad\Longleftrightarrow\quad \frac{b}{d}\;\Bigm|\;k\,\frac{a}{d},
pois basta dividir ambos os lados da divisibilidade por d.

Passo 3

Como \gcd\bigl(\tfrac{a}{d},\tfrac{b}{d}\bigr)=1, a condição
\frac{b}{d}\;\Bigm|\;k\,\frac{a}{d}
implica que \tfrac{b}{d} deve dividir k. Ou seja,
b\mid k\,a \quad\Longleftrightarrow\quad \frac{b}{d}\mid k.

Passo 4

Entre os inteiros de 1 até b, os múltiplos de \tfrac{b}{d} são
\frac{b}{d},\;2\frac{b}{d},\;3\frac{b}{d},\;\dots,\;d\frac{b}{d}=b.
Há exatamente
\frac{b}{\,b/d\,} \;=\; d
destes múltiplos. Concluímos que, na sequência dada, há d valores de k tais que b\mid k\,a.

Resposta

d

Exercícios relacionados