Iniciação à Aritmética (30)

Text Material Preview

“principal”
2010/4/19
page 51
Estilo OBMEPi
i
i
i
i
i
i
i
N SEC. 3.3: DIVISORES 51
muito eficiente para fazer este cálculo. O Algoritmo de Euclides, como
é conhecido o método por ele desenvolvido, será descrito no próximo
capítulo e repousa numa generalização da propriedade do Problema
3.13(c) que recordamos abaixo:
Um número d é divisor comum de a e b, não ambos nulos, se, e
somente se, ele é um divisor comum de a e b − a.
Tomando o máximo divisor comum, obtemos a seguinte identi-
dade:
mdc(a, b) = mdc(a, b − a),
que permite ir reduzindo sucessivamente o cálculo do mdc de dois
números ao cálculo do mdc de números cada vez menores.
Como exemplo de aplicação, vejamos como isto vai permitir o
cálculo de mdc(3 264, 1 234):
mdc(3 264, 1 234) = mdc(1 234, 3 264 − 1 234) =
mdc(1 234, 2 030) = mdc(1 234, 2 030 − 1 234) =
mdc(1 234, 796) = mdc(796, 1 234 − 796) =
mdc(796, 438) = mdc(796 − 438, 438) =
mdc(358, 438) = mdc(358, 438 − 358) =
mdc(358, 80) = mdc(358 − 80, 80) =
mdc(278, 80) = mdc(198, 80) =
mdc(118, 80) = mdc(38, 80) =
mdc(38, 42) = mdc(38, 4) =
mdc(34, 4) = mdc(30, 4) =
mdc(26, 4) = mdc(22, 4) =
mdc(18, 4) = mdc(14, 4) =
mdc(10, 4) = mdc(6, 4) = 2
“principal”
2010/4/19
page 52
Estilo OBMEPi
i
i
i
i
i
i
i
52 � CAP. 3: OS INTEIROS E SUAS PROPRIEDADES
As contas anteriores serão abreviadas de modo drástico com o
algoritmo de Euclides para o cálculo do mdc que iremos apresentar
na Seção 3.8.
Problema 3.15. Sejam a e b dois números com um divisor comum
d. Mostre que d divide a×n+b×m, quaisquer que sejam os números
inteiros n e m.
Dois números inteiros, não ambos nulos, serão ditos primos entre
si se não forem múltiplos de um mesmo número diferente de 1 e de
−1.
Portanto, dois inteiros a e b, não ambos nulos, são primos entre
si se os únicos divisores comuns de a e b são 1 e −1, o que equivale a
dizer que mdc(a, b) = 1.
Exemplos de pares de inteiros primos entre si são: 2 e 3; 4 e 15; 9
e 7. Não são primos entre si os pares: 2 e 4; 3 e 6; 9 e 12.
Dois números primos distintos são sempre primos entre si.
Dois números consecutivos são sempre primos entre si. De fato,
podemos escrever os dois números na forma n e n + 1, logo
mdc(n, n + 1) = mdc(n, n + 1 − n) = mdc(n, 1) = 1.
Problema 3.16.
(a) Mostre que dois números inteiros da forma n e 2n + 1 são sempre
primos entre si.
(b) Mostre que se n é um número ímpar, então mdc(n, 2n + 2) = 1.