S-3.3 Dados 0<a <= n<m, mostre que no intervalo [ 1, n ] existem q múltiplos de a, onde q é o quociente da divisão de n por q. Quantos são os múltiplos de a no intervalo [n, m] ? (Na última situação, divida a análise em dois casos: n múltiplo de a e o contrário.)

Passo 1

O enunciado pede para contar quantos números em dois intervalos são divisíveis por um inteiro a>0: primeiro no intervalo [1,n] e depois em [n,m], sabendo que a<= n<m. Vamos usar o algoritmo da divisão euclidiana e propriedades de progressões aritméticas para fazer essa contagem.

Passo 2

Aplicamos a divisão de n por a. Existem inteiros q e r tais que
n = a,q + r, 0 <= r < a
Por definição de divisão inteira, temos
q = llfloor tfracnarrfloor

Passo 3

No intervalo [1,n], os múltiplos de a são exatamente
a,;2a,;3a,;dots,;q,a,
pois q,a <= n < (q+1)a. Essa sequência é uma progressão aritmética de razão a com q termos. Logo, há q múltiplos de a em [1,n].

Passo 4

Para contar os múltiplos de a em [n,m], seja
p = llfloor tfracmarrfloor
Caso 1: se r=0, então n=a,q é múltiplo de a. Os múltiplos de a em [n,m] são
a,q,;a,(q+1),;dots,;a,p,
que são p-q+1 termos.

Passo 5

Caso 2: se r>0, então n não é múltiplo de a. O primeiro múltiplo de a >= n é a,(q+1). Assim, os múltiplos em [n,m] são
a,(q+1),;a,(q+2),;dots,;a,p,
totalizando p-(q+1)+1 = p-q termos.

Resposta

No intervalo
onde .

Exercícios relacionados