Introdução à Teoria dos Números

Prévia do material em texto

ANTONIO CARLOS MARQUES DA SILVA
ANA PAULA LIMA MARQUES FERNANDES
Maceió-Alagoas
2011
INTRODUÇÃO À
TEORIA DOS NÚMEROS
 UNIVERSIDADE FEDERAL DE ALAGOAS
Reitora
Ana Dayse Rezende Dorea
Vice-reitor
Eurico de Barros Lôbo Filho
Diretora da Edufal
Sheila Diab Maluf
Conselho Editorial Edufal
Sheila Diab Maluf (Presidente)
Cícero Péricles de Oliveira Carvalho
Elton Casado Fireman
Roberto Sarmento Lima
Iracilda Maria de Moura Lima
Lindemberg Medeiros de Araújo
Leonardo Bittencourt
Eurico Eduardo Pinto de Lemos 
Antonio de Pádua Cavalcante
Cristiane Cyrino Estevão Oliveira
Direitos desta edição reservados à
Edufal - Editora da Universidade Federal de Alagoas
Campus A. C. Simões, BR 104, Km, 97,6 - Fone/Fax: (82) 3214.1111
Tabuleiro do Martins - CEP: 57.072-970 - Maceió - Alagoas
E-mail:edufal@edufal.ufal.br - Site: www.edufal.ufal.br ASSOCIAÇÃO BRASILEIRA
DE EDITORAS UNIVERSITÁRIAS
Editora afiliada:
Catalogação na fonte
Editoração eletrônica, capa e programação visual
ANTONIO CARLOS MARQUES DA SILVA
Universidade Federal de Alagoas
Biblioteca Central
Divisão de Tratamento Técnico
Bibliotecária Responsável: Helena Cristina Pimentel do Vale
 
 
 
UFAL – IM 
Universidade Federal de Alagoas
Instituto de Matemática
Amauri da Silva Barros
José Carlos Almeida de Lima
Ediel Azevedo Guerra
José Fábio Boia Porto
Julienne Barros
Diretor do Instituto de Matemática
Vice-Diretor do IM
Coordenador Acadêmico
Coordenador de Tutoria
Revisora EAD
CURSO DE LICENCIATURA EM MATEMÁTICA
Anamelea de Campos Pinto
Coordenadora Institucional de Educação à Distância
(CIED-UFAL)
Propriedades aritméticas dos inteiros 7
CAPÍTULO 1
PROPRIEDADES ARITMÉTICAS DOS INTEIROS
A Matemática é a rainha das ciências e a Teoria dos Números
é a rainha da Matemática.
C.F.Gauss
Objetivos do Capítulo 1
(a) Descrever as propriedades da soma e do produto de inteiros;
(b) Destacar a propriedade de domínio de integridade;
(c) Explicitar a estrutura de ordem induzida pelo conjunto dos números naturais;
(d) Aplicar a teoria a problemas elementares de contagem.
1.1 INTRODUÇÃO
A Teoria dos Números é um vasto edifício matemático, repleto de resultados que ilustram a interdisci-
plinaridade das grandes áreas de atuação da Matemática. A parte elementar da Teoria dos Números
é a chamada Aritmética, que estuda as propriedades das operações de soma e produto dos números
inteiros, aí incluído o algoritmo euclidiano da divisão e suas aplicações. Esse desenvolvimento,
iniciado pelos Os Elementos de Euclides (cerca de 300 AC) foi consolidado na Renascença, pelos
trabalhos de Fermat, Euler e Gauss. Na realidade, prosseguindo na direção apontada por Gauss, os
trabalhos de Kummer, Dedekind e Kronecker, favoreceram a consolidação da Teoria Algébrica dos
Números. Um pouco mais tarde, ainda no século 19, a chamada Teoria Analítica dos Números
incorporou métodos de análise real e complexa, dos trabalhos de Dirichlet e Riemann. Atualmente,
uma nova vertente, a Geometria Aritmética, fruto dos estudos de Artin, Hasse, Mordell e Weil,
vem permitindo avanços notáveis, notadamente, por exemplo, a demonstração do Último Teorema
de Fermat (Wiles, 1995).
Nesse curso introdutório, procuraremos sistematizar a parte inicial da Aritmética, em seus aspectos
mais aplicados ao bom entendimento da estrutura operacional do conjunto dos inteiros.
1.1 SOMA E PRODUTO DE INTEIROS
Representaremos por Z = {. . . ,−3,−2,−1, 0, 1, 2, 3, 4, . . .} o conjunto dos números inteiros e por
N = {0, 1, 2, 3, . . .} o subconjunto de Z formado pelos números naturais.
Dados os inteiros a e b, indicaremos por a + b o inteiro que representa sua soma e por ab o inteiro
que representa seu produto, ou seja: + : Z× Z −→ Z . : Z× Z −→ Z
(a, b) 7−→ a+ b (a, b) 7−→ a.b
Essas operações, também chamadas de adição e multiplicação, possuem as seguintes propriedades
características.
8 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
1) A adição e a multiplicação são bem definidas:
∀a, b, c, d ∈ Z, a = c e b = d =⇒ a+ b = c+ d e ab = cd
2) A adição e a multiplicação são comutativas:
∀a, b ∈ Z, a+ b = b+ a e ab = ba
3) A adição e a multiplicação são associativas:
∀a, b, c ∈ Z, (a+ b) + c = a+ (b+ c) e (ab)c = a(bc)
4) A adição e a multiplicação possuem elementos neutros, unicamente determinados pelas condições:
∀a ∈ Z, a+ 0 = 0 + a = a e a · 1 = 1 · a = a
5) Todo inteiro a ∈ Z possui um único oposto aditivo, notado (−a), tal que
a+ (−a) = (−a) + a = 0
6) A multiplicação é distributiva com relação à adição:
∀a, b, c ∈ Z, a(b+ c) = ab+ ac
Observações Essas propriedades, as leis básicas da aritmética, que estamos supondo conhecidas,
também comparecem em muitas situações, relativas a conjuntos outros que o dos inteiros.
Observemos que o produto de inteiros não possui a propriedade correspondente a (5) acima,
isto é, não existe, em geral, para cada inteiro a, algum inteiro b tal que ab = ba = 1; na realidade,
apenas 1 · 1 = (−1) · (−1) = 1 [como veremos na Prop.B do Ÿ1.7]. Para contornar parcialmente essa
dificuldade, vale a seguinte relação.
7) [Integridade] Dados a, b ∈ Z, se ab = 0, então a = 0 ou b = 0. Equivalentemente, tendo em conta
a formulação contrapositiva, se a 6= 0 e b 6= 0, então ab 6= 0, ou notando Z∗ = Z−{0} o conjunto dos
inteiros não nulos, temos, se a, b ∈ Z∗, então a · b ∈ Z∗, o que significa que Z∗ é estável pelo produto
dos inteiros.
EXEMPLO 1.3
Nesse exemplo, usaremos as propriedades (1)�(7) para recordar vários resultados.
1. Dados os inteiros a e b, a equação x+ a = b possui solução única x = b+ (−a) = b− a.
De fato, se x + a = b = y + a, então x + a = y + a, donde, somando (−a) a ambos os membros,
(x+a)+(−a) = (y+a)+(−a), logo, pela associatividade, x+(a+(−a)) = y+(a+(−a)), x+0 = y+0,
x = y; assim, só pode existir uma solução. Enfim, para exibir tal solução, partindo de x + a = b e
adicionando (−a) a ambos os membros, (x+ a) + (−a) = b+ (−a), x+ (a+ (−a)) = b+ (−a), isto
é, x+ 0 = b+ (−a), x = b+ (−a).
Como de hábito, notaremos b − a = b + (−a). Em particular, se x + a = 0, então x = −a é o único
inteiro que verifica tal soma. Ora, como a+ (−a) = 0, segue que −(−a) = a.
2. A adição é compatível e cancelativa com relação à igualdade:
∀a, b, c ∈ Z, a+ b = a+ c ⇐⇒ b = c
Se a+ b = a+ c, então, somando (−a) a ambos os membros, temos (−a) + (a+ b) = (−a) + (a+ c),
ou, pela associatividade, ((−a) + a) + b = ((−a) + a) + c, donde 0 + b = 0 + c, b = c. A recíproca é
imediata da propriedade 1).
3. Para cada a ∈ Z, temos a · 0 = 0.
Temos a0 = a(0 + 0) = a0 + a0, isto é, 0 + a0 = a0 + a0, donde, pelo cancelamento aditivo acima,
a0 = 0.
4. Dados a, b ∈ Z, temos a(−b) = (−a)b = −(ab); em particular, (−a)(−b) = ab.
Propriedades aritméticas dos inteiros 9
Como b+(−b) = 0, vem a(b+(−b)) = a0 = 0, vem ab+a(−b) = 0, logo −(ab) = a(−b); analogamente,
(−a)b = −(ab). Enfim, (−a)(−b) = −(a(−b)) = −(−(ab)) = ab.
5. Dados a, b, c ∈ Z, temos a(b− c) = ab− ac.
De fato: a(b− c) = a(b+ (−c)) = ab+ a(−c) = ab+ (−ac) = ab− ac.
6. [Cancelamento restrito da multiplicação]
∀a, b, c ∈ Z, a 6= 0, ab = ac =⇒ b = c
De ab = ac segue ab− ac = 0, ou a(b− c) = 0; pela propriedade da integridade 7), como a 6= 0, vem
b− c = 0, ou b = c.
Observação Vale a recíproca para todo a ∈ Z, como decorre da propriedade 1).
7. Em Z, se a2 = 2a, então a = 0 ou a = 2.
Temos a2 − 2a = a(a− 2) = 0, donde, usando a integridade, a = 0 ou a− 2 = 0.
Observação Os códigos para efetuar as operações com inteiros são, certamente, conhecidos de todos
nós. A aparência algo formalizada da exposição é, tão-somente, o sotaque matemático adequado para
validar os mecanismos operacionais. Por exemplo, no exercício 7. acima, lançamos mão da potência
a2, mesmo que ainda nãotenhamos (re)visto sua definição.
Atividade-proposta 1.4
1. Verifique a validade das relações:
(a) −a = (−1)a
(b) −(a+ b) = (−a) + (−b)
(c) (a− b) + (c− d) = (a+ c)− (b+ d)
(d) (a− b)(c− d) = (ac+ bd)− (ad+ bc)
(e) (a− b)(a+ b) = a2 − b2
2. Encontre todos os inteiros x ∈ Z tais que:
(a) x+ 2 = 18; (b) 10x = 0; (c) 2x− 3 = 0; (d) 2x+ 4 = 0; (e) x2 + 1 = 0
3. Dados a, b ∈ Z, considere a equação ax = b. Comprove os seguintes resultados:
(a) se b = 0 e a = 0, então todo x inteiro é solução da equação dada;
(b) se b = 0 e a 6= 0, então x = 0 é a única solução da equação considerada;
(c) se a = 0 e b 6= 0, então a equação não possui solução inteira;
(d) se a 6= 0 e se existir alguma solução x da equação, então tal solução é únicamente determinada;
(e) mostre com um exemplo em que a condição a 6= 0 não é suficiente para garantir a existência de
solução inteira da equação dada.
4. Encontre todos os inteiros x ∈ Z tais que:
(a) x2 = 1; Sugestão: x2 − 1 = (x− 1)(x+ 1);
(b) x3 = x;
(c) x2 + 2x+ 1 = 0
5. Quantos inteiros x verificam 0 ≤ x ≤ 10 ? 25 ≤ x ≤ 79?
6. Indique o inteiro que ocupa a posição 53 na sequência 86, 87, 88, . . ..
7. Dentre 123 inteiros consecutivos, o maior vale 307. Indique o menor inteiro.
8. Sejam os inteiros a e b tais que a+ b = 21 e ab = −7. Calcule (a) a2 + b2; (b)a4 + b4.
9. Calcule (mentalmente...) o inteiro a = 1234567892 − 123456790× 123456788.
10 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
1.5 A estrutura de ordem
O conjunto dos inteiros possui uma ordem natural: Z = {. . . ,−4,−3,−2,−, 1, 0, 1, 2, 3, 4, 5, . . .}; essa
ordem, habitualmente, é expressa em termos da relação a < b, onde a afirmação a é menor do que
b significa que o inteiro a está à esquerda do inteiro b na lista acima, isto é, a diferença b − a é um
inteiro positivo. Desse modo, as propriedades da relação a < b podem ser obtidas das propriedades
do conjunto dos inteiros positivos N∗ = {1, 2, 3, 4, . . .}.
Admitiremos, assim, como postulados, as seguintes propriedades de N∗:
(O1) Adição: a soma de dois inteiros positivos é um inteiro positivo;
(O2) Multiplicação: o produto de dois inteiros positivos é um inteiro positivo;
(O3) Tricotomia: para cada inteiro a, vale uma e somente uma das alternativas: ou a é positivo, ou
a = 0, ou −a é positivo.
Usaremos as seguintes definições:
a < b ⇐⇒ b > a ⇐⇒ b− a > 0;
a ≤ b significa que ou a < b ou a = b.
Assim, os inteiros positivos a são os inteiros maiores do que zero; inteiros b < 0 são chamados
negativos.
Propriedades
1) [Transitividade]
∀a, b, c ∈ Z, a < b e b < c =⇒ a < c
Como b− a > 0 e c− b > 0, segue de (O1) que c− a = (c− b) + (b− a) > 0, ou seja, a < c.
2) [Adição compatível e cancelativa]
∀a, b, c ∈ Z, a < b ⇐⇒ a+ c < b+ c
De fato, vale (b+ c)− (a+ c) = b− a.
3) [Multiplicação compatível e cancelativa restrita]
∀a, b, c ∈ Z, c > 0, a < b ⇐⇒ ac < bc
Basta usar as definições e a relação bc− ac = (b− a)c.
4) A relação ≤ é uma relação de ordem, isto é, valem as propriedades:
(a) Reflexiva: ∀a, a ≤ a;
(b) Anti-simétrica: ∀a, b, a ≤ b e b ≤ a =⇒ a = b
(c) Transitiva: ∀a, b, c, a ≤ b e b ≤ c =⇒ a ≤ c
Exemplo 1.6
1. Seja x ∈ Z∗; vale x2 > 0. De fato, pela tricotomia, como x 6= 0, então ou x ou −x é positivo.
No primeiro caso, x2 é positivo pela condição (O2); no segundo, −x é positivo, logo x2 = (−x)2 > 0.
Em particular, 1 = 12 é sempre positivo.
2. Para cada a ∈ Z, o valor absoluto de a é dado por: |a| =
{
a, se a ≥ 0
−a, se a < 0
Valem as relações: (a) |ab| = |a| |b|;
(b) −|a| ≤ a ≤ |a|
(c) |a+ b| ≤ |a| |b|
Pratique um pouco! Verifique as três relações acima.
Propriedades aritméticas dos inteiros 11
1.7 O princípio da Boa Ordenação
Seja S um subconjunto de N. Diremos que um inteiro a é um menor elemento de S se
(i) a ∈ S;
(ii) para cada x ∈ S, vale x ≥ a.
Caso exista, o menor elemento de S é unicamente determinado, pois se a e b são menores elementos
de S, então a ≤ b e b ≤ a, donde a = b (antisimetria da relação de ordem). Usaremos a notação
minS para denotar, se existir, o menor elemento de S.
Um resultado notável garante a existência de menor elemento de subconjuntos não vazios de N.
Diremos, então, que o conjunto N é bem ordenado.
Axioma da Boa Ordenação Todo subconjunto não vazio de números naturais possui um menor
elemento.
Proposição A Dado a ∈ Z, se a > 0, então a ≥ 1.
Por absurdo, se existe a ∈ Z tal que 0 < a < 1, então o conjunto S = {x ∈ N ; 0 < x < 1} é não
vazio. Portanto, S possui um menor elemento b tal que 0 < b < 1, donde 0 < b2 < b < 1, e seria
b2 ∈ S, com b2 < b, contradizendo a minimalidade de b.
Corolário 1 Dados os inteiros a e b, se a > b, então a ≥ b+ 1.
De fato, se b < a < b + 1, então a − b = c > 0 é tal que b < b + c < b + 1, ou 0 < c < 1, o que é
impossível.
Corolário 2 Dados os inteiros a e b, com b 6= 0, vale |ab| ≥ |a|.
Como b 6= 0, vem |b| ≥ 1, donde |a||b| ≥ |a|, ou |ab| ≥ |a|.
Proposição B Sejam os inteiros a e b. Se ab = 1, então a = b = 1 ou a = b = −1.
De fato, de ab = 1 vem que a 6= 0 e b 6= 0; então, do corolário 2 e da condição 1 > 0, vemos que
1 = |ab| ≥ |a| e 1 = |ab| ≥ |b|. Também, como |a| > 0 e |b| > 0, vem da propsição A que |a| = |b| = 1,
ou a = ±1 e b = ±1; enfim, da hipótese ab = 1, temos bem a = b = 1 ou a = b = −1.
Proposição C [Propriedade Arquimediana] Dados os inteiros a e b, com b 6= 0, existe um inteiro
n tal que nb ≥ a.
De fato, como b 6= 0, segue do corolário 2 que |b||a| = |ba| ≥ |a| ≥ a. Assim, se b > 0, basta escolher
n = |a| e o resultado decorre da desigualdade anterior. Se b < 0, então a escolha n = −|a| também
verifica o resultado enunciado.
Observação Com um pouco de precaução, é possível estender para o conjunto Z o princípio do
menor inteiro (ou da boa ordem). Na realidade, suporemos subconjuntos não vazios A ⊂ Z e que
sejam limitados inferiormente (ou minorados), isto é, para os quais existe algum minorante b ∈ Z tal
que, para todo x ∈ A, vale b ≤ x. Nessas condições, vale o resultado:
Proposição D Todo subconjunto A de Z, que é não vazio e limitado inferiormente, possui um
elemento mínimo.
De fato, se b é um minorante de A, então o conjunto S = {x − b ; x ∈ A} é um subconjunto não
vazio de N. Logo, pelo princípio do menor inteiro natural, existe k = minS; portanto, existe m ∈ A
tal que k = m − b. Enfim, se x ∈ A é um elemento qualquer, temos x − b ∈ S, logo m − b ≤ x − b,
donde m ≤ x, isto é, m é o mínimo de A.
12 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
1.8 RESPOSTAS DAS ATIVIDADES PROPOSTAS
1.4
1. (a) Partindo de 1 + (−1) = 0 e multiplicando ambos os membros por a, segue a + (−1)a = 0,
donde −a = (−1)a.
(b) Temos −(a+ b) = (−1)(a+ b) = (−1)a+ (−1)b = (−a) + (−b).
(c) Sempre usando as definições: (a−b)+(c−d) = (a+(−b))+(c+(−d)) = (a+c)+((−b)+(−c)) =
(a+ c)− (b+ d).
(d) Analogamente: (a − b)(c − d) = (a + (−b))(c + (−d)) = ac + a(−d) + (−b)c + (−b)(−d) =
ac+ bd− ad− bc = (ac+ bd)− (ad+ bc).
(e) Basta desenvolver (a− b)(a+ b) usando (d).
2. (a) De x+ 2 = 18, segue x = 18− 2, ou x = 16;
(b) Como 10 6= 0 em 10x = 0, vem da integridade que x = 0.
(c) Observando que {2x ; x ∈ Z} = {. . . − 2, 0, 2, 4, 6, . . .}, vemos que não existe x ∈ Z tal que
2x = 3.
(d) Se 2x+ 4 = 0, então x = −2.
(e) Para cada x ∈ Z, temos x2 ≥ 0, logo x2+1 ≥ 1; então, a equação dada não possui solução inteira.
3. (d) Se x e y são inteiros verificando ax = ay = b, então a(x − y) = 0; como a 6= 0, segue da
integridade que x− y = 0, isto é, x = y.
(e) Por exemplo, considere 2x = 3.
4.(a) Se x2 = 1, então x2 − 1 = (x − 1)(x + 1) = 0, donde x − 1 = 0 ou x + 1 = 0, isto é, x = 1 ou
x = −1.
(b) Se x3 = x, então x3 − x = x(x2 − 1) = x(x− 1)(x+ 1) = 0, donde x = 0 ou x = 1 ou x = −1.
(c) Como x2 + 2x+ 1 = 0 significa que (x+ 1)2 = 0, vemos que x+ 1 = 0, ou x = −1.
5. No primeiro caso, há 11 = (10− 0) + 1 inteiros; no segundo, (79− 25) + 1 = 55 inteiros.
6. 86 + 52 = 1387. 307− 123 + 1 = 185
8.(a) a2 + b2 = (a+ b)2 − 2ab = 212 + 14 = 455
(b) a4 + b4 = (a2 + b2)2 − 2a2b2 = 4552 − 2 · 49 = 206.927
9. Se x = 123456789, então o enunciado nos dá: x2 − (x+ 1)(x− 1) = 1.
Indução Finita 13
CAPÍTULO 2
INDUÇÃO FINITA
Deus fez os inteiros; o resto é invenção humana.
L.Kronecker
Objetivos do Capítulo 2
(a) Discutir a validação de sentenças abertas em conjuntos infinitos;
(b) Descrever o método da indução matemática;
(c) Explicitar o Teorema da Indução Finita em suas duas formas;
(d) Estabecer definições por recorrência;
(e) Aplicar a teoria a problemas elementares de contagem.
2.1 INTRODUÇÃO
Como o conjunto Z dos inteiros é infinito, ocorrem dificuldades de ordem lógica e operacional para
formular e validar corretamente várias propriedades, mesmo aquelas de caráter discreto.
A indução matemática ou indução finita fornece critérios eficientes para estabelecer verdades
matemáticas, válidas em conjuntos infinitos. Às vezes, uma indução empírica pode apontar para
uma certa conclusão, após várias tentativas �experimentais� concordantes. Mesmo que o número de
tentativas seja muito grande, uma indução empírica não implica, necessariamente, numa certeza.
Consideremos os exemplos, onde n representa um qualquer número natural:
(1) P (n) = n2 + n+ 41 é um número primo;
(2) T (n) = n(2n− 1) < 6000;
(3) Se Sn é a soma dos angulos internos de um polígono, então Sn = (n− 2)pi rad;
(4) 1 + 2 + · · ·+ n = n(n+ 1)
2
No caso (1), um exemplo de Euler, substituindo sucessivamente n = 1, 2, 3, . . . , 39, encontramos a
sequência de números primos 43, 47, 53, . . . , 1601, mas P (40) = 402+40+41 = 40(40+1)+41 = 41·41
não é primo.
No caso (2), procedendo por tentativas, como em (1), com n = 1, 2, 3, . . . , 55, encontramos os valores
de T (n): 1, 6, 15, . . . , 5995; já T (56) = 6216, contrariando a validade da sentença aberta dada.
São verdadeiros os resultados (3) e (4). [Justifique!].
14 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
2.2 Teorema da Indução Finita (1
a
forma)
Seja P (n) uma sentença aberta associada a cada número natural n ≥ n0, com n0 natural, tal que:
(i) P (n0) é verdade;
(ii) Para todo n ≥ n0, se P (n) é verdade, então P (n+ 1) é verdade.
Então P (n) é verdade para todo n ≥ n0.
A verificação usa a Boa Ordenação dos números naturais. Seja S = {x ∈ N ; x ≥ n0 e P (x) é falsa.}.
Suponhamos, por absurdo, que S 6= φ; então, pelo princípio da boa ordenação, S possui um menor
elemento m; como m ∈ S, deve ser m ≥ n0; pela condição (i) do teorema, temos n0 /∈ S, logo m > n0,
donde m − 1 ≥ n0; ora, sendo m = min S, segue que m − 1 /∈ S, donde P (m − 1) é verdadeira.
Enfim, da hipótese (ii), vem P (m) verdadeira, portanto m /∈ S. Contradição.
EXEMPLO 2.3
1. Mostremos que Sn = 1 + 3 + 5 + . . .+ (2n− 1) = n2, n ≥ 1.
Alguns termos de Sn sugerem que, realmente, a expressão de Sn = n2 é correta...! Observemos:
S1 = 1, S2 = 1 + 3 = 4, S3 = 1 + 3 + 5 = 9, ...
Usando o teorema da indução finita, temos:
(i) S1 = 1 = 12 é verdadeira;
(ii) Supondo n ≥ 1 e Sn = n2, caculemos Sn+1. Temos:
Sn+1 = 1 + 3 + . . . + (2n − 1) + (2n + 1) = Sn + (2n + 1) = n2 + (2n + 1) = n2 + 2n + 1,
isto é, Sn+1 = (n + 1)2 coincide com a expressão enunciada! Segue do teorema que a sentença
Sn = 1 + 3 + 5 + . . .+ (2n− 1) = n2 vale para todo n ≥ 1.
2. Verificar que 2n > n2, para todo n ≥ 5.
Pondo P (n) : 2n > n2, temos P (5) : 25 = 32 > 25 = 52, logo verdadeira. Supondo n ≥ 5
e 2n > n2, temos, multiplicando a desigualdade por 2, 2 · 2n > 2 · n2, ou 2n+1 > 2n2. Enfim,
2n2 > (n + 1)2 = n2 + 2n + 1, pois 2n2 − n2 − 2n − 1 = n2 − 2n − 1 = (n − 1)2 − 2 > 0 equivale a
(n− 1)2 > 2, o que é evidente, pois n ≥ 5.
3. Uma Progressão Geométrica com primeiro termo a1 e razão q (q 6= 0 e q 6= 1) é uma sequência
numérica dada por an+1 = an · q se n ≥ 1 .
Por indução sobre n, verifiquemos as relações:
(a) an = a1qn−1 , n ≥ 1;
(b) Se Sn = a1 + a2 + · · ·+ an , então Sn = a1 1− q
n
1− q ;
Em particular, vale 1 + x+ x2 + x3 + ·+ xn = 1− x
n+1
1− x , n ≥ 1 , x 6= 1 .
(a) A expressão dada vale para n = 1, pois q0 = 1. Supondo n ≥ 1, temos an+1 = anq = (a1qn−1)q,
isto é, an+1 = a1qn.
(b) Para a soma dos termos da PG, começamos observando que, multiplicando por q a soma, vem:
Sn = a1+a2+ · · ·+an ⇒ Snq = a1q+a2q+ · · ·+anq = a2+a3+ · · ·+an+anq. Subtraindo membro
a membro, vem Sn − Snq = a1 − anq, ou Sn(1− q) = a1 − anq, donde Sn = a1 − anq1− q = a1
1− qn
1− q .
Na realidade, fizemos um rascunho para melhor perceber a fórmula da soma. Ainda é necessária uma
prova formal por indução! Vamos lá. Para n = 1, tudo bem, pois S1 = a1. Para a etapa indutiva, já
supondo n ≥ 1, temos: Sn+1 = Sn + an+1 = a1 − anq1− q + an+1 =
a1 − an+1q
1− q .
Indução Finita 15
Atividade-proposta 2.4
1. Use o teorema da Indução Finita para verificar as relações.
(a)
1
1 · 2 +
1
2 · 3 + · · ·+
1
n(n+ 1)
=
n
n+ 1
, n ≥ 1;
(b) 13 + 23 + · · ·+ n3 = (1 + 2 + · · ·+ n)2, n ≥ 1 ;
(c) 1.2 + 2.3 + · · ·+ n(n+ 1) = n(n+ 1)(n+ 2)
3
.
2.[TARSKI] Aponte a falha da seguinte �demonstração�.
Proposição Se E é um conjunto com n elementos (n ≥ 1), então os elementos de E são todos iguais.
Demonstração. O resultado sendo válido para n = 1, suponhamos n ≥ 1 e a afirmação verdadeira
para conjuntos com n elementos. Seja En+1 = {x1, . . . , xn+1} um conjunto qualquer com n + 1
elementos; como os conjuntos {x1, x2, . . . , xn} e {x2, x3, . . . , xn+1} têm n elementos, segue da hipótese
que x1 = x2 = . . . = xn e x2 = x3 = . . . = xn+1, donde a igualdade entre todos os elementos de En+1.
Pelo Teorema da Indução Finita, vale o resultado para todo n ≥ 1.
3. Ache uma fórmula para cada uma das seguintes somas.
(a) 2 + 4 + · · ·+ 2n;
(b) 2 + 4 + 8 + · · ·+ 2n
4. Uma vitória régia encontra-se em um tanque de água. Sabendo que ela dobra de área a cada dia,
e que, no final de 20 dias, ela ocupará toda a superfície do tanque, em qual dia ela ocupará a metade
da superfície do tanque?
2.5 Teorema da Indução Finita (2
a
forma)
O método da indução que aplicamos até aqui, parte de uma posição inicial n0 ∈ N e procura validar
as expressões subsequentes passando de uma posição para a posição consecutiva [n → (n + 1)]. Há
uma outra forma desse método que, após a verificação do índice de partida n0, procura validar uma
posição supondo válidas todas as posições anteriores!
Teorema Seja P (n) uma sentença aberta associada ao número natural n ≥ n0, com n0 natural.
Suponhamos que:
(i) P (n0) é verdade;
(ii) Se n > n0 e, para cada inteiro k, n0 ≤ k < n, se a validade de P (k) implicar na validade de P (n),
então P (n) é verdade para todo n ≥ n0.
A demonstração é uma adaptação da indução já vista. Seja S = {n ∈ N ; n ≥ n0 e P (n) falsa}.
Se S 6= φ e m = minS, então m 6= n0; como m é mínimo, então vale P (k) para cada k verificando
n0 ≤ k < m. Então, por (ii), P (m) é verdadeira. Contradição.
Exemplo Seja a sequência (an) dada por a1 = 1, a2 = 3 e an = an−1 + an−2 para todo n ≥ 3. Na
realidade, (an) é uma sequência definida por recorrência. Mostrar que an < (1/4)n, n ≥ 1.
Temos a1 = 1 < (7/4), a2 = 3 < (7/4)2 = (49/16); se n ≥ 3 e supondo a relação válida para todo
1 ≤ k < n, vem an = an−1 + an−2 < (7/4)n−1 + (7/4)n−2 = (7/4)n−2((7/4) + 1) = (7/4)n−2(11/4);
enfim, an < (7/4)n−2(49/16) = (7/4)n.
16 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
2.6 Recorrência
Uma definição por recorrência para uma certa expressão En, associada ao inteiro n ≥ a, é uma
aplicação interessante do método da indução. Por exemplo, basta definir a expressão Ea e mostrar
como obter En+1 a partir de En, para todo n ≥ a. Uma definição semelhante pode ser feita com o
auxílio de termos iniciais, digamos E1, E2, . . . , Er e a informação para obter os termos posteriores.
Exemplo 2.7
1. Para definir a função fatorial de n ∈ N, f(n) =n!, podemos usar a recorrência:
f(0) = 1 e f(n+ 1) = (n+ 1)f(n), isto é, 0! = 1 e (n+ 1)! = (n+ 1)n! para todo n ≥ 0.
Assim, f(6) = 6·f(5) = 6·5·f(4) = 6·5·4·f(3) = 6·5·4·3·f(2) = 6·5·4·3·2·f(1) = 6·5·4·3·2·1·f(0).
Assim 6! = 720.
2. Consideremos a recorrência an = an−1 + n, onde a0 = 1. Para calcular uma expressão para an,
observemos que an − an−1 = n, donde, somando,
n∑
j=1
(aj − aj−1) =
n∑
j=1
j
Ora, a soma do primeiro membro dá an − a0 = an − 1, donde an = 1 + n(n+ 1)2 .
3. [Potência de números inteiros]
Para definir as potências de um número inteiro an, com n ∈ N, vamos proceder por recorrência.
Pondo a1 = a e a0 = 1, se 6= 0, e supondo an definido, tomemos an+1 = an · a.
Usando indução, podemos verificar as propriedades usuais das potências.
Dados os inteiros a, b,m, n, com m > 0, n > 0, temos
(a) am · an = am+n;
(b) (am)n = amn;
(c) (a · b)n = an · bn
Verifiquemos (a). Fixando a e m arbitrariamente, usemos indução sobre n.
Se n = 1, então, pela definição dada, temos am · a1 = am · a = am+1. Por outro lado, supondo que
am · an = am+n, temos que
am · an+1 = am · (an · a) = (am · an) · a = am+n · a = am+n+1,
donde o resultado, pelo teorema da indução.
Pratique um pouco! Complete a demonstração de (b) e (c), procedendo como fizemos acima.
Atividade-proposta 2.8
1. Considere a sequência recorrente an+1 = 2an + 1, n ≥ 1, dado a1 = 1. Examine alguns termos
para perceber a lei de formação e prove seu prognóstico com o teorema da indução.
2. Uma função g : N −→ N é definida recursivamente por g(1) = 2 e g(n) = 2 g(n−1) se n ≥ 2.
Calcule g(4).
3. [A pizza de Steiner] Determine o número máximo Rn de regiões em que n retas dividem o plano.
Sugestão. Verifique que Rn = Rn−1 + n, n ≥ 1.
Selecionamos, a seguir, três grupos de aplicações, que ilustram o uso da metodologia indutiva e
alguns resultados surpreendentes: (I) Números binomiais e o Binômio de Newton; (II) Sequência de
Fibonacci; (iii) A Torre de Hanoi.
Cicero Gomes
Realce
Indução Finita 17
2.9 Números binomiais
Exemplo motivador Suponhamos uma urna contendo 5 bolas distintas, rotuladas como a,b,c,d,e.
Quantos são os agrupamentos de 3 bolas, retiradas sucessivamente e sem reposição? Tais agrupa-
mentos são chamados de arranjos simples de 5 elementos tomados 3 a 3, notados A35, cujo cálculo
não oferece maiores dificuldades: A35 = 5 × 4 × 3 = 60. Olhando melhor a distribuição desses
agupamentos, encontramos 10 formações básicas e, para cada uma, 6 permutações, totalizando os
10 × 6 = 60 arranjos. A tabela abaixo ilustra a disposição considerada; representamos apenas as 6
permutações da primeira coluna; escreva as demais, para treinar.
abc abd abe acd ace ade bcd bde bce cde
acb
bac
bca
cab
cba
Se convencionarmos identificar, em cada coluna, as respectivas permutações com cada agrupamento
básico da primeira linha, isto é, não levar em conta a ordenação de cada permutação, nosso quadro
ficará, apenas, com 10 agrupamentos, que correspondem aos subconjuntos de 3 elementos formados
a partir do conjunto de 5 elementos {a, b, c, d, e}. Esses 10 agrupamentos são as combinações
simples de 5 elementos, tomados 3 a 3 e notados C35 ou
(
5
3
)
; nesta segunda notação, são denominados
números binomiais de 5 sobre 3.
Representando por 3! = 1× 2× 3 = 6 as permutações de cada coluna, temos, então, por definição:
3!C35 = A
3
5, ou C
3
5 =
A35
3!
=
5× 4× 3
6
=
60
6
= 10
Mais geralmente, partindo de um conjunto com n elementos, para cada 1 ≤ k ≤ n, indicaremos:
Akn = n(n− 1)(n− 2) · · · (n− k + 1) =
n!
(n− k)!
Pn = Ann = n! = n(n− 1)(n− 2) · · · 3.2.1
Ckn =
(
n
k
)
=
Akn
k!
=
n!
k!(n− k)! ; por extensão, escrevemos: 0! = 1, 1! = 1,
(
n
0
)
=
(
n
n
)
= 1
Primeiras propriedades
(1) Complementaridade ou simetria:
(
n
n− k
)
=
(
n
k
)
(2) Relação de Stiefel:
(
n− 1
k
)
+
(
n− 1
k − 1
)
=
(
n
k
)
, onde 1 ≤ k ≤ n.
A igualdade (1) segue direto da definição. Quanto a (2), temos:(
n− 1
k
)
+
(
n− 1
k − 1
)
=
(n− 1)!
k!(n− k − 1)! +
(n− 1)!
(k − 1)!(n− k)! =
(n− 1)!
(n− k − 1)!(k − 1)!
(
1
k
+
1
n− k
)
, donde
o resultado.
(3) Dados os inteiros n e k, com 0 ≤ k ≤ n, o coeficiente binomial
(
n
k
)
é um número inteiro.
De fato, por indução sobre n, o resultado é evidente para n = 1. Supondo válido pra n, temos(
n+1
0
)
=
(
n+1
n+1
)
= 1, logo inteiros; se 1 ≤ k ≤ n, segue da relação de Stifel (n+1k ) = ( nk−1) + (nk), logo
inteiro, pela hipótese de indução.
18 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
2.10 O triângulo de Pascal
Vamos dispor os números binomiais em linhas e colunas, como indicado a seguir, usando sistemati-
camente a relação de Siefel.
n
(
n
0
) (
n
1
) (
n
2
) (
n
3
) (
n
4
) (
n
5
) (
n
6
) (
n
7
) (
n
8
) (
n
9
) (
n
10
)
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
7 1 7 21 35 35 21 7 1
8 1 8 28 56 70 56 28 8 1
9 1 9 36 84 126 126 84 36 9 1
10 1 10 45 120 210 252 210 120 45 10 1
Como veremos a seguir, há um grande número de propriedades binomiais �escondidas� no triângulo.
Por exemplo, a propriedade complementar (1) significa que dois elementos de uma mesma linha,
equidistantes dos extremos, são iguais.
2.11 O binômio de Newton
Considerando sucessivas potências da soma a+ b de dois números inteiros:
(a+ b)1 = a+ b
(a+ b)2 = a2 + 2ab+ b2
(a+ b)3 = a3 + 3a2b+ 3ab2 + b3
(a+ b)4 = a4 + 4a3b+ 6a2b2 + 4ab3 + b4
observamos que os coeficientes dos segundos membros correspondem às linhas do triângulo de Pascal
(veja acima!). Tal fato também não passou desapercebido por Newton que sistematizou as potências,
inclusive generalizando para o caso de expoente não-inteiro,o que fornece (sua) série binomial!
Teorema Dados a e b inteiros e n ∈ N∗, temos
(a+ b)n = an +
(
n
1
)
an−1b+
(
n
2
)
an−2b2 + · · ·+ ( nn−1)abn−1 + bn
A demonstração, por indução sobre n, usa, essencialmente, a relação de Stiefel. O caso n = 1 sendo
evidente, suponhamos a expressão válida para n ≥ 1 e examinemos o expoente n+ 1:
(a+ b)n+1 = (a+ b)(a+ b)n = a · (a+ b)n + b · (a+ b)n; calculando cada parcela:
a · (a+ b)n = an+1 + (n1)anb+ (n2)an−1b2 + · · ·+ ( nn−1)a2bn−1 + (nn)abn
b · (a+ b)n = anb+ (n1)an−1b2 + · · ·+ ( nn−2)a2bn−1 + ( nn−1)abn + bn+1
Somando membro a membro as duas últimas igualdades e usando a relação de Stiefel, vemos que
vale (a+ b)n+1.
Corolário
n∑
k=0
(
n
k
)
= 2n
Basta fazer a = b = 1 no binômio. Em particular, recuperamos o bem conhecido resultado sobre o
número de subconjuntos um conjunto de n elementos. Observe que a expressão dada é a soma dos
elementos da linha de ordem n+ 1.
Indução Finita 19
Atividade-proposta 2.12
1. Verificar a identidade
n∑
k=0
(−1)k
(
n
k
)
= 0. Sugestão. Escolher a = 1 e b = −1 no binômio.
2. Estabelecer a identidade das diagonais (depois de uma análise cuidadosa do triângulo de Pascal):(
m
0
)
+
(
m+ 1
1
)
+
(
m+ 2
2
)
+ · · ·+
(
m+ n
n
)
=
(
m+ n+ 1
n
)
3. Verificar a identidade das colunas (depois de uma análise cuidadosa do triângulo de Pascal):(
m
m
)
+
(
m+ 1
m
)
+ · · ·+
(
n
m
)
=
(
n+ 1
m+ 1
)
Aplicação Se S =
n∑
k=1
k(k + 1) = 2
n∑
k=1
(
k + 1
2
)
, então S = 2
(
n+ 2
3
)
= n(n+ 1)(n+ 2)/3.
4. [Absorção] Verifique a igualdade k
(
n
k
)
= n
(
n− 1
k − 1
)
, 1 ≤ k ≤ n.
5. Verifique as igualdades:
(a)
n∑
k=1
k
(
n
k
)
= n2n−1 (b)
n∑
k=0
1
k + 1
(
n
k
)
=
1
n+ 1
(
2n+1 − 1)
6. Mostrar que, se m e n são inteiros positivos, então
(m+ n)!
(m+ n)m+n
<
m!
mm
n!
nn
2.13 Sequênciade Fibonacci
A sequência de Fibonacci é uma sequência de números naturais, definida por recorrência pelas
relações:
f1 = f2 = 1; fn = fn−1 + fn−2, n ≥ 3.
Tais relações permitem obter os termos f = {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, . . .}
Possuindo notáveis propriedades aritméticas, a sequência possui inúmeras interpretações, dentre as
quais a de Leonardo de Pisa, seu grande estudioso:
Um casal de coelhos recém-nascidos foi posto em um local cercado. A cada mês, um casal de
coelhos produz outro casal; um casal começa a procriar dois meses após o seu nascimento. Quantos
casais estarão presentes após um ano? Seguindo o modelo de procriação enunciado, temos a tabela:
mês n
◦
casais mês anterior n
◦
casais recém-nasc total
1 0 1 1
2 1 0 1
3 1 1 2
4 2 1 3
5 3 2 5
6 5 3 8
7 8 5 13
8 13 8 21
9 21 13 34
10 34 21 55
11 55 34 89
12 89 55 144
20 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
Fórmula de Binet Essa relação permite achar o termo geral da sequência, sem recorrer aos termos
anteriores. A idéia original é encontrar progressões geométricas un = qn, q 6= 0, que verificam a
recorrência dada: un = un−1+un−2, donde qn = qn−1+ qn−2, ou q2 = q+1 = 0, q2− q−1 = 0, cujas
raizes são α =
1 +
√
5
2
e β =
1−
√
5
2
. Assim, fn = aαn + bβn satisfaz a recorrência, desde f1 = 1 e
f2 = 1, o que permite achar a e b: a = 1/
√
5 e b = −1/√5, donde, a expressão procurada:
fn =
αn − βn√
5
=
(
1 +
√
5
2
)n
−
(
1−
√
5
2
)n
√
5
Observemos as simplificações que devem ocorrer com todas essas raizes de 5, para resultar gentis
números inteiros!
EXEMPLO 2.14
1. Verifiquemos que f1 + f2 + · · ·+ fn = fn+2 − 1.
Temos as igualdades sucessivas:
f1 = f3 − f2
f2 = f4 − f3
f3 = f5 − f4
· · ·
fn−1 = fn+1 − fn
fn = fn+2 − fn+1
Somando membro a membro, segue f1 + f2 + · · ·+ fn = fn+2 − 2, donde o resultado, pois f2 = 1.
2. Dados n ≥ 2, m ≥ 1, verificar que fn+m = fn−1fm + fnfm+1.
Usemos indução sobre m (n estando arbitrariamente fixado). Para m=1, temos
fn+1 = fn−1f1 + fnf2 = fn−1 + fn, relação válida. Suponhamos, a seguir, a relação válida para
m = 1, 2, . . . , k e verifiquemos que ainda vale para m = k + 1. Temos
fn+k = fn−1fk + fnfk+1
fn+(k−1) = fn−1fk−1 + fnfk
fn+k + fn+(k−1) = fn−1(fk + fk−1) + fn(fk+1 + fk)
fn+(k+1) = fn−1fk+1 + fnfk+2
. Essa última expressão comprova a validade.
3. Para comprovar que f2n + f
2
n+1 = f2n+1, a fórmula de Binet é mais significativa:
partindo de fn =
1√
5
(αn − βn), vem f2n =
1
5
(α2n + β2n − 2(−1)n); analogamente, encontramos
f2n+1 =
1
5
(α2n+2 + β2n+2 − 2(−1)n+1). Enfim, f2n + f2n+1 =
1√
5
(α2n+1 + β2n+1) = f2n+1
Atividade-proposta 2.15
1. Seja (fn) a sequência de Fibonacci; verifique que:
(a) f2 + f4 + · · ·+ f2n = f2n+1 − 1 (b) f21 + f22 + · · ·+ f2n = fnfn+1
2. Seja A =
(
1 1
1 0
)
. Mostre que An =
(
fn+1 fn
fn fn−1
)
, n ≥ 2.
Usando determinantes na relação anterior, obter a identidade de Cassini:
fn−1fn+1 − f2n = (−1)n, n ≥ 2.
Indução Finita 21
3.[Lucas]
Seja dn =
(
n−1
0
)
+
(
n−2
1
)
+
(
n−3
2
)
+ · · · =∑k (n−1−kk ) uma diagonal ascendente do triângulo de Pascal,
onde k ≥ 0 é limitado pela condição n− 1− k ≤ k, isto é, o maior inteiro k =
[
n− 1
2
]
. Mostre que
dn = fn .
2.16 Torre de Hanoi
Trata-se de um jogo idealizado pelo matemático francês Edouard Lucas, em 1882. Consiste de n
discos de diâmetros diferentes com um furo no seu centro, e uma base onde estão fincadas três hastes.
Inicialmente, os discos estão enfiados numa haste de modo que nenhum disco esteja sobre um outro de
diâmetro menor. O objetivo é mover todos os discos, da haste original a uma outra, prédeterminada,
com as seguintes regras:
a) somente um disco pode ser movido de cada vez;
b) um disco maior nunca pode ser posto sobre um disco menor.
Seja T (n) o número mínimo para a trasnferência dos discos. Brincando um pouco, não é difícil ver
que T (1) = 1, T (2) = 3, T (3) = 7, T (4) = 15... Mas qual seria a forma genérica de T (n)?
Podemos usar um raciocínio indutivo: supondo conhecido um processo para obter T (n − 1), então
saberemos obter T (n). A idéia é muito simples: transferimos (n− 1) discos de uma pilha para outra,
deixando o maior disco em sua haste inicial. Feito isso, deslocamos o disco maior para sua haste final,
o que libera a haste inicial. Enfim, trazemos os n − 1 discos sobre o disco maior. Portanto, fizemos
quantos movimentos para transferir os n discos? É só contar: T (n−1)+1+T (n−1) = 1+2T (n−1).
Assim, obtemos T (n) = 1 + 2T (n − 1), com n ≥ 2, e T (1) = 1. Ora, na Atividade-proposta 2.8,
exercício 1, solicitamos uma fórmula para a sequência recorrente acima. Esperamos que o valor correto
T (n) = 2n − 1, n ≥ 1, tenha sido obtido!!
Uma lenda apocalíptica acompanha o jogo. No início dos tempos, sacerdotes de um templo oriental
deveriam transferir 64 discos de ouro puro ao redor de 3 colunas de diamante. Quando os 64 discos
fossem transferidos, o mundo acabaria...! Pois bem, o número mínimo para transferirmos 64 discos
é T = 264 − 1, que é um número meio grande. Se cada movimento durar 1 segundo, como em
cada século, há 3.110.400.000 segundos, verifique que serão necessários 5, 93067× 109 séculos para a
transferência!
22 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
2.17 RESPOSTAS DAS ATIVIDADES PROPOSTAS
2.4
1(a) A relação dada
1
1 · 2 +
1
2 · 3 + · · ·+
1
n(n+ 1)
=
n
n+ 1
, n ≥ 1 (*), vale para n = 1, pois 1/2 = 1/2.
Agora, supondo (*) verdadeira na posição n, verifiquemos sua validade para n+ 1:
1
1 · 2 +
1
2 · 3 + · · ·+
1
n(n+ 1)
+
1
(n+ 1)(n+ 2)
=
n
n+ 1
+
1
(n+ 1)(n+ 2)
Efetuando o segundo membro:
n(n+ 2) + 1
(n+ 1)(n+ 2)
=
n2 + 2n+ 1
(n+ 1)(n+ 2)
=
n+ 1
n+ 2
Assim,
1
1 · 2 +
1
2 · 3 + · · · +
1
n(n+ 1)
+
1
(n+ 1)(n+ 2)
=
n+ 1
n+ 2
, donde a validade em n + 1 e, por
indução, para todo n ≥ 1.
Há um método alternativo, que usa a chamada simplificação telescópica. Retomando (*):
1
1.2
= 1− 1
2
1
2.3
=
1
2
− 1
3
.
.
.
1
n(n+ 1)
=
1
n
− 1
n+ 1
Somando membro a membro:
1
1 · 2 +
1
2 · 3 + · · ·+
1
n(n+ 1)
= 1− 1
n+ 1
=
n
n+ 1
(b) A igualdade sendo válida para n = 1 (pois 1 = 1), podemos logo supor que
13 + 23 + · · ·+ n3 = (1 + 2 + · · ·+ n)2, n ≥ 1 ; na posição consecutiva n+ 1, temos
13 + 23 + · · ·+ n3 + (n+ 1)3 = (1 + 2 + · · ·+ n)2 + (n+ 1)3 (**) Para avaliar o segundo membro de
(**), consideremos
(1 + 2 + · · ·+ n+ (n+ 1))2 = (1 + 2 + · · ·+ n)2 + (n+ 1)2 + 2(1 + 2 + · · ·n)(n+ 1) =
= (1 + 2 + · · ·+ n)2 + (n+ 1)2 + n(n+ 1)2 = (1 + 2 + · · ·+ n)2 + (n+ 1)3
Juntamente com (**), fica, então, validada a expressão em n+ 1.
(c) Se 1.2 + 2.3 + · · ·+ n(n+ 1) = n(n+ 1)(n+ 2)
3
, então
1.2+2.3+ · · ·+n(n+1)+(n+1)(n+2) = n(n+ 1)(n+ 2)
3
+(n+1)(n+2) =
(n+ 1)(n+ 2)(n+ 3)
3
.
2. O argumento usado não permite que E1 ⇒ E2, isto é, se os conjuntos com um só elemento possuem
todos os elementos iguais, nada podemos concluir, então, para os conjuntos com dois elementos. O
enunciado exibe uma situação em que, de fato, E2 ⇒ E3, só que a afirmação para E2 é falsa.
3. (a) Temos 2 + 4 + · · ·+ 2n = 2(1 + 2 + · · ·n) = n(n+ 1).
(b) Trata-se da soma de uma PG, com a1 = 2, an = 2n, q = 2. A expressão
a1 − anq
1− q nos dá 2
n+1−2.
4. No 19
◦
dia.
2.8
1. Partindo de an+1 = 2an + 1, n ≥ 1, a1 = 1, e escrevendo alguns termos:
a2 = 2a1 + 1 = 3 ou a2 − a1 = 2
a3 = 2a2 + 1 = 7 ou a3 − a2 = 22
a4 = 2a3 + 1 = 15 ou a4 − a3 = 23
a5 = 2a4 + 1 = 3 ou a5 − a4 = 24. Somando membro a membro as colunas da direita, obtemos
Indução Finita 23
an − 1 = 2 + 22 + · · ·+ 2n−1, donde an = 1 + 2 + 22 + · · ·+ 2n−1 = 2n − 1, n ≥1.
Observação Uma outra solução seria propor a validade da fórmula an = 2n − 1, n ≥ 1, e verificá-la
por indução. Como a1 = 2− 1 = 1, e, por definição, an+1 = 2an + 1, vemos que
an+1 = 2(2n − 1) + 1 = 2n+1 − 1, donde o resultado.
2. Temos, sucessivamente: g(4) = 2g(3); g(3) = 2g(2); g(2) = 2g(1). Como g(1) = 2, podemos
substituir, voltando: g(2) = 22 = 4; g(3) = 24 = 16; g(4) = 216 = 65.536.
3. Se an é o número procurado, então é claro que a1 = 2. Agora, partindo de n− 1 retas já traçadas
e acrecentando uma n-ésima reta, a condição ótima será que essa nova reta interceptará as n − 1
retas já construídas em n− 1 pontos [basta considerar que a nova reta não é paralela a nenhuma das
anteriores e que intercepta todas em diferentes pontos]; esse procedimento adiciona n novas regiões,
isto é, an = an−1 + n, n ≥ 1 e a1 = 2. Enfim, use o Exemplo 2.7-2 e conclua que an = 1 + n(n+ 1)2 .
2.12
2. Na maioria das identidades propostas neste item, a primeira dificuldade é vencer a profusão de
índices envolvidos nas notações: é o preço da generalidade corretamente formulada. O resultado
abaixo, codificado em bom português, seria algo assim: �A soma de um número qualquer de
elementos consecutivos de uma mesma diagonal, a partir de um elemento da primeira coluna, é igual
ao elemento que se encontra na mesma coluna do último elemento considerado e imediatamente
abaixo deste�.
Por exemplo (acompanhe no triângulo de Pascal):
1 + 4 + 10 + 20 = 35, ou
(
3
0
)
+
(
4
1
)
+
(
5
2
)
+
(
6
3
)
=
(
7
3
)
Para confirmar a lei de formação dos binomiais, usemos a relação de Stiefel. Logo no início, o que
seria
(
3
0
)
+
(
4
1
)
? Como
(
3
0
)
=
(
4
0
)
= 1, vamos escrever
(
4
0
)
+
(
4
1
)
=
(
5
1
)
; daí para a frente é só efetuar:(
5
1
)
+
(
5
2
)
=
(
6
2
)
;
(
6
2
)
+
(
6
3
)
=
(
7
3
)
.
No caso geral, procederemos como acima.(
m
0
)
=
(
m+ 1
0
)
;
(
m+ 1
0
)
+
(
m+ 1
1
)
=
(
m+ 2
1
)
;
(
m+ 2
1
)
+
(
m+ 2
2
)
=
(
m+ 3
2
)
; · · · ;(
m+ n
n− 1
)
+
(
m+ n
n
)
=
(
m+ n+ 1
n
)
3. A propriedade se escreve: �A soma de um número qualquer de elementos começando de uma
coluna, a partir do primeiro, é igual ao elemento que se encontra na interseção da linha e da coluna
imediatamente posteriores aquelas a que pertence o último dos elementos considerados.�
Acompanhe, por exemplo, no triângulo:
1 + 3 + 6 + 10 = 20, ou
(
2
2
)
+
(
3
2
)
+
(
4
2
)
+
(
5
2
)
=
(
6
3
)
Tal como no caso das diagonais, usaremos, sucessivamente a relação de Stiefel, partindo de(
2
2
)
+
(
3
2
)
=
(
3
3
)
+
(
3
2
)
=
(
4
3
)
e prosseguindo até o último agupamento.
Pratique um pouco. Verifique o caso geral, tal como fizemos acima.
Aplicação. Para calcular S =
n∑
k=1
k(k+1), observemos logo que k(k+1) = 2
(
k+1
2
)
; assim, tendo em
conta a identidade das colunas:
S = 2
n∑
k=1
(
k + 1
2
)
= 2
(
n+ 2
3
)
= n(n+ 1)(n+ 2)/3.
24 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
4. A validade é imediata, partindo de
(
n
k
)
=
n!
k!(n− k)! ; temos, para 1 ≤ k ≤ n:
k
(
n
k
)
=
n!
(k − 1)!(n− k)! = n
(n− 1)!
(k − 1)!(n− k)! = n
(
k − 1
n− 1
)
5. (a) Tendo em conta a absorção acima, vale:
n∑
k=1
k
(
n
k
)
= n
n∑
k=1
(
n− 1
k − 1
)
Por outro lado, o segundo membro acima pode ser escrito n
n−1∑
k=0
(
n− 1
k
)
= n2n−1, pois
n∑
k=0
(
k
n
)
= 2n. Em definitivo,
n∑
k=1
k
(
n
k
)
= n2n−1.
(b) Sempre usando a absorção
(
n+ 1
k + 1
)
=
n+ 1
k + 1
(
n
k
)
, temos que
n∑
k=0
1
k + 1
(
n
k
)
=
n∑
k=0
1
n+ 1
(
n+ 1
k + 1
)
=
1
n+ 1
n∑
k=0
k + 1
n+ 1
. Ora,
n∑
k=0
(
n+ 1
k + 1
)
= 2n+1 − 1, pois(
n+ 1
0
)
= 1, donde, vale bem
n∑
k=0
1
k + 1
(
n
k
)
=
1
n+ 1
(
2n+1 − 1).
6. Observemos que a expansão do binômio (m + n)m+n é formada de m + n + 1 termos da forma(
m+ n
k
)
mm+n−knk; em particular, um desses termos, quando k = n, vale
(
m+ n
n
)
mmnn, que é
menor do que (m+ n)m+n, isto é,
(m+ n)!
m!n!
mmnn < (m+ n)m+n, donde o resultado solicitado.
2.15
1. (a)Imitando a solução do Exemplo 2.14-1, temos;
f2 = f3 − f1
f4 = f5 − f3
f6 = f7 − f5 · · ·
f2n = f2n+1 − f2n−1.
Somando membro a membro, vem f2 + f4 + · · ·+ f2n = f2n+1 − f1 = f2n+1 − 1.
(b) Procedendo como acima:
f21 = f1f1
f22 = f2f2 = f2(f3 − f1)
f23 = f3f3 = f3(f4 − f2) · · ·
f2n = fnfn = fn(fn+1 − fn−1)
Somando membro a membro, vem a conclusão f21 + f
2
2 + · · ·+ f2n = fnfn+1.
2. Seja a matriz A =
[
1 1
1 0
]
; temos A2 =
[
1 1
1 0
] [
1 1
1 0
]
=
[
2 1
1 0
]
=
[
f3 f2
f2 f1
]
.
Partindo de An =
[
fn+1 fn
fn fn−1
]
, vem An+1 =
[
fn+1 fn
fn fn−1
] [
1 1
1 0
]
, logo
An+1 =
[
fn+1 + fn fn+1
fn + fn−1 fn
]
=
[
fn+2 fn+1
fn+1 fn
]
. Por indução, vale o resultado para cada n ≥ 2.
A aplicação de Cassini segue de: det(An) = (detA)n, isto é, fn+1 · fn−1 − f2n = (−1)n.
Indução Finita 25
3. Observe com atenção o triângulo de Pascal: os termos diagonais ascendentes são
d1 =
(
0
0
)
= 1
d2 =
(
1
0
)
= 1
d3 =
(
2
0
)
+
(
1
0
)
= 1 + 1 = 2
d4 =
(
3
0
)
+
(
2
1
)
= 1 + 2 = 3
d5 =
(
4
0
)
+
(
3
1
)
+
(
2
2
)
= 1 + 3 + 1 = 5
Verifiquemos, então, que dn+ dn+1 = dn+2, n ≥ 1. Para tal, basta usar a relação de Stiefel e agrupar
convenientemente as parcelas:
dn + dn+1 =
[(
n−1
0
)
+
(
n−2
1
)
+
(
n−3
2
)
+ · · · ]+ [(n0)+ (n−11 )+ (n−22 )+ · · · ]
=
(
n
0
)
+
[(
n−1
0
)
+
(
n−1
1
)]
+
[(
n−2
1
)
+
(
n−2
2
)]
+ · · ·
=
(
n
0
)
+
(
n
1
)
+
(
n−1
2
)
+ · · ·
=
(
n+1
0
)
+
(
n
1
)
+
(
n−1
2
)
+ · · · = dn+2
Divisibilidade e Algoritmo Euclidiano da Divisão 27
CAPÍTULO 3
DIVISIBILIDADE
ALGORITMO EUCLIDIANO DA DIVISÃO
Não há dúvida sobre o surgimento de símbolos pictográficos expressando
numerais abstratos. Também está bem firmado (em cerca de 3100AC)
que a contagem abstrata é precursora da origem da escrita.
DAMEROW, P. The material culture of calculation.
Berlin: Max Planck Institut, 1999, p.12 et passim.
Objetivos do Capítulo 3
(a) Estabelecer relação de divisibilidade de números inteiros;
(b) Descrever o algoritmo da divisão euclidiana (existência e unicidade);
(c) Explicitar as propriedades da divisão de inteiros;
(d) Estabecer a construção de sistemas de numeração, com ênfase no sistema binário e suas
aplicações;
(e) Descrever o algorimo de Euclides para o cálculo do mdc;
(f) Explicitar as propriedades do mmc;
(g) Aplicar a teoria a problemas elementares de contagem.
3.1 INTRODUÇÃO
Precursor do método axiomático, Euclides de Alexandria (c.330-275 AC) foi o primeiro matemático a
tratar a Geometria e a Aritmética como ciências dedutivas. Os Elementos, uma coleção de 13 livros,
apresentou os fatos matemáticos de sua época com notável rigor, descrevendo cada teoria a partir
de definições, postulados e axiomas, e seu ordenamento em teoremas, cujas demonstrações seguem
regras lógicas bem determinadas.
A Aritmética tem início no livro VII, onde, dentre inúmeros resultados, é usada sistematicamente a
chamada Divisão Euclidiana, algumas propriedades dos números primos (inclusive sua demonstração
sobre a infinidade de primos) e o algoritmo para o cálculo efetivo do mdc de dois inteiros.
Os Elementos são (a seguir à Bíblia), provavelmente, o livro mais reproduzido e estudadona história
do mundo ocidental.
28 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
3.2 DIVISIBILIDADE em Z
Dados dois números inteiros a e b, com a 6= 0, diremos que a divide b quando existir c ∈ Z tal que
b = a · c; neste caso, diremos também que a é um divisor de b, ou a é um fator de b ou, ainda, que
b é um múltiplo de a. Usaremos a notação a|b para indicar que a divide b e sua negação, por a 6 | b.
Observemos que a notação a|b nada tem a ver com frações.
Por exemplo, 2|0, 1|10, 4|4, 2|4; 36 | 4; 56 | 2; 56 | 11.
Se a|b (a 6= 0), então o inteiro c tal que b = a · c é unicamente determinado por essa condição, pois se
b = ac = ad, como a 6= 0, vem que c = d. O inteiro c é o quociente de b por a e denotado por c = b
a
.
Por exemplo,
0
2
= 0,
10
1
= 10,
4
4
= 1;
4
2
= 2.
3.3 Propriedades
(1) Sejam a, b ∈ Z∗ e c ∈ Z. Temos:
(i) 1|c; a|a e a|0;
(ii) se a|b e b|c, então a|c
O item (i) decorre das igualdades c = 1 · c, a = a · 1 e a · 0 = 0. No caso (ii), por hipótese, existem
x, y ∈ Z tais que b = ax e c = by, donde c = by = (ax)y = a(xy), ou a|c.
Em particular, todo número inteiro é divisível por 1 e, se não nulo, por si mesmo.
(2) Sejam a, b ∈ Z∗; se a|b, então |a| ≤ |b|.
Como existe um inteiro c tal que b = ac, a hipótese b 6= 0 exige c 6= 0, logo |c| ≥ 1, donde |a| |c| ≥ |a|,
isto é, |b| ≥ |a|.
Em particular, se a|1, então |a| ≤ 1, donde |a| = 1, ou a = ±1.
(3) Em N∗ a divisibilidade é uma relação de ordem, isto é, possui as propriedades:
(i) reflexiva: a|a;
(ii) transitiva: a|b, b|c ⇒ a|c;
(iii) anti-simétrica: a|b, b|a ⇒ a = b.
De fato, já vimos a validade de (i) e (ii) em Z∗. Quanto à antisimetria, se a, b, x, y são inteiros não
nulos e verificam a = bx e b = ay, então b = b(xy), donde xy = 1, logo, em N∗, x = y = 1 e a = b.
(4) Sejam os inteiros a, b, c, com c 6= 0.
Se c|a e c|b, então, para todos os inteiros α e β, vale c|(αa+ βb).
De fato, se a = cx e b = cy, então αa+ βb = α(cx) + β(cy) = (αx+ βy)c, donde o resultado.
Observação Dados os inteiros a, b, c, com c 6= 0, a condição c|(a + b) não acarreta c|a ou c|b. Por
exemplo, é claro que 2|(7 + 3), mas 26 | 7 nem 26 | 3.
Vale, entretanto, o seguinte resultado: se a 6= 0, a|(b+ c) e a|b, então a|c.
De fato, se b+ c = xa e b = ya, então ya+ c = xa, logo xa− ya = c, isto é, (x− y)a = c, donde a|c.
(5) Sejam os inteiros a, b, c, d, com a 6= 0 e c 6= 0.
Se a|b e c|d, então ac|bd.
Temos b = xa e d = cy, logo (bd) = (xy)(ac).
Em particular, se a|b, então ac|bc, para todo c ∈ Z∗.
Divisibilidade e Algoritmo Euclidiano da Divisão 29
3.4 Proposição
Se a 6= 0 e b 6= 0 são inteiros, e n ≥ 0 um número natural, verifiquemos as seguintes relações:
(a) (a− b)|(an − bn) e an − bn = (a− b) (an−1 + an−2b+ · · ·+ abn−2 + bn−1);
(b) (a+ b)|(a2n+1 + b2n+1) e a2n+1 + b2n+1 = (a+ b)(a2n − a2n−1b+ · · · − ab2n−1 + b2n
(c) (a+ b)|(a2n − b2n) e a2n − b2n = (a+ b)(a2n−1 − a2n−2b+ · · ·+ ab2n−2 − b2n−1
Observemos que a proposição solicita, em cada item, dois procedimentos: inicialmente, há que
verificar a divisibilidade solicitada; em seguida, exibir o quociente. A idéia é usar indução sobre n,
em todos os casos.
(a) A afirmação é verdade para n = 0, pois a − b divide a0 − b0 = 0. Suponhamos, agora, que
a− b|an − bn; escrevendo an+1 − bn+1 = aan − ban + ban − bbn = (a− b)an + b(an − bn), vemos que
a− b|an+1 − bn+1, usando a propriedade (4) do item anterior.
(b) Procedendo analogamente, a etapa indutiva resulta de
a2(n+1)+1 + b2(n+1)+1 = a2a2n+1 − b2a2n+1 + b2a2n+1 − b2b2n+1 = (a2 − b2)a2n+1 + b2(a2n+1 − b2n+1).
(c) Enfim, no caso (c), a etapa indutiva decorre das relações:
a2(n+1) + b2(n+1) = a2a2n − b2a2n + b2a2n − b2b2n = (a2 − b2)a2n + b2(a2n − b2n).
EXEMPLO 3.5
1. Se a e b são inteiros positivos para os quais
1
a
+
1
b
é um inteiro, então a = b. Além disso, mostre
que a = 1 ou a = 2.
De fato, a expressão
1
a
+
1
b
=
a+ b
ab
mostra que deve ser ab|a+ b; segue,então, que a|a+ b, donde a|b;
analogamente, b|a. Assim, concluimos que a = b. Voltando à primeira condição, temos 1
a
+
1
a
=
2
a
,
um inteiro, por hipótese, donde a|2 e a = 2 ou a = 1.
2. Ache todos os inteiros n ≥ 1 para os quais (n+ 1)|(n2 + 1).
Como n2 + 1 = [(n+ 1)− 1]2 + 1 = (n+ 1)2 − 2(n+ 1) + 2, vemos que (n+ 1)|(n2 + 1) ⇔ (n+ 1)|2,
donde n+ 1 = 1 (o que é impossível, pois n > 0) ou n+ 1 = 2, donde n = 1.
3. Para todo n ≥ 1, mostre que 3|22n − 1.
Podemos escrever: 22n− 1 = (22)n− 1 = 4n− 1 = (3+ 1)n− 1 = 3n+ (n1)3n−1+ · · ·+ ( nn−1)3+ 1− 1,
isto é, um múltiplo de 3.
4. Usando indução sobre n ≥ 1, verficar que 8|32n + 7.
A relação vale se n = 1, pois 32 + 7 = 9 + 7 = 16 é múltiplo de 8. Suponhamos
n ≥ 1 e a relação válida para n, isto é, 8|32n + 7, ou 32n + 7 = 8x. Podemos escrever
32n+2 + 7 = 9(32n) + 7 = 9(8x− 7) + 7 = 72x− 56, que é bem um múltiplo de 8.
5. Use as relações polinomiais a− b|an − bn, a+ b|a2n+1 + b2n+1 e a+ b|a2n − b2n para mostrar que
(a) 9|10n − 1; (b) 8|32n − 1; (c) 53|74n − 24n; (d) 6|52n+1 + 1
Temos: (a) 9 = 10− 1|10n − 1n = 10n − 1;
(b) 32n − 1 = (32)n − 1 = 9n − 1, logo 8 = 9− 1|9n − 1;
(c) 74n − 24n = (72)2n − (22)2n = 492n − 42n é múltiplo de 49 + 4 = 53;
(d) 6 = 5 + 1|52n+1 + 1.
30 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
6. Considere a sequência de Fibonacci (fn). Dados 1 ≤ m < n, se m|n então fm | fn.
Sugestão. Use a relação de (2.14-(2)), e verifique que fm|fqm.
Se m|n, seja q ∈ N tal que n = mq; para mostrar que fm|fqm, usaremos indução sobre q ≥ 1,
e a relação fn+m = fn−1fm + fnfm+1. O resultado sendo imediato pra q = 1, consideremos,
sucessivamente, n = m,n = 2m, · · · , n = (q − 1)m na relação anterior:
fm−1fm + fmfm+1 = f2m ⇒ fm|f2m
f2m−1fm + f2mfm+1 = f3m ⇒ fm|f3m
.
.
.
f(q−1)m−1fm + f(q−1)mfm+1 = fqm ⇒ fm|fqm
Atividade-proposta 3.6
1. Se possível, dê exemplos de números inteiros a, b, c, com a 6= 0, a < b e a < c, tais que a | bc, com
a 6 |b e a 6 |c.
2. Seja X um número natural de 2 dígitos e Y o número obtido de X quando são permutados seus
(dois) dígitos. Mostre que 9|Y −X e ache todos os inteiros X tais que |Y −X| = 18.
3. Para todo n ≥ 1, use o binômio de Newton para mostrar que n2|(n+ 1)n − 1 .
4. Mostre que 147 + 247 + 347 + 447 + 547 + 647 é múltiplo de 7.
5. Fixados a ≥ 2 e 0 < m ≤ n, mostre que am|an. Além disso, se m|n, então am − 1|an − 1.
6. Seja Nn um inteiro formado de n 1's consecutivos. Por exemplo, N3 = 111,N7 = 1111111. Se
1 ≤ m < n e m | n, então Nm | Nn.
Divisão Euclidiana 3.7
Exemplo motivador Para comparar (as medidas de) dois segmentos, associados aos números natu-
rais a e b, e tomando b como referência, podemos considerar os sucessivos segmentos b, 2b, 3b, · · · , qb,
onde, se a não é múltiplo de b, o segmento qb é o menor segmento que não ultrapassa a, isto
é, qb < a < (q + 1)b. Observemos que a existência de q está garantida pela propriedade arqui-
mediana [cf. 1.7 � Prop. C]. Assim, pondo r = a − qb, temos a = qb + r, com 0 ≤ r < b.
0 br 2br qbr r
a
(q+1)br
A interpretação acima, na realidade, é um poderoso algoritmo, denominado de Divisão Euclidiana,
que passaremos a considerar em toda sua aplicabilidade.
Teorema Dados a, b ∈ Z, com b 6= 0, existem inteiros q e r tais que a = bq + r, onde 0 ≤ r < |b|.
Além disso, os inteiros q e r são unicamente determinados pelas condições anteriores.
Faremos a demonstração em várias etapas.
10 caso: b > 0. Seja S = {x ∈ N ; x = a− bn, para algum n ∈ Z}.
Notemos que S é não vazio, pois para n = −|a|, temos a − bx = a + b|a| ≥ a + |a| ≥ 0; pela boa
ordem de N, existe r = min S e temos r ≥ 0 e r = a − bq, isto é, a = bq + r, onde q ∈ Z. Se, por
absurdo, b ≤ r, temos r = b + s, onde s ≥ 0 e como b > 0 teremos s < r, portanto s /∈ S; mas, por
outro lado, s = r − b = a− bq − b = a− b(q + 1), logo s ∈ S e chegamos a uma contradição!.
Cicero Gomes
Realce
Divisibilidade e Algoritmo Euclidianoda Divisão 31
20 caso: b < 0. Pelo caso anterior, existem inteiros q1, r1 tais que a = q1(−b) + r1 = b(−q1) + r1,
onde 0 ≤ r1 < −b = |b|. Portanto, basta escolher q = −q1 e r = r1.
30 caso. Unicidade do par (q,r). De fato, se (q1, r1) também verifica a = bq + r = b1q + r1, com
0 ≤ r ≤ |b| e 0 ≤ r1 ≤ |b|, teremos b(q − q1) = r1 − r, logo |b||q − q1| = |r1 − r|. Se r 6= r1, teremos
|q − q1| ≥ 1, logo |b|(q − q1) ≥ |b|, |r1 − r| ≥ |b| ; por outro lado, |r1 − r| < |b|. Contradição!
Nas condições do teorema acima, os números q e r são, respectivamente, denominados quociente e
resto da divisão euclidiana de a por b; observemos que b|a se, e só se, é nulo o resto r = 0.
EXEMPLO 3.8
1. Vamos calcular o quociente e o resto da divisão de a = ±680 por b = ±12 (4 casos!).
a) O caso mais simples (a = 680, b = 12) já é nosso velho conhecido: 680 = 12 · 56 + 8;
b) Se a = 680 e b = −12, a expressão anterior nos dá: 680 = (−12) · (−56) + 8, onde q = −56 e
r = 8 < |b| = 12;
c) Com a = −680 e b = 12, vem −680 = 12 · (−56) − 8. Atenção! Essa igualdade não representa
uma divisão euclidiana, pois o candidato a resto é negativo! Para contornar essa dificuldade,
vamos somar e subtrair b = 12 ao segundo membro: −680 = 12 · (−56)− 8− 12+12 = 12 · (−57)+4;
observe que r = 4 < b = 12
d) O último caso a = −680 e b = −12 pode ser formado de (c): −680 = 57(−12) + 4.
2. Para cada x ∈ R, a função maior inteiro contido em x é dada por:
se n ∈ Z e n ≤ x < n+ 1, então I(x) = [x] = n.
Se b > 0 é um inteiro, consideremos a divisão euclidiana a = qb+ r, 0 ≤ r < b. Temos q =
[a
b
]
.
De fato, temos
a
b = q +
r
b , onde
r
b é um número racional tal que 0 ≤ rb < 1. Segue, então,
q ≤ a
b
= q +
r
b
< q + 1, logo q =
[a
b
]
.
Aplicação Se 0 < b < a, então há q =
[a
b
]
múltiplos não nulos de b menores ou iguais a a. Por
exemplo, entre 1 e 1000, há [1000/7] = 142 inteiros divisíveis por 7.
3. Fixado um número natural m ≥ 2, todo inteiro n se escreve, de modo único, na forma n = mq+ r,
com 0 ≤ r < m, isto é, o resto pode assumir m possíveis valores distintos r = 0, 1, 2, · · · , (m − 1);
assim, os inteiros se dividem em m classes, cada uma com o valor de r correspondente. Por exemplo,
(a) m = 2; há 2 classes de inteiros: os da forma 2q (inteiros pares) e os da forma 2q + 1 (ímpares);
(b) m = 3; há 3 classes: inteiros da forma 3k, ou 3k + 1 ou 3k + 2;
(c) m = 4; há 4 classes: inteiros das formas 4q, 4q + 1, 4q + 2, 4q + 3.
4. Verificar que o quadrado de um inteiro é da forma 4k ou 4k + 1.
Basta observar cada uma das quatro classes do resto (divisão por 4): a = 4q ⇒ a2 = 16q2 = 4k;
a = 4q + 1 ⇒ a2 = (4q + 1)2 = 16q2 + 8q + 1 = 4K + 1;
a = 4q + 2 ⇒ a2 = (4q + 2)2 = 16q2 + 16q + 4 = 4Q;
a = 4q + 3 ⇒ a2 = (4q + 3)2 = 16q2 + 24q + 9 = 4t+ 1.
Em particular, todo quadrado perfeito impar é da forma 4k + 1.
Pratique um pouco! Mostre que nenhum termo da sequência 11, 111, 1111, ... é um quadrado
perfeito.
5. Verifique as relações, onde a ∈ Z: (a) a é par ⇐⇒ a2 é par;
(b) a é impar ⇐⇒ a2 é impar.
32 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
Se a = 2q é par, então a2 = 4q2 = 2k é par. Analogamente, se a = 2m + 1 é impar, então
a2 = 4m2 + 4m+ 1 = 2q + 1 é impar. Reciprocamente, se a2 é par, então não pode ser a impar, do
contrário, seria a2 impar, contra a hipótese; ora, se não pode ser a impar, é porque a é par, pois há
exatamente dois tipos disjuntos de classes de inteiros: a dos números pares e a dos números ímpares.
Analogamente, se a2 é impar, então a é impar.
Atividade-proposta 3.9
1. Em uma divisão de números naturais, o dividendo vale 802 e o quociente 14; encontre os possíveis
divisores e restos.
2. Mostre como, usando uma calculadora que só realiza as quatro operações, pode-se efetuar a
divisão euclidiana de dois números naturais em apenas três passos. Aplique esse processo para dividir
a = 12.615 por b = 58.
3. Determine quantos dos inteiros x tais que 1 ≤ x ≤ 1000 são divisíveis por 4, e quantos, verificando
100 ≤ x ≤ 999 são divisíveis por 5.
4. Use o algoritmo da divisão para verificar que:
(a) Todo inteiro ímpar é da forma 4k + 1 ou 4k + 3;
(b) O quadrado de um inteiro é da forma 3k ou 3k + 1;
(c) O cubo de um inteiro é da forma 9k, 9k + 1 ou 9k + 8.
5. Se o inteiro a não é divisível por 3, então a2 deixa resto 1 na divisão por 3. Conclua que, se
3|a2 + b2, então a e b são divisíveis por 3.
6. Mostre que o produto de k números naturais consecutivos é divisível por k!. Conclua que, para
todo n ∈ N: (i) 6|n(n+ 1)(n+ 2); (ii) 6|n(n+ 1)(2n+ 1).
3.10 Sistemas de numeração
O algoritmo da divisão fornece um método muito simples para a representação de inteiros em outras
bases de numeração que não a base decimal, com a qual estamos já acostumados. Com a expansão do
cálculo numérico efetivo em computadores digitais, outras bases de numeração voltaram a ser mais
estudadas, como a base binária (b = 2) e a hexadecimal (b = 16).
O processo está resumido na próxima proposição.
Proposição Dados os inteiros a e b, com a ≥ 0 e b > 1, existem inteiros r0, r1, . . . , rn, . . ., univoca-
mente determinados pelas condições:
(a) Existe um número natural m tal que rn = 0 para todo n ≥ m;
(b) Para todo n, temos 0 ≤ rn < b;
(c) a = r0 + r1b+ · · ·+ rnbn + · · · .
Aplicando sucessivamente a divisão euclidiana:
a = bq0 + r0, r0 < b,
q0 = bq1 + r1, r1 < b,
q1 = bq2 + r2, r2 < b,
e assim por diante. Como a > q0 > q1 > · · · , deve ocorrer, em alguma posição, qn−1 < b, logo, da
igualdade
qn−1 = bqn + rn,
resulta qn = 0, o que acarreta 0 = qn = qn+1 = · · · , donde 0 = rn+1 = rn+2 = · · · .
Divisibilidade e Algoritmo Euclidiano da Divisão 33
Obtemos,então,
a = r0 + r1b+ · · ·+ rnbn, ou a = rnbn + · · ·+ r1b+ r0
Essa expressão é a expansão b-ádica do inteiro a. Para representar os números de 0 a b−1, usamos
os símbolos S = {s0, s1, . . . , sb−1}, onde s0 = 0.
Casos particulares
(a) Sistema binário: S = {0, 1} (dígitos binários). Por exemplo, 1002 = 22 = 4, 10112 = 1+ 2+ 23 =
11.
(b) Sistema hexadecimal: S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A,B,C,D,E, F}.
Por exemplo, 2A716 = 2× 162 + 10× 16 + 7 = 512 + 160 + 7 = 679.
Exemplos 3.11
1. Na tabela abaixo, verifique cada representação:
Base 2 Base 10 Base 16
0 0 0
1 1 1
10 2 2
11 3 3
100 4 4
101 5 5
110 6 6
111 7 7
1000 8 8
1001 9 9
1010 10 A
1011 11 B
1100 12 C
1101 13 D
1110 14 E
1111 15 F
10000 16 10
10001 17 11
10100 20 14
1001101 77 4D
2. Quantos algarismos são usados para numerar as 300 páginas de um livro {1, 2, 3, . . . , 300}?
Ora, os números de 1 a 9 usam 9 algarismos; os de 10 a 99, usam 2 × 90 = 180 algarismos; enfim,
para numerar as páginas de 100 a 300, necessitaremos 3 × 201 = 603 algarismos. Ao todo, são
9+180+603=792 algarismos.
3. Considere um produto finito de números naturais a1 · a2 · · · ak. Verificar que o algarismo das
unidades do produto a1 · · · ak é igual ao algarismo das unidades do produto dos algarismos da unidades
de cada fator. Conclua, então, que
(a) o algarismo das unidades de um quadrado perfeito só pode ser 0,1,4,5,6 ou 9;
(b) todo número da forma M = n(n+1)/2 (n ∈ N∗) é inteiro e seu algarismo das unidades não pode
ser 2,4,7,nem 9.
Cicero Gomes
Realce
34 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
Sendo u1, u2, . . . uk os respectivos algarismos das unidades dos números dados, temos a1 = m1 ·10+u1,
a2 = m2 · 10 + u2, logo a1a2 = m12 · 10 + u12, onde mi · 10 indica um múltiplo de 10 e ui dígito de
unidades (0 ≤ ui ≤ 9); mais geralmente, vale a1 · · · ak = m1···k · 10 + u1···k.
(a) Em particular, se a = m · 10 + u, então o algarismo das unidades de a2 é o mesmo de de u2, isto
é, 0,1,4,5,6 ou 9.
(b) Como n e n+1 são inteiros consecutivos, um deles é par, logo n(n+1) é par, dondeM é bem inteiro.
O algarismodas unidades de 2M não pode ser 4 ou 8, pois se n termina em {0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
então n(n+ 1) termina em {0, 2, 6, 2, 0, 0, 2, 6, 2, 0}.
4. Em um sistema de numeração de base b > 2, o número 121 é um quadrado; se for b > 3, então
1331 é um cubo.
De fato, 121 = b2 + 2b+ 1 = (b+ 1)2; também, 1331 = b3 + 3b2 + 3b+ 1 = (b+ 1)3.
Atividade-proposta 3.12
1.Considere um sistema de numeração de base arbitrária b > 0. Mostre que o número 10101 é divisível
por 111, e escreva o quociente correspondente.
2. No sistema decimal, um número se escreve 12551. Encontre a base na qual o número é da forma
30407.
3. Utilizando os sistemas decimal e binário, justifique o seguinte algoritmo utilizado pelos antigos
egípcios para efetuar a multiplicação de dois inteiros positivos a e b representados no sistema decimal.
Ponha a e b no alto de duas colunas. Abaixo de a ponha o quociente q0 da divisão de a por 2, abaixo
de q0 ponha o quociente q1 da divisão de q0 por 2, etc. Abaixo de b ponha 2b , abaixo de 2b ponha
4b , etc. Toda vez que o número da coluna do a for ímpar, coloque um sinal + ao lado do número da
mesma linha da coluna do b . Some todos os números assinalados com o sinal +, este é o produto de
a por b . Por exemplo, a = 35 e b = 47 :
a=35 b=47 +
17 94 +
8 188
4 376
2 752
1 1504 +
1645 = 35× 47
Sugestão. Na representação binária a = r0 + r1 · 2 + · · ·+ rn · 2n, observe que cada resto ri+1 = 1 se
o quociente q i é impar, e ri+1 = 0 se q i é par. Logo, no produto ab = r0 · b+ r1 · 2b1 + · · ·+ rn · 2nb,
são retidos os termos provenientes dos elementos ímpares da coluna da esquerda.
2.[Jogo do NIM]
Trata-se de um antigo jogo chinês de palitos jogado por duas pessoas. Na realidade, há uma estratégia
que, se adotada pelo jogador que inicia o jogo, ele sempre ganhará. Grupos de palitos são alinhados
em uma mesa, com um número qualquer de palitos e de grupos (colunas). Um movimento consiste em
retirar um número qualquer de palitos de um grupo, inclusive todo o grupo, mas apenas um grupo
pode ser alterado. Os jogadores se alternam e quem retirar o último palito ganha o jogo. Vamos
estabelecer uma estratégia de tal modo que, quem iniciar a partida, jogando com a boa regra, sempre
vencerá!
Divisibilidade e Algoritmo Euclidiano da Divisão 35
Basta escrever o número de palitos de cada linha na base 2, e colocando-os de modo que os algarismos
das unidades se correspondam. Por exemplo, no início da partida, temos 15 palitos separados em
três grupos de 3, 5 e 7 palitos:
[3] Grupo 1 1 1
[5] Grupo 2 1 0 1
[7] Grupo 3 1 1 1
2 2 3
[3] Grupo 1 1 1
[5] Grupo 2 1 0 1
[6] Grupo 3 1 1 0
2 2 2
Somando os três números como se fosse na base dez, obtemos 223, a chamada chave do jogo. O
primeiro jogador poderá, então, com uma jogada, tornar pares todos os algarismos da chave (veja
acima, após a retirada de um palito do grupo 3). Por sua vez, o segundo jogador transformará a chave
222 numa outra com, pelo menos, um algarismo ímpar, o que, mediante uma jogada conveniente,
poderá ser recolocada numa situação par, a chamada posição segura (para o primeiro jogador), pois
ganhadora!
Pratique um pouco!
(a) São seguras as configurações (2, 2), (1, 2, 3), (2, 3, 6, 7), (1, 2n, 2n+ 1), (n, 7− n, 7);
(b) Não são seguras: (1, 3, 4), (1, 2n+ 1, 2n+ 2);
(c) Transfome cada configuração (1, 3, 9, 27) , (3, 5, 7, 8, 11) numa configuração segura. A solução é
única?
(d) Classifique as configurações (1, 1, 1) e (1, 0, 0).
3.13 Máximo Divisor Comum
Sejam a e b inteiros não ambos nulos; um divisor comum de a e b é um inteiro c 6= 0 tal que c|a e c|b.
Estamos interessados em explicitar o máximo divisor comum de a e b, como um inteiro d que seja o
maior divisor comum de a e b; na realidade, usaremos a seguinte definição.
Um inteiro d é um máximo divisor comum (mdc) de a e b quando:
(i) d é um divisor comum de a e b;
(ii) se c é um divisor comum de a e b, então c|d.
Observemos logo que, se d e D, são inteiros não nulos verificando (i) e (ii), então d|D e D|d, isto é,
d = ±D. Assim, quando existe d = mdc (a, b) = (a, b), se convencionarmos escolher d > 0, então
poderemos especificar o mdc como o único inteiro positivo verificando (i) e (ii). Vemos, também,
que, se c 6= 0 é um divisor comum de a, b, então c|d, donde c ≤ |c| ≤ d, isto é, o mdc é o maior dos
divisores comuns.
Por exemplo,
(1) se a ∈ Z, (1, a) = 1;
(2) se a ∈ Z∗, então (0, a) = |a|; (a, a) = |a|;
(3) se a ∈ Z∗, então a|b ⇐⇒ (a, b) = |a|;
(4) se a, b ∈ Z, não ambos nulos, então (a, b) = (|a|, |b|).
3.14 Lema de Euclides Sejam os inteiros a, b,m, n.
Se existe (a−mb, b) então (a, b) existe e (a, b) = (a−mb, b).
Se existe (a, b− na) então (a, b) existe e (a, b) = (a, b− na).
Pondo, por exemplo, d = (a−mb, b), como d|(a−mb) e d|b, vemos que d divide a = (a−mb) +mb,
ou seja, d é um divisor comum de a e b. Por outro lado, se c é um divisor comum de a e b, então c é
um divisor comum de a−mb e b, portanto c|d; enfim, segue bem que d = (a, b).
36 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
EXEMPLO 3.15
1. Verifique: (2, 3) = 1; (14, 15) = 1; (4, 20) = 4; (10, 200) = 10; (10, 201) = 1
2. Vamos exemplificar o Lema de Euclides (a−mb, b) = (a, b) = (a, b− na) nas situações-problemas
abaixo; todas as variáveis são números naturais ≥ 1.
a) (n, n+ 1) = 1, pois (n, n+ 1) = (n, (n+ 1)− n) = (n, 1) = 1; observe, também, que n e n+ 1 têm
paridades diferentes.
b) (n, 2n+ 1) = (n, (2n+ 1)− 2n) = (n, 1) = 1.
c) (n2 + n+ 1, n+ 1) = (n2 + n+ 1− n(n+ 1), n+ 1) = (1, n+ 1) = 1
d) (n!+1, (n+1)!+1) = (n!+1, (n+1)!+1− (n+1)(n!+1)) = (n!+1, n) = (n!+1−n(n−1)!, n) =
(1, n) = 1
e)
(
am − 1
a− 1 , a− 1
)
= (m, a− 1), a ≥ 2.
Inicialmente, observemos que
am − 1
a− 1 = a
m−1 + am−2 + · · ·+ a+ 1
am − 1
a− 1 = (a
m−1 − 1) + (am−2 − 1) + · · ·+ (a− 1) +m = α(a− 1) +m
(α(a− 1) +m, a− 1) = (m, a− 1).
3. Verificar a relação:(a, a+ b)|b.
Pondo d=(a,a+b), temos d|a e d|a+ b, logo d|b.
4. Verificar: se ms− nr = 1, então (ma+ nb, ra+ sb) = (a, b).
Pondo d = (a, b), α = ma + nb, β = ra + sb, D = (α, β), temos que, como d|a e d|b, segue d|α e
d|β, logo d|D. Reciprocamente, temos D|α e D|β; explicitando a e b das equações ma + nb = α
e ra + sb = β, cuja matriz é inversível, pois ms − nr = 1 é o valor de seu determinante, obtemos
a = αs− βn e b = βm− αr, o que mostra que D|a e D|b, logo D|d. Como d|D e D|d, e ambos são
positivos, vem d = D.
Atividade-proposta 3.16
1. Um floricultor possui 100 rosas brancas e 60 rosas vermelhas e pretende fazer o maior número
possível de ramalhetes iguais entre si. Quantos serão os ramalhetes e quantas rosas de cada cor deve
ter cada um deles?
2. Indique os possíveis valores de (n, n+ 10).
3. Se (a, b) = 1, então (a) ((a + b), (a2 − ab + b2)) = 1 ou 3; (b) encontre os posssíveis valores de
(a2 − b2, a3 − b3).
4. Considere os números de Fermat Fn = 2(2
n) + 1, n ≥ 0. Mostre que:
(a) se 0 ≤ m < n, então Fm | (Fn − 2); (b) se m 6= n, então (Fm, Fn) = 1.
3.17 Algoritmo de Euclides
Para o cálculo explícito do mdc de dois inteiros dados, dispomos do método de Euclides, das divisões
sucessivas, um bem fundamentado algoritmo, inclusive do moderno ponto de vista computacional.
Sejam os inteiros a e b, que podemos logo supor a > b > 0.
Usando a divisão euclidiana, temos a = bq1 + r2, 0 ≤ r2 < b.
Divisibilidade e Algoritmo Euclidiano da Divisão 37
Pelo Lema de Euclides, vemos que (a, b) = (a− bq1, b) = (r2, b) = (b, r2). Podem ocorrer dois casos:
(1) r2 = 0. Nesse caso, (a, b) = (b, r2) = (b, 0) = b;
(2) r2 6= 0. Agora, prosseguimos com a divisão euclidiana, de b por r2:
b = r2q2 + r3, 0 ≤ r3 < r2
Com o mesmo argumento do Lema de Euclides, vem (a, b) = (b, r2) = (r2, r3). Novamente dois casos
podem se apresentar:
(1) r3 = 0. Temos (a, b) = (r2, 0) = r2;
(2) r3 6= 0. Prosseguimos com a divisãoeuclidiana, de r2 por r3, e assim por diante.
Obtemos uma sequência estritamente decrescente b > r2 > r3 > r4 > · · · > 0 de números naturais,
o que obriga a ocorrência de algum rn 6= 0 e rn+1 = 0, tornando estacionária aquela sequência. Por
construção:
(a, b) = (b, r2) = · · · = (rn, rn+1) = (rn, 0) = rn
onde o último resto não nulo rn indica o mdc procurado.
As divisões sucessivas podem ser resumidas no quadro abaixo:
q1 q2 q3 · · · qn−2 qn−1 qn
a b r2 r3 · · · rn−2 rn−1 rn
r2 r3 r4 r5 · · · rn 0
Exemplo motivador
Aliquemos o algoritmo de Euclides aos inteiros a = 4512 e b = 4128, obtendo o quadro-resumo:
1 10 1 3
4512 4128 384 288 96
384 288 96 0
Além de indicar o mdc (4512, 4128) = 96, o algoritmo fornece uma informação surpreendente: uma
combinação linear αa + βb = d !! A obtenção dessa combinação linear é feita assim: depois de
indicar, por coluna, as divisões sucessivas, ordenadamente, iniciando pela penúltima (a que contem
o resto-mdc), explicitamos cada resto e substituimos na equação anterior. Do quadro acima, temos:
384 = 1 · 288 + 96 =⇒ 96 = 384− 1 · 288
4128 = 10 · 384 + 288 =⇒ 96 = 384− 1 · (4128− 10 · 384) = 11 · 384− 1 · 4128
4512 = 1 · 4128 + 384 =⇒ 96 = 11 · (4512− 1 · 4128)− 1 · 4128 = 11 · 4512− 12 · 4128
O processo indicado forneceu uma combinação linear (dita de Bézout): 11a− 12b = d = 96.
3.18 Propriedade característica
Sejam a e b inteiros não ambos nulos, e J(a, b) = {ax + by ; x, y ∈ Z} o conjunto de todas as
combinações lineares inteiras de a e b. Então:
(i) J(b, a) = J(a, b) 6= ∅;
(ii) Se d > 0 é menor inteiro positivo de J(a, b) (que é combinação linear de a e b), então d = (a, b) e
J(a, b) = {rd ; r ∈ Z};
(iii) Em particular, existe uma combinação linear d = ax0 + by0.
As combinações lineares a = 1 · a e b = 1 · b mostram que tanto a como b figuram em J(a, b);
na realidade, por hipótese, o conjunto J(a, b) contém inteiros não nulos. Por outro lado, se z ∈
J(a, b), então é claro que −z ∈ J(a, b), logo, há inteiros positivos no conjunto considerado. Pela Boa
Ordenação, existe um menor inteiro positivo d > 0 combinação linear de a e b, digamos d = ax0+by0.
Cicero Gomes
Realce
38 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
Se c|a e c|b, a combinação linear anterior mostra que c|d. Enfim, mostremos que d|a e
d|b. Conside-remos a divisão euclidiana de a por d: a = qd + r, 0 ≤ r < d. Segue que
r = a − qd = a − q(m0a + n0b) = a(1 − qm0) − qn0b é uma combinação linear de J(a, b); ora,
a condição 0 ≤ r < d e a minimalidade de d obriga r = 0, logo d|a. Analogamente, d|b. Enfim,
qualquer combinação linear z ∈ J(a, b) é um múltiplo de d, e vice-versa.
Corolário Sejam a, b ∈ Z∗ e n um inteiro positivo; então (na, nb) = n(a, b).
De fato, temos J(na, nb) = nJ(a, b) = {nz ; z ∈ J(a, b)}; segue, então, que
(na, nb) = menor valor positivo de (na)x+ (nb)y, onde x, y ∈ Z; como n > 0,
= n · { menor valor positivo de ax+ by, onde x, y ∈ Z }, isto é,
(na, nb) = n(a, b).
Pratique um pouco!
Pondo d = (a, b) e D = (na, nb), verifique que D = nd, mostrando que D|nd e nd|D.
3.19 Inteiros primos relativos
Dois inteiros a e b são primos relativos, primos entre si ou coprimos, se (a, b) = 1.
Por exemplo, 10 e 21 são primos relativos, pois (10, 21) = 1. Também são coprimos os inteiros 2010
e 2011.
Proposição 1 Dois inteiros a e b são primos relativos se, e somente se, existem inteiros α e β tais
que αa+ βb = 1 (isto é, alguma combinação linear de a e b igual a 1).
Realmente, se (a, b) = 1, então uma combinação de Bézout verifica bem αa+βb = 1. Reciprocamente,
partindo de uma tal combinação linear, se d = (a, b), então d|a e d|b, logo d|1, ou d = 1.
Proposição 2 Se d = (a, b), então
(
a
d
,
b
d
)
= 1
Pondo a = da1 e b = db1, se αa + βb = d, então, simplificando por d, vem αa1 + βb1 = 1, isto é,
(a1, b1) = 1.
Proposição 3 Sejam a, b e c inteiros não nulos. Se a|(bc) e (a, b) = 1, então a|c.
De fato, se αa + βb = 1, então, multiplicando por c, obtemos αac + βbc = c; por hipótese, a|bc, ou
bc = qa; segue, enfim, a(αc+ βq) = c é da forma ak = c,donde a|c.
Exemplo 3.20
1. Sejam os inteiros coprimos a e b : (a, b) = 1 ; para cada inteiro c, se a|c e b|c, então (ab)|c.
Realmente, como a|c, então existe α tal que c = αa; analogamente, existe β tal que c = βb; assim,
vale c = αa = βb. Ora, vemos daí que a|βb, donde, como (a, b) = 1, segue a|β; portanto, existe k
inteiro tal que β = ka e c = (ka)b = k(ab), ito é, (ab)|c.
Pratique um pouco! No resultado acima, a hipótese (a, b) = 1 pode ser enfraquecida?
2. Seja n ≥ 1; após ter verificado que a = n(n+ 1)
2
e b =
n(n+ 1)(2n+ 1)
6
são inteiros positivos,
calcule (a, b), considerando os dois casos: n = 3q ou n = 3q + 2, e n = 3q + 1.
O número a é inteiro, pois o produto n(n + 1) é par [ver o exemplo 3.11(3)]; b é inteiro pelo
argumento de 3.9(6). Seja d = (a, b); temos
6d = (6a, 6b) = (3n(n+1), n(n+1)(2n+1)) = n(n+1)(3, 2n+1) = n(n+1)D, com D = (3, 2n+1).
Caso(1) n = 3q ou n = 3q + 2. Então D = (3, 2n+ 1) = 1, 6d = n(n+ 1) · 1 e d = n(n+ 1)/6.
Caso(2) n = 3q + 1; vemos que D = (3, 2n+ 1) = 3; 6d = n(n+ 1) · 3 e d = n(n+ 1)/2.
Divisibilidade e Algoritmo Euclidiano da Divisão 39
3. Se (a, b) = 1, então (a, bc) = (a, c); concluir que
(a, bc) = 1 se, e somente se, (a, b) = (a, c) = 1.
(a) Sejam d = (a, bc) e D = (a, c); como D|a e D|c, então D|bc, logo D|d. Por outro lado, com
(a, b) = 1, existe alguma combinação linear xa+yb = 1, donde, multiplicando por c, (xa)c+(yb)c = c;
enfim, como d|a e d|bc, segue que d|c, logo d|D.
(b) Se (a, b) = (a, c) = 1, então a primeira igualdade, junto com (a), nos dá (a, bc) = (a, c) = 1.
Reciprocamente, se (a, bc) = 1, então uma combinação linear xa+ y(bc) = 1 informa que (a, b) = 1 =
(a, c).
Atividade proposta 3.21
1. Use o algoritmo de Euclides para calcular d = (a, b) e indicar uma combinação linear xa+ yb = d.
(a) (−14, 5); (b) (33810, 4116); (c) (1000,−761)
2. Dados a = 188887 e b = 211109, calcule (a, b) e encontre os inteiros x e y tais que
x
y
=
a
b
, com
x+ y = 108.
3. [Continuação do exemplo 3.20, Exercício 3]
Suponhamos (a, b) = (a, d) = (c, b) = (c, d) = 1; mostre que
(a) ((ac), (bd)) = 1;
(b) Para todos m,n ∈ N, (am, bn) = 1 ;
(c) Em particular, se (α, β) = 1, então (αn, βn) = 1.
Conclua que, dados a, b ∈ Z, vale (an, bn) = (a, b)n .
3.22 Mínimo Múltiplo Comum
Dados os inteiros não nulos a e b diremos que um m.m.c de a e b é um inteiro m tal que
(1) m é múltiplo comum de a e b: a|m e b|m;
(2) para todo inteiro c que seja múltiplo comum de a e de b, isto é, tal que a|c e b|c, então
deve ser m|c.
Tal como no caso do mdc, se o inteiro m1 também verifica as duas condições (1) e (2), então m|m1 e
m1|m; se fixarmos da definição anterior a escolham > 0, vemos que o mmc é unicamente determinado
pela condições consideradas. Usaremos, então, a notação [a, b] para representar o mmc(a,b)> 0.
Por exemplo, [2, 3] = 6, [5, 500] = 5, [−4, 10] = 20.
Proposição 1 Se a, b ∈ Z∗, então |ab| = (a, b)[a, b].
Supondo logo a > 0 e b > 0, e pondo d = (a, b), a = a1d, b = b1d e m = [a, b], a relação ab = dm fica
m = a1b = ab1(∗). Ora, essa igualdade (*) mostra que m|a e m|b. Em seguida, se a|c e b|c, então
c = xa = yb, ou xa1 = yb1, donde b1|xa1, mas (a1, b1) = 1, logo b1|x e, digamos, x = qb1, que, em
c = xa, nos dá c = qb1a = qm , tendo em conta (*). Assim, m|c.
Corolário Se (a, b) = 1, então [a, b] = |ab|.
Exemplo 3.23
1. Como (10, 201) = 1, vem [10, 201] = 10 × 201 = 2010. Do mesmo modo, vimos que
(4512, 4128) = 96, logo [4512, 4128] = 4512× 4128/96 = 194016.
Cicero Gomes
Realce
Cicero Gomes
Realce
40 Introdução à Teoria dos Números � [Antonio Carlos & Ana Paula Marques]
2. Achar cada mmc, onde n ∈ N.
(a) [n, 2n+ 1]
Como (n, 2n+ 1) = 1, segue [n, 2n+ 1] = n(2n+ 1).
(b) [n+ 1, n2 + 1]
Temos (n+ 1, n2 + 1) = (n(n+ 1)− (n2 + 1)) = (n− 1, n+ 1) = (2, n+