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−