14/01/2014
2
Divisibilidade
• Inteiros 𝑎 e 𝑏
• 𝑎|𝑏
INTEIROS, DIVISORES E PRIMOS:
DIVISIBILIDADE E PRIMALIDADE
• “𝑎 divide 𝑏”
• “𝑎 é um divisor de 𝑏”
• “𝑏 é um múltiplo de 𝑎”
Matemática Discreta
• Existe inteiro 𝑚 tal que 𝑏 = 𝑎𝑚
Prof. João Paulo Lima
• Se 𝑎 ≠ 0, então 𝑏 𝑎 é inteiro
Universidade Federal Rural de Pernambuco
Departamento de Estatística e Informática
Copyright © 2006 by The McGraw-Hill Companies, Inc. All rights reserved.
3
4
Divisibilidade
Números Primos
• Inteiros 𝑎 e 𝑏
• Inteiro 𝑝 > 1 é primo se não é divisível por qualquer
inteiro diferente de 1, −1, 𝑝 e −𝑝
•𝑎∤𝑏
• Inteiro 𝑝 > 1 é primo se não pode ser escrito como
• “𝑎 não divide 𝑏”
produto de dois inteiros positivos menores que ele
• “𝑎 não é um divisor de 𝑏”
• 2, 3, 5, 7, 11 são primos
• “𝑏 não é um múltiplo de 𝑎”
• Inteiro 𝑛 > 1 que não é primo é denominado composto
• Não existe inteiro 𝑚 tal que 𝑏 = 𝑎𝑚
• Se 𝑎 > 0, então pode-se dividir 𝑏 por 𝑎 com resto 𝑟
4=2∙2
6 =2∙3
• 8 = 2 ∙ 4 são compostos
9 =3∙3
10 = 2 ∙ 5
•0<𝑟<𝑎
• 𝑏 = 𝑎𝑞 + 𝑟
5
Números Primos
6
Números Primos
• “Buracos” na sequência de primos
• Quão grandes são esses “buracos”?
• Existe um número primo com um dado número qualquer
de dígitos?
• Resposta: sim (aplicações em criptografia)
1
14/01/2014
7
8
Fatoração em Primos
Fatoração em Primos
• Métodos de fatoração ficam impraticáveis quando número
• Teorema Fundamental da Teoria dos Números
possui mais de 20 dígitos
• Supercomputadores e sistemas massivamente paralelos
conseguem fatorar números com cerca de 140 dígitos
• Tempo cresce exponencialmente com número de dígitos
• Fatorar número com 400 dígitos está muito além das
possibilidades dos computadores no futuro previsível
• Aplicações em criptografia
• Todo inteiro positivo pode ser escrito como produto de
números primos
• Fatoração é única a menos da ordem dos fatores primos
9
10
Fatoração em Primos
Fatoração em Primos
• Prova por contradição
• 𝑛 = 𝑝1 ∙ 𝑝2 ∙ ⋯ ∙ 𝑝𝑚 = 𝑞1 ∙ 𝑞2 ∙ ⋯ ∙ 𝑞𝑘
• Criminoso mínimo
• Vamos assumir que 𝑝1 é o menor primo das duas
fatorações, sem perda de generalidade
• Vamos assumir que existe um inteiro 𝑛 com duas
• Vamos obter uma contradição ao produzir um criminoso
fatorações diferentes
menor que 𝑛
• Criminoso
• Pode haver vários criminosos, mas estamos interessados
no menor deles
• Criminoso mínimo
11
12
Fatoração em Primos
Fatoração em Primos
• 𝑝1 não pode ocorrer entre 𝑞𝑖 , caso contrário seria possível
• 𝑛′ também tem duas fatorações diferentes
dividir ambos os lados por 𝑝1 e obter um criminoso menor
• 𝑞𝑖 = 𝑝1 𝑎𝑖 + 𝑟𝑖 , onde 0 < 𝑟𝑖 < 𝑝1
• 𝑟𝑖 ≠ 0, pois um primo não pode dividir outro primo
• 𝑛′ = 𝑟1 ∙ 𝑟2 ∙ ⋯ ∙ 𝑟𝑘
• 𝑟𝑖 < 𝑝1 < 𝑞𝑖
• 𝑛′ = 𝑟1 ∙ 𝑟2 ∙ ⋯ ∙ 𝑟𝑘 < 𝑞1 ∙ 𝑞2 ∙ ⋯ ∙ 𝑞𝑘 = 𝑛
• 𝑛′ = 𝑟1 ∙ 𝑟2 ∙ ⋯ ∙ 𝑟𝑘
• 𝑟𝑖 pode não ser primo, mas pode ser fatorado
• 𝑛′ = 𝑞1 − 𝑎1 𝑝1 ∙ 𝑞2 − 𝑎2 𝑝1 ∙ ⋯ ∙ 𝑞𝑘 − 𝑎𝑘 𝑝1
• 𝑛′ = 𝑞1 ∙ 𝑞2 ∙ ⋯ ∙ 𝑞𝑘 + 𝑝1 …
𝑛
• 𝑝1 | 𝑛, logo 𝑝1 | 𝑛′
• 𝑛′ = 𝑝1 ∙ 𝑛′ 𝑝1
• Fatorando 𝑛′ 𝑝1 obtém-se uma fatoração para 𝑛′
2
14/01/2014
13
Fatoração em Primos
14
Conjunto dos Números Primos
′
• As duas fatorações de 𝑛 são diferentes
• O conjunto dos números primos é infinito
• 𝑝1 aparece na segunda fatoração, mas não pode
• Para todo inteiro positivo 𝑛, existe um primo maior que 𝑛
aparecer na primeira fatoração, pois 𝑟𝑖 < 𝑝1
• Logo, 𝑛′ é um criminoso menor que 𝑛 (contradição)
• Então, o Teorema Fundamental da Teoria dos Números é
verdadeiro, c.q.d.
• 𝑛! + 1
• 𝑝 é primo e 𝑝 | 𝑛! + 1
• Queremos mostrar que 𝑝 > 𝑛
• Vamos assumir que 𝑝 ≤ 𝑛
• Então 𝑝 | 𝑛!, pois 𝑝 é um dos inteiros cujo produto é 𝑛!
• Se 𝑝 | 𝑛! + 1 e 𝑝 | 𝑛!, então 𝑝 | 𝑛! + 1 − 𝑛!
• Logo, 𝑝 | 1 (contradição)
• Sendo assim, 𝑝 > 𝑛 (conjunto dos primos é infinito), c.q.d.
15
16
Conjunto dos Números Primos
Teorema do Número Primo
• Para todo inteiro positivo 𝑘, existem 𝑘 inteiros compostos
• 𝜋 𝑛 é a quantidade de primos entre 1 e 𝑛
consecutivos
• 𝑛 =𝑘+1
• 𝑛! + 2, 𝑛! + 3, …, 𝑛! + 𝑛
• 𝑛! = 𝑛 ∙ 𝑛 − 1 ∙ ⋯ ∙ 3 ∙ 2 ∙ 1
• 𝑛! + 2 é divisível por 2, pois 𝑛! e 2 são divisíveis por 2
• 𝑛! + 3 é divisível por 3, pois 𝑛! e 3 são divisíveis por 3
• ...
• 𝑛! + 𝑛 é divisível por 𝑛, pois 𝑛! e 𝑛 são divisíveis por 𝑛
• 𝑛! + 2, 𝑛! + 3, …, 𝑛! + 𝑛 são compostos
• 𝑛 − 1 = 𝑘 números compostos consecutivos, c.q.d.
• Temos que:
𝜋 𝑛 ~
𝑛
ln 𝑛
• ln 𝑛 é o logaritmo natural de 𝑛
• ln 𝑛 = log 𝑒 𝑛, onde 𝑒 = 2,718281 … é o número de Euler
• Prova do Teorema do Número Primo é muito difícil
17
18
Teorema do Número Primo
Teorema do Número Primo
• Gráfico de 𝜋 𝑛 com 𝑛 variando de 1 a 100
• Gráfico de 𝜋 𝑛 com 𝑛 variando de 1 a 2000
3
14/01/2014
19
20
Teorema do Número Primo
Primos Gêmeos
• Quantos primos com 200 dígitos existem?
• Dois números primos cuja diferença é 2
• 𝜋 10200 − 𝜋 10199
• 3,5 , 5,7 , 11,13 , 17,19 são primos gêmeos
•
10200
200∙ln 10
−
10199
199∙ln 10
• Existem primos gêmeos com centenas de dígitos
197
≈ 1,95 ∙ 10
• Até hoje não foi encontrada prova de que existe uma
• Quantidade de inteiros positivos com 200 dígitos:
10
•
200
199
− 10
9∙10199
1,95∙10197
quantidade infinita de primos gêmeos
199
= 9 ∙ 10
≈ 460
• Entre os inteiros positivos com 200 dígitos,
aproximadamente um em cada 460 é primo
21
22
Conjectura de Goldbach
Quantidade de Primos em um Intervalo
• Para todo inteiro par 𝑛 > 2,
• Existe um primo entre 𝑛 e 𝑛! + 1
existem dois primos 𝑎 e 𝑏
tais que 𝑎 + 𝑏 = 𝑛
• Problema não resolvido
• Intervalo muito grande
• Ex: 𝑛 = 10, 10! + 1 = 3628801
• Teorema de Chebychev: existe um primo entre 𝑛 e 2𝑛,
𝑛>1
• Existe um primo entre dois cubos consecutivos
• Ex: entre 27 = 33 e 64 = 43
• Não resolvido: se existe um primo entre dois quadrados
consecutivos
• Ex: entre 100 = 102 e 121 = 112, temos 101, 103, 107,
109 e 113
23
“Pequeno” Teorema de Fermat
𝑝
• Se 𝑝 é um primo e 𝑎 é um inteiro, então 𝑝 | 𝑎 − 𝑎
• Se 𝑝 é um primo e 𝑎 é um inteiro não divisível por 𝑝,
então 𝑝 | 𝑎𝑝−1 − 1
• Para provar o “Pequeno” Teorema de Fermat, é
necessário antes provar o seguinte lema:
se 𝑝 é um primo e 0 < 𝑘 < 𝑝, então 𝑝 | 𝑝𝑘
24
“Pequeno” Teorema de Fermat
𝑝
• 𝑘 = 𝑝 ∙ 𝑝 − 1 ∙ ⋯∙ 𝑝 − 𝑘 + 1
• 𝑝 | 𝑝∙ 𝑝 −1 ∙ ⋯∙ 𝑝 −𝑘 + 1
𝑘 ∙ 𝑘 − 1 ∙ ⋯∙ 1
• 𝑝 ∤ 𝑘 ∙ 𝑘 − 1 ∙ ⋯ ∙ 1, pois 𝑘 < 𝑝
• Se 𝑝 | 𝑏 e 𝑝 ∤ 𝑎, então 𝑝 |
𝑏
𝑎
𝑏
𝑏
𝑎
𝑎
• 𝑝 | 𝑎 ∙ , mas 𝑝 ∤ 𝑎, logo 𝑝 |
• Se 𝑝 não ocorre na fatoração prima de 𝑎, então ocorre na de
• Sendo assim, 𝑝 |
𝑝
𝑘
𝑏
𝑎
, c.q.d.
4
14/01/2014
25
26
“Pequeno” Teorema de Fermat
“Pequeno” Teorema de Fermat
• Agora podemos provar o “Pequeno” Teorema de Fermat
• Demonstração:
por indução sobre 𝑎
• Caso base: 𝑎 = 0
• 𝑎 𝑝 − 𝑎 = 0𝑝 − 0 = 0
• 𝑝|0
• Passo indutivo:
• Hipótese indutiva: 𝑝 | 𝑏 𝑝 − 𝑏, onde 𝑏 = 𝑎 − 1
• Tese: 𝑝 | 𝑎𝑝 − 𝑎
• 𝑎𝑝 − 𝑎 = 𝑏 + 1 𝑝 − 𝑏 + 1
𝑝
𝑝
• 𝑎𝑝 − 𝑎 = 𝑏 𝑝 + 1 𝑏 𝑝−1 + ⋯ + 𝑝−1 𝑏 + 1 − 𝑏 − 1
• 𝑎𝑝 − 𝑎 = 𝑏 𝑝 − 𝑏 +
𝑝
1
𝑏 𝑝−1 + ⋯ +
𝑝
𝑝−1
𝑏
• Por hipótese, 𝑝 | 𝑏 𝑝 − 𝑏
𝑝
• Pelo lema provado anteriormente, 𝑝 | 𝑘 , onde 0 < 𝑘 < 𝑝
• Logo, 𝑝 | 𝑎𝑝 − 𝑎, c.q.d.
27
28
Último Teorema de Fermat
Máximo Divisor Comum
• Para todo inteiro 𝑛, se 𝑛 > 2 então não existem inteiros
• Inteiros positivos 𝑎 e 𝑏
positivos 𝑎, 𝑏, 𝑐 tais que 𝑎𝑛 + 𝑏 𝑛 = 𝑐 𝑛
• Fermat afirmou em uma nota de margem que a prova
para o teorema era muito grande para caber na margem
• Problema não resolvido por mais de 300 anos
• Em 1995, Andrew Wiles provou a validade do teorema
• Máximo divisor comum de 𝑎 e 𝑏 é maior inteiro positivo
que é divisor de ambos
• 𝑚𝑑𝑐 𝑎, 𝑏
• 𝑎 e 𝑏 são primos entre si sse 𝑚𝑑𝑐 𝑎, 𝑏 = 1
• 𝑚𝑑𝑐 𝑎, 0 = 𝑎, para todo 𝑎 ≥ 0
29
30
Máximo Divisor Comum
Algoritmo de Euclides
• 𝑚𝑑𝑐 𝑎, 𝑏 pode ser obtido a partir das fatorações de 𝑎 e 𝑏
• Método para calcular 𝑚𝑑𝑐 𝑎, 𝑏
• Produto dos fatores primos comuns elevados aos
• Baseia-se no seguinte teorema: seja 𝑟 o resto da divisão
menores expoentes dos dois
• Ex: 300 = 22 ∙ 3 ∙ 52 e 18 = 2 ∙ 33
• 𝑚𝑑𝑐 300,18 = 2 ∙ 3 = 6
• 𝑎 = 𝑏𝑞 + 𝑟
de 𝑎 por 𝑏, então 𝑚𝑑𝑐 𝑎, 𝑏 = 𝑚𝑑𝑐 𝑏, 𝑟
• 𝑟 = 𝑎 − 𝑏𝑞
• Como 𝑚𝑑𝑐 𝑎, 𝑏 | 𝑎 e 𝑚𝑑𝑐 𝑎, 𝑏 | 𝑏, então 𝑚𝑑𝑐 𝑎, 𝑏 | 𝑟
• Como 𝑚𝑑𝑐 𝑎, 𝑏 | 𝑏 e 𝑚𝑑𝑐 𝑎, 𝑏 | 𝑟, então 𝑚𝑑𝑐 𝑎, 𝑏 é
divisor comum de 𝑏 e 𝑟
• Logo 𝑚𝑑𝑐 𝑎, 𝑏 ≤ 𝑚𝑑𝑐 𝑏, 𝑟
5
14/01/2014
31
32
Algoritmo de Euclides
Algoritmo de Euclides
• 𝑎 = 𝑏𝑞 + 𝑟
• Ex: 𝑚𝑑𝑐 300,18
• Como 𝑚𝑑𝑐 𝑏, 𝑟 | 𝑏 e 𝑚𝑑𝑐 𝑏, 𝑟 | 𝑟, então 𝑚𝑑𝑐 𝑏, 𝑟 | 𝑎
• 𝑚𝑑𝑐 300,18 = 𝑚𝑑𝑐 18,12
• Como 𝑚𝑑𝑐 𝑏, 𝑟 | 𝑎 e 𝑚𝑑𝑐 𝑏, 𝑟 | 𝑏, então 𝑚𝑑𝑐 𝑏, 𝑟 é
• 𝑚𝑑𝑐 18,12 = 𝑚𝑑𝑐 12,6
divisor comum de 𝑎 e 𝑏
• Logo 𝑚𝑑𝑐 𝑏, 𝑟 ≤ 𝑚𝑑𝑐 𝑎, 𝑏
• Se 𝑚𝑑𝑐 𝑎, 𝑏 ≤ 𝑚𝑑𝑐 𝑏, 𝑟 e 𝑚𝑑𝑐 𝑏, 𝑟 ≤ 𝑚𝑑𝑐 𝑎, 𝑏 , então
𝑚𝑑𝑐 𝑎, 𝑏 = 𝑚𝑑𝑐 𝑏, 𝑟 , c.q.d.
• 𝑚𝑑𝑐 12,6 = 𝑚𝑑𝑐 6,0 = 6
• 𝑚𝑑𝑐 300,18 = 6
300
12
16
18
6
1
12
0
2
6
33
Algoritmo de Euclides
• 𝑑 = 𝑚𝑑𝑐(𝑎, 𝑏)
• 𝑑 = 𝑚𝑎 + 𝑛𝑏, onde 𝑚 e 𝑛 são inteiros
• Ex:
𝑚𝑑𝑐 300,18 = 𝑚𝑑𝑐 18,12 = 𝑚𝑑𝑐 12,6 = 𝑚𝑑𝑐 6,0 = 6
• 12 = 300 − 16 ∙ 18
• 6 = 18 − 1 ∙ 12
• 6 = 18 − 300 − 16 ∙ 18
• 6 = 17 ∙ 18 − 300
• 6 = −1 ∙ 300 + 17 ∙ 18
300
12
16
18
6
1
12
0
2
6
6