Teoria Aritmética dos Números
Jair Donadelli
Sumário
O que é?
4
Pra que serve?
4
0 Preliminares: partição e relação de equivalência
9
0.1 Partição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
9
0.2 Relação de equivalência . . . . . . . . . . . . . . . . . . . . . . . . . .
9
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1 Números Naturais e Indução Matemática
13
1.1 Operações aritméticas . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.2 Relação de ordem ≤ . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.3 Subtração em N . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
1.4 Princípio da Boa Ordem (PBO) . . . . . . . . . . . . . . . . . . . . . . 23
1.5 Princípios de Indução . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2 Divisibilidade em N
28
2.1 Algoritmo de divisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.2 Representação — sistemas posicionais . . . . . . . . . . . . . . . . . 33
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
2.3 MDC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
2.4 MMC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3 Números primos e Teorema Fundamental da Aritmética
43
3.1 Distribuição dos primos . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Pequeno Teorema de Fermat (PTF) . . . . . . . . . . . . . . . . . . . . 48
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4 Construção dos Inteiros
51
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
5 Inteiros e suas propriedades aritméticas e de ordem
53
5.1 Valor absoluto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
5.2 Indução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
6 Divisibilidade em Z
60
6.1 Teorema da Divisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
6.2 MDC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
6.3 Teorema de Bézout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
6.4 Equações diofantinas lineares . . . . . . . . . . . . . . . . . . . . . . 66
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7 Congruências
70
7.1 Sistema completo de restos . . . . . . . . . . . . . . . . . . . . . . . . 74
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
8 Congruências lineares e sistemas de congruências
77
8.1 Teorema chinês do resto . . . . . . . . . . . . . . . . . . . . . . . . . . 79
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
9 A função ϕ de Euler e o Teorema de Euler
86
9.1 Sistema completo de invertíveis (sci) . . . . . . . . . . . . . . . . . . 88
9.2 O Teorema de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
2
9.3 O Pequeno Teorema de Fermat revisitado . . . . . . . . . . . . . . . . 91
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
10 Restos quadráticos
93
10.1 O símbolo de Legendre . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
10.2 Lei da Reciprocidade Quadrática . . . . . . . . . . . . . . . . . . . . . 97
Exercícios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3
O que é?
A Matemática tem sido resultado de elaborações a partir das noções básicas de
número e figura geométrica. Número, segundo Euler, é uma contagem ou uma
medida, é resultado da comparação de uma grandeza com a unidade.
Teoria dos números é uma disciplina da matemática dedicada principalmente ao estudo das propriedades dos números inteiros em geral, e dos números primos em particular, bem como as propriedades dos objetos obtidos a
partir dos números inteiros (e.g., números racionais) ou de generalizações dos
números inteiros (e.g., inteiros algébricos). Propriedades de números reais e
números complexos são estudados em Análise Real e Análise Complexa.
No início do século 20 o termo usado para a “Teoria dos Números” era Aritmética (a palavra "aritmética"é usada pelo público em geral para significar "cálculos elementares"). Aritmética também adquiriu outros significados como em
Aritmética de Peano e Aritmética de ponto flutuante. O uso do termo Aritmética
para designar o mesmo que Teoria dos Números recuperou algum terreno na segunda metade do século 20, em parte devido à influência francesa; em particular
aritmética, como um adjetivo, é preferido ao teórico-numérico [Wikipedia].
A primeira descoberta histórica de natureza aritmética foi a Tábula de Plimpton 322, 1800 aC.
Este primeiro contato com a Teoria dos Números é por meio da Teoria Elementar dos Números. Através desta disciplina introduziremos propriedades interessantes e notáveis dos números inteiros.
Pra que serve?
Os números estão na base da civilização, faz parte da cultura dos povos e, segundo historiadores, já se contava na Idade da Pedra.
Números estão na base da construção do conhecimento matemático, em
particular, o conjunto dos números naturais, em alguns aspectos, é a peça mais
básica da matemática pois você pode construir os demais conjuntos numéricos
4
a partir de números naturais
−
²
÷
i
N −−→ Z −−→ Q −→ R −→ C
daí você pode chegar ao cálculo, a topologia e outras disciplinas da Matemática.
Por outro lado, a Teoria dos Números utiliza técnicas dessas disciplinas (álgebra,
análise, geometria e topologia, lógica e a ciência da computação) para resolver
as questões que lhes são próprias, e muitas vezes direciona desenvolvimentos
nestes campos.
Teoria dos Números é um ótimo lugar para aprender a ler e escrever provas. É uma rica fonte de conjecturas que são fáceis de enunciar e muito difíceis de provar. É uma área que lida com problemas de entendimento simples,
são acessíveis pois envolvem elementos que são familiares, embora as soluções
nem sempre são simples, exigem engenhosidade, em muitos casos, são muito
difíceis, embora os números inteiros sejam familiares e suas propriedades parecerem simples, é sim um assunto muito profundo. Por exemplo, aqui estão
alguns problemas na teoria dos números que permanecem sem solução (um
número primo é um número inteiro maior que 1, cujos divisores positivos são 1
e o próprio número). Note-se que estes problemas são simples de enunciar
• (conjectura de Goldbach) Todo inteiro n > 2 par é soma de dois primos?
• (conjectura dos primos gêmeos) Há um número infinito de primos gêmeos? (primos gêmeos diferem por 2, como 11 e 13)
• A sequência de números de Fibonacci tem infinitos números primos?
• Existem infinito primos de Mersenne (da forma 2p + 1, com p primo)?
• n 2 − n + 41 é primo para n de 1 até 40, há infinitos primos dessa forma?
• Há um primo entre n 2 e (n + 1)2 ?
• Há uma quantidade infinita de números perfeitos? (perfeito se é a soma
de seus divisores, 6 = 3 + 2 + 1 por exemplo)
5
• Existe um número ímpar perfeito?
• Existe um algoritmo eficiente para fatorar inteiros?
• (Conjectura de Collatz — conjectura 3n +1) Comece com qualquer inteiro
n. Obtenha um novo número inteiro m dividindo na metade n, se for
par, ou tomando 3n + 1, se for ímpar. Repita, se m é par, tome a metade,
senão tome 3m + 1. E assim por diante. É verdade que este procedimento
iterativo sempre resuta em 1, independente do valor inicial?
• (Problema de Catalan Os números 8 e 9 são as únicas duas potências consecutivas? Ou seja, as únicas soluções nos naturais para x a −y b = 1, x, y, a, b >
1, são x = 3, a = 2, y = 2 e b = 3?
• (Conjectura dos números palíndromos) Escolha um inteiro. Inverta seus
dígitos e adicione ao resultado o inteiro original. Se o resultado não é um
palíndromo, repita o processo. Será que todos os números inteiros, eventualmente, tornam-se palíndromos por este processo?
• Existem inifinitos primos com todos os dígitos iguais a 1?
• (Hipótese de Riemann) Essa não dá pra descrever de modo simples!!! Mas
pra motivar, se você resolver o problema, ganha US$1.000.000,00.
A Teoria dos Números é considerada uma disciplina desafiadora e instigante.
Teoria dos Números tem algumas grandes aplicações. A criptografia de chave
pública (RSA é o mais famoso), a construção de grafos expansores, a Teoria de
Códigos, etc. Todo sistema digital está baseado nos números inteiros. Duas aplicações modernas: códigos corretores de erros e criptografia de chave pública.
Códigos corretores de erros fazem parte do nosso cotidiano de várias formas,
e.g., ao falar pelo telefone, ao ouvir um CD de música, ao assistir um filme em
DVD ou navegar pela Internet. Códigos corretores de erros são usados frequentemente em aplicações militares para proteção contra interferência inimiga intencional. Quando queremos transmitir uma informação através de um canal
6
de comunicação (linha telefônica, DVD, internet) podem ocorrer ruídos, o que
acaba provocando erros na informação inicial. Detectar tais erros e, se possível,
corrigi-los é o objetivo dos códigos corretores de erros. A Álgebra, a Combinatória e a Teoria de Números são ferramentas fundamentais no estudo da Teoria de
Códigos.
Criptografia RSA
1. Escolha dois números primos p e q, por exemplo, p = 3 e q = 11
2. Compute n = p ∗ q, no exemplo n = 33
3. Compute φ(n) = (p − 1) ∗ (q − 1), φ(33) = 20
4. Escolha e ∈ {2, 3, . . . φ(n)} com e e n coprimos, e = 7
5. Compute d tal que (d ∗ e) ÷ φ(n) deixa resto 1, d = 3
7
6. Chave pública (e, n), (7, 33)
7. Chave privada (d , n), (3, 33)
Para criptografar convertemos a mensagem num inteiro m e calculamos c = m e
(mod n), m = 2, c = 29 .
Para decodificar, calculamos c d (mod n), m = 293 (mod 33) = 2 .
A conversão pra inteiro não é problema, informação é normavelmente codificada em computador usando um sistema de numeração
String: teoria aritmética dos números
ASCII (decimal): 116 101 111 114 105 97 32 97 114 105 116 109 101 116 105 99 97
32 100 111 115 32 110 117 109 101 114 111 115
Binário: 01110100 01100101 01101111 01110010 01101001 01100001 00100000
01100001 01110010 01101001 01110100 01101101 01100101 01110100 01101001
01100011 01100001 00100000 01100100 01101111 01110011 00100000 01101110
01110101 01101101 01100101 01110010 01101111 01110011
Hexadecimal: 74 65 6F 72 69 61 20 61 72 69 74 6D 65 74 69 63 61 20 64 6F 73 20
6E 75 6D 65 72 6F 73
Texto comum: teoria aritmética dos números
Texto criptografado (representado em hex): c40bd12d61340e76830f00de6e590e
98f58cacf59b314d791824c280943770d4984caca3543496c543459d0051a299f57ce6
03aeff7745572ec659159ab0613e0a9ed6d5accb2f7588c60b7aaf13b05df9f4a51735b
0ca71d52922a94e9dff1f271285c3defad9fb5605f9e4c9e58c26898e40f47c078f328b7
3814ed6c6555b
8
0 Preliminares: partição e relação de equivalência
0.1 Partição
Uma família de conjuntos A = {A 1 , A 2 , . . . , A n } particiona o conjunto X se seus
elementos são não-vazio, disjuntos e a união deles é X , isto é,
A i 6= ; para todo i
A i ∩ A j = ; para todo i 6= j ,
(1)
e
A1 ∪ A2 ∪ · · · ∪ An = X .
(2)
(3)
Dizemos que A é uma partição X . Notemos que A i ⊂ X para todo i . A definição
é a mesma no caso em que A não é finito.
Exemplo 1. Sejam R 0 , R 1 e R 2 subconjuntos de N definidos por
R i = {n : n dividido por 3 deixa resto i }
{R 0 , R 1 , R 2 } é uma partição de N.
0.2 Relação de equivalência
Uma relação binária R sobre um conjunto A é um conjunto de pares ordenados
de elementos de A, em outras palavras, é um subconjunto R ⊂ A × A.
Notação: Escrevemos aRb com o significado de (a, b) ∈ R.
Exemplo. <⊂ N × N é uma relação binária e (2, 3) ∈<, mas usamos 2 < 3.
Uma relação binária ∼ sobre um conjunto A é de equivalência se valem as
propriedades
reflexiva a ∼ a para todo a ∈ A;
simétrica se a ∼ b, então b ∼ a para todos a, b ∈ A;
transitiva se a ∼ b e b ∼ c, então a ∼ c para todos a, b, c ∈ A;
9
Exemplo.
1. = é uma relação de equivalência em N.
2. ≤ não é uma relação de equivalência em N.
3. Se T e S são triângulos no plano e T ∼
= S se os triângulos são semelhantes,
então ∼
= é relação de equivalência sobre o conjunto de todos os triângulos
no plano.
4. Semelhança de matriz é uma relação de equivalência sobre o conjuntos de
todas as matrizes quadradas de ordem n de números reais.
5. ⊂ não é relação de equivalência sobre o conjunto das partes de A.
Exemplo. Seja {R 0 , R 1 , R 2 } a partição de N dada no exemplo 1. Definimos ∼ sobre
N por
a ∼ b se existe i ∈ {0, 1, 2} tal que a, b ∈ R i
ou seja, a e b pertencem a um mesmo conjunto da partição.
Exercício 2. Se A é uma partição de X então a relação definida por
a ∼ b se, e só se, a ∈ A e b ∈ A, para algum A ∈ A
é uma relação de equivalência.
Solução. Sejam A , X e ∼ como no enunciado e vamos provar que ∼ é uma relação binária reflexiva, simétrica e transitiva.
Para todo a ∈ X , a ∈ A para algum A ∈ A S pois A é partição; da definição
temos a ∼ a , logo a relação ∼ é reflexiva.
Se a ∼ b então a ∈ A e b ∈ A, para algum A ∈ A , mas também, b ∼ a. Logo a
relação ∼ é simétrica.
Finalmente, se a ∼ b então a ∈ A e b ∈ A, para algum A ∈ A , e se b ∼ c então
b ∈ B e c ∈ B , para algum B ∈ A . Portanto b ∈ A ∩ B .
Como A é partição A ∩ B = ; ou A = B . Vale a segunda opção. De a, c ∈ A
temos a ∼ c. Logo a relação ∼ é transitiva.
10
Classe de equivalência
Seja ∼ uma relação de equivalência sobre o conjunto X e a ∈ X
[a] := {b ∈ X : b ∼ a}
é o subconjunto de X formado por todos os elementos equivalentes a a, chamado de classe de equivalência de a. O elemento dentro dos colchetes é chamado de representante da classe.
Por transitividade, qualquer elemento da classe pode ser seu representante.
Seja b ∈ X com b ∼ a. Para todo c ∈ [a] vale c ∼ a, portanto, c ∼ b, logo c ∈ [b].
Reciprocamente, se c ∈ [b] então c ∈ [a], por argumento análogo. Assim [a] = [b].
Também, se [a] = [b] então de a ∈ [a] temos a ∈ [b], portanto a ∼ b. Com isso
provamos
a ∼ b ⇔ [a] = [b].
(4)
O que podemos dizer no caso [a] 6= [b]? Imediatamente, por (4) que a 6∼ b.
Para qualquer c ∈ X , se c ∼ a então b 6∼ c, caso contrário teríamos uma contradição pela transitividade, de modo que [a] ∩ [b] = ;.
Concluindo, dos parágrafos precedentes temos que para as classes de equivalência vale um dos casos: para quaisquer a, b ∈ X
1. [a] = [b], ou
2. [a] ∩ [b] = ;.
O conjunto quociente de X pela relação de equivalência ∼ é o conjunto das
classes de equivalência da relação
X /∼ := {[a] : a ∈ X }.
Exercício 3. Prove que X /∼ é uma partição de X .
Exemplo. No caso de exemplo 1
R 0 = [0] = {0, 3, 6, 9, 12, 15, . . . }
11
(5)
R 1 = [1] = {1, 4, 7, 10, 13, 16, . . . }
R 2 = [1] = {2, 5, 8, 11, 14, 17, . . . }
Observemos que [0] = [3] = [6]. O Teorema da Divisão (que veremos com detalhe
nesse curso) garante que R 0 ∪ R 1 ∪ R 2 = N.
Exercício 4. Considere a relação Z ⊂ N × N definida por
(a, b)Z(n, m) se, e só se a + m = b + n
(6)
Para cada (a, b) definimos a classe de equivalência de (a, b) por
©
ª
[(a, b)] := (n, m) ∈ N × N : (a, b)Z(n, m) .
(7)
©
ª
©
ª
Por exemplo, [(1, 2)] = (0, 1), (1, 2), (2, 3), (3, 4), . . . e [(5, 2)] = (3, 0), (4, 1), (5, 2), (6, 3), . . . .
Também definimos uma soma de classes de equivalência por
[(a, b)] + [(n, m)] := [(a + n, b + m)].
(8)
1. Prove que Z é uma relação de equivalência.
2. Verifique que [(1, 2)] + [(5, 2)] = [(0, 1)] + [(3, 0)].
3. Generalizando o item anterior prove que a soma de conjuntos definida acima
é compatível com a relação de equivalência, isto é, a soma não depende dos
representantes de cada classe de equivalência envolvida.
Definimos um produto de classes de equivalência por
[(a, b)] · [(n, m)] := [(an + bm, am + bn)].
(9)
Prove que tal operação é compatível com a relação de equivalência, isto é, ela não
depende dos representantes de cada classe de equivalência envolvida.
Observação 5. Os exercícios 2 e 3 nos dizem que partição e relação de equivalência são definições equivalentes.
12
Exercícios
1. Verifique se são relações de equivalência:
(a) Em R, x ∼ y se x − y ∈ Q.
(b) Em R, x ∼ y se x ≤ y.
(c) Em R, x ∼ y se |x − y| ≤ 1.
(d) Em X não vazio, x ∼ y para todo x, y ∈ X .
(e) Em R2 , P ∼ Q se a reta PQ passa pela origem.
(f) Em [−1, 1], x ∼ y se sin2 (x) + cos2 (y) = 1.
2. Suponha que ∼ é uma relação simétrica e transitiva sobre o conjunto X .
Se a ∼ b, então b ∼ a por simetria e, então, a ∼ a por transitividade, assim
a propriedade reflexiva é dispensável na definição de relação de equivalência, pois é consequência das outras duas. O que está errado?
1 Números Naturais e Indução Matemática
Os axiomas de Peano apareceram na publicação de 1889 Arithmetic principia:
novo methodo exposita — Novo método de exposição dos princípios da Aritmética. Esses axiomas formalizavam a ideia de que todos os números naturais podem ser obtidos a partir do número 1 pela soma sucessiva da unidade. O grande
mérito de Guiseppe Peano (1858-1932) foi a constatação de que a partir de quatro axiomas pode-se conceituar ou deduzir todas as definições e propriedades dos
números naturais, como por exemplo: adição, multiplicação e relação de ordem.
Na realidade, os axiomas conhecidos como Axiomas de Peano foram enunciados pela primeira vez por Dedekind um ano antes, em 1888. Dedekind usou de
modo informal a teoria dos conjuntos, Peano, trabalhando de modo independente, não construiu sua teoria dentro da teoria dos conjuntos. Apresentamos a
seguir uma breve exposição dos axiomas de Peano.
13
Axiomas de Peano. Vamos começar um estudo aritmético do conjunto N dos
números naturais com uma abordagem formal a partir da construção lógica de
N. Consideremos conceitos elementares de teoria dos conjuntos e três conceitos
primitivos: número natural, zero e sucessor. O conjunto dos números naturais
é caracterizado pelas seguintes propriedades:
1. Todo número natural possui um único sucessor, que também é um número natural.
2. Existe um único número natural que não é sucessor de nenhum outro.
Este número é chamado de zero e é representado pelo símbolo 0.
3. Números naturais diferentes possuem sucessores diferentes.
4. Axioma da Indução: Se um conjunto de números naturais contém o número 0 e, além disso, contém o sucessor de cada um dos seus elementos,
então esse conjunto coincide com o conjunto dos números naturais.
Ou seja, 0 ∈ N e existe uma função injetiva s : N → N \ {0}, que associa a cada
n ∈ N um elemento s(n) ∈ N, chamado de sucessor de n. O axioma da Indução
fica escrito assim
Axioma da Indução: Paa todo X , se X ⊂ N é um subconjunto tal
que
1. 0 ∈ X e
2. ∀n, n ∈ X ⇒ s(n) ∈ X ,
então X = N.
Exercício 6. Nenhum número é sucessor dele mesmo
Solução. Seja X o conjunto dos números naturais n tais que n 6= s(n).
0 ∈ X pelo axioma 2.
n ∈ X ⇒ n 6= s(n); pelo axioma 3, s(n) 6= s(s(n)), portanto, s(n) ∈ X .
Pelo axioma da indução X = N.
14
s é bijetiva:
Exercício 7. Todo natural, exceto o zero, é sucessor de algum número natural.
Solução. Seja S o conjunto de todos os naturais que são sucessores de outro
natural. Definimos X := {0} ∪ S. Então X ⊂ N e 0 ∈ X .
Seja n ∈ X , vamos mostrar que s(n) ∈ X . Se n 6= 0 então n = s(m) e s(n) =
s(s(m)) (ax. 3); como o natural s(n) é sucessor de alguém (a saber, de s(m)) ele
está em S, logo s(n) ∈ X . Se n = 0, então s(0) ∈ S, portanto, s(0) ∈ X .
Pelo axioma da indução X = N, portanto, S = N \ {0}.
Denota-se 1 := s(0), 2 := s(1) = s(s(0)), 3 := s(2) = s(s(s(0))) e assim vai.
1.1 Operações aritméticas
Adição: Para cada m ∈ N, somar m é definido por
1. m + 0 = m;
2. m + s(n) = s(m + n).
De modo que
m + 1 = m + s(0) = s(m + 0) = s(m).
(10)
Daí 1+1 = s(1) = 2. Notemos que s(1) = 2 é uma definição enquanto que 1+1 = 2
é um teorema.
Fixado m ∈ N, notemos que se
X m := {n ∈ N : m + n está definido }
então pelo Axioma da Indução X m = N pois
a. 0 ∈ X m
b. se m + n está definido então s(m + n) ∈ N logo m + s(n) está definido.
15
X m = N vale para todo natural m, portanto, m + n está definido para todo par de
número naturais.
Observação: + é uma operação binária + : N × N → N e escrevemos a +b para
denotar +(a, b). A rigor, a demonstração acima tem o problema de que “está definido” usando em X n não tem significado preciso. É possíver provar que f : N → N
que satisfaça f (0) = m e f (s(n)) = s( f (n)) existe e é única, ou seja, a soma é a
única operação binária sobre N que satisfaz os itens 1 e 2 acima.
Multiplicação: Para m ∈ N, multiplicar por m é definido por
1. m · 0 = 0
2. m · s(n) = m · n + m.
Exercício 8. Mostre que m · n está definido para todo par m, n de números naturais.
Observação: · é uma operação binária · : N × N → N e escrevemos a · b para
denotar ·(a, b). Como na observação anterior, é possíver provar que f : N → N que
satisfaça f (0) = m e f (s(n)) = s( f (n)) existe e é única, ou seja, amultiplicação é a
única operação binária sobre N que satisfaz os itens 1 e 2 acima.
A adição e a multiplicação de números naturais têm as seguintes propriedades.
Teorema 9. Sejam a, b, c, m, n, p números naturais quaisquer
1. (adição é associativa)(a + b) + c = a + (b + c)
Demonstração. Dados a e b, seja X := {c : (a + b) + c = a + (b + c)}.
Se c = 0, então (a + b) + 0 = a + b e a + (b + 0) = a + b, portanto 0 ∈ X .
Seja c ∈ X . Então (a + b) + s(c) = s((a + b) + c) = s(a + (b + c)). Usando a
definição de soma duas vezes s(a + (b + c)) = a + s(b + c) = a + (b + s(c)).
Portanto s(c) ∈ X . Pelo axioma da indução X = N.
16
2. (adição é comutativa) a + b = b + a
Demonstração. Começamos com o caso a = 1. Lembremos de (10) que
s(b) = b + 1. Seja X = {b : s(b) = 1 + b}. Verifique que 0 ∈ X . Se b ∈ X então
s(b) = 1+b, logo s(s(b)) = s(1+b) = 1+ s(b), logo s(b) ∈ X , portanto X = N.
Com isso b + 1 = 1 + b para todo natural b.
Agora, Y := {a : a + b = b + a(∀b)}. 0, 1 ∈ Y . Se a ∈ Y então s(a) + b =
(a+1)+b = a+(1+b) = a+s(b) = s(a+b) = s(b+a). Agora, s(b+a) = b+s(a),
portanto, s(a) ∈ X . Assim Y = N.
3. (elemento neutro da adição) 0 é o único natural tal que a + 0 = 0 + a = a
Demonstração. Que a + 0 = 0 + a segue da comutatividade. Falta provar
que 0 é o único natural com essa propriedade. Seja u tal que a+u = u+a =
a para todo natural a. Tomando a = 0, u + 0 = 0 portanto u = 0.
4. (lei de cancelamento da adição) a + c = b + c ⇒ a = b
Demonstração. Exercício: dado que
a + s(c) = b + s(c) ⇒ s(a + c) = s(b + c) ⇒ a + c = b + c
justifique a última implicação e complete a demonstração.
5. Se a + b = 0 então a = b = 0.
Demonstração. Se a + b = 0 e b 6= 0 então existe um natural c tal que
b = s(c) e a + s(c) = 0. Da definição de soma s(a + c) = 0, que contradiz
o axioma 2. Analogamente, se a 6= 0 então derivamos uma contradição.
Portanto, a = b = 0.
6. (elemento neutro da multiplicação) m · 1 = 1 · m = m e 1 é único com essa
propriedade.
17
Demonstração. Exercício.
7. (multiplicação é associativa)(m · n) · p = m · (n · p).
Demonstração. Exercício.
8. (multiplicação é comutativa) m · n = n · m.
Demonstração. Veja exercício 13 a seguir.
9. (lei de cancelamento da multiplicação) mp = np e p 6= 0 ⇒ m = n.
Demonstração. Exercício.
10. (multiplicação é distributiva com respeito a adição) (a+b)·m = a·m+b·m.
Demonstração. Exercício.
11. Se m · n = 0 então m = 0 ou n = 0.
Demonstração. Se m · n = 0 e n 6= 0. Então n = s(p) para algum natural p.
Então m · n = m · s(p) = mp + m = 0. Pelo item 5 mp = m = 0, assim m = 0.
Analogamente, se m 6= 0 deduzimos que n = 0.
12. Se m · n = 1 então m = n = 1.
Demonstração. Se m = 0 ou n = 0 então m · n = 0 pela definição de produto. Portanto, existem naturais a e b tais que m = s(a) e n = s(b). Assim
s(a)s(b) = 1, porém 1 = s(a)s(b) = (a + 1)(b + 1) = ab + a + b + 1. Usando
a lei de cancelamento, item 4, ab + a + b = 0, portanto ab = a + b = 0. De
a + b = 0 temos a = b = 0, pelo item 5, logo m = n = 1.
18
1.2 Relação de ordem ≤
Para a, b ∈ N escrevemos
a ≤b
se existe um natural m tal que
a + m = b.
Escrevemos a < b caso m 6= 0. Ainda a ≥ b equivale a b ≤ a e a > b equivale a
b < a. A relação ≤ é
reflexiva ∀a ∈ N, a ≤ a, pois
a = a + 0;
anti-simétrica ∀a, b ∈ N, se a ≤ b e b ≤ a então b = a, pois existem naturais
m, n
a ≤b
⇒
a +m = b
b≤a
⇒ b +n = a
portanto (a + m) + n = a, donde a + (m + n) = a por associatividade da
soma, pela lei cancelativa da soma m+n = 0; disso sabemos que m = n = 0
(teo. 9, item 5);
transitiva ∀a, b, c ∈ N, se a ≤ b e b ≤ c então a ≤ c, pois
a ≤b
⇒
a +m = b
b≤c
⇒ b +n = c
portanto (a + m) + n = c, donde a + (m + n) = c e por definição de ≤ temos
a ≤ c.
Teorema 10. Para quaisquer a, b ∈ N, a ≤ b ou b ≤ a.
Demonstração. Para um dado natural b definimos
X b := {n : n ≤ b} ∪ {n : b ≤ n}.
19
Vamos mostrar que X b = N, assim a ∈ X b portanto a ≤ b ou b ≤ a.
Como 0 ≤ b temos 0 + b = b, portanto, 0 ∈ X b .
Seja n ∈ X b , então n ≤ b ou b ≤ n. Se n ≤ b então existe r tal que n + r = b.
Caso r = 0, de n = b temos s(n) = b + 1 ∈ X b pois b ≤ b + 1. Caso r 6= 0 existe u tal
que r = s(u). De n+s(u) = b temos s(n)+u = b, portanto b ≤ s(n), logo s(n) ∈ X b .
Se b ≤ n, então b + t = n para algum t , donde s(n) = s(b + t ) = b + s(t ), isto é,
b ≤ s(n) portanto s(n) ∈ X b .
Pelo axioma da indução X b = N.
Exercício 11 (Lei da tricotomia em N). Para quaisquer a, b ∈ N, vale uma e só
uma das relações
a = b, a < b, b < a
Solução. Dados naturais a e b, pelo teorema acima a ≤ b ou b ≤ a. Logo existem
n, m ∈ N tais que a + n = b ou b + m = a. Se a 6= b então n, m 6= 0, portanto a < b
ou b < a.
Agora, se a < b e b < a então a+n = b e b+m = a para n e m naturais diferentes de 0. De a + n = b e b + m = a concluímos que (b + m) + n = b (substituindo a
segunda na primeira); pela associativa b+(m+n) = b, pela cancelativa, m+n = 0
e pelo item 5 do teorema 9 m = n = 0. Uma contradição.
Se a < b e a = b então a + n = b e a = b para n natural diferente de 0. De
a + n = b e a = b concluímos que a + n = a, portanto, n = 0. Uma contradição.
Se a < b e a = b então a + n = b e a = b para n natural diferente de 0. De
a + n = b e a = b concluímos que a + n = a, portanto, n = 0. Uma contradição.
Desse modo vale exclusivamente um de a = b, a < b, b < a.
Exercício 12. Mostre que ≤ é compatível com a adição, i.e.,
a ≤ b ⇒ a +c ≤ b +c
(∀c)
(11)
e é compatível com a multiplicação, i.e.,
a ≤ b ⇒ a ·c ≤ b ·c
20
(∀c).
(12)
Exercício 13. Deduza de (11) o item 4 do teorema 9.
Exercício 14. Se a < b então a + 1 ≤ b. Prove a recíproca.
Solução: Se a < b então a + r = b com r 6= 0. Existe n tal que r = n + 1. Assim
a +(n +1) = b, porém a +(n +1) = a +(1+n) = (a +1)+n e de (a +1)+n = b temos
a + 1 ≤ b.
Obs.: n < p < n + 1 denota: n < p e p < n + 1
Exercício 15. Prove que não existe natural p tal que n < p < n + 1, qualquer que
seja n ∈ N.
Solução: Se p ∈ N é tal que que n < p < n + 1 então, por definição de <, existem
naturais a, b ∈ N \ {0} tais que
n+a
=
p
p +b
= n +1
logo n + (a + b) = (n + a) + b = p + b = n + 1, ou seja, a + b = 1 pela lei cancelativa
da adição. Mas não pode haver a, b ∈ N \ {0} com a + b = 1, logo temos uma
contradição.
1.3 Subtração em N
Definimos
b − a := c, sempre que a ≤ b em que c é o natural tal que a + c = b
(13)
c existe por definição de ≤. Portanto, para quaisquer a, b, c com a ≤ b
b −a = c ⇔ b = a +c
(14)
Como a ≤ a, está definido a − a que, por (14), vale a − a = 0. Por definição
b = a + (b − a).
21
Proposição 16. Para quaisquer a, b, c com a ≤ b vale
c · (b − a) = c · b − c · a
Demonstração. Primeiro, verifiquemos que c · b − c · a está definido. De fato,
pela compatibilidade da multiplicação com a relação de ordem, exercício 12,
a ≤ b ⇒ a · c ≤ b · c. Agora, pela definição de ≤, existe um natural d tal que
a + d = b, portanto, c · (a + d ) = c · b; usando os itens 8, 10 e 8 do teorema 9
c · (a + d ) = (a + d ) · c
= a ·c +d ·c
= c ·a +c ·d
logo c · a + c · d = c · b e por (14)
c ·b −c ·a = c ·d
e a proposição segue do fato de que d = b − a que decorre de (14) e da escolha
de d .
Exercícios
1. Prove os itens 6,7,9 e 10 do teorema 9.
2. Prove que a multiplicação tem 1 como único elemento neutro.
3. Seja a 6= 0. Mostre que a potência a n está definida para todo n ∈ N se
a0
a s(n)
:= 1
:=
a · an
4. Prove que a ≤ b ⇒ a n ≤ b n .
5. Prove que não existem a, b ∈ N \ {0} com a + b = 1.
22
6. Mostre que o fatorial, n!, está definido para todo n ∈ N se
0! := 1
(n + 1)! := (n + 1) · n!
7. Sejam a, b, c naturais tais que esteja definido a − (b − c). Mostre que (a +
c) − b está bem definido e a − (b − c) = (a + c) − b.
8. Sejam a, b, c naturais tais que b + c ≤ a. Mostre que a − (b + c) e (a − b) − c
estão bem definidos e a − (b + c) = (a − b) − c.
9. Sejam a, b, c naturais tais que 0 < c < b < a. Mostre que 0 < b−c < a−c < a.
10. Sejam a, b, c naturais tais que a ≤ c e b ≤ c. Mostre que, se c − a ≤ c − b
então b ≤ a.
11. Sejam a, b, c, d naturais tais que a ≤ b e c ≤ d . Mostre que b − a ≤ d − c ⇔
b + c ≤ a + d.
12. Mostre que s(m − 1) = m sempre que m − 1 está definido.
1.4 Princípio da Boa Ordem (PBO)
Teorema 17 (PBO). Todo A ⊂ N não-vazio tem um menor elemento, ou seja,
existe a ∈ N tal que
a∈A
∀x ∈ A, a ≤ x.
Demonstração. Se 0 ∈ A então 0 é o menor elemento de A pois 0 ≤ n para todo
natural n. De fato 0 + n = n, donde 0 ≤ n.
Supondo 0 6∈ A definimos
X := {n ∈ N : para todo k ≤ n, k ∉ A}
23
e notamos que 0 ∈ X (pois, 0 6∈ A). Se valer que n ∈ X ⇒ n + 1 ∈ X para todo
natural n, então teremos X = N, o que não é verdade (por quê?), portanto existe
um natural m tal que m ∈ X e m + 1 6∈ X .
De m ∈ X temos que n ∉ A para todo n ≤ m e de m + 1 ∈ X temos m + 1 ∈ A e
como não há p, m < p < m + 1, m + 1 é menor elemento de A. De fato,
x ∈ A⇒x >m
portanto, pelo exercício 8, x ≥ m + 1.
Exercício 18. A ⊆ N é dito limitado superiormente se existir um natural n tal que
∀x ∈ A, x ≤ n
e se n com a propriedade acima pertence a A ele é dito maior elemento de A.
Mostre que se A é limitado superiormente e não vazio então admite maior
elemento.
Exemplo 19. Para toda função não-crescente f : N → N existe um natural n 0 a
partir do qual f é constante. A imagem da função, Im( f ), é um subconjunto não
vazio de naturais. Seja n 0 um natural tal que f (n 0 ) é o menor elemento de Im( f ).
Como f é não-crescente n ≥ n 0 ⇒ f (n) ≤ f (n 0 ), mas f (n) 6< f (n 0 ) pois f (n 0 ) é o
menor elemento de Im( f ), portanto n ≥ n 0 ⇒ f (n) = f (n 0 ).
1.5 Princípios de Indução
O axioma de indução tem um papel de fundamental não só na teoria dos números naturais como em toda matemática. É visto como um método de demonstração, conhecido como Princípio de Indução Matemática ou Princípio de
Indução Finita, usualmente expresso da seguinte maneira
P (n) é um predicado sobre N
24
Princípio da Indução Finita (PIF). Se são satisfeitas as condições
1. P (0) é verdadeiro, e
2. para todo k ≥ 0, se P (k) é verdadeiro então P (k + 1) é verdadeiro,
então P (n) é verdadeiro para todo natural n.
Esse princípio decorre facilmente do axioma da Indução se tomarmos X
como o conjunto dos naturas para os quais o predicado é verdadeiro, isto é,
X = {n ∈ N : P (n) é verdadeiro}
da condição 1 temos 0 ∈ X da condição 2 temos que se k ∈ X então k + 1 ∈ X ,
portanto, X = N.
Princípio da Indução Finita generalizado (PIFg). Seja a um número natural.
Se
1. P (a) é verdadeiro, e
2. para todo k ≥ a, se P (k) é verdadeiro então P (k + 1) é verdadeiro,
então P (n) é verdadeiro para todo natural n ≥ a.
Esse princípio decorre do Princípio da Boa Ordem da seguinte forma: suponha que não vale a sentença “P (n) é verdadeiro para todo natural n ≥ a”, logo
A := {n ∈ N : n ≥ a e P (n) não é verdadeiro}
é não vazio, portanto admite um menor elemento b := min A.
b > a (estrito pois a ∉ A) logo b não é zero, portanto existe existe um natural
c tal que b = s(c) = c + 1, ainda b > a ⇒ c ≥ a mas como b é o menor elemento
de A devemos ter c 6∈ A, ou seja, P (c) é verdadeiro. Mas, isso implica (condição
2) que P (c + 1) = P (b) é verdadeiro, uma contradição.
25
Exemplo. 2n < n! para todo n ≥ 4: P (n) é 2n < n! que é verdadeiro para n = 4
(confira). Seja k um natural maior ou igual a 4 e assumamos que P (k) é verdadeiro, ou seja
2k < k!
(15)
Pela escolha de k, k > 1 ⇒ k + 1 > 2 ⇒ (k + 1) · k! > 2 · k!, portanto (k + 1)! > 2 · k! e
usando (15) (k + 1)! > 2k+1 . Pelo PIFg, 2n < n! para todo n ≥ 4.
Notemos que, da dedução acima, PBO⇒PIFg. Entretanto, PIFg⇒PIF, basta
tomar a = 0 e provamos o PBO usando PIF, isto é, PIF⇒PBO, portanto
PIF⇒PBO⇒PIFg⇒PIF
tais princípios são equivalentes.
Princípio da Indução Finita, segunda forma (PIF2). Seja a um número natural. Se
1. P (a) é verdadeiro, e
2. P (k) verdadeiro para todo k ∈ {a, a + 1, . . . , n} implica P (n + 1) verdadeiro,
então P (n) é verdadeiro para todo natural n ≥ a.
Exercícios
1. Seja a um número natural e P um predicado sobre N. Verifique o seguinte
Princípio de Indução: Se
(1) P (a) é verdadeiro, e
(2) P (b) verdadeiro para todo b ∈ {a, a + 1, . . . , k} implica P (k + 1) verdadeiro,
então P (n) é verdadeiro para todo natural n ≥ a.
26
2. Seja a i uma sequência (estritamente) crescente de números naturais. Verifique o seguinte Princípio de Indução: Se P (n) é um predicado a respeito
de n ∈ N de modo que
(1) P (a i ) é verdadeiro para todo i ∈ N e
(2) P ( j ) verdadeiro implica P ( j − 1) verdadeiro, para todo j > a 1
então P (n) é verdadeiro para todo n ≥ a 1 .
3. Descubra uma falha na prova: todos os números naturais são iguais Denotamos por max(a, b) o maior número natural dentre a e b. Vamos mostrar
por indução que se max(a, b) = n então a = b.
(a) Se max(a, b) = 0 então a = b = 0.
(b) Suponha que se max(a, b) = k − 1 então a = b.
Vamos mostrar que
se max(a, b) = k + 1 então a = b.
Suponha que max(a, b) = k + 1. Então max(a − 1, b − 1) = k e pela
hipótese indutiva a − 1 = b − 1, portanto a = b.
4. Sejam A 1 , A 2 , . . . , A n conjuntos e n ≥ 2. Suponha que para dois conjuntos
quaisquer A i e A j vale que A i ⊆ A j ou A j ⊆ A i . Prove, por indução, um
desses conjuntos é subconjunto de todos eles.
5. Prove, usando indução, que todo número natural, exceto o zero, pode ser
expresso como soma de potências distintas de 2
6. Demonstre usando indução:
(a) 9 + 9 · 10 + 9 · 102 + · · · + 9 · 10n−1 = 10n − 1.
(b) 1 + 3 + 5 + · · · + (2n − 1) = n 2 .
(c) 1 + 2 + 4 + · · · + 2n = n(n + 1)
(d) 2n ≤ 2n+1 − 2n−1 − 1
27
(e) n! < n n , n ≥ 2
(f) 13 + 33 + · · · + (2n + 1)3 = (n + 1)2 (2n 2 + 4n + 1)
2 Divisibilidade em N
Dizemos que o natural a divide o natural b, e escrevemos a|b, se existe um natural c tal que b = a · c. Em símbolos essa definição é
a|b ⇔ ∃c ∈ N, b = a · c
Notação: 6 | significa não divide e b é múltiplo de a significa a|b.
Observação. 0|0 pois 0 = 0 · c para todo c, mas 0 6 |b caso b 6= 0 pois, nesse caso,
não existe c tal que b = 0 · c. Ainda a|0.
Como o menor ou igual, o divide é uma relação sobre o conjunto N que satisfaz1
reflexiva ∀a ∈ N, a|a , pois a = a · 1;
antissimétrica ∀a, b ∈ N, se a|b e b|a então b = a , pois de a|b e b|a ou a =
b = 0 ou a, b 6= 0 e existem naturais m, n
a|b
⇒
a ·m = b
b|a
⇒ b ·n = a
portanto (a · m) · n = a, donde tiramos que m · n = 1 e disso sabemos que
m = n = 1 (teo. 9, item 12);
transitiva ∀a, b, c ∈ N, se a|b e b|c então a|c , pois
a|b
⇒
a ·m = b
b|c
⇒ b ·n = c
portanto (a · m) · n = c, donde a|c.
1 toda relação reflexiva, antissimétrica e transitiva sobre um conjunto é chamada de ordem
parcial sobre o conjunto.
28
Teorema 20. Para quaisquer números naturais a, b, c, d
1. 1|a;
2. a|b e c|d ⇒ a · c|b · d ;
£
¤
3. a|(b + c) =⇒ a|b ⇔ a|c ;
£
¤
4. c ≤ b e a|(b − c) =⇒ a|b ⇔ a|c ;
5. a|b e a|c ⇒ a|(bx + c y) para todos x, y ∈ N. Também, a|b e a|c ⇒ a|(bx −
c y) para todos x, y ∈ N pros quais bx ≥ c y;
6. a|b e b 6= 0 ⇒ a ≤ b.
Demonstração.
1. De 1 · a = a segue que 1|a.
2. Se a|b e c|d então existem m, n ∈ N tais que
a ·m = b
c ·n = d
de modo que b · d = (a · m) · (c · n) = (a · c) · (m · n), portanto a · c|b · d .
3. Suponhamos que a|(b + c), i.e, a · d = b + c para algum d . Se a = 0 então
b + c = 0, então b = c = 0 e vale a conclusão. Seja a 6= 0.
Se a|b, a · x = b para algum x, portanto a · d = a · x + c, assim a · x ≤ a · d e
pela equação (14)
a ·d −a ·x = c
como a 6= 0, a · x ≤ a · d ⇒ x ≤ d e pela Proposição 16
a · (d − x) = c
donde concluímos que a|c.
Acima provamos que a|b ⇒ a|c. Resta provar que a|c ⇒ a|d .
a|c ⇒ a · y = c ⇒ a · d = a · y + b ⇒ a · (d − y) = b ⇒ a|b
pelas mesmas justificativas apresentadas acima.
29
4. Exercício.
5. Se a|b e a|c então existem m, n ∈ N tais que
a ·m = b
a ·n = c
portanto, dados x, y ∈ N
a ·m ·x = b ·x
a ·n · y = c · y
portanto
a ·m ·x +a ·n · y = b ·x +c · y ⇔
a · (m · x + n · y) = b · x + c · y
ou seja a|(bx + c y).
6. a|b e b 6= 0 ⇒ a · c = b para algum c 6= 0; também, c = d + 1 para algum
d ∈ N. Portanto a · (d + 1) = b o que implica em
a +a ·d = b
que equivale a a ≤ b.
2.1 Algoritmo de divisão
Exercício 21. Sejam a e b números naturais, b 6= 0. Então para algum natural q
bq ≤ a < b(q + 1).
(16)
Solução. Se a < b então q = 0 é o único natural que satisfaz (16). Se a ≥ b então
definimos o conjunto
A := {n ∈ N : bn > a}
30
que é não-vazio pois a + 1 ∈ A (verifique2 ), portanto tem um menor elemento
m > 0 (pois 0 ∉ A); ademais m é sucessor de algum natural q, m = q +1, b(q +1) >
a e, pela minimalidade de q + 1, temos que bq ≤ a.
Continuando nas hipóteses acima, se bq ≤ a então existe um natural r tal
que
bq + r = a
e com r < b pois, caso contrário, r ≥ b ⇒ bq + r ≥ b(q + 1) ⇒ a ≥ b(q + 1) contrariando (16).
Ademais, tais r e q são únicos. Por (14)
bq + r = a ⇔ r = a − bq
Admitamos que exista r 0 6= r com r 0 = a − bq 0 , r = a − bq e r 0 < r < b. Então
bq 0 + r 0 = bq + r ⇔
bq 0 = bq + r − r 0
portanto b|(bq + r − r 0 ) e pelo teorema 20, item 3, b|(r − r 0 ) e pelo teorema 20,
item 6, b ≤ r −r 0 , contrariando r < b. Caso r < r 0 , por dedução análoga, também
termina em contradição. Pela lei de tricotomia r = r 0 . Agora, se r 0 = a − bq 0 e
r = a − bq e r = r 0 então q = q 0 , ou seja, q também é único.
Em resumo, os naturais q e r cujas existência foi determinada acima são os
únicos a satisfazerem bq + r = a. Provamos o seguinte teorema
Teorema 22 (Algoritmo da divisão, livro VII de Elementos de Euclides, 300 aC).
Para todo natural a e todo natural b 6= 0 existe um único natural q e um único
natural r com r < b tal que
a = bq + r.
Notação No teorema acima, caso a = bq + r
2 b ≥ 1 ⇒ ba ≥ a ⇒ ba + b ≥ a + b > a
31
(17)
a é o dividendo, b é o divisor
ba/bc := q é o quociente da divisão, quando r = 0 escrevemos apenas a/b
a mod b := r é o resto é o resto.
Outra prova do teorema da divisão. Se a < b então basta tomarmos q = 0 e, assim, r = a. Agora, para unicidade, se q > 0 então q ≥ 1 (exercício 14), então
bq + r ≥ b1 + r para todo r (exercício 12), ou seja, a ≥ b + r para todo r . Fazendo
r = 0 temos a ≥ b. Portanto q é único, e por conseguinte r também é único.
Se a ≥ b, a ideia é considerar as sucessivas subtrações a, a−b, a−2b, a−3b, . . .
enquanto estiver definida. Definimos o conjunto
R := {n ∈ N : a − bn está definido }.
(18)
e como 1 ∈ R, R 6= ;. Como a −bn ≤ a (∀n ∈ R) podemos definir q como o maior
elemento de R, que existe pelo exercício 18, e r := a − bq.
Por (14)
bq + r = a ⇔ r = a − bq.
Caso r ≥ b deduzimos
∃t , r + t = b ⇔ ∃t , bq + r + t = bq + b ⇔ ∃t , a + t = b(q + 1)
portanto q + 1 ∈ R, o que contraria o fato de q ser o maior elemento desse conjunto, portanto, r < b.
Para provar a unicidade, suponhamos que r = a − bq e r 0 = a − bq 0 e r < r 0 <
b. Assim, r 0 − r = b(q − q 0 ) e b|(r − r 0 ) donde b ≤ r − r 0 , um absurdo. Analogamente, não vale r 0 < r . Portanto r = r 0 , e disso a −bq = a −bq 0 , donde q = q 0 .
Exemplo. Do teorema temos que o resto da divisão de n por 2, para qualquer
n ∈ N, é 0 ou 1; quando o resto é 0 dizemos que n é um natural par e quando o
resto é 1 dizemos que n é um natural ímpar. A característica de um número ser
par ou ímpar é chamada de paridade.
Exemplo. Todo número natural pode ser escrito em uma (e só uma) das formas:
3q, 3q + 1, 3q + 2.
32
Exemplo. 253 = 50 · 5 + 3, portanto, os naturais menores ou iguais a 253 e múltiplos não-nulos de 5 são: 1 · 5, 2 · 5, 3 · 5, . . . , 49 · 5, 50 · 5.
De um modo geral, se b ≤ a então a quantidade de naturais menores ou
iguais a a que são múltiplos não-nulos de b é ba/bc.
Exercício 23. Discuta a paridade da adição, do produto, da subtração e da potência de números naturais.
Exercício 24. Um número natural a é par se e somente se a n é par para todo
n ∈ N \ {0}.
Solução. Seja a um natural par. Então a 1 é par. Suponhamos que para n > 1
fixo, a n−1 é par, então a n = a n−1 · a e por ser o produto de dois pares, a n é par.
Pelo PIFg a n é par para todo n ≥ 1.
Se a n é par para todo n ∈ N \ {0}, em particular a 1 é par.
2.2 Representação — sistemas posicionais
No sistema decimal 253 = 200 + 50 + 3 cada algarismo tem o seu valor e, além
disso, um peso determinado pela posição; todo natural m é escrito como o numeral d n d n−1 . . . d 1 d 0 com d i ∈ {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} para todo i de modo que
m = d n · 10n + d n−1 · 10n−1 + · · · + d 1 · 10 + d 0
Exemplo. No sistema binário os números são escritos com os algarismos 0 e 1 do
sistema posicional de base 2
253 = (11111101)2 = 1 · 27 + 1 · 26 + 1 · 25 + 1 · 24 + 1 · 23 + 1 · 22 + 0 · 21 + 1 · 20
Em computação {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B,C , D, E , F } são os algarismos do sistema
posicional de base 16
253 = (F D)16 = 15 · 161 + 13 · 160
33
Teorema 25. Seja b > 1 um natural e R = {0, 1, . . . , b − 1}. Para todo natural m
existem natural n e únicos d i ∈ R para 0 ≤ i ≤ n, tais que
m = d n · b n + d n−1 · b n−1 + · · · + d 1 · b + d 0
(19)
com d n 6= 0, exceto quando m = 0.
Demonstração. Se m = 0 então n = 0 e d 0 = 0; se m = 1 então n = 0 e d 0 = 1.
Seja m > 1 um natural e assumamos que todo natural menor que m pode ser
representado de forma única como em (19).
Usando o algoritmo de divisão para dividir m por b temos que existem q e r
únicos tais que
m = bq + r, r < b
e pela hipótese de indução, pois q < m (justifique), existem e 0 , e 1 , . . . , e n 0 −1 , e n 0
únicos tais que
0
q = e n0 · bn + · · · + e 1 · b + e 0
para algum n 0 . Assim
0
bq + r = e n 0 · b n +1 + · · · + e 1 · b 2 + e 0 b + r
de modo que, fazendo
d0 = r
d i = e i −1 para 1 ≤ i ≤ n
e depois disso fazendo n = n 0 + 1, o resultado segue pela segunda forma do PIF.
Da demostração acima tiramos que a representação de m na base b é obtida
34
por
m = bq 0 + d 0
q 0 = bq 1 + d 1
q 1 = bq 2 + d 2
..
.
como q 0 > q 1 > q 2 > · · · essa sequência fica constante a partir de algum n (exemplo 19), de fato, quando q n−1 < b temos q n = 0 e a partir daí os restos valem 0 e
temos (19).
Exemplo. 253 na base binária é obtido por
253 = 2 · 126+1
126 = 2 · 63+0
63 = 2 · 31+1
31 = 2 · 15+1
15 = 2 · 7+1
7 = 2 · 3+1
3 = 2 · 1+1
1 = 2 · 0+1
Exemplo 26 (divisibilidade por 5). Dado n ∈ N,
n = d t · 10t + d t −1 · 10t −1 + · · · + d 1 · 10 + d 0
= 10(d t −1 · 10t −2 + d t −2 · 10t −3 + · · · + d 1 ·) + d 0
assim, se 5|n, como 5|10(d t −1 ·10t −2 +d t −2 ·10t −3 +· · ·+d 1 ·) (teorema 20) portanto
deve dividir d 0 , logo
d 0 ∈ {0, 5}
35
de modo que um natural é divisível por 5 se, e só se, termina com o algarismo 0
ou o algaismo 5.
Exemplo 27 (divisibilidade por 3). Vamos denotar, só nesse exemplo, por 9.[t. ].9 o
numeral escrito com t ocorrências do algarismo 9, por exemplo, 9.[3]
. .9 = 999.
Dado n ∈ N,
n = d t · 10t + d t −1 · 10t −1 + · · · + d 1 · 10 + d 0
= d t · (9.[t. ].9 + 1) + d t −1 · (9[t.−1]
. . 9 + 1) + · · · + d 1 · (9 + 1) + d 0
¡
¢
= d t · 9.[t. ].9 + d t −1 · 9[t.−1]
. . 9 + · · · + d 1 · 9 + (d t + d t −1 + · · · + d 0 )
¡
¢
= 9 · d t · 1.[t. ].1 + d t −1 · 1[t.−1]
. . 1 + · · · + d 1 · 1 + (d t + d t −1 + · · · + d 0 )
assim, se 3|n, como 3|9(d t −1 · 1.[t. ].1 + · · · + d 1 ) (teorema 20) portanto deve dividir
d t + d t −1 + · · · + d 0 , de modo que um natural é divisível por 3 se, e só se, a soma de
seus algarismos for divisível por 3.
Exercício 28. Obtenha um critério de divisibilidade por 9.
Exercícios
1. Mostre que 8|32n + 7 para todo n.
2. Mostre que 3|10n − 7n para todo n.
3. Mostre que 8|n 2 − 1 para todo n ímpar.
4. Mostre que 3|2n − 1 para todo n par.
5. Mostre que n 2 |(n + 1)n − 1 para todo n.
6. Sejam n ∈ N, x, y quaisquer x 6= −y. Mostre que x 2n − y 2n é divisível por
x + y. Mostre que x 2n−1 + y 2n−1 é divisível por x + y. Mostre que x n − y n é
divisível por x − y.
7. Seja n um natural. Um, e só um, número dentre n, n + 2, e n + 4 é divisível
por 3.
36
8. Mostre que se 3 6 |a então a 2 mod 3 = 1.
9. Use o exercício anterior para mostrar que se 3|(a 2 + b 2 ) então a e b são
divisíveis por 3.
10. Mostre que n 2 dividido por 6 nunca deixa resto 2.
11. Quantos múltiplos de 6 há entre 92 e 196?
12. Mostre que de dois números pares consecutivos um é divisível por 4.
13. Prove que (121)b em qualquer base b > 2 é um quadrado perfeito.
14. Prove que 4|(a r · · · a 1 a 0 )5 ⇔ 4|(a r + · · · + a 1 + a 0 )
15. Obtenha um critério de divisibilidade por 4.
2.3 MDC
Para todo a ∈ N denotemos por D(a) o conjunto dos divisores de a
D(a) = {m : m ∈ N e m|a}.
(20)
Para quaisquer a e b temos 1 ∈ D(a) ∩ D(b) e se não são ambos nulos temos,
para todo m ∈ D(a) ∩ D(b), que m ≤ max{a, b}, portanto a interseção é nãovazia e limitada superiormente. Pelo exercício 18 está definido o maior elemento max D(a) ∩ D(b) para quaisquer a, b ∈ N não ambos nulos. Notemos que
se a = b = 0 então D(a) ∩ D(b) = N.
mdc(a, b) é o maior divisor comum de a e b


0,
se a = b = 0,
mdc(a, b) :=

max D(a) ∩ D(b), caso contrário.
(21)
Claramente, mdc(a, b) = mdc(b, a); ressaltamos que mdc(0, 0) = 0 é uma convenção. Vejamos alguns casos particulares
1. a 6= 0 ⇒ mdc(0, a) = a
37
2. mdc(1, a) = 1.
3. b|a se, e somente se, mdc(a, b) = b.
Agora, se b 6 |a então temos a = bq + r , 0 6= r < b. Todo divisor de b e r divide
bq + r (teo. 20, item 5) portanto divide a e b; ou seja, D(b) ∩ D(r ) ⊂ D(a) ∩ D(b).
De r = a−bq, todo divisor de a e b divide r e b; ou seja, D(b)∩D(r ) ⊃ D(a)∩D(b).
Logo, D(b) ∩ D(r ) = D(a) ∩ D(b) e, então, mdc(a, b) = mdc(b, r ).
Repetindo esse processo temos mdc(b, r ) = mdc(r, b mod r ) e como o sequência dos restos é decrescente, em algum momento o resto é 0 e voltamos ao caso
do item 3 acima.
Teorema 29 (Algoritmo de Euclides, livro VII de Elementos de Euclides, 300 aC).
Se a = bq + r então mdc(a, b) = mdc(b, r ).
Assim, obtemos mdc(a, b) com divisões sucessivas:
a = bq 1 + r 1 , r 1 < b
b = r 1 q2 + r 2 , r 2 < r 1
r 1 = r 2 q3 + r 3 , r 3 < r 2
r 2 = r 3 q4 + r 4 , r 4 < r 3
r 3 = r 4 q5 + r 5 , r 5 < r 4
..
.
a sequência de restos r 1 , r 2 , . . . é decrescente, então (decorre do exemplo 19, ou
do PBO) para algum n
r n−2 = r n−1 q n + r n ,
r n < r n−1
r n−1 = r n q n+1 + r n+1 , r n+1 = 0
r n |r n−1 logo mdc(r n , r n−1 ) = r n e do teorema acima mdc(a, b) = mdc(b, r 1 ) =
· · · = mdc(r n−1 , r n ) = r n .
38
Exemplo. mdc(41, 12) = 1:
41 = 12 · 3+5
12 = 5 · 2+2
5 = 2 · 2+1
2 = 1 · 2+0
Exemplo 30 (números de Fermat). Fermat conjecturou que os números da forma
n
22 + 1 eram primos, para todo natural n; Euler mostrou que não era o caso de
5
22 + 1 = 4.294.967.297. Atualmente não é sabido se há uma quantidade infinita
de números de Fermat que são primos (veja mais aqui).
Para qualquer n > m
³ n
´
m
mdc 22 + 1, 22 + 1
Da identidade 22
m+1
m
(22)
m
− 1 = (22 + 1)(22 − 1) temos
´³ m
´³ m
´
³ n−1
´ ³ n−2
´ ³ n−3
´ ³ m+1
n
22 − 1 = 22 + 1 22 + 1 22 + 1 · · · 22 + 1 22 + 1 22 − 1
portanto
³
´¯³ n
´
m
¯
22 + 1 ¯ 22 − 1
m
n
portanto um divisor de 22 + 1 divide 22 − 1, ademais
³ n
´
n
22 + 1 = 22 − 1 + 2
n
n
portanto um divisor de 22 +1, que divide 22 −1, divide 2 (teo. 20, item 3), ou seja,
n
m
um divisor comum de 22 + 1 e 22 + 1, que são ímpares, divide 2, logo o mdc é 1.
Quando mdc(a, b) = 1 dizemos que a e b são coprimos ou primos entre si.
Exercício 31. Para a, b, c ∈ N,
1. mdc(ca, cb) = c · mdc(a, b).
2. Para a, b 6= 0, se mdc(a, b) = 1 então existem x e y tais que ax − b y = 1.
3. Se a|bc e mdc(a, b) = 1 então a|c.
39
4. Se a|c e b|c, c 6= 0, e mdc(a, b) = 1 então ab|c.
5. c é divisível por 6 se, e só se, é divisível por 2 e por 3.
6. Se mdc(a, c) = 1 e mdc(b, c) = 1 então mdc(ab, c) = 1.
Solução. Sejam a, b, c ∈ N.
1. Vamos provar o item 1. Do algoritmo da divisão, para mdc(a, b) com divisões sucessivas temos:
c a = (cb)q 1 + cr 1
cb = (cr 1 )q 2 + cr 2
cr 1 = (cr 2 )q 3 + cr 3
..
.
cr n−2 = (cr n−1 )q n + cr n
cr n−1 = (cr n )q n+1
logo mdc(ca, cb) = mdc(cb, cr 1 ) = · · · = mdc(r n−1 , r n ) = cr n = cmdc(a, b).
2. Para provar o item 2, primeiro observamos que se d = ax − b y para algum
x e algum y, então d = b y 0 − ax 0 para para algum x 0 e algum y 0 . De fato, se
d = ax−b y então por (16) existem q e p tais que q a > y e pb > x. Tomando
m := max{q, p} temos ma > y e mb > x. Agora, d = (ma − y)b − (mb − x)a.
Agora, consideremos d = ax 0 − b y 0 = b y 00 − ax 00 o menor natural não-nulo
que pode ser escrito da forma ax − b y. Notemos que a = a1 − b0 e que
b = ab − b(a − 1), portanto d está definido. Se m = ax − b y, então d |m:
pelo algoritmo da divisão r = m − d q e r < d , i.e,
r = ax − b y − (b y 00 − ax 00 )q = a(x + x 00 q) − b(y + y 00 q)
portanto existem x 1 , y 1 tais que r = ax 1 − b y 1 e r < d , e como d é o menor
não-nulo dessa forma, só resta a possibilidade de r = 0. Se d |m então d |a
e d |b, portanto d = 1.
40
3. Para o item 3, observamos que an − bm = 1 pelo item anterior, de modo
que anc − bmc = c. Como az = bc para algum z, temos anc − amz = c,
portanto a|c. Se a = 0 então b = 1 e c = 0, e se b = 0 então a = 1, então a|c
em ambos os casos.
4. Para o item 4, temos por hipótese (e item 1) que existem x, y, n, m tais que
ax = c, b y = c e an − bm = 1. Dessa última, anc − bmc = c e substituindo
anb y − bmax = c, ou seja ab(n y − mx) = c, portanto, ab|c. Se a = 0 então
c = 0, portanto, ab|c. Por hipótese c 6= 0, logo b 6= 0.
2.4 MMC
Analogamente, M (a) := {n · a : n 6= 0} ⊂ N denota o conjunto dos múltiplos de
a. Assim M (a) ∩ M (b) é não vazio, pois a · b está nessa intersecção, e pelo PBO
admite um menor elemento m, dizemos que m é o mínimo múltiplo comum
de a e b. Denotamos o maior divisor comum de a e b por mmc(a, b). É claro
que mmc(a, b) = mmc(b, a).
Proposição 32. Sejam a, b ∈ N. O mmc(a, b) existe e satisfaz
mdc(a, b) · mmc(a, b) = a · b
(23)
Antes de demonstrarmos essa proposição, vejamos uma notação bastante
útil. Usamos b ba c para o quociente da divisão
a =b
No caso r = 0 definimos
jak
b
+ r, r < b
jak
a
:=
b
b
(24)
e notemos que
b
jak
a
=b
= a.
b
b
41
(25)
Demonstração. Sejam a, b 6= 0 (os outros casos ficam como exercício),
d := mdc(a, b)
e, com a notação introduzida acima
m :=
ab
d
de modo que md = ab. Vamos mostrar que m = mmc(a, b)
Notemos que m = a db = b da (verifique), ou seja, m ∈ M (a) ∩ M (b). Ademais
µ
¶
a b
mdc ,
=1
(26)
d d
(verifique).
Agora, seja c ∈ M (a) ∩ M (b). Precisamos mostrar que m ≤ c e, para tal, provaremos que m|c (teo. 20, item 6).
Por hipótese existem q e k tais que c = q a e c = kb então q a = kb portanto,
por (25), qd da = kd db , e usando a cancelativa, q da = k db , portanto temos que
¯
a¯ b
d ¯k d .
¯
¯
Pelo exercício 31, item 2, da ¯k db e mdc( da , db ) = 1 implicam da |k, ou seja, existe
t tal que k = t da donde c = t da b = t m, i.e., m|c como queríamos.
Exercícios
1. Faça os itens 5 e 6 do exercício 31.
2. Prove que para a, b, c ∈ N o mdc satisfaz as seguintes propriedades:
(a) mdc(a, b) = mdc(a, b + a · c).
(b) mdc(a, c · a) = a.
3. Para quaisquer a e b, prove que se exitem n, m tais que an − bm = 1 então
mdc(a, b) = 1.
4. Para quaisquer a e b, prove que se exitem x, y ∈ N que satisfazem ax +b y =
mdc(a, b) então mdc(x, y) = 1
42
5. Determine mmc(n, 2n + 1) para todo n.
6. Prove que mmc(a, b) = ab se e só se mdc(a, b) = 1
7. M (a) ∩ M (b) = M (mmc(a, b))?
8. Prove que se a|m e b|m então mmc(a, b)|m.
9. Prove a equação (26).
3 Números primos e Teorema Fundamental da Aritmética
Um natural p > 1 é primo se os únicos divisores de p são 1 e p; se p > 1 não é
primo então é dito composto; logo, por definição, se p é composto então admite
um divisor d tal que 1 < d < n.
Exercício 33. Se a 6= 0, 1 e
d (a) := {n : n > 1 e n|a}
(27)
então o menor elemento de d (a) é um número primo.
Solução. d (a) 6= ; pois a ∈ d (a). Se m := min d (a) é composto então m = d q
para algum d , 1 < d < m. Como d |m e m|a temos, por transitividade, d |a.
Como m é menor elemento de d (a) e d < m, temos m 6∈ d (a), ou seja, d ≤ 1,
uma contradição.
Proposição 34 (Proposição 30, livro VII de Elementos de Euclides, 300 aC). Sejam a, b 6= 0 naturais. Se p é primo e p|ab então p|a ou p|b.
Demonstração. Sejam a, b, p naturais como enunciado. Se p 6 |a então mdc(p, a) =
1 e pelo exercício 31, item 3, p|b. Analogamente, p 6 |b ⇒ p|a.
Corolário Se p é primo e p|a 1 a 2 · · · a n , então p|a i para algum i .
Demonstração. Segue por indução (verifique).
43
Teorema 35 (Teorema Fundamental da Aritmética (TFA)). Todo natural maior
que 1 ou é primo ou pode ser escrito de maneira única, a menos da ordem dos
fatores, como um produto de primos.
Demonstração. Provemos usando indução em n que o predicado P (n) :=”n ou
é primo ou é produto de primos” é verdadeiro para todo n > 1.
P (2) é verdadeiro.
Suponha k > 1 é um natural e P (n) é verdadeiro para todo n ∈ {2, 3, 4, . . . , k}.
Provaremos que P (k + 1) é verdadeiro. Pelo exercício 33
m := min d (k + 1)
é primo. Se m = k + 1, então k + 1 é primo, senão 1 < m < k + 1 é um primo que
divide k + 1, i.e, tal que k + 1 = m · q. Como q < k + 1, P (q) é verdadeiro, ou seja,
q é primo ou um produto de primos, logo m · q é produto de primos.
Pela 2ª forma do PIF, P (n) é verdadeiro para todo n > 1.
Agora, provaremos que a escrita de n como produto de primos é única a
menos da ordem dos fatores. Se esse não é o caso, seja n o menor natural que
pode ser escrito como diferentes produtos de primos
n = p 1 p 2 · · · p a = q1 q2 · · · qb
com p 1 ≤ p 2 ≤ · · · ≤ p a e q 1 ≤ q 2 ≤ · · · ≤ q b primos. Então
p 1 |q 1 q 2 · · · q b
e pelo Corolário acima p 1 |q j para algum j , logo p 1 = q j ≥ q 1 . Analogamente,
q 1 |p 1 p 2 · · · p b
logo para algum i , q 1 = p i ≥ p 1 . Portanto, p 1 = q 1 . Pela minimalidade de n,
p 2 · · · p a = q2 · · · qb
é o mesmo produto de primos, uma contradição.
44
Assim, para todo n > 1 existem p 1 < p 2 < · · · < p k primos e α1 , α2 , . . . , αk ∈
N \ {0} tais que
α
α
α
n = p1 1 p2 2 · · · pk k
(28)
que chamamos de fatoração canônica de n em primos. Por exemplo
84 = 22 · 3 · 7 e 120 = 23 · 3 · 5 e 350 = 2 · 52 · 7
Exercício 36. Quantos divisores tem n, para qualquer n > 1?
Solução.
σ(n) := (α1 + 1)(α2 + 1) · · · (αk + 1)
(29)
Exercício 37. σ(n) é ímpar se, e só se, n é um quadrado perfeito.
α
α
Solução. n = p 1 1 · · · p r r
σ(n) ímpar ⇔ αi + 1 ímpar (∀i )
⇔ αi par (∀i )
¶
µ α1
αr 2
2
2
⇔ n = p1 · · · pr
3.1 Distribuição dos primos
Crivo de Eratóstenes
p
Notação b nc := max{x ∈ N : x 2 ≤ n}.
Os números primos até n podem ser obtidos por
1. Liste todos os números de 2 até n
p
2. Para cada i ∈ {2, 3, . . . , b nc}: se i está na lista então apague os múltiplos
de i maiores que i .
45
conhecido como Crivo de Eratóstenes. Por exemplo, para conhecer os primos
menores que 60 excluímos das lista 2, . . . , 60 os múltiplos de 2, 3, 5, 7.
Os naturais que sobram depois desse processo não são divisíveis pelos nap
p
turais x ∈ {2, 3, . . . , b nc} para os quais vale que x 2 ≤ n por definição de b nc.
Lema 38 (Eratóstenes, 230 ac). Se n > 1 não é divisível por nenhum dos primos
p tais que p 2 ≤ n então n é primo.
Demonstração. Se n é composto então tomamos q o menor primo que divide
n. Então n = qm com q ≤ m, logo q 2 ≤ mq = n e q|n, uma contradição.
Distribuição dos primos
A distribuição dos números primos dentro de N tem muitos problemas desafiadores, como a conjectura dos primos gêmeos, da infinitude de números de Fibonacci (respec., de Mersenne; respec., perfeitos) que são primos. Além desses,
existe um primo entre n 2 e (n+1)2 ? Existem infinitos primos da forma n 2 −n+41?
São perguntas difíceis de responder a respeito da distribuição dos primos. Um
resultado importante nesse contexto que não provaremos aqui é o Teorema dos
Números Primos: se π(x) é a quantidade de primos que são menores ou iguais a
x, então
lim
x→∞
π(x)
x
log(x)
=1
(30)
Denotamos por p n o n-ésimo número primo. A conjectura dos primos gê?
meos pergunta se |{n : p n+1 − p n = 2}| = |N|.
Sabemos que há primos consecutivos arbitrariamente distantes:
Exercício 39. Para todo n, existem n naturais consecutivos e compostos.
Solução: (n +1)!+2, (n +1)!+3, . . . , (n +1)!+n +1 é divisível, respectivamente, por
2, 3, . . . , n + 1
Em geral sabemos pouco sobre o comportamento de p n+1 − p n . Se verdadeira, a conjectura dos primos gêmeos implica em lim inf(p n+1 − p n ) = 2. Até
46
recentemente não se sabia se lim inf(p n+1 − p n ) é finito, quando em 2013 Zhang
mostrou que lim inf(p n+1 − p n ) < 70000000; o que tem sido melhorado e no momento vale lim inf(p n+1 − p n ) < 246.
Teorema 40 (Euclides). Há infinitos números primos.
Demonstração. Se p 1 , p 2 , . . . , p r são todos os números primos então
n = p1 p2 · · · pr + 1
pode ser escrito como o produtos desses primos, mas se p i |n então p i |1, um
absurdo.
Outra demonstração. Vamos mostrar que para todo natural n existe um primo
maior que n. Para tal, tome p um fator primo do número n! + 1. Se p ≤ n então
p|n! por definição de fatorial. Se p divide n! e n! + 1 então p divide a diferença
desses números, i.e., p|1, portanto p = 1, um absurdo que estabelece p > n.
Lema 41. Há infinitos primos da forma 4k + 3.
Demonstração. A prova é um exercício com o seguinte roteiro:
1. Todo primo ímpar é da forma 4k + 1 ou 4k + 3.
2. O produto de dois números da forma 4k + 1 também é dessa forma.
3. Para quaisquer p 1 , . . . , p r ∈ N \ {0}, N = 4(p 1 · · · p r ) − 1 é da forma 4k + 3 e
existe um primo p da forma 4k + 3 tal que p|N .
4. Suponha que na descrição de N os naturais p 1 , . . . , p r acima sejam todos
os primos da forma 4k + 3. Determine a existência de um primo da forma
4k + 3 que não seja nenhum dos listados acima.
O teorema 40 afirma que na sequência
1, 2, 3, 4, 5, 6, . . . , n, n + 1, . . .
47
há infinitas ocorrências de números primos. O execício 41 afirma que o mesmo
ocorre na sequência
3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47, . . . , 4n + 3, 4(n + 1) + 3, . . .
e um teorema famoso da Teoria Analítica dos Números, o Teorema de Dirichlet,
afirma que o mesmo ocorre com a sequência (ou melhor, na progressão aritmética que começa em a e tem razão d )
a, a + d , a + 2d , a + 3d , . . . , a + nd , a + (n + 1)d , . . .
para quaisquer a, d coprimos.
3.2 Pequeno Teorema de Fermat (PTF)
Para 0 ≤ b ≤ a, é possivel provar que (b!(a − b)!) | b! (exercício). Definimos
à !
a
a!
:=
b!(a − b)!
b
(31)
e vale para todo n (outro exercício)
à !
n n
X
(a + b) =
a i b n−i .
i
i =0
n
Exercício 42. Se p é primo então
¡p ¢
i
(32)
é divisível por p para todo 0 < i < p.
Teorema 43 (Pequeno Teorema de Fermat). Se p é primo então p|(a p − a) para
todo a ≥ 1.
Demonstração. Para a = 1 a afirmação certamente vale. Suponha que vale para
a e vamos provar que vale para a + 1.
à !
à !
p
p−1
X
X p i p−i
p i p−i
p
p
(a + 1) − (a + 1) =
a 1
− (a + 1) = (a − a) +
a 1
i =0 i
i =1 i
e como p|(a p − a) e p|
¡p ¢
i
(0 < i < p) temos p|[(a + 1)p − (a + 1)].
Notemos que p|(a p −a) ⇒ p|a(a p−1 −1), portanto, se p 6 |a então p|(a p−1 −1)
48
Corolário 44 (também chamado de Pequeno Teorema de Fermat). Se p é primo
e p 6 |a, então p|(a p−1 − 1).
Exemplo. Se p 6= 2, 5 é primo, p divide algum número dentre 1, 11, 111, 1111, 11111,
111111, 1111111, . . . . Se p = 3 então p divide todo número com quantidade divisível por 3 de algarismos 1. Se p > 5 então mdc(10, p) = 1 portanto p|10p−1 − 1 =
9 · 1111 · · · 11 e como p 6 |9 temos p|1111 · · · 11.
Exemplo. 10|(n 9 − n). Como n 9 e n têm a mesma paridade, 2|(n 9 − n). Vamos
verificar que 5|(n 9 − n) que, como mdc(2, 5) = 1, concluímos que 10|n 9 − n.
n 9 − n = n(n 4 − 1)(n 4 + 1) = (n 5 − n)(n 4 + 1)
O PTF garante que 5|(n 5 −n), portanto 10|(n 9 −n); em outras palavras n 9 e n têm
o mesmo algarismo da unidade em base 10.
De acordo com o teorema de Fermat, dados inteiros n e a, se n é primo e não
divide a então a n−1 mod n = 1, portanto, qualquer outro resultado indica que n
é composto. Entretanto, o teorema não garante que se a n−1 mod n = 1 então n é
primo.
Por exemplo 2340 mod 341 = 1 mas 341 = 11 · 31 não é primo. Em algumas
referências tais números são ditos pseudo-primos de Fermat. Um número inteiro ímpar e composto n é um pseudo-primo para a base a se a n−1 mod n = 1.
Assim, 341 é pseudo-primo para a base 2. De fato, é o menor pseudo-primo para
a base 2. Podemos descobrir que 341 é composto testando-o contra outras bases e nesse caso 3340 mod 341 = 54 o que atesta que 341 é composto. Entretanto,
estender essa estratégia não produz um algoritmo eficiente para decidir primalidade. Não há números que sejam pseudo-primos para toda base a ∈ {2, . . . , n −2}
pois se mdc(a, n) > 1 então a n−1 mod n 6= 1. Isso garante que se incrementamos
a base e fazemos o teste de Fermat então o mais longe que iremos é até o menor
divisor primo de n, mas isso pode não ser muito mais eficiente do que usar crivo
de Eratóstenes.
49
Exercícios
1. Para quais valores de m e n o número 9m 10n tem 27 divisores?
2. Qual é a forma geral de um número que tem só mais um divisor além do 1
e dele mesmo?
3. Prove que se mdc(n, m) = 1 então σ(n · m) = σ(n)σ(m).
4. Verifique as afirmações.
(a) 287 é primo.
(b) Todo primo da forma 3k + 1 é da forma 6q + 1.
(c) Entre n e n! existe um primo.(Dica: considere n! − 1)
(d) Todo primo maior que 6 é da forma 6k + 1 ou 6k + 5.
(e) O único primo da forma n 3 − 1 é 7.
5. Deduza da coprimalidade dos números de Fermat (exemplo 30) que há
infinitos números primos.
6. Mostre que há infinitos primos da forma 6k + 5.
7. Se a soma de dois naturais não-nulos é primo, esses números são coprimos?
8. Considere os inteiros positivos com as respectivas fatorações canônicas
α
α
α
β
β
β
a = p 1 1 p 2 2 · · · p k k e b = p 1 1 p 2 2 · · · p k k . Defina
γi := max{αi , βi }
δi := min{αi , βi }
e prove que
δ
δ
δ
γ
γ
γ
mdc(a, b) = p 1 1 p 2 2 · · · p k k
mmc(a, b) = p 1 1 p 2 2 · · · p k k
50
9. Vamos mostrar que há infinitos primos estabelecendo que π(n) ≥ 12 log2 (n).
(a) Dizemos que r é livre de quadrado se não tem um divisor diferente
α
α
α
do 1 que é um quadrado perfeito. Equivalentemente, r = p 1 1 p 2 2 · · · p k k
com αi = 0, 1 para cada i . Prove que a quantidade de naturais menores ou iguais a n livres de quadrado é no máximo 2π(n) .
(b) Prove que todo m ≤ n é da forma m = s 2 · r , com r livre de quadrado
e s 2 ≤ m.
p
(c) Use os itens anteriores para provar que n ≤ 2π(n) b nc.
(d) Prove que π(n) ≥ 12 log2 (n).
4 Construção dos Inteiros
Intuitivamente, digamos que queremos construir um conjunto de números onde
n − k faça sentido quaisquer que sejam os naturais n, k, por exemplo 4 − 11. Façamos −7 := 4 − 11. Mas então há várias representações −7 := 4 − 11 = 3 − 10 =
5−12 = · · · . Notemos que se a −b = n −m então a +m = b +n e s e fizermos todas
essas representações do −7 equivalentes temos um velho conhecido, a relação
de equivalência do exercício 4.
Formalmente, considere a relação Z ⊂ N × N definida por
(a, b)Z(n, m) se, e só se a + m = b + n
Z é uma relação de equivalência (exercício 4, página 4).
Para cada (a, b), a classe de equivalência de (a, b) é o conjunto
©
ª
[(a, b)] := (n, m) ∈ N × N : (a, b)Z(n, m) .
Por exemplo,
©
ª
[(1, 2)] = (0, 1), (1, 2), (2, 3), (3, 4), . . .
©
ª
[(5, 2)] = (3, 0), (4, 1), (5, 2), (6, 3), . . .
Notemos que [(1, 2)] = [(2, 3)] = [(0, 1)] 6= [(5, 2)] = [(4, 1)].
51
(33)
©
ª
Quando denotamos a classe de equivalência para (0, 1), (1, 2), (2, 3), (3, 4), . . .
por [(2, 3)] dizemos que o par (2, 3) é o representante da classe.
Z é o conjunto dessas classes de equivalência e seus elementos são chamados
números inteiros.
Denotamos
0 :=[(0, 0)] = {(n, n) : n ∈ N}
1 :=[(1, 0)] = {(n + 1, n) : n ∈ N}
−1 :=[(0, 1)] = {(n, n + 1) : n ∈ N}
−a :=[(0, a)] = {(n, n + a) : n ∈ N}
Denotamos por Z+ := {1, 2, 3, 4, . . . } o conjunto dos números inteiros positivos, i.e., inteiros maiores que 0. O conjunto Z \ Z+ , dos inteiros menores ou
iguais a 0 são ditos não-positivos. Analogamente, definimos os inteiros negativos Z− := {−1, −2, −3, −4, . . . } e os inteiros não-negativos. Assumimos a identificação
Z \ Z− = N
Denotemos por p a classe [(a, b)] e por q a classe [(n, m)]. Definimos p + q
como a classe de equivalência
p + q := [(a + n, b + m)]
(34)
Notemos que [(1, 2)] + [(5, 2)] = [(0, 1)] + [(3, 0)]. Definimos p · q como a classe de
equivalência
p · q := [(a · n + b · m, a · m + b · n)]
Definimos
p − q := p + (−q)
e definimos
p ≤ q ⇔ q −p ∈N
para quaisquer inteiros p e q.
52
(35)
Exercícios
1. Prove que a soma de conjuntos definida acima é compatível com a relação
de equivalência, isto é, a soma não depende dos representantes de cada
classe de equivalência envolvida.
2. Prove que a multiplicação de conjuntos definida acima é compatível com
a relação de equivalência, isto é, não depende dos representantes de cada
classe de equivalência envolvida.
3. Para classes de equivalência p, q, r e as operações definidas acima valem
(a) p + (q + r ) = (p + q) + r
(b) p + q = q + p
(c) p + 0 = p
(d) p + (−p) = 0
(e) p · (q · r ) = (p · q) · r
(f) p · q = q · p
(g) p · 1 = p
(h) p · (q + r ) = p · q + p · r
(i) p · q = 0 ⇒ p = 0 ou q = 0
4. A relação ≤ é reflexiva, antissimétrica e transitiva. Além, disso para quaisquer dois inteiros p e q vale: p ≤ q ou q ≤ p.
5. Prove que
(a) p ≤ 0 ⇒ −p ≥ 0
(b) (−p) · q = −(p · q)
5 Inteiros e suas propriedades aritméticas e de ordem
©
ª
Z = . . . , −2, −1, 0, 1, 2, . . . é o conjunto dos números inteiros, os quais satisfazem
as seguintes propriedades provadas a partir da construção dos inteiros.
53
— Com relação a soma —
Associativa ∀a, b, c ∈ Z
a + (b + c) = (a + b) + c
Comutativa ∀a, b ∈ Z
a +b = b +a
Elemento neutro ∀a ∈ Z,
a +0 = a
e 0 é o único inteiro que satisfaz essa sentença.
Elemento inverso ∀a ∈ Z, ∃!b ∈ Z
a +b = 0
b é denotado por −a.
Exercício 45 (Lei cancelativa). ∀a, b, c ∈ Z
a +b = a +c ⇒ b = c
Exercício 46. ∀a, b ∈ Z
−(a + b) = (−a) + (−b) = −a − b
— Com relação ao produto —
Associativa ∀a, b, c ∈ Z
a · (b · c) = (a · b) · c
Comutativa ∀a, b ∈ Z
a ·b = b ·a
Distributiva ∀a, b, c ∈ Z
a · (b + c) = a · b + a · c
54
Elemento neutro ∀a ∈ Z
a ·1 = a
e 1 é o único inteiro que satisfaz essa sentença.
Anulamento ∀a, b ∈ Z
a · b = 0 ⇒ a = 0 ou b = 0
Exercício 47 (Lei cancelativa). ∀a, b, c ∈ Z
a 6= 0 e a · b = a · c ⇒ b = c
Exercício 48. Prove que a lei cancelativa e a propriedade do anulamento são
equivalentes.
Exercício 49. Para a, b, c ∈ Z
1. a · 0 = 0.
2. (−a) · b = −(a · b) = a · (−b).
3. c(a − b) = ca − cb.
— Com relação a ≤ —
Comparabilidade ∀a, b ∈ Z; a ≤ b ou b ≤ a.
≤ é reflexiva ∀a ∈ Z; a ≤ a.
≤ é antissimétrica ∀a, b ∈ Z; a ≤ b e b ≤ a ⇒ a = b.
≤ é transitiva ∀a, b, c ∈ Z; a ≤ b e b ≤ c ⇒ a ≤ c.
Exercício 50. Para quaisquer a, b, c ∈ Z valem
1. Compatibilidade de ≤ com as operações aritméticas
a ≤ b ⇒ a +c ≤ b +c
a ≤ b e 0 ≤ c ⇒ a ·c ≤ b ·c
55
2. Tricotomia a < b ou a = b ou b < a.
Exercício 51. Para quaisquer inteiros a, b, c
1. a ≤ b ⇔ −a ≥ −b.
2. a < b ⇔ −a > −b.
3. Regras de sinal
(a) a > 0 e b > 0 ⇒ ab > 0
(b) a < 0 e b < 0 ⇒ ab > 0
(c) a < 0 e b > 0 ⇒ ab < 0
4. a ≤ b e c ≤ d ⇒ a + c ≤ b + d .
5. a ≤ b e c < d ⇒ a + c < b + d .
6. a 2 ≥ 0.
7. a < b e c > 0 ⇒ ac < bc
8. a < b e c < 0 ⇒ ac > bc
9. ac ≤ bc e c < 0 ⇒ a ≥ b
5.1 Valor absoluto
Definimos, para todo a ∈ Z, o valor absoluto de a


a
se a ≥ 0,
|a| :=

−a caso contrário.
Exercício 52. O valor absoluto satisfaz, para quaisquer inteiros a, b
1. |a| ≥ 0 e |a| = 0 se e só se a = 0.
2. −|a| ≤ a ≤ |a|.
56
(36)
3. | − a| = |a|.
4. |ab| = |a||b|.
5. |a| ≤ b ⇔ −b ≤ a ≤ b.
6. |a + b| ≤ |a| + |b|.
7. |a| − |b| ≤ |a − b| ≤ |a| + |b|
Exercícios
Prove a partir das propriedades acima que para a, b ∈ Z
1. −(−a) = a.
2. −(a − b) = b − a.
3. a − b = 0 ⇔ a = b.
4. (−a) · (−b) = a · b.
5. (−1) · a = −a
6. ab = 1 ⇒ a = b = 1 ou a = b = −1
Solução item 6.
ab = 1 ⇔ |ab| = |1| ⇔|ab| = 1
⇔|a||b| = 1 pelo item 4 do exercício 52
⇔|a| = |b| = 1 pelo teo. 9, item 12
Assim a = ±1 e b = ±1 pela definição de valor absoluto. Como 1 · (−1) = −1
(1 é neutro) a = b.
57
5.2 Indução
A ⊂ Z não-vazio é limitado inferiormente se existe m ∈ Z (chamado cota inferior) tal que
∀a ∈ A, m ≤ a
e m é menor elemento ou mínimo de A se m ∈ A. Denotamos o mínimo de A
por min(A).
Princípio do menor inteiro: A ⊂ Z não vazio e limitado inferiormente tem um
único mínimo.
Que o mínimo, caso exista, é único decorre da definição: se m e m 0 são mínios então m ≤ m 0 e m 0 ≤ m, portanto m = m 0 . Que o mínimo existe, segue do
PBO: se m é uma cota inferior então
B := {a − m : a ∈ A} ⊂ N
então, para algum b ∈ A temos b − m é o menor elemento de B . Mostremos que
b é uma cota inferior para A. Se a ∈ A então a − m ∈ B , logo b − m ≤ a − m,
portanto b ≤ a.
P (n) é um predicado sobre os inteiros n, n ≥ a para algum inteiro fixo a
Princípio da Indução Finita. Se, para um inteiro a,
1. P (a) é verdadeiro, e
2. para todo k ≥ a, se P (k) é verdadeiro então P (k + 1) é verdadeiro,
então P (n) é verdadeiro para todo inteiro n ≥ a.
58
Princípio da Indução Finita, segunda forma. Se, para um inteiro a,
1. P (a) é verdadeiro, e
2. para todo n > a, se P (k) verdadeiro para todo k ∈ {a, a+1, . . . , n} então P (n+
1) é verdadeiro,
então P (n) é verdadeiro para todo inteiro n ≥ a.
Demonstração. Se S é o conjunto dos inteiros m ≥ a tais que P (m) é falso e assumimos que S 6= ; então a é uma cota inferior e temos m 0 = min S.
m 0 > a por 1 e P (a), . . . , P (m 0 −1) é verdadeiro pela minimalidade de m 0 , logo
P (m 0 ) é verdadeiro, por 2, o que é uma contradição. Assim, S deve ser vazio.
Exercícios
1. Mostre que todo S ⊂ Z limitado superiormente possui (único) máximo.
Defina, nesse caso, os termos limitado superiormente, máximo e cota superior.
2. Prove usando indução
(a) Seja a ∈ Z e P (n) um predicado a respeito dos inteiros n ≤ a. Suponha que (i ) P (a) é verdadeiro; (i i ) para todo n ≤ a, se P (n) é verdadeiro então P (n − 1) é verdadeiro. Prove que P (n) é verdadeiro para
todo n ≤ a.
(b) Seja n ∈ Z, n > 0. n = 1 + 1 + 1 + · · · + 1 (n parcelas)
(c) Seja n ∈ Z, n < 0. n = (−1) + (−1) + (−1) + · · · + (−1) (−n parcelas)
(d) 2n+1 ≥ n + 2 para todo n ≥ −1.
(e) para a 6= 0, (−a)n = a n para todo n par.
(f) para a 6= 0, (−a)n = −a n para todo n ímpar.
3. Sejam a > 0 e b inteiros. Mostre que existe um inteiro k tal que b + ka > 0.
(dica: boa-ordem)
59
6 Divisibilidade em Z
Sejam a, b ∈ Z.
b divide a se existe c ∈ Z tal que bc = a. Dizemos que b é um divisor de
a, que c é o quociente. Se b|a também dizemos que b é múltiplo de a. Por
exemplo, o subconjunto dos inteiros múltiplos de 0 é {0} e dos múltiplos de 1 é
Z = {0, ±1, ±2, . . . }. Os múltiplos de 2 são os inteiros pares
{0, ±2, ±4, ±6 . . . }
e o complemento
{±1, ±3, ±5, . . . }
são os inteiros ímpares. De modo geral, o subconjunto dos múltiplos de a, que
é o mesmo dos múltiplos de −a é denotado por
a · Z := {a · n : n ∈ Z} = {0, ±a, ±2a, ±3a, . . . }
Exercício 53. Prove para inteiros a, b, c
1. 0|a se e somente se a = 0
2. Se b|a e a 6= 0 então |b| ≤ |a|.
3. (reflexiva) a|a.
4. (transitiva) Se a|b e b|c então a|c.
5. Se a|b e b|a então a = ±b.
6. Se a|b e c|d então ac|bd .
7. Se a|b e a|c então a|(mb + nc) ∀m, n ∈ Z .
¯
¯
8. a|b se e só se |a| ¯ |b|.
9. se a|(b + c) então a|b se e só se a|c.
60
(37)
Algumas soluções.
2. Se b|a, então bc = a para algum inteiro c. Usando o
exercício 52, item 4 |b||c| = |a|. Como c 6= 0, |b||c| = |b| + |b|(|c| − 1), portanto |b| ≤ |a|.
3. Se a = b = 0 então a afirmação vale. Se a, b 6= 0 então a|b ⇒ ac = b, para
algum c 6= 0 e b|a ⇒ bd = a, para algum d 6= 0. Assim, a(cd ) = a, logo
cd = 1 donde concluímos que c = d = 1 ou c = d = −1 (exercício 6, página
57).
8. a|b ⇒ ac = b para algum c; pelo exercício 52, item 4 |a||c| = |b|, portanto,
¯
¯
¯
¯
|a| ¯ |b|. Por outro lado, se |a| ¯ |b| então |a|c = |b| para algum c; notemos
que c = |c|, portanto |ac| = |b|. Mas |b| = ±b e |ac| = ±ac = a(±c), logo
b = a(±c).
6.1 Teorema da Divisão
Teorema 54 (Teorema da Divisão). Para todo inteiro a e todo inteiro b 6= 0 existe
um único inteiro q e existe um único inteiro r tal que
a = bq + r e 0 ≤ r < |b|
(38)
Demonstração. Provaremos em dois casos, de acordo com o sinal de b.
Para b > 0: se a ≥ 0 não há o que demonstrar pois a e b são naturais e já
provamos esse caso. Agora, se a < 0, tomamos q 0 e r 0 tais que |a| = bq 0 + r 0 . Se
r = 0 então q = −q 0 donde
a = −|a| = b(−q 0 ) + r = bq + r.
Senão,
q 0 b ≤ |a| < (q 0 + 1)b ⇒ −(q 0 + 1)b < −|a| ≤ −q 0 b
(eq. 16), tomamos q = −(q 0 + 1) e r = b − r 0 ,
61
−|a|
−(q 0 + 1)b
|a|
−q 0 b
−2−1 0 1 2
r0
b −r0
q 0b
Z
(q 0 + 1)b
r0
de modo que
a = −|a| = b(−q)0 − r 0 = b(q + 1) + r − b = bq + r.
Para b < 0: tomamos q 0 e r 0 tais que a = q 0 |b| + r 0 (como fizemos acima) e
tomamos q = −q 0 e r = r 0 , assim a = qb + r com 0 ≤ r < |b|.
Por exemplo
7 = 3·2+1
− 7 = 3 · (−3) + 2
7 = −3 · (−2) + 1
− 7 = −3 · 3 + 2
Outra demonstração. Para b > 0 definimos
R := {a − nb : n ∈ Z}
e R ∩ Z+ 6= ; pois para n = −|a|b temos a + |a|b 2 ≥ a + |a| ≥ 0. Seja r o menor
inteiro positivo de R ∩ Z+ , r = a − qb.
Se r ≥ b então r = b + s para algum s ≥ 0. De b + s = a − qb temos s = a − (q +
1)b ∈ R com s < r , uma contradição.
Para b < 0 tomamos q 0 e r 0 tais que a = q 0 |b| + r 0 e fazemos q = −q 0 e r = r 0 ,
assim a = qb + r com 0 ≤ r < |b|.
A prova de que r e q são únicos fica como exercício.
6.2 MDC
Para quaisquer a, b ∈ Z
mdc(a, b) := mdc(|a|, |b|)
Se d = mdc(a, b) então (verifique)
1. d ≥ 0
62
2. d |a e d |b
3. c|a e c|b ⇒ c|d
4. b|a ⇒ d = |b|
5. a = bq + r ⇒ mdc(a, b) = mdc(b, r )
Os inteiros a e b são coprimos, ou primos relativos, se mdc(a, b) = 1 o que
equivale a dizer que os únicos divisores comuns a eles são o 1 e o −1.
Exercícios
1. Prove que se a|1 então a = 1 ou a = −1.
2. Ache o quociente e o resto das divisões inteiras de
(a) 390 por 74
(b) -124 por 18
(c) 420 por -58
3. Na divisão de -345 por b > 0 o resto é 12. Quais são os possíveis divisores
e quocientes?
4. Mostre que um dos inteiros a, a + 2, a + 4 é divisível por 3.
5. Escreva o mdc(154, 15) como combinação linear de 154 e 15.
6. Seja a e b inteiros. Prove que se existem inteiros x e y tais ax + b y = 1,
então a e b são coprimos.
7. Prove que mdc(ca, cb) = |c|mdc(a, b).
63
6.3 Teorema de Bézout
Observemos o seguinte
mdc(42, 12) = 6:
42 = 12 · 3+6
12 = 6 · 2+0
42 · 1 + 12 · (−3) = 6
mdc(41, 12) = 1:
41 = 12 · 3+5
12 = 5 · 2+2
5 = 2 · 2+1
2 = 1 · 2+0
1 = 5−2·2
= 5 − (12 − 5 · 2)2 = 5 · 5 − 12 · 2
= (41 − 12 · 3) · 5 − 12 · 2 = 41 · 5 − 12 · 17
1 = 41 · 5 + 12 · (−17)
mdc(81, 57) = 3:
81 = 57 · 1 + 24 =⇒ 24 = 81 − 57 · 1
57 = 24 · 2 + 9 =⇒ 9 = 57 − 24 · 2
24 = 9 · 2 + 6 =⇒ 6 = 24 − 9 · 2
9 = 6 · 1 + 3 =⇒ 3 = 9 − 6
6 = 3 · 2 + 0.
3 = 9 − 6 = 9 − 24 + 9 · 2 = (9)3 − 24
= (57 − 24 · 2)3 − 24 = 57 · 3 − (24)7
= 57 · 3 − (81 − 57 · 1)7 = 81 · (−7) + 57 · 10
3 = 81 · (−7) + 57 · 10
64
Obs.: 1 = 41 · 17 + 12 · (−58) e 3 = 81 · (12) + 57 · (−17), i.e., o modo de escrever
não é único.
Definimos
a · Z + b · Z := {a · n + b · m : n, m ∈ Z}
(39)
o conjunto de todos os números que são combinações lineares inteiras de a e
b, ou seja, o conjunto dos inteiros da forma ax + b y para algum x e algum y
inteiros. Vamos provar que o menor elemento positivo desse conjunto é o mdc
de a e b.
Teorema 55 (Teorema de Bézout). Se a, b ∈ Z então existem inteiros x e y tais
que
ax + b y = mdc(a, b)
(40)
Demonstração. O caso a = b = 0 é trivial. Vamos supor que a 6= 0 ou b 6= 0,
portanto (a · Z + b · Z) ∩ Z+ 6= ; (justifique com detalhes) e podemos usar o PBO
e tomarmos
d := min[(a · Z + b · Z) ∩ Z+ ]
o menor elemento positivo de a·Z+b·Z. Existem x 0 , y 0 ∈ Z tais que d = ax 0 +b y 0 .
Mostraremos que d divide qualquer elemento de a · Z + b · Z.
Seja c ∈ a · Z + b · Z. Existem inteiros x 1 e y 1 tais que c = ax 1 + b y 1 . Pelo
Teorema da Divisão existem inteiros q e r tais que c = d q + r , onde 0 ≤ r < d , e
r = c − d q = ax 1 + b y 1 − (ax 0 + b y 0 )q = a(x 1 − x 0 q) + b(y 1 − y 0 q),
(41)
ou seja, r ∈ a · Z + b · Z. Como 0 ≤ r < d e d é mínimo deduzimos que r = 0,
portando d |c.
Em particular, d |a e d |b, isto é, d ∈ D(a) ∩ D(b) por definição de mdc temos
d ≤ mdc(a, b). Por outro lado, d = ax 0 + b y 0 e como mdc(a, b)|ax 0 + b y 0 segue
que mdc(a, b)|d (veja exerc. 53, item 7). Do exercício 53 (item 2) mdc(a, b) ≤ d ,
logo, mdc(a, b) = d .
Corolário 56. Prove que se a e b são inteiros não ambos nulos, então d = mdc(a, b)
se, e somente se,
65
1. d ≥ 0;
2. d |a e d |b;
3. para todo inteiro c, c|a e c|b ⇒ c|d .
Demonstração. Exercício.
Corolário 57. Se a, b, c são inteiros tais que a|bc e mdc(a, b) = 1, então a|c.
Demonstração. Exercício.
Exercício 58. Se a|c e b|c, c 6= 0, e mdc(a, b) = 1 então ab|c.
Exercício 59. Se a e b são inteiros, pelo menos um não-nulo, e d = mdc(a, b),
então mdc( da , db ) = 1.
Solução. Existem n, m tais que an + bm = d , portanto
a
dn
+ db m = 1, que é o
menor positivo de da Z + db Z = 1, portanto mdc( da , db ) = 1.
6.4 Equações diofantinas lineares
Estudaremos as equações da forma
a X + bY = c
(42)
em que a, b, c ∈ Z, a e b não ambos nulos; uma solução para tal equação é um par
de inteiros (x 0 , y 0 ) para o qual a igualdade acima vale quando X = x 0 e Y = y 0 .
Proposição 60. Dados inteiros a, b e c a equação (42) admite solução inteira se e
somente se mdc(a, b)|c.
Demonstração. Denotemos por d := mdc(a, b) e por (n, m) uma solução de a X +
bY = d caso exista.
De d |(ax + b y) para quaisquer x, y ∈ Z, em particular, caso (42) tenha solução, d |an + bm e portanto d |c.
Por outro lado, se d |c então existe q tal que d q = c. Pelo Teorema de Bézout
existem x, y ∈ Z tais que ax + b y = d , portanto (q x, q y) é solução de a X + bY =
c.
66
O resultado acima estabelece a seguinte iguldade de conjuntos
a · Z + b · Z = mdc(a, b) · Z
Notemos que se a e b são coprimos então (42) tem solução qualquer que
seja o inteiro c. Também vale a recíproca.
Corolário 61. Dois inteiros a, b são coprimos se, e só se, a equação (42) admite
solução inteira, qualquer que seja c ∈ Z.
Demonstração. Se a e b são coprimos então, pela proposição 60 a equação (42)
tem solução qualquer que seja o inteiro c.
Agora, se existem x, y ∈ Z que satisfazem a equação para c = 1, então todo
divisor d de a e b divide ax + a y = 1, portanto, d = ±1, logo mdc(a, b) = 1.
Notemos que para a ou b não-nulo e d = mdc(a, b) 6= 0
ax + b y = c ⇐⇒
a
b
c
x+ y =
d
d
d
para quaiquer x, y ∈ Z (d |c como provamos acima, logo dc tem sentido). Ademais
mdc( da , db ) = 1, portanto toda equação diofantina linear
a X + bY = c
é equivalente — tem as mesmas soluções — de uma equação reduzida
a
b
c
X+ Y =
d
d
d
na qual os coeficientes são coprimos.
Ainda, se (x 0 , y 0 ) é uma solução de
solução de
a
dX
a
dX
+ db Y = 1 então (x 0 dc , y 0 dc ) é uma
+ db Y = dc .
Por exemplo, para achar uma solução de 81X + 57Y = 27 basta achar uma
solução de 27X + 19Y = 9 e para achar uma solução dessa equação, primeiro
procuramos por uma solução de 27X + 19Y = 1.
67
Usando o algoritmo de Euclides para calcular o mdc e substituindo-se os
restos, como fizemos anteriormente mdc(27, 19) = 1:
27 = 19 · 1 + 8
19 = 8 · 2 + 3
8 = 3·2+2
3 = 2·1+1 ⇔ 1 = 3−2·1
⇔ 1 = 3 − (8 − 3 · 2) · 1
⇔ 1 = −8 + 3 · 3 = −8 + (19 − 8 · 2) · 3
⇔ 1 = 8 · (−7) + 19 · 3
⇔ 1 = (27 − 19 · 1) · (−7) + 19 · 3
⇔ 1 = 27 · (−7) + 19 · 10
logo (−7, 10) é solução de 27X + 19Y = 1, portanto (−7 · 9, 10 · 9) é solução de
27X + 19Y = 9 e, consequentemente, de 81X + 57Y = 27.
Teorema 62. Se (x 0 , y 0 ) é uma solução particular de (42) com a 6= 0 e b 6= 0, então
o conjunto de todas as soluções de (42) é
½µ
¶
¾
b
a
x0 + t , y o − t : t ∈ Z
d
d
(43)
em que d = mdc(a, b).
³
´
Demonstração. É um exercício verificar que x 0 + db t , y o − da t é solução de (42).
Agora, suponha que (x, y) seja uma solução de (42), então
ax + b y = c = ax 0 + b y 0
portanto
a(x − x 0 ) = b(y 0 − y).
Se a = d r e b = sd ,
r (x − x 0 ) = s(y 0 − y)
68
(44)
com mdc(r, s) = 1. Ainda, s|r (x − x 0 ), portanto, s|(x − x 0 ), ou seja, existe t ∈ Z tal
que x − x 0 = st , portanto
x = x0 +
b
t.
d
(45)
Substituindo x − x 0 = st em (44) s(y 0 − y) = r (x − x 0 ) = r st , logo
y = y0 −
a
t
d
(46)
como queríamos.
Exercício 63. De quantas maneiras podemos comprar selos de 3 e 5 reais de modo
a gastar 50 reais?
Exercício 64. Mostre que se (x 0 , y 0 ) é solução de a X + bY = c, então
1. (−x 0 , y 0 ) é solução de −a X + bY = c;
2. (x 0 , −y 0 ) é solução de aX − bY = c;
3. (−x 0 , −y 0 ) é solução de −a X − bY = c.
Exercício 65. Sejam a, b, c, d inteiros. Defina mdc(a, b, c) := mdc(mdc(a, b), c).
Estabeleça e prove um critério para existência de solução de
a X + bY + c Z = d .
Exercícios
1. Deduza do Teorema de Bézout:
(a) se a|c então mdc(a, b)|mdc(c, b).
(b) se a e b são coprimos então mcd(ac, b) = mdc(c, b).
2. Sejam a e b inteiros positivos e coprimos. Mostre que para todo inteiros c > ab − a − b, a equação a X + bY = c admite soluções inteiras nãonegativas.
69
3. Sejam a e b inteiros positivos e coprimos. Mostre que equação a X −bY = c
admite infinitas soluções nos naturais.
4. Determine as soluções inteiras de
(a) 3x + 4y = 20
(b) 5x − 2y = 2
(c) 18x − 20y = −8
5. Ache todos inteiros positivos que deixam resto 6 quando divididos por 11
e resto 3 quando divididos por 7.
6. Ache todos os naturais que quando divididos por 18 deixam resto 4 e que
quando divididos por 14 deixam resto 6.
7. Um parque cobra ingresso de 1 real de crianças e 3 de adultos. Para que
a arrecadação de um dia seja 200 reais qual o menor numero de pessoas,
adultos e crianças, que frequentam o parque?
8. Um fazendeiro dispõe de 1.770 reais pra gastar em boi e cavalo. Um cavalo
custa 31 reais e boi 21 reais. Qual o maior número de animais que pode
comprar?
7 Congruências
Para inteiros a, b, n, com n 6= 0, dizemos que a é congruente a b módulo n, e
escrevemos
a ≡b
(mod n)
(47)
se n|(a − b). Como n|(a − b) ⇔ −n|(a − b) nos restringiremos ao caso n > 0. O
caso n = 1 é trivial pois quaisquer dois inteiros são congruentes. Geralmente,
os casos interessantes são para n > 1. Para n = 2, por exemplo, dois inteiros são
congruentes se, e só se, eles diferem por um inteiro par, ou seja, têm mesma
paridade.
70
Por exemplo, 152 ≡ 5 (mod 7) (152 = 21 · 7 + 5) e −152 ≡ 2 (mod 7) (152 =
(−22) · 7 + 2). Também, 7 ≡ 15 (mod 8), 3 ≡ 21 (mod 6).
Dados a e b congruentes, usando o Teorema da Divisão, dividimos ambos
por n e temos únicos q a , r a , q b , r b tais que a = nq a + r a e b = nq b + r b de modo
que 0 ≤ r a , r b < n, portanto, −n < r a − r b < n e temos
a − b = n(q a − q b ) + (r a − r b )
(48)
com n|(a − b) e n|n(q q − q b ) logo n|(r a − r b ) e como o único múltiplo de n que
satisfaz −n < r a − r b < n é o 0 temos
r a = rb .
Concluindo, se a é congruente a b módulo n então a e b deixam o mesmo
resto quando divididos por n. Por outro lado, se a e b deixam o mesmo resto
quando divididos por n então n|(a −b) pois a −b = n(q a −q b ). Usando a notação
introduzida na página 31, o que estabelecemos foi
Proposição 66. a ≡ b (mod n) ⇐⇒ a mod n = b mod n.
Observação 67. Segue da equivalência dada na proposição acima e do Teorema
da Divisão que todo inteiro é congruente a um, e somente um, dentre os números
{0, 1, 2, . . . , n − 1}
Claramente, ≡ (mod n) é uma relação de equivalência; é reflexiva (a ≡ a
(mod n)), é simétrica (a ≡ b (mod n) ⇔ b ≡ a (mod n)), e é transitiva (a mod
n = b mod n e b mod n = c mod n ⇔ a mod n = c mod n).
Proposição 68. ≡ é uma relação de equivalência sobre Z.
Além de ser relação de equivalência, congruência é compatível com as operações aritméticas dos inteiros.
Proposição 69. Para quaisquer inteiros a, b, c, d , n, se a ≡ b (mod n) e c ≡ d
(mod n) então valem
71
1. a + c ≡ b + d (mod n)
2. a − c ≡ b − d (mod n)
3. a · c ≡ b · d (mod n)
Note que, em particular, vale quando c = d .
Demonstração. Da hipótese temos que n|(a − b) e n|(c − d ) e do exercício 53,
item 7 temos que n|x(a − b) + y(c − d ) para quaisquer x, y ∈ Z, daí
1. o item 1 segue de (a − b) + (c − d ) = (a + c) − (b + d );
2. o item 2 segue de (a − b) − (c − d ) = (a − c) − (b − d );
3. o item 3 segue de c(a − b) + b(c − d ) = ac − bd .
Corolário 70. Para quaisquer inteiros a, b, c e n > 0
a +c ≡ b +c
(mod n) ⇒ a ≡ b
(mod n).
Demonstração. Segue do item 2.
Corolário 71. Se a ≡ b (mod n), então a k ≡ b k (mod n), para todo k ∈ N.
Demonstração. Segue do item 3.
Exercício 72. Mostre, usando indução, que para n pares de inteiros a i e b i , tais
que a i ≡ b i (mod n) (i ∈ {1, 2, . . . , n}) valem
n
X
i =1
n
Y
i =1
ai ≡
ai ≡
n
X
i =1
n
Y
bi
(mod n)
(49)
bi
(mod n)
(50)
i =1
Lema 73. Se c a ≡ cb (mod n) e mdc(c, n) = d > 0 então
a ≡b
(mod
72
n
).
d
Demonstração. Se ca ≡ cb (mod n) então existe q tal que nq = c a − cb = c(a −
b). Como d > 0 divide n e divide c temos
n
dq
=
c
d (a
− b), portanto
n c
d | d (a
−
b)mmas mdc( dn , dc ) = 1, portanto dn |(a − b).
Corolário 74. Se mdc(c, n) = 1 então
ac ≡ bc
(mod n) ⇒ a ≡ b
(mod n).
Corolário 75. Se c a ≡ cb (mod p) e p primo que não divide c então
a ≡b
(mod p).
Por exemplo, 10 ≡ −1 (mod 11), portanto 10200 ≡ −1200 (mod 11), e como
1 ≡ −1200 (mod 11) temos 1 ≡ 10200 (mod 11), portanto, 11|10200 − 1.
Exemplo 76 (critério de divisibilidade por 9). Seja a r . . . a 0 a representação decimal de n. De 10 ≡ 1 (mod 9) temos, pela proposição 69 que 10s ≡ 1 (mod 9),
a · 10s ≡ a (mod 9) (∀a), portanto, pelo exercício 72
a 0 + a 1 10 + a 2 102 − · · · + a r 10r ≡ a 0 + a 1 + a 2 + · · · + a r
(mod 9).
Exemplo 77 (critério de divisibilidade por 11). Seja a r . . . a 0 a representação decimal de n. De 10 ≡ −1 (mod 11) temos que a · 10s ≡ a · (−1)s (mod 11) portanto
a 0 + a 1 10 + a 2 102 − · · · + a r 10r ≡ a 0 − a 1 + a 2 − · · · + (−1)r a r
(mod 11).
Exemplo (ISBN – International Standard Book Number). Um dos livros texto tem
ISBN 8-585-81825-5.
O ISBN tem dez dígitos. O último é um dígito de controle. Os primeiros nove
dígitos codificam informações como a língua e a editora do livro. Um código ISBN
válido d 0 − d 1 d 2 d 3 − d 4 d 5 d 6 d 7 d 8 − d 9 satisfaz
10d 0 + 9d 1 + 8d 2 + 7d 3 + 6d 4 + 5d 5 + 4d 6 + 3d 7 + 2d 8 + 1d 9 ≡ 0 (mod 11)
quando d 9 vale 10 é usado a letra X .
Exercício 78. Mostre que 31|2015 − 1. (dica: 20 ≡ −11 (mod 31))
73
Esboço da solução. 20 ≡ −11 (mod 31) portanto 202 ≡ 121 ≡ −3 (mod 31). Multiplicando as congruências 203 ≡ 33 ≡ 2 (mod 31) logo 2015 ≡ 25 ≡ 1 (mod 31).
Exercício 79. Qual o resto da divisão de 53
20
por 13?
Solução. Nas potências de 5
50 ≡ 1 (mod 13)
54 ≡ 1 (mod 13)
51 ≡ 5 (mod 13)
55 ≡ 5 (mod 13)
52 ≡ −1 (mod 13) 56 ≡ −1 (mod 13)
53 ≡ −5 (mod 13) 57 ≡ −5 (mod 13) · · ·
os restos se repetem com período 4. Portanto precisamos conhecer 320 mod 4:
3 ≡ −1 (mod 4) logo 320 ≡ 1 (mod 4), portanto 53
20
≡ 5 (mod 13).
Exercício 80. Qual os dois últimos algarismos de 3200 .
Solução. 3200 = 9100 = (10 − 1)100 =
¡ ¢
¡100¢
P100 ¡100¢
100100−k (−1)k ≡ − 100
99 10 + 100
k=0 k
(mod 100) ≡ 1 (mod 100). Portanto, 01.
7.1 Sistema completo de restos
S ⊂ Z é um sistema completo de restos módulo n se para todo a ∈ Z existe um,
e só um, b ∈ S tal que a ≡ b (mod n). Por exemplo, alguns sistemas completos
de resíduos módulo 5 são os conjuntos:
{−2, −1, 0, 1, 2},
{0, 1, 2, 3, 4},
{1, 2, 3, 4, 5},
{12, 24, 35, −4, 18}.
Conforme vimos, observação 67, {0, 1, . . . , n −1} é um sistema completo de restos
módulo n.
74
Para qualquer sistema completo de restos módulo n deve haver uma bijeção
com {0, 1, . . . , n − 1} (por quê?) logo todo sistema completo de restos módulo n
tem que ter cardinalidade n.
Observação 81. ≡ é uma relação de equivalência; uma classe de equivalência é
dada por todos os inteiros que deixam o mesmo resto quando divididos por n. Um
sistema completo de restos é um conjunto formado por um representante de cada
classe de equivalência.
Por exemplo, definimos para r ∈ Z
[r ]n := {a ∈ Z : a ≡ r
(mod n)}
e temos as classes que equivalência módulo 5 dadas por [0]5 , [1]5 , [2]5 , [3]5 , [4]5 .
Ademais, no exemplo acima identificamos que [0]5 = [5]5 = [35]5 , e [−2]5 = [3]5 =
[18]5 , e [−1]5 = [4]5 = [24]5 , e [2]5 = [12]5 e [−4]5 = [1]5 .
Exemplo 82. A equação X 3 − 117Y 3 + 1 = 5 não tem solução inteira3 . Se (x, y) é
uma solução de inteiros então x 3 − 117y 3 + 1 ≡ 5 (mod 9) que, como 117 é múltiplo de 9, equivale a x 3 + 1 ≡ 5 (mod 9) a qual não tem solução.
Considerando o sistema completo de restos S = {0, 1, 2, 3, 4, 5, 6, 7, 8}, x ∈ Z é
congruente a um (e só um) elemento r ∈ S, portanto, x 3 ≡ r 3 (mod 9) (r ∈ S) e os
cubos módulo 9 são {0, 1, 8}
0 1 2 3 4
r
r 3 mod 9
0
1
8
0
1
5
6
7
8
8
0
1
8
porém nenhum inteiro dentre 0, 1, 8 satisfaz X 3 + 1 ≡ 5 (mod 9).
Exercício 83. A congruência X 2 + 1 ≡ 0 (mod 8) não tem solução.
Solução. Consideremos o seguinte sistema completo de restos módulo 8 (verifique): {0, ±1, ±2, ±3, 4}. Se x ∈ Z então existe um único r ∈ {0, ±1, ±2, ±3, 4} tal que
x ≡ r (mod 8), assim x 2 ≡ r 2 (mod 8) e
3 uma história curiosa a respeito dessa equação pode ser lida na página 81 de COUTINHO, C.;
Números inteiros e criptografia RSA. IMPA-SBM, 2009.[512.7 COUn Estante:4H]
75
r
4
±3
±2
±1
0
r 2 mod 8
0
1
4
1
0
portanto x 2 + 1 é congruente a um dentre 1, 2, 5.
Exercício 84. Sejam m 1 , m 2 , . . . , m k inteiros positivos e defina para todo k > 2,
mmc(m 1 , m 2 , . . . , m k ) := mmc(mmc(m 1 , m 2 , . . . , m k−1 ), m k )
(51)
Prove que se a ≡ b (mod m i ) para todo i , então
a ≡b
(mod mmc(m 1 , m 2 , . . . , m k )).
(52)
Prove a recíproca.
Exercícios
1. Sejam a, b, r, s inteiros, s 6= 0. Prove que a ≡ b (mod r ) se, e somente
se,as ≡ bs (mod r s).
2. Prove que se a é um cubo então a 2 é congruente a 0, ou 1, ou 9, ou 28
módulo 36.
3. Determinar todos os inteiros positivos m tais que as soluções de X 2 ≡ 0
(mod m) também sejam soluções de X ≡ 0 (mod m).
4. Determinar os restos das divisões
(a) 250 por 7;
(b) 4165 por 7.
5. Verifique
(a) 89|(244 − 1);
(b) 97|(211 − 1).
100
6. Qual os dois últimos algarismos de 77 . (dica: 7k mod 100 é periódico)
76
8 Congruências lineares e sistemas de congruências
Dados inteiros a, b e n > 0 vamos estudar as soluções da congruência linear em
uma variável com incógnita X
aX ≡ b
(mod n).
(53)
Uma solução dessa congruência linear é um inteiro x tal que ax ≡ b (mod n)
e uma solução módulo n é um inteiro x tal que x ∈ {0, 1, . . . , n − 1} (ou qualquer
outro s.c.r. previamente escolhido) e ax ≡ b (mod n).
Por definição, existe um inteiro x tal que ax ≡ b (mod n) se, e somente se,
ax − b é um múltiplo de n, ou seja, existe y ∈ Z tal que ax − b = n y que reescrevemos como
ax + n y = b
(54)
Pelo Teorema de Bézout a existência de inteiros x e y que satisfazem a equação
acima é equivalente a mdc(a, n)|b, além disso, se x 0 é uma solução particular
então todas as soluções da congruência linear são
x t := x 0 +
n
t
mdc(a, n)
(55)
para todo t ∈ Z, portanto a congruência linear que tem solução tem infinitas
soluções.
Vejamos quando duas dessas infinitas soluções são congruentes módulo n,
façamos d := mdc(a, n) (d > 0)
xt ≡ xs
e como mdc( dn , n) =
n
d
n
n
t ≡ x 0 + s (mod n)
d
d
n
n
⇔ t ≡ s (mod n)
d
d
(mod n) ⇔ x 0 +
temos, pelo lema 73 que
xt ≡ xs
(mod n) ⇔ t ≡ s
(mod d )
portanto, quando há solução, há exatamente d = mdc(a, n) soluções incongruentes x t com t ∈ S, para algum S sistema completo de restos mod d .
77
Teorema 85. Uma congruência linear em uma variável a X ≡ b (mod n) admite
solução inteira se e somente se mdc(a, n)|b. No caso de haver solução, se x 0 ∈
{0, 1, . . . , n − 1} é solução então
½
x0 +
são todas as soluções e
½
x0 +
¾
n
t: t ∈Z
mdc(a, n)
n
t : t ∈ {0, 1, . . . , mdc(a, n) − 1}
mdc(a, n)
¾
são todas as soluções módulo n da congruência.
Por exemplo, 3X ≡ 6 (mod 15) é satisfeita por todo inteiro x da forma 2 + 5t
(t ∈ Z) e 2, 7, 12 são três soluções incongruentes módulo 15.
Corolário 86. Se mdc(a, n) = 1 então a X ≡ b (mod n) tem única solução módulo
n.
Corolário 87 (Inverso multiplicativo). a X ≡ 1 (mod n) tem (única) solução se e
somente se mdc(a, n) = 1.
A única solução módulo n garantida no último resultado é chamado de inverso multiplicativo de a módulo n.
Por exemplo, 3X ≡ 1 (mod 5) tem solução e como 3 e 5 são coprimos a solução módulo 5 é única. Uma solução para a equação é 2, portanto, toda solução
inteira x é da forma x = 2 + 5t , portanto se x é solução então
x ≡ 2 (mod 5).
Notemos que toda solução de 3X ≡ 1 (mod 5) também é solução de X ≡ 2 (mod 5),
ademais 2 é o inverso multiplicativo de 3 módulo 5.
A equação 2X ≡ 3 (mod 9) também tem única solução módulo 9, que é 6,
donde temos que 6+9t são todas as soluções, ou seja, se x é solução então x ≡ 6
(mod 9); de novo, notemos que toda solução de 2X ≡ 3 (mod 5) também é solução de X ≡ 6 (mod 9). Esse fato não é um particularidade desses exemplos.
78
Sejam a, n ∈ Z inteiros quaisquer, não nulos e d := mdc(a, n); b ∈ d · Z. As equações
aX ≡ b
(mod n)
a
b
X≡
d
d
e
(mod
n
)
d
(56)
têm as mesmas soluções, pois para quaisquer x, y ∈ Z
ax + n y = b ⇔
a
n
b
x+ y = .
d
d
d
Como mdc( da , dn ) = 1, usamos o corolário 87 para termos o inverso a 0 de
dulo
n
d
a
d
mó-
logo
b
a
X≡
d
d
n
b
) ⇔ X ≡ a0
d
d
(mod
(mod
n
)
d
portanto
aX ≡ b
(mod n)
e
X ≡ a0
b
d
(mod
n
)
d
(57)
têm as mesmas soluções. Ademais, todas as soluções inteiras de X ≡ a 0 db (mod
n
d)
são dadas por
a0
b n
+ t,
d d
∀t ∈ Z
e todo inteiro dessa forma é congruente a algum de
a0
b n
+ t,
d d
∀t ∈ {0, 1, 2, . . . , d − 1}.
8.1 Teorema chinês do resto
Consideremos o seguinte sistema de congruências lineares



X ≡ 2 (mod 5)



X ≡ 6 (mod 9)




 X ≡ 5 (mod 11)
se a primeira congruência é satisfeita por x ∈ Z então x = 2 + 5t , para algum t ,
que para satisfazer a segunda congruência deve valer 2 + 5t ≡ 6 (mod 9), que
equivale a 5t ≡ 4 (mod 9) que, como 5 tem inverso 2 módulo 9, equivale a t ≡ 8
(mod 9) donde t = 8 + 9s, logo
x = 2 + 5t = 2 + 5(8 + 9s) = 42 + 45s.
79
Observemos que para cada s ∈ Z o valor de x associado satisfaz as duas primeiras congruências lineares do sistema. Agora, para x satisfazer a última congruência linear 42 + 45s ≡ 5 (mod 11) que equivale a 45s ≡ −37 (mod 11) ou
ainda 45s ≡ 7 (mod 11). Como 45 é invertível módulo 11, e seu inverso é 1, a
última congruência equivale a s ≡ 7 (mod 11), ou seja, s = 7 + 11u, portanto
x = 42 + 45r = 42 + 45(7 + 11u) = 357 + 495u
ou seja, para cada u ∈ Z o inteiro x associado satisfaz o sistema de congruências
lineares acima. De fato, essas são todas as soluções inteiras, e a única solução
módulo 495 = 5 · 9 · 11 é 357
x ≡ 357 (mod 5 · 9 · 11).
No caso geral, consideremos o sistema de congruências lineares


 X ≡ a (mod n)

X ≡ b
(58)
(mod m)
a primeira congruência linear tem soluções inteiras a + nt , para t ∈ Z. Dos inteiros que satisfazem a primeira congruência, substituindo em X na segunda
congruência linear, temos os inteiros que satisfazem as duas congruências concomitantemente, que são dados pelos inteiros t tais que a +nt ≡ b (mod m), ou
seja, as soluções de
nX ≡ b − a
(mod m)
(59)
caso existam. Portanto,
(58) tem solução se e só se mdc(m, n)|b − a.
(60)
Garantimos essa condição exigindo que mdc(m, n) = 1
Observação 88. A hipótese mdc(m, n) = 1 é suficiente mas não é necessária para
que mdc(m, n)|b − a.
80
Ademais, se mdc(m, n) = 1 então n tem inverso n 0 módulo m, portanto, t é
solução de (59) se, e só se,
t ≡ n 0 (b − a) (mod m)
ou seja t = n 0 (b − a) + ms, para todo s ∈ Z, portanto, se x é uma solução inteira
do sistema de congruências então, para algum s,
x s = a + nt = a + n(n 0 (b − a) + ms) = (1 − nn 0 )a + nn 0 b + nms
e, ainda, 1 − nn 0 = mm 0 para algum m 0 ∈ Z (segue do teorema de Bézout, m 0 é o
inverso de m módulo n), o que resulta em
x s = mm 0 a + nn 0 b + nms,
(61)
e o valor de x s é uma solução inteira para ambas congruências para cada s ∈ Z.
De fato, todas as soluções são da forma (61). Se x, y ∈ Z satisfazem ambas
as equações acima, então por transitividade vale que x ≡ y (mod n) e x ≡ y
(mod m), donde n|(x − y) e m|(x − y) e como mdc(m, n) = 1 temos (exercício
58) mn|(x − y), isto é, x ≡ y (mod mn).
Portanto, a única solução módulo mn é
x ≡ mm 0 a + nn 0 b
(mod mn).
(62)
Observamos que esse caso é suficiente para resolver um sistema com qualquer número de congruências lineares, como os módulos coprimos dois-a-dois,
resolvendo-as duas-a-duas. No entanto, podemos generalizar a demonstração
acima, o que fazemos abaixo.
O seguinte resultado é o famoso Toerema Chinês do Resto. A forma original
do teorema apareceu no livro Sun Tzu Suan Ching (manual de aritmética de Sun
Tzu) do terceiro-século e generalizado e republicado em 1247 por Qin Jiushao.
Teorema 89 (Teorema Chinês do Resto). Sejam n 1 , n 2 , . . . , n k inteiros maiores
que 1 e tais que mdc(n i , n j ) = 1 para todos i 6= j , e sejam a 1 , . . . , a k inteiros arbitrários. Então o sistema de congruências lineares
X ≡ ai
(mod n i ),
81
∀i ∈ {1, 2, . . . , k}.
(63)
tem uma única solução módulo n = n 1 n 2 · · · n k dada por
m 10 m 1 a 1 + m 20 m 2 a 2 + · · · + m k0 m k a k
em que m i =
n 1 n 2 ···n k
ni
(64)
e m i0 é o inverso multiplicativo de m i módulo n i , para todo
i ∈ {1, 2, . . . , k}. A solução é única módulo n 1 · n 2 · · · n k .
Demonstração. Notemos que mdc(m i , n i ) = 1, logo m i0 existe para todo i . ToP
mamos x 0 := ki=1 m i0 m i a i e vamos mostrar que é solução.
Para cada i temos
m j ≡ 0 (mod n i ) (∀ j 6= i )
logo
x 0 ≡ m i0 m i a i
(mod n i ) (∀i ∈ {1, . . . , k}).
e m i m i0 ≡ 1 (mod n i ) logo m i0 m i a i ≡ a i (mod n i ), portanto
x0 ≡ ai
(mod n i )
para todo i , ou seja, x 0 é solução de cada congruência linear.
Agora vamos mostrar que a solução é única módulo n. Assuma que para
x ∈ Z vale x ≡ a i (mod n i ) para todo i . Por transitividade x ≡ x 0 (mod n i ) para
todo i , portanto para todo i , n i |(x − x 0 ) e pela coprimalidade dos n i ’s temos
Qk
i =1 n i |(x − x 0 ).
Exemplo 90. Considere o sistema


 X ≡ 2 (mod 2)



X ≡ −1 (mod 3)




 X ≡ 4 (mod 7).
Seguindo a notação da demonstração, n = 42, m 1 = 21, m 2 = 15 e m 3 = 6.
i
m i0
mi
1
1
21
2
−1
14
3
−1
6
82
e x 0 = 2 · 1 · 21 + (−1)(−1)14 + 4(−1)6 = 32. Ainda, toda solução inteira é da forma
32 + 42t , para todo t ∈ Z.
Exercício 91. Mostre que as soluções do exemplo 90 são soluções do sistema


6X ≡ 4 (mod 4)



2X ≡ 1 (mod 3)




4X ≡ 2 (mod 7).
Variantes do TCR
Exercício 92. Mostre que


X ≡ a
(mod n)

X ≡ b
(mod m)
tem solução apenas quando a ≡ b (mod mdc(n, m)). Nesse caso a solução é unica
módulo mmc(n, m) (veja a observação 88 e a discussão anterior, que garante que
há solução).
Exercício 93. Verifique a seguinte versão do Teorema Chinês do Resto: Sejam
n 1 , n 2 , . . . , n k inteiros maiores que 1 e sejam a 1 , . . . , a k inteiros arbitrários. Então
o sistema
X ≡ ai
(mod n i ),
∀i ∈ {1, 2, . . . , k}.
(65)
tem solução se e somente se mdc(n i , n j )|a i − a j para todo i 6= j . Caso exista, a
solução é única módulo mmc(n 1 , n 2 , . . . , n k ). (Dica: indução e o exercício 84.)
Exercício 94. Sejam n 1 , n 2 , . . . , n k inteiros maiores que 1, e sejam a 1 , . . . , a k e b 1 , . . . , b k
inteiros arbitrários tais que mdc(a i , n i )|b i para todo i . Prove que o sistema
ai X ≡ bi
(mod n i ),
tem solução.
83
∀i ∈ {1, 2, . . . , k}.
(66)
Compartilhar segredos usando o TCR
O problema é: dados inteiros n > k ≥ 1 determinar uma estratégia para que n
pessoas partilhem uma senha s ∈ Z sem conhece-la de modo que
1. qualquer subconjunto de k pessoas permite calcular s facilmente,
2. para menos que k pessoas quaisquer é muito difícil computar s.
A ideia é tomar uma lista L = {m 1 < m 2 < · · · < m n } números inteiros tais que
mdc(m i , m j ) = 1 para todo i 6= j e escolher s
N <s<M
(67)
onde N = m 1 m 2 · · · m k (produto dos k menores) e M = m n−k+2 m n−k+3 · · · m n
(produto dos k − 1 maiores).
Note que o produto de quaisquer k números de L é maior que N , o produto
de menos que k é menor que M e s > m para todo m ∈ L. Cada pessoa recebe
um par (m, s m ) com m ∈ L e s m = s mod m. Note que s > s m .
Em um grupo de t pessoas temos o sistema
X ≡ si
(mod m i ) ∀i ∈ {1, 2, . . . , t }
(68)
cuja solução x 0 ≡ s (mod m 1 m 2 · · · m t ). Agora,
t ≥ k: nesse caso m 1 m 2 · · · m t ≥ N > s e, pelo teorema chinês do resto, existe uma
única solução x 0 módulo m 1 m 2 · · · m t , como s é solução x 0 = s.
t < k: nesse caso m 1 m 2 · · · m t < M < s e x 0 6= s, mas como s é solução devemos
ter s = x 0 + y(m 1 m 2 · · · m t ), com
M < x 0 + y(m 1 · · · m t ) < N ,
(69)
e podemos escolher os módulos de modo que esse intervalo seja muito
grande, o que torna a busca por y inviável.
Como exercício, verifique o protocolo acima de partilha de senha para o caso
k = 2 com L = {11, 13, 17, 19, 23}.
84
Exercícios
1. Num teatro duas tropas se enfrentam numa cena de batalha. Uma tropa
tem 100 mosquetes e depois de atirar tantos tiros quanto possíveis lhes
sobraram 13 cartuchos. A outra tropa tem 67 mosquetes e ao fim lhes restam 32 cartuchos. Supondo que a cada salva de tiros cada soldado atirou
apenas uma vez determine o número mínimo de cartuchos de cada tropa
no início da apresentação.
2. Resolva X 2 +42X +21 ≡ 0 (mod 105). (Dica: fatore 105 e resolva a equação
para módulo cada fator e use o teorema chinês do resto)
3. A teoria do Biorritmo diz que os estados físico, mental e emocional de uma
pessoa oscilam periodicamente, a partir do dia do nascimento, em ciclos
de 23, 29 e 33 dias, respectivamente. Dado que os dias mais positivos dos
ciclos físico, mental e emocional são, respectivamente, o 6º, o 7º e o 8º
dias de cada ciclo, quantas vezes os três ciclos estão simultaneamente no
ponto máximo nos primeiros 10 anos de vida?
4. Verifique que


 X ≡ −1 (mod 4)

 X ≡ 2 (mod 6)
não tem solução.
5. Verifique que x ≡ 3 (mod 12) é solução de


 X ≡ −1 (mod 4)

 X ≡ 3 (mod 6)
(note os módulos não-coprimos).
6. Mostre que x ≡ 3 (mod 24) é solução de


 X ≡ 3 (mod 12)

 X ≡ 19 (mod 8)
85
7. Mostre que


X ≡ a
(mod n)

X ≡ b
(mod m)
tem no máximo uma solução módulo mmc(n, m) (não estamos assumindo
coprimalidade).
8. Sejam p 6= q primos, n = pq. Digamos que conhecemos uma solução para
X 2 ≡ a (mod p) e X 2 ≡ a (mod q). Mostre como usar o teorema chinês
do resto para achar solução de X 2 ≡ a (mod n).
9. 3 satélites passarão sobre SA esta noite. O primeiro a 1h da manha, o segundo as 4h e o terceiro as 8h. O primeiro leva 13hs para completar uma
volta, o segundo 15h e o terceiro 19h. Quantas horas decorrerão, a partir
da meia-noite até que os 3 passam ao mesmo tempo sobre SA.
10. Determine um número que dividido por 3,5,7 de restos 2,3,2
9 A função ϕ de Euler e o Teorema de Euler
A função ϕ de Euler associa a cada inteiro positivo n a quantidade de inteiros
positivos menores que n que são coprimos com n
¯
¯
¯
¯
ϕ(n) := ¯{a ∈ N : mdc(a, n) = 1 e 1 ≤ a ≤ n}¯
n
1
2
3
4
5
6
7
8
9
10
ϕ(n)
1
1
2
2
4
2
6
4
6
4
(70)
Decorre da definição que se p é primo então ϕ(p) = p − 1. Para potências de
primo temos que dentre 1, 2, . . . , p k não são coprimos com p k aquele que têm p
como fator primo, a saber p, 2p, 3p, . . . , p k−1 p, portanto p k − p k−1 são os coprimos, isto é
k
k
ϕ(p ) = p − p
k−1
A função ϕ é multiplicativa
86
µ
¶
1
= p 1−
p
k
Teorema 95. Se n, m ∈ Z+ são coprimos então ϕ(nm) = ϕ(n)ϕ(m).
Demonstração. O caso m = 1 ou n = 1 é imediato. Sejam n, m > 1 inteiros. Definimos os conjuntos
A
:= {a ∈ N : mdc(a, nm) = 1 e 1 ≤ a ≤ nm}
B
:= {b ∈ N : mdc(b, n) = 1 e 1 ≤ b ≤ n}
C
:= {c ∈ N : mdc(c, m) = 1 e 1 ≤ c ≤ m}
portanto o enunciado do teorema afirma que |A| = |B | · |C |. Vamos mostrar uma
bijeção entre A e B ×C .
Seja a ∈ A. Primeiro, vejamos que (a mod n, a mod m) pertence a B ×C . Observemos que se a é múltiplo de n > 1 ou múltiplo de m > 1 então mdc(a, nm) >
1, o que contraria a ∈ A, portanto a mod n 6= 0 6= b mod m. Ainda
mdc(a, nm) = 1 ⇒ mdc(a, n) = 1 e mdc(a, m) = 1
(71)
e
mdc(a mod n, n) = mdc(a, n) = 1 e mdc(a mod m, m) = mdc(a, m) = 1
como sabemos do algoritmo de Euclides. Para provar (71) notemos que existem
x, y ∈ Z tais que ax + nm y = 1 donde temos que a X + nY = 1 tem solução e
aX + mY = 1 tem solução, portanto, mdc(a, n) = mdc(a, m) = 1 pelo corolário
61.
Com isso temos que a função f : A → B dada por
f (a) = (a mod n, a mod m)
está bem definida. Para provar o teorema, vamos mostrar que a função é uma
bijeção.
Sejam a 1 e a 2 são elementos de A. Se f (a 1 ) = f (a 2 ) então a 1 mod n = a 2 mod
n e a 1 mod m = a 2 mod m portanto
a1 ≡ a2
(mod n)
a1 ≡ a2
(mod m)
87
logo a 1 ≡ a 2 (mod nm) (veja o argumento no parágrafo anterior a equação (62)),
e como 1 ≤ a 1 , a 2 ≤ nm temos a 1 = a 2 . Portanto a função é injetiva.
Resta provar que a função é sobrejetiva. Seja (b, c) um elemento qualquer
de B × C , isto é, 1 ≤ b ≤ n, 1 ≤ c ≤ m, mdc(b, n) = 1 e mdc(c, m) = 1. Como
mdc(n, m) = 1 o Teorema Chinês do Resto garante que há uma única solução a
módulo nm para o sistema de congruências


 X ≡ b (mod n)

X ≡ c
(mod m)
portanto (a mod n, a mod n) = (b, c), ademais, mdc(a, nm) = 1 pela recíproca de
(71) (veja exercício 31, item 6).
Exercício 96. Use indução (em k) para mostrar que se mdc(n i , n j ) = 1 para todo
i 6= j então ϕ(n 1 n 2 · · · n k ) = ϕ(n 1 )ϕ(n 2 ) · · · ϕ(n k ).
m
m
Agora, pelo exercício anterior, se n = p 1 1 · · · p k k é a fatoração canônica de n
então
ϕ(n) =
k
Y
i =1
m
ϕ(p i i ) =
k
Y
i =1
m
p i i (1 − 1/p i ) =
k
Y
i =1
mi
pi
k
Y
(1 − 1/p i )
i =1
ou seja,
k
Y
µ
¶
1
.
ϕ(n) = n
1−
pi
i =1
(72)
Exercício 97. Mostre que ϕ(n) = n − 1 se e só se n primo.
9.1 Sistema completo de invertíveis (sci)
Do conjunto R := {0, 1, . . . , n − 1} dos restos módulo n, consideremos apenas os
que são coprimos com n, isto é, o subconjunto S := {r 1 , r 2 , . . . , r ϕ(n) } ⊂ R de todos
os restos r i ∈ R tais que mdc(r i , n) = 1. Como R é um sistema completo de restos
(scr) módulo n, todo inteiro b é côngruo a um, e só um, r ∈ R; agora, se b é
coprimo com n então r ∈ S: do Teorema de Euclides temos mdc(n, b mod n) =
mdc(b, n) = 1 e r = b mod n. Ou seja, todo inteiro coprimo com n é congruente a
um e só um elemento de S.
88
Para n ≥ 1, um conjunto com ϕ(n) inteiros incongruentes entre si módulo
n e coprimos com n é chamado de sistema completo de invertíveis módulo n.
Equivalentemente, um conjunto S ⊂ Z tal que mdc(a, n) = 1 para todo a ∈ S e
tal que para todo z ∈ Z com mdc(z, n) = 1 existe um único a ∈ A tal que a ≡ z
(mod n) é um sistema completo de invertíveis módulo n.
Por exemplo {1, 3, 5, 7}, {±1, ±3} e {±5, ±7} são sci módulo 8.
Exercício 98. Seja S um scr módulo n qualquer. Mostre que os elementos de S
coprimos como n formam um sci módulo n.
Em vista disso, um sci também é chamado de sistema reduzido de restos módulo n.
Proposição 99. Se S é um sci módulo n então para todo a coprimo com n o conjunto a · S é um sci módulo n.
Demonstração. Tome S = {x 1 , x 2 , . . . , x ϕ(n) } um sistema completo de invertíveis
módulo n e forme o conjunto a ·S = {ax 1 , ax 2 , . . . , ax ϕ(n) } para a coprimo com n.
Como a é invertível módulo n, então
ax i ≡ ax j
(mod n) ⇒ x i ≡ x j
(mod n) ⇒ i = j ,
ademais mdc(ax i , n) = 1 para todo i , ou seja, os ϕ(n) elementos de a · S são
incongruentes entre si e invertíveis módulo n.
9.2 O Teorema de Euler
Teorema 100 (Teorema de Euler). Sejam a, n ∈ Z, n > 0 e mdc(a, n) = 1. Então
a ϕ(n) ≡ 1 (mod n).
(73)
Demonstração. Tome A = {x 1 , x 2 , . . . , x ϕ(n) } sci e consideremos a · A. Como, para
cada i vale mdc(ax i , n) = 1, devemos ter ax i ≡ x j (mod n) para algum j portanto,
x 1 x 2 · · · x ϕ(n) a ϕ(n) ≡ x 1 x 2 · · · x ϕ(n)
e como cada x i é invertível módulo n segue (73).
89
(mod n)
Exemplo. 2|(n 13 − n) para todo n pois n 13 − n = n(n 12 − 1) e
n 12 − 1 = (n − 1)(n 11 + n 10 + · · · + n + 1)
e 2|n(n − 1).
Exemplo. 3|(n 13 − n) para todo n pois
n 12 − 1 = (n 2 − 1)(n 10 + n 8 + · · · + n 2 + 1)
e 3|n ou, pelo Teorema de Euler, n 2 ≡ 1 (mod 3) isto é 3|n 2 − 1.
Exemplo. Ainda, 5|(n 13 − n) para todo n pois
n 12 − 1 = (n 4 − 1)(n 8 + n 4 + 1)
e 5|n ou, pelo Teorema de Euler, n 4 ≡ 1 (mod 5) isto é 5|n 4 − 1.
Se mdc(a, n) = 1 então aX ≡ b (mod n) tem solução x que é única módulo
n, e como a é invertível
x ≡ a ϕ(n)−1 b
(mod n)
(74)
de modo que todas as soluções da congruência linear são
x = a ϕ(n)−1 b + t n,
∀t ∈ Z
(75)
agora, se mdc(a, n) = d > 1 e a congruência linear tem solução, então a congruência tem as mesmas soluções de
invertível módulo
n
d
a
dX
≡
b
d
(mod
e a única solução módulo
x=
n
d
n
a
d ), de modo que, agora d
é
é
³ a ´ϕ( n )−1 b
d
d
d
(76)
e as d soluções módulo n são
x≡
³ a ´ϕ( n )−1 b n
d
+ t
d
d d
(mod n),
90
∀t ∈ {0, 1, . . . , d − 1}.
(77)
9.3 O Pequeno Teorema de Fermat revisitado
Corolário 101 (Pequeno Teorema de Fermat). Seja a ∈ Z e p um primo que não
divide a. Então
a p−1 ≡ 1 (mod p).
(78)
Equivalentemente
Teorema 102 (Pequeno Teorema de Fermat). Para todo a ∈ Z e todo primo p
ap ≡ a
(mod p).
(79)
Demonstração. Se p 6 |a, o resultado segue de (78). Se p|a, então p|(a p − a).
A recíproca do teorema de Fermat não é verdadeira (verifique), mas vale o
seguinte resultado.
Teorema 103. Sejam a, n > 1. Se mdc(a, n) = 1, a n−1 ≡ 1 (mod n) e a k 6≡ 1
(mod n) para todo inteiro positivo k < n − 1 então n é primo.
Demonstração. Do Teorema de Euler temos a ϕ(n) ≡ 1 (mod n), portanto, por
hipótese, ϕ(n) ≥ n − 1, donte temos ϕ(n) = n − 1. O teorema segue do exercício
97.
Exercícios
1. Se n = kd então |{m : 1 ≤ m ≤ n e mdc(m, n) = d }| = ϕ(k).
2. Mostre que se p é primo ímpar então {±1, ±2, . . . , ±(p − 1)/2} é um sci módulo n.
3. Mostre que se mdc(a, n) = 1 então
i≡j
(mod ϕ(n)) ⇒ a i ≡ a j
91
(mod n).
4. Mostre que 7 e 13 dividem n 13 − n para todo n.
5. Mostre que 2730|n 13 − n.
6. Seja p primo.
(a) Prove que p divide
¡p ¢
i
para todo i ∈ {1, 2, . . . , p − 1}.
(b) Prove que para inteiros x e y vale (x + y)p ≡ x p + y p (mod p).
(c) Prove, usando indução, que n p ≡ n (mod p) para todo natural n ≥ 1.
(d) Deduza (78) a partir dos resultados obtidos acima.
7. Use o Pequeno Teorema de Fermat para provar que
(a) 13|(270 + 370 ).
(b) 9|(n 3 + (n + 1)3 + (n + 2)3 ).
(c) X 13 + 12X + 13Y 6 = 1 não admite solução inteira.
RSA
Relembrando o protocolo de criptografia RSA:
1. Escolha dois números primos p e q e compute n := p · q;
2. Compute ϕ(n) = (p − 1) · (q − 1);
3. Escolha e ∈ {2, 3, . . . ϕ(n)−1} com mdc(e, ϕ(n)) = 1; disponibilize o par (e, n),
é a sua chave pública.
4. Compute d tal que d ·e ≡ 1 (mod ϕ(n)) e mantenha-o em segredo, a chave
privada é o par (d , n).
Consideremos que uma mensagem é um natural m ∈ Z (por exemplo, m é
o número representado em base 2 que o computador usa para gravar o arquivo
com a mensagem no HD) tal que m < n (isso não é uma restrição que põe tudo
a perder, como foi explicado em sala, basta considerar o binário em blocos).
92
Para eu mandar-lhe a mensagem m criptografada busco pela sua chave pública e calculo c := m e mod n e o envio. Você, que é o único portador da chave
privada, calcula a c d mod n e tem de volta a mensagem m.
c d mod n = (m e mod n)d mod n
Notemos que, quaisquer inteiros a e k ≥ 0, vale a k ≡ (a mod n)k (mod n). Assim, c d ≡ (m e )d (mod n) e de ed = 1 + r ϕ(n) para algum r ∈ Z
¡
¢(q−1)r
m ed = m 1+r ϕ(n) = m m p−1
Se p 6 |m então
¡
¢(q−1)r
m m p−1
≡m
(mod p)
(80)
pois m p−1 ≡ 1 (mod p) pelo Pequeno Teorema de Fermat. Também, m ed ≡ m
(mod p) se p|P , ou seja,
m ed ≡ m
(mod p).
(81)
m ed ≡ m
(mod q).
(82)
Analogamente, vale
De (81) e (82) temos que pq|m ed − m, ou seja, m ed ≡ m (mod n). Como m < n,
temos m ed mod n = m.
10 Restos quadráticos
Sejam p primo e a, b, c inteiros com a não divisível por p. Notemos que para
qualquer inteiro x
ax 2 + bx + c ≡ 0 (mod p) ⇔ (completando quadrados)
(2ax + b)2 ≡ b 2 − 4ac
(mod p)
assim, estamos interessados nas soluções módulo p de X 2 ≡ d (mod p) (se assumimos que p > 2 então a e 2 são invertíveis mod p) ou, mais precisamente,
determinar quando existe solução.
93
O caso d = 0 é trivial, assim como não é difícil mostrar que módulo 2 sempre
há solução (justifique), de modo que reformulamos a discussão como segue.
Sejam p um primo ímpar e a um inteiro não divisível por p; dizemos que a
é um resíduo (ou resto) quadrático módulo p se
X2 ≡ a
(mod p)
(83)
tem solução em {0, 1, . . . , p − 1}.
Por exemplo, 2 não é um resto quadrático módulo 3; módulo 5 temos 02 ≡ 0,
12 ≡ 1 ≡ 42 , 22 ≡ 4 ≡ 32 , ou seja, 2 e 3 não são resíduos quadráticos módulo 5.
Notemos que se x é uma solução de (83), então −x também é solução; se y
é outra solução então y 2 ≡ a ≡ x 2 (mod p), logo y 2 − x 2 ≡ 0 (mod p) e
y 2 − x 2 ≡ 0 (mod p) ⇔ (y − x)(y + x) ≡ 0 (mod p)
⇔ (y − x) ≡ 0 (mod p) ou (y + x) ≡ 0 (mod p)
⇔
y ≡x
(mod p) ou y ≡ −x
(mod p)
agora ou x ≡ −x (mod p) caso em que há uma única solução módulo p de (83),
ou x 6≡ −x (mod p) caso em que há exatamente duas soluções módulo p de (83).
Porém, x ≡ −x (mod p) ⇔ 2x ≡ 0 (mod p) ⇔ p|x ou p|2. Como p 6 |a, também p 6 |x 2 , portanto p 6 |x, e como p é ímpar segue que x 6≡ −x (mod p). Provamos
Proposição 104. Sejam p > 2 primo e a inteiro não-múltiplo de p. Se X 2 ≡ a
(mod p) tem solução então tem duas soluções módulo p.
Exercício 105. Mostre que (p − 1)/2 inteiros de {0, 1, 2, . . . , p − 1} são restos quadráticos módulo p > 2.
Solução. {0, ±1, ±2, . . . , ±(p − 1)/2} é um scr, portanto, x 2 é congruente a algum
de {02 , 12 , 22 , . . . , ((p − 1)/2)2 }, para todo inteiro x. Ainda quaisquer dois desses
quadrados são incongruentes mod p. Excluindo o 0 dá a resposta.
Apesar desse exercício, na prática pode ser difícil decidir se um número é ou
não é um resíduo quadrático.
94
Seja x uma solução da congruência de grau 2. Considerando o caso que
2
x ≡ a (mod p) com x ∈ {0, . . . , p − 1}, notemos que
(p − 1)! = 1 · 2 · · · x · · · (p − x) · · · (p − 2) · (p − 1)
Para cada fator a 0 ∈ {1, 2, . . . , p − 2, p − 1} do fatorial acima a equação a 0 X ≡ a
(mod p) admite uma solução x 0 módulo p, 1 ≤ x 0 ≤ p − 1. Ademais, se a 0 6=
x, p − x então x 0 6= a 0 . Em outras palavras, exceto por x e p − x, os fatores do
produto podem ser agrupados aos pares {a 0 , x 0 } de modo que a 0 x 0 ≡ a (mod p),
i.e.
1 · 2 · · · (x − 1)(x + 1) · · · (p − x − 1)(p − x + 1) · · · (p − 2) · (p − 1) ≡ a
p−3
2
(mod p)
portanto
(p − 1)! ≡ a
p−3
2
x(p − x) (mod p)
(84)
e como x(p − x) ≡ x(−x) ≡ −x 2 ≡ −a (mod p), temos
(p − 1)! ≡ −a
p−1
2
(mod p)
(85)
Agora, no caso que X 2 ≡ a (mod p) não tem solução, para cada resto r do conjunto R := {1, 2, . . . , p − 1}, existe um único resto r 0 ∈ R tal que r 0 6= r e r r 0 ≡ a
(mod p) portanto
(p − 1)! ≡ a
p−1
2
(mod p).
(86)
Com isso temos o seguinte resultado,
Proposição 106. Sejam a ∈ Z e p > 2 primo. Se mdc(p, a) = 1 então
1. se a é um resto quadrático módulo p então (p − 1)! ≡ −a
p−1
2
2. se a não é um resto quadrático módulo p então (p −1)! ≡ a
(mod p);
p−1
2
(mod p).
O seguinte resultado foi enunciado Ibn al-Haytham4 e por e John Wilson5 .
4 nasceu no ano 965 em Basra (Iraque) e morreu em 1040 na cidade do Cairo. Físico e matemá-
tico árabe. Pioneiro da Óptica, depois de Ptolomeu. Um dos primeiros a explicar o fenômeno dos
corpos celestes no horizonte.
5 matemático inglês do fim do século 18
95
Edward Waring6 anunciou o teorema em 1770, embora nem ele nem seu aluno
Wilson deram uma prova. Lagrange deu a primeira prova em 1771.
Teorema 107 (Teorema de Wilson). p é primo se, e somente se, (p − 1)! ≡ −1
(mod p).
Demonstração. Seja p um primo. O caso p = 2 é imediato, portanto supomos
p > 2. 1 é um resíduo quadrático módulo p, portanto, (p − 1)! ≡ (−1)
p−1
2
≡ −1
(mod p).
Seja p composto. Se p = 4 então (p − 1)! ≡ 6 6≡ −1 (mod 4). Se p > 4 então
p = ab com 1 < a, b < p. Se a 6= b então a e b ocorrem em (p − 1)! portanto
p|(p − 1)!; agora, se a = b > 2 então a, 2a, . . . , (a − 1)a ocorrem em (p − 1)!, logo
p|(p − 1), ou seja, se p > 4 é composto então (p − 1)! ≡ 0 (mod n).
Como consequência desse teorema e da proposição anterior
a é um resto quadrático mod p
a não é um resto quadrático mod p
⇒ −1 ≡ (p − 1)! ≡ −a
⇒ −1 ≡ (p − 1)! ≡ a
p−1
2
p−1
2
(mod p)
(mod p)
Do Pequeno Torema de Fermat
a p−1 − 1 ≡ 0 (mod p) ⇒ (a
portanto a
p−1
2
≡ 1 (mod p) ou a
p−1
2
p−1
2
− 1)(a
p−1
2
+ 1) ≡ 0 (mod p)
≡ −1 (mod p), de modo que as implicações
acima são de fato equivalentes.
Corolário 108 (Critério de Euler). Sejam p uma primo ímpar e a um inteiro não
divisível por p.
1. a é um resto quadrático módulo p se, e só se, a
p−1
2
≡ 1 (mod p);
2. a é não um resto quadrático módulo p se, e só se, a
p−1
2
≡ −1 (mod p).
6 orientador de Wilson, Lucasian Professor of Mathematics na Universidade de Cambridge que
é uma das mais prestigiadas cátedras no mundo, já foi ocupada por Isaac Newton, Paul Dirac e
Stephen Hawking entre outros.
96
10.1 O símbolo de Legendre
Para p > 2 primo e a inteiro


1
se p 6 |a e a é um resto quadrático módulo p

µ ¶ 

a
= 0
se p|a

p



−1 caso contrário.
portanto, pelo critério de Euler
µ ¶
p−1
a
≡a 2
p
(mod p)
(87)
(88)
Proposição 109. O símbolo de Legendre possui as seguintes popriedades
³ ´ ³ ´
1. se a ≡ b (mod p) então pa = pb
2.
³
a2
p
´
= 1 se p 6 |a
3.
³
−1
p
´
= (−1)
4.
³
ab
p
´
=
p−1
2
³ ´³ ´
a
p
b
p
se, e só se, p ≡ 1 (mod 4)
.
10.2 Lei da Reciprocidade Quadrática
O seguinte resultado é um importante teorema da Teoria dos Números. Foi demonstrado pela primeira vez (de modo correto, houveram outras “provas” antes,
Euler conhecia esse resultado e Legendre deu uma demosntração incompleta)
por Gauss em Disquisitiones Arithmeticae. Aqui são dadas quase 200 demonstrações desse resultado. Essa lei diz que se p e q são primos ímpares distintos e
pelo menos um deles é congruente a 1 módulo 4, então p é um resíduo quadrático
módulo q se, e só se, q é um resíduo quadrático módulo p; congruente a 1 módulo
4, então p é um resíduo quadrático módulo q se, e só se, q é um resíduo quadrático módulo p; se ambos são congruentes a 3 módulo 4, então p é um resíduo
quadrático módulo q se, e só se, q não é um resíduo quadrático módulo p;
Usando o símbolo de Legendre, podemos enunciar a lei da reciprocidade da
seguinte maneira; a demonstração fica para a próxima.
97
Teorema 110 (Lei da Reciprocidade Quadrática). Se p 6= q são primos ímpares
então
µ ¶µ ¶
p−1 q−1
p q
= (−1) 2 · 2
q p
Em outras palavras, as congruências X 2 ≡ p (mod q) e X 2 ≡ q (mod p) ou
ambas têm solução ou nenhuma tem, exceto quanto p ≡ 3 (mod 4), quando
uma tem solução e a outra não.
Exercício 111. Prove que a lei de reciprocidade é equivalente às seguintes afirmações, enunciadas por Euler:
1. se q ≡ 1 (mod 4) então q é um resíduo quadrático módulo p se, e só se,
p ≡ r (mod q), em que r é um resíduo quadrático módulo q;
2. se q ≡ 3 (mod 4) então p é um resíduo quadrático módulo q se, e só se,
p ≡ ±b 2 (mod 4q) em que b é ímpar e não divisível por q.
Exercícios
1. Prove que 6X 2 +5X +1 ≡ 0 (mod m) tem solução para todo inteiro positivo
m.
2. Determine as soluções de X 2 ≡ 11 (mod 35).(Dica: fatore 35)
3. Seja a um resíduo quadrático módulo p > 2. Mostre que
(a) se p ≡ 1 (mod 4) então p − a é um resíduo quadrático módulo p;
(b) se p ≡ 3 (mod 4) então p − a não é um resíduo quadrático módulo
p.
4. Mostre que X 2 + 1 ≡ 0 (mod p) (p > 2 primo) tem solução se, e somente
se, p ≡ 1 (mod 4).
5. Use o teorema de Wilson para encontrar o menor resto de 8·9·10·11·12·13
módulo 7.
98
6. Mostre que se p é primo e a inteiro então p|(a p + (p − 1)!a).
7. Mostre que p é o menor primo que divide (p − 1)! + 1.
8. Mostre que se o primo ímpar p é tal que p ≡ 1 (mod 4) então X 2 ≡ −1
(mod p) tem duas soluções.
9. Mostre que se o primo ímpar p é tal que p ≡ 3 (mod 4) então ((p −1)/2)! ≡
±1 (mod p).
10. Mostre que para oo primo ímpar p vale (((p−1)/2)!)2 ≡ (−1)(p+1)/2 (mod p).
11. Prove a proposição 109
12. Use o critério de Euler a reciprocidade quadrática para mostrar que, para
p primo,
(a) se p = 4n + 1 então p|n n − 1.
(b) se p = 4n − 1 então p|n n + 2n(−1)n+1 .
99