Álgebra I – Divisibilidade
20
Problema. O conjunto dos números primos é infinito?
A resposta a essa pergunta aparece na obra de Euclides, num teorema cuja
demonstração é considerada até hoje, como um modelo de raciocínio matemático.
Teorema. O conjunto dos números primos é infinito.
Demonstração. Suponhamos que o conjunto dos primos seja finito e sejam p1, p2 , p3, ...,pn esses
primos. Consideremos então o seguinte número: P = p1.p2.p3...pn + 1. Pelo lema anterior segue
que P possui um divisor primo pi, e como o conjunto dos primos é finito, segue que pi é um dos
elementos do conjunto {p1, p2 , p3, ...,pn}. Assim, segue que pi divide o produto p1.p2.p3...pn . Então
temos que pi |(p1.p2.p3...pn) e pi | P  pi | (P – p1.p2.p3...pn), mas P – p1.p2.p3...pn = 1, assim segue
que pi | 1  pi = 1, o que é um absurdo, pois pi é primo. (c.q.d)
3.6 Máximo divisor comum
Sendo a um número inteiro, denotaremos por D(a) o conjunto dos divisores positivos de a.
Exemplo: D(12) = {1 , 2, 3, 4, 6, 12} e D(15) = {1,3, 5, 15}
Definição. Chama-se máximo divisor comum de a e b, o maior de seus divisores comuns. O
máximo divisor comum de a e b será denotado por mdc(a,b).
Exemplo: D(12)  D(15) = {1,3}, logo mdc(12,15) = 3.
3.6.1 Algoritmo de Euclides
O algoritmo de Euclides é um dispositivo prático para determinar o mdc de dois inteiros.
Esse dispositivo aparece no sétimo livro dos Elementos de Euclides e é baseado no seguinte
teorema:
Teorema. Sejam a, b inteiros, b  0, e sejam q e r o quociente e o resto da divisão de a por b.
Então, mdc(a,b) = mdc(b,r).
Demonstração. Sejam x = mdc(a,b) e y = mdc(b,r). Vamos mostrar que x = y.
Lembrando que a = bq + r temos:
x = mdc(a,b)  x | a e x |b  x | (a – bq)  x | r . Logo, x | b e x | r.
Agora, como y = mdc(b,r) segue que x  y. (1)
Por outro lado, se y = mdc(b,r) temos: y|b e y|r  y | (bq + r)  y | a. Assim, y | a e y | b.
Agora,como x = mdc(a,b) segue que y  x. (2)
De (1) e (2) segue que x = y. (c.q.d)
Prof. Robson Rodrigues da Silva
21
Observação. Utilizando o resultado anterior podemos determinar mdc(a,b) fazendo divisões
sucessivas.
Exemplo: Calcule mdc(336, 120) = 24
quociente
2
1
4
336
120
96
24
resto
96
24
0
Definição. Sejam a e b dois inteiros. Dizemos que a e b são primos entre si, se e somente se,
mdc(a,b) = 1.
3.6.2 Resolução de problemas envolvendo mdc.
Um lojista dispõe de três peças de um mesmo tecido, cujos comprimentos
são 48 m, 60 m e 80 m. Nas três peças o tecido tem a mesma largura.
Deseja-se vender o tecido em retalhos iguais, cada um tendo a largura das
peças e o maior comprimento possível, de modo a utilizar todo o tecido das peças. Quantos
retalhos ele deverá obter?
3.7 Mínimo múltiplo comum
Sendo a um inteiro, denotaremos por M(a) o conjunto dos múltiplos positivos de a.
Exemplo. M(3) = {3,6,9,12,15,...} M(4) = {4,8,12,16, ...}
Definição. Chama-se mínimo múltiplo comum de a e b, ao menor dos seus múltiplos comuns. O
mínimo múltiplo comum de a e b será denotado por mmc(a,b).
Exemplo. M(3)M(4) = {12, 24,...}, logo mmc(3,4) = 12.
Observação. O mmc de dois inteiros pode ser calculado através da decomposição em fatores
primos.
Exemplo. Calcule o mmc(24,60)
3.7.1 Resolução de problemas envolvendo o mmc.
Os planetas Júpiter, Saturno e Urano têm períodos de revolução em torno do Sol de
aproximadamente 12, 30 e 84 anos, respectivamente. Quanto tempo decorrerá,
depois de uma observação, para que eles voltem a ocupar simultaneamente as mesmas
posições em que se encontravam no momento da observação?