unidade2

Mestrado Profissional
em Matemática em Rede Nacional
Iniciação à Matemática
Autores:
Krerley Oliveira Adán J. Corcho
Unidade II:
Capítulos III e IV
3
Divisibilidade
Os números governam o mundo. Platão
A teoria dos números é o ramo da Matemática que estuda os mis-
térios dos números e teve sua origem na antiga Grécia. Os belíssimos
problemas ligados a esta área constituem, até hoje, uma das princi-
pais fontes inspiradoras dos amantes da Matemática. Além disso, essa
área possui várias aplicações úteis a humanidade, como por exemplo,
o processo de criptogra�a usado em transações pela Internet.
Alguns problemas em teoria dos números demoram séculos para
serem resolvidos, como por exemplo o último teorema de Fermat, que
a�rma que não existe nenhum conjunto de inteiros positivos x, y, z e n
com n maior que 2 que satisfaça xn + yn = zn. Esse problema foi ob-
jeto de fervorosas pesquisas durante mais de 300 anos e foi �nalmente
demonstrado em 1995 pelo matemático Andrew Wiles.
Ainda hoje persistem muitas questões naturais e simples sem res-
posta. Por exemplo, ninguém sabe mostrar (apesar de todo mundo
89
90 3 Divisibilidade
acreditar que é verdade!) que todo natural par é soma de dois pri-
mos. Essa é a famosa conjectura de Goldbach. Essa simplicidade de se
anunciar problemas e a extrema di�culdade em resolvê-los faz desta
área um grande atrativo para os matemáticos do mundo todo.
Este capítulo será dedicado ao estudo de algumas propriedades
básicas relativas aos números inteiros.
3.1 Conceitos Fundamentais e Divisão Eu-
clidiana
Denotamos por Z o conjunto dos números inteiros formado pelo con-
junto dos números naturais N = {1, 2, 3, . . .} munido do zero e dos
números negativos. Ou seja, Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, . . .}.
Começamos observando que a soma, diferença e produto de núme-
ros inteiros também serão números inteiros. Entretanto, o quociente
de dois inteiros pode ser um inteiro ou não.
Uma das propriedades fundamentais dos números naturais que uti-
lizaremos ao longo do texto é o conhecido princípio da boa ordenação,
que a�rma o seguinte:
Princípio da Boa Ordenação: todo subconjunto não vazio A ⊆ N
possui um elemento menor que todos os outros elementos deste, ou
seja, existe a ∈ A tal que a ≤ n para todo n ∈ A.
Por exemplo, se A é o conjunto dos números pares, o menor ele-
mento de A é o número 2. Por outro lado, observamos que o conjunto
dos números inteiros não goza da boa ordenação.
Apesar do princípio da boa ordenação parecer inocente e natural,
muitos resultados importantes a respeito dos números naturais decor-
3.1 Conceitos Fundamentais e Divisão Euclidiana 91
rem do mesmo, como veremos ao longo de todo este capítulo.
De�nição 3.1. Sejam a e b inteiros. Dizemos que a divide b se existe
um inteiro q tal que b = aq. Também usaremos as frases a é divisor
de b ou b é múltiplo de a para signi�car esta situação.
Usaremos a notação a | b para representar todas as frases equi-
valentes ditas anteriormente. Se a não for divisor de b, então escre-
veremos a - b.
Exemplo 3.2. 7 | 21 pois 21 = 7 · 3. Por outro lado 3 - 8 pois
considerando o conjunto M = {3m, m ∈ N} = {3, 6, 9, 12, . . .} dos
múltiplos positivos de 3 vemos que 8 não pertence ao mesmo.
A seguinte proposição é um bom exercício para entender os con-
ceitos enunciados acima.
Proposição 3.3. Sejam a, b e c números inteiros. Então,
(a) se a | b e b | c então a | c;
(b) se a | b e a | c então a | (b+ c) e a | (b− c);
(c) se a e b são positivos e a | b então 0 < a ≤ b;
(d) se a | b e b | a então a = b ou a = −b.
Demonstração. Se a | b e b | c então existem inteiros q1 e q2 tais que
b = aq1 (3.1)
e
c = bq2. (3.2)
92 3 Divisibilidade
Substituindo (3.1) em (3.2) temos que
c = aq1q2 = aq, onde q = q1q2 ∈ Z, (3.3)
provando isto a a�rmação feita em (a).
Agora provaremos (b). Com efeito, se a | b e a | c valem as
igualdades
b = aq1, q1 ∈ Z (3.4)
e
c = aq2, q2 ∈ Z. (3.5)
Operando com os ambos lados das igualdades (3.4) e (3.5) temos que
b+ c = a(q1 + q2︸ ︷︷ ︸
r∈Z
) e b− c = a(q1 − q2︸ ︷︷ ︸
s∈Z
),
obtendo assim o resultado desejado.
Continuamos agora com a prova de (c). De fato, se a | b, sendo
ambos positivos, então b = aq com
q ≥ 1. (3.6)
Logo, multiplicando por a ambos lados de (3.6) temos (como a é posi-
tivo) que
b = aq ≥ a > 0,
como esperávamos.
Finalmente, provaremos (d). Com este propósito observamos que
se a | b e b | a então |a| divide |b| e |b| divide |a|. Portanto, pelo item
(c) temos que |a| ≤ |b| e |b| ≤ |a|, ou seja, |a| ≤ |b| ≤ |a|. Logo,
|a| = |b| e consequentemente a = b ou a = −b.
3.1 Conceitos Fundamentais e Divisão Euclidiana 93
Exemplo 3.4. Prove que o número N = 545362−7 não é divisível por
5.
Solução. Vamos mostrar isso utilizando o método do absurdo. Se
este número fosse divisível por 5, então 545362 − 7 = 5q. Logo, 7 =
545362 − 5q, ou seja, 7 seria divisível por 5, o que é um absurdo.
O próximo passo de nossa discussão é ver o que acontece quando
um número não é divisível por outro. Por exemplo, analisemos se 31 é
divisível por 7 e para isto listaremos a diferença entre 31 e os múltiplos
positivos de 7, isto é:
r1 = 31− 7 · 1 = 24,
r2 = 31− 7 · 2 = 17,
r3 = 31− 7 · 3 = 10,
r4 = 31− 7 · 4 = 3,
r5 = 31− 7 · 5 = −4,
r6 = 31− 7 · 6 = −11,
...
Claramente 31 não é divisível por 7, pois caso contrário teríamos
que alguma das diferenças acima seria igual a zero, o que é impossível
pois as diferenças rq = 31 − 7q com 1 ≤ q ≤ 4 são todas positivas
e com q ≥ 5 são todas negativas. Entretanto, notamos que entre as
diferenças positivas a única que é menor que 7 corresponde ao caso
q = 4. O resultado seguinte nos diz o que acontece no caso geral da
divisão de um inteiro b por um inteiro positivo a.
94 3 Divisibilidade
Teorema 3.5 (Divisão Euclidiana). Dados dois inteiros a e b, sendo
a positivo, existem únicos inteiros q e r tais que
b = aq + r, 0 ≤ r < a.
Se a - b, então r satisfaz a desigualdade estrita 0 < r < a.
Demonstração. Por simplicidade, suporemos que b é positivo. Se b <
a, basta tomar q = 0 e r = b. Se b = a, então tomamos q = 1 e r = 0.
Assim, assumiremos também que b > a > 0. Consideremos o conjunto
R = {b− aq ∈ Z; b− aq ≥ 0} ⊆ N ∪ {0} (3.7)
Notemos que o conjunto R é não vazio, pois b − a ∈ R, já que
b − a > 0. Deste modo, pelo princípio da boa ordenação temos que
R admite um menor elemento, que denotaremos por r. Claramente
r = b − aq ≥ 0, para algum q ≥ 0. Além disso, r < a pois caso
contrário
r = b− aq ≥ a⇒ b− a(q + 1) ≥ 0. (3.8)
Por outro lado,
a > 0⇒ b− a(q + 1) < b− aq. (3.9)
Das desigualdades (3.8) e (3.9) segue que
0 ≤ b− a(q + 1) < b− aq,
contradizendo o fato de que r = b−aq é o menor elemento não negativo
de R.
Agora provaremos que de fato r e q, escolhidos desta forma, são
únicos. Com efeito, suponhamos que existem outros inteiros r1 e q1
tais que
b = aq1 + r1, 0 ≤ r1 < a.
3.1 Conceitos Fundamentais e Divisão Euclidiana 95
Então resulta que aq + r = aq1 + r1. Logo,
(r − r1) = (q1 − q)a; (3.10)
sendo assim, r−r1 é múltiplo de a. Mas, em virtude de−a < r−r1 < a,
o único valor que r − r1 pode tomar, sendo este múltiplo de a, é
r − r1 = 0. Portanto, r = r1, de onde se deduz diretamente de (3.10)
que q = q1.
Os números q e r no enunciado do teorema acima são chamados,
respectivamente, de quociente e resto da divisão de b por a.
Um resultado imediato da divisão euclidiana é o seguinte.
Corolário 3.6. Dados dois números naturais a e b com 1 < a ≤ b,
existe um número natural n tal que
na ≤ b < (n+ 1)a.
Demonstração. Pela divisão euclidiana, existem únicos q, r ∈ N com
0 ≤ r < a tais que b = aq + r. Assim
aq ≤ b = aq + r < aq + a = a(q + 1).
Basta agora tomar q = n para obtermos o resultado.
Os exemplos a seguir apresentam a utilidade do Teorema 3.5.
Exemplo 3.7. Se a é um natural com a ≥ 3, então a2 deixa resto 1
na divisão por a− 1. Consequentemente, a− 1 divide a2 − 1.
Solução. Usando a identidade a2 − 1 = (a − 1)(a + 1) temos que
a2 = (a− 1)(a+ 1) + 1 com 1 < a−