teoria dos números primos

Prévia do material em texto

5
N¶umeros primos
Neste cap¶³tulo, apresentamos o conceito de n¶umero primo e exploramos as primeiras
propriedades dos n¶umeros primos.
5.1 Conceitos e propriedades imprescind¶³veis
O inteiro positivo 1 tem somente um divisor positivo. Qualquer outro inteiro positivo n,
n > 1, tem pelo menos dois divisores positivos, 1 e n.
De¯ni»c~ao 5.1 Dizemos que um inteiro p ¶e primo se p6= 0, p6= 1, p6= ¡1, e os ¶unicos
inteiros divisores de p s~ao 1, p, ¡1 e ¡p. Dizemos que um inteiro m ¶e composto se
m6= 0, m6= 1, m6= ¡1, e m n~ao ¶e primo.
Assim sendo, um inteiro p ¶e primo quando p6= §1 e seus ¶unicos divisores positivos
s~ao 1 e jpj. J¶a um inteiro m ¶e composto quando m6= 0, e m possui divisores positivos
diferentes de 1 e de jmj.
O teorema abaixo estabelece o papel dos n¶umeros primos positivos, como blocos
construtivos dos inteiros positivos maiores que 1.
Teorema 5.1 Todo inteiro m, m ¸ 2, ¶e um n¶umero primo ou tem a forma m =
p1 ¢ ¢ ¢ pn, para certos inteiros primos positivos p1; : : : ; pn, com n ¸ 2. Ou seja, cada
inteiro, a partir de 2, ¶e um n¶umero primo ou um produto de fatores todos primos
positivos.
Demonstra»c~ao por indu»c~ao sobre m.
Se m = 2, ent~ao m ¶e primo (demonstre).
Seja k ¸ 2 e suponhamos que todo inteiro m, com 2 · m · k, ¶e primo ou se
decomp~oe como produto de fatores primos. Trataremos de demonstrar que ent~ao k + 1
38
N¶umeros primos 39
tamb¶em ¶e primo ou se escreve como produto de fatores primos. Note que ¯zemos uma
hip¶otese de indu»c~ao com a inten»c~ao de utilizarmos o segundo princ¶³pio de indu»c~ao ¯nita.
Consideremos o inteiro k+1. Se k+1 ¶e primo, ent~ao nada mais temos a demons-
trar.
Se k + 1 n~ao ¶e primo, como k + 1 ¸ 3, temos que k + 1 ¶e composto. Ent~ao
existem inteiros positivos a e b, com 1 < a < k + 1 e 1 < b < k + 1, tais que k + 1 se
fatora na forma k + 1 = a ¢ b.
Agora, como 2 · a · k e 2 · b · k, pela hip¶otese de indu»c~ao cada um dos
inteiros a e b ¶e um primo ou se decomp~oe como produto de fatores primos positivos.
Logo, como k + 1 = ab, k + 1 se decomp~oe como um produto de fatores primos
positivos.
Assim sendo, cada inteiro m ¸ 2 ¶e primo ou se escreve como um produto de
primos.
O teorema 5.1 enuncia, em parte, o Teorema Fundamental da Aritm¶etica, que ser¶a
estudado oportunamente. O Teorema Fundamental da Aritm¶etica estabelece tamb¶em
que a decomposi»c~ao de cada inteiro positivo, maior que 1, em fatores primos, ¶e ¶unica, a
menos da ordem dos fatores.
O teorema seguinte estabele um resultado que pode ser usado para testar se um
inteiro positivo n ¶e primo. Como veremos, utilizando um procedimento devido a Erat¶os-
tenes, o mesmo teorema pode ser usado para listar todos os primos positivos menores
que ou iguais a um inteiro positivo n, quando n ¸ 2.
Teorema 5.2 Se n ¶e um inteiro positivo composto ent~ao n tem um fator primo p
satisfazendo p · pn.
Equivalentemente, se n ¸ 2, e nenhum primo p, com 2 · p · pn, ¶e fator de n,
ent~ao, n ¶e primo.
Demonstra»c~ao. Sendo n composto, temos n ¸ 2, e pelo teorema 5.1, n = p1 ¢ ¢ ¢ ps,
para certos fatores primos positivos p1; : : : ; ps, com s ¸ 2 (se s = 1, n ¶e um n¶umero
primo).
Da¶³, p1 ·
p
n ou p2 ·
p
n, pois se p1 >
p
n e p2 >
p
n, ent~ao
n = p1 ¢ ¢ ¢ ps ¸ p1 ¢ p2 >
p
n ¢ pn = n
o que nos d¶a uma contradi»cao.
Como p1 e p2 s~ao fatores primos quaisquer de n, conclu¶³mos incidentalmente que,
se n ¸ 2 ¶e um inteiro composto, n n~ao pode ter dois fatores primos maiores que pn,
ou seja, todos os fatores primos de n (com poss¶³vel exce»c~ao de apenas um) s~ao menores
que
p
n.
N¶umeros primos 40
Exemplo 5.1 Para testar se o inteiro 1007 ¶e primo observamos, com o uso de uma
calculadora, que
p
1007 ¼ 31; 73.
Os primos positivos p satisfazendo p · p1007 ¼ 31; 73 s~ao 2, 3, 5, 7, 11, 13,
17, 19, 23, 29, 31. Com a calculadora, veri¯camos que 1007 n~ao ¶e divis¶³vel por nenhum
desses fatores, e portanto ¶e primo.
J¶a o mesmo procedimento, de testar os poss¶³veis fatores primos p de n, que satis-
fazem p · pn, nos revela que 1003 = 17 ¢ 59 e que 1001 = 13 ¢ 17.
5.2 O crivo de Erat¶ostenes
O teorema 5.2 pode ser usado, por exemplo, para listar os primos menores que ou iguais
a n, quando n ¶e um inteiro positivo.
Um procedimento para tal listagem ¶e chamado de Crivo de Erat¶ostenes, e consiste
em listar os n¶umeros menores que ou iguais a n crivando (demarcando) os m¶ultiplos dos
primos menores que ou iguais a
p
n.
Como mostramos no exemplo abaixo, para n = 100, consideramos como ponto de
partida os primos p satisfazendo 2 · p · p100 = 10, sendo eles 2, 3, 5 e 7.
Descartamos inicialmente o n¶umero 1, que n~ao ¶e primo. Em seguida, demarcamos
(crivamos) os m¶ultiplos de 2 maiores que 2. Em seguida, crivamos os m¶ultiplos de 3
maiores que 3. O procedimento ¶e repetido para os primos 5 e 7.
Al¶em de 2, 3, 5 e 7, ser~ao primos positivos menores que 100 todos os n¶umeros
da tabela que n~ao foram crivados, pois se um inteiro positivo n, 2 · n · 100, n~ao for
primo, ele dever¶a ter um fator primo p satisfazendo p · pn · p100.
ÂÁ1 2 3 Á4 5 Á6 7 Á8 Â9 Á10
11 Á12 13 Á14 Â15 Á16 17 Á18 19 Á20
Â21 Á22 23 Á24 |25 Á26 Â27 Á28 29 Á30
31 Á32 Â33 Á34 |35 Á36 37 Á38 Â39 Á40
41 Á42 43 Á44 Â45 Á46 47 Á48 ÂÁ49 Á50
Â51 Á52 53 Á54 |55 Á56 Â57 Á58 59 Á60
61 Á62 Â63 Á64 |65 Á66 67 Á68 Â69 Á70
71 Á72 73 Á74 Â75 Á76 ÂÁ77 Á78 79 Á80
Â81 Á82 83 Á84 |85 Á86 Â87 Á88 89 Á90
ÂÁ91 Á92 Â93 Á94 |95 Á96 97 Á98 Â99 Á100
Observando o crivo de Erat¶ostenes acima, escreva a lista dos primos positivos
abaixo de 100.
Desde muito cedo, matem¶aticos questionaram se o conjunto de primos positivos ¶e
¯nito ou n~ao. Em seus Elementos, Euclides de Alexandria deu a resposta.
N¶umeros primos 41
Teorema 5.3 (Euclides) Existem in¯nitos n¶umeros primos positivos.
Demonstra»c~ao. Demonstraremos que, sendo dado um conjunto ¯nito qualquer de primos
positivos, ¶e poss¶³vel \construir" um primo positivo que est¶a fora desse conjunto. Assim,
o conjunto de primos positivos ¶e in¯nito.
Seja ent~ao fp1; : : : ; png um conjunto de n primos positivos distintos, n ¸ 1.
Considere o inteiro positivo
a = p1 ¢ ¢ ¢ pn + 1
Mostraremos que a possui um fator primo diferente dos primos p1, : : : , pn.
Obviamente, a ¶e um inteiro positivo maior que cada um dos primos p1, : : : , pn.
Se a ¶e primo, ele mesmo ¶e o primo procurado, fora do conjunto fp1; : : : ; png.
Se a n~ao ¶e primo, pelo teorema 5.1, ele possui um fator primo positivo q. Temos
ent~ao q62 fp1; : : : ; png: se q = pi para algum i 2 f1; : : : ; ng, ent~ao q j p1 ¢ ¢ ¢ pn; como
q j a, temos que q j (a ¡ p1 ¢ ¢ ¢ pn), e portanto q j 1, o que contradiz o fato de q ser
primo.
Assim, o inteiro a tem um fator primo diferente dos primos p1, : : : , pn.
Portanto, o conjunto dos n¶umeros primos n~ao pode ser ¯nito.
5.3 Densidade dos n¶umeros primos e conjecturas
famosas
Exporemos agora, a t¶³tulo de divulga»c~ao apenas, alguns resultados que envolvem a
distribui»c~ao dos primos dentre os inteiros.
5.3.1 O teorema dos n¶umeros primos
O teorema dos n¶umeros primos foi conjecturado por Gauss em 1793, mas demonstrado
somente em 1896, pelos matem¶aticos Jacques Hadamard e C.J. de la Vall¶ee Poussin,
em trabalhos independentes.
Na matem¶atica universit¶aria, destacam-se duas constantes num¶ericas muito im-
portantes. S~ao elas o n¶umero pi, ¼ ¼ 3; 14159, que surge no estudo da circunfere^ncia e
suas propriedades m¶etricas, e o n¶umero e ¼ 2; 71828.
O n¶umero e ¶e de¯nido como sendo o limite da seqÄue^ncia (1+ 1
n
)n, n = 1; 2; 3; : : : ,
ou seja, na linguagem de limites de seqÄue^ncias,
e = lim
n!+1
n2N
µ
1 +
1
n
¶n
N¶umeros primos 42
Pode ser demonstrado que o n¶umero e ¶e irracional.
Na tabela 5.1, exibimos valores (aproximados) de
¡
1 + 1
n
¢n
, para n = 1, 10, 100,
1000, 10000, 100000.
Tabela5.1.
n 1=n 1 + 1
n
¡
1 + 1
n
¢n
1 1 2 21 = 2
10 0; 1 1; 1 (1; 1)10 ¼ 2; 59374
100 0; 01 1; 01 (1; 01)100 ¼ 2; 70481
1000 0; 001 1; 001 (1; 001)1000 ¼ 2; 71692
10000 0; 0001 1; 0001 (1; 0001)10000 ¼ 2; 71815
100000 0; 00001 1; 00001 (1; 00001)100000 ¼ 2; 71828
O logaritmo natural de x, lnx, para x real positivo, ¶e de¯nido como sendo
lnx = loge x
Para cada n¶umero real positivo x, de¯ne-se o n¶umero ¼(x), a quantidade de
n¶umeros primos positivos p satisfazendo 2 · p · x.
Observando o crivo de Erat¶ostenes, constru¶³do acima, temos ¼(10) = 4, ¼(20) =
15, e ¼(100) = 25.
Teorema 5.4 (Teorema dos n¶umeros primos) Para valores su¯cientemente grandes
de x, veri¯ca-se que
¼(x)
x= lnx
¶e aproximadamente igual a 1. Mais precisamente, na
linguagem de limites,
lim
x!1
¼(x)³ x
lnx
´ = 1
Exibimos a tabela 5.2, para que o leitor aprecie evide^ncias num¶ericas a respeito do
teorema 5.4, o qual n~ao temos condi»c~oes de demonstrar aqui.
Segundo o teorema 5.4, quando n tende ao in¯nito, temos que
¼(n) ¢ lnn
n
=
¼(n)
n
lnn
tende a 1. Por outro lado, lnn tamb¶em tende ao in¯nito.
Assim, temos que
¼(n)
n
=
µ
¼(n) ¢ lnn
n
¶.
lnn tende a 0 quando n tende ao
in¯nito.
N¶umeros primos 43
Tabela 5.2. Compara»c~oes de ¼(x) com x
lnx
(lnx = loge x)
x ¼(x) x
lnx
¼(x)= x
lnx
1000 168 144; 8 1; 160
10000 1229 1085; 7 1; 132
100000 9592 8685; 9 1; 104
1000000 78498 72382; 4 1; 085
1010 455052512 434294481; 9 1; 048
1012 37607912018 36191206825; 3 1; 039
1014 3204941750802 3102103442166 1; 033
Assim, a porcentagem de primos positivos at¶e n, dada aproximadamente pela
fra»c~ao decimal ¼(n)=n, tende µa zero µa medida em que n cresce. Isto nos revela que ¶e
cada vez mais dif¶³cil encontrar n¶umeros primos µa medida em que avan»camos nos inteiros
positivos.
Para valores inteiros de n muito grandes, este percentual ¶e dado aproximadamente
por
¼(n)
n
=
¼(n)= n
lnn
lnn
¼ 1
lnn
Tabela 5.3. Densidade dos n¶umeros primos dentre os primeiros inteiros positivos. Por-
centagens de primos positivos at¶e n, e compara»c~oes com 1= lnn.
n ¼(n) ¼(n)
n
1= lnn
103 168 0;168 0;1447648273
106 78498 0;078498 0;0723824136
109 50847534 0;050847534 0;04825494243
1010 455052512 0;0455052512 0;04342944819
1014 3204941750802 0;03102103442166 0;0310210344216608
Observando a tabela 5.3, notamos que s~ao primos, 16;8% dos inteiros positivos
at¶e 103, 7;8498% dos inteiros at¶e 106, e aproximadamente 3;1% dos inteiros at¶e 1014.
Para estudantes que conhecem c¶alculo integral, uma aproxima»c~ao ainda melhor
para ¼(n), para n ¸ 2, ¶e dada por ¼(n) = R n
2
1
lnx
dx. Geometricamente,
R
n
2
1
lnx
dx ¶e a
medida da ¶area compreendida entre a curva y = 1= lnx, o eixo x, e as retas verticais
N¶umeros primos 44
x = 2 e x = n. Por exemplo, para n = 1014, temos ¼(n)=(
R
n
2
1
lnx
dx) ¼ 0;9999999,
enquanto que ¼(n)=(n= lnn) ¼ 1;033.
5.3.2 A conjectura de Goldbach
Existem v¶arias conjecturas envolvendo n¶umeros primos, f¶aceis de se enunciar, consti-
tuindo-se em propriedades ainda n~ao demonstradas e tampouco refutadas. Uma delas ¶e
sobre a existe^ncia de in¯nitos primos da forma n2 + 1, com n inteiro positivo. Ou seja,
n~ao se sabe se o conjunto dos primos dessa forma ¶e ¯nito ou in¯nito.
Uma outra ¶e a conjectura sobre a in¯nitude de primos ge^meos (veja problema 8,
p¶agina 45).
Uma outra, bastante famosa, ¶e a seguinte conjectura.
Conjetura de Goldbach Todo inteiro par, maior que dois, pode ser escrito como soma
de dois primos positivos.
Esta propriedade de inteiros pares, formulada por Christian Goldbach em uma carta
escrita a Euler, em 1742, ¶e verdadeira para todos os inteiros pares at¶e inteiros pares muito
grandes, da ordem de milh~oes. Sua validade, veri¯cada apenas experimentalmente em
supercomputadores, prossegue sendo um problema em aberto. Como exemplo,
4 = 2 + 2
6 = 3 + 3
8 = 3 + 5
10 = 3 + 7 = 5 + 5
24 = 5 + 19 = 7 + 17 = 11 + 13
100 = 3 + 97 = 11 + 89 = 17 + 83 = 29 + 71 = 41 + 59 = 47 + 53
Outra famosa conjectura de Goldbach diz que todo inteiro ¶³mpar, maior que 5, ¶e
soma de tre^s primos positivos.
5.4 Exerc¶³cios
1. Determine quais dos seguintes n¶umeros s~ao primos, usando o teorema 5.2.
(a) 101 (b) 103 (c) 107 (d) 211 (e) 213 (f) 221
2. Encontre todos os primos da forma a4 ¡ b4 com a e b inteiros positivos.
3. Mostre que nenhum inteiro da forma n3 + 1 ¶e primo, exceto 2 = 13 + 1 e ¡7 =
(¡2)3 + 1.
4. Mostre que se a e n s~ao inteiros positivos, com n ¸ 2, tais que an ¡ 1 ¶e primo,
ent~ao necessariamente a = 2 e n ¶e primo.
N¶umeros primos 45
Sugest~ao: Se a ¸ 3, sendo n ¸ 2, temos an¡1 = (a¡1)(an¡1+an¡2+¢ ¢ ¢+a+1).
Se a = 2 e n ¸ 2 ¶e composto, temos n = k` com 2 · k < n e 2 · ` < n. Agora,
fazemos uso da identidade
ak` ¡ 1 = (ak)` ¡ 1 = (ak ¡ 1) ¡ak(`¡1) + ak(`¡2) + ¢ ¢ ¢+ ak + 1¢
5. Demonstre que, para cada inteiro positivo n, todo fator primo, do inteiro n! + 1,
¶e maior que n. Conclua ent~ao, por uma nova demonstra»c~ao, que o conjunto dos
inteiros primos positivos ¶e in¯nito.
6. Demonstre que, para cada inteiro positivo n, existe ao menos uma seqÄue^ncia de n
inteiros consecutivos, todos compostos. Ou seja, no conjunto dos n¶umeros inteiros
positivos, h¶a espa»cos de inteiros consecutivos, t~ao grandes quanto quisermos, sem
a presen»ca de um ¶unico n¶umero primo.
Sugest~ao. Fixado um inteiro positivo n, considere os n inteiros consecutivos
(n+ 1)! + 2; (n+ 1)! + 3; : : : ; (n+ 1)! + n; (n+ 1)! + (n+ 1)
7. (a) De acordo com a proposi»c~ao enunciada no problema 6, os sete inteiros con-
secutivos, a partir de com 8! + 2 (= 40322), s~ao compostos. Observando
o crivo de Erat¶ostenes, µa pagina 40, mostre que estes n~ao s~ao os primeiros
sete inteiros positivos consecutivos compostos.
(b) Dentre os inteiros positivos de 1 at¶e 100, quantas listas existem, de cinco
inteiros positivos consecutivos compostos? Resposta. Nove.
(c) Indique como fazer uma lista de um milh~ao de inteiros consecutivos compos-
tos.
8. Existem muitos pares de primos \consecutivos", diferindo entre si por duas uni-
dades, sendo por isto chamados de primos ge^meos. Alguns exemplos de primos
ge^meos s~ao: 3 e 5, 5 e 7, 11 e 13, 17 e 19, 101 e 103. A existe^ncia de um
n¶umero in¯nito de pares de primos ge^meos ¶e uma conjectura matem¶atica famosa
(um problema em aberto).
Mostre que n~ao existem primos trige^meos p, p+ 2 e p+ 4, a n~ao ser 3, 5 e 7.
9. Demonstre que qualquer inteiro n ¸ 12 ¶e a soma de dois inteiros compostos.
Sugest~ao. Sendo n ¸ 12, se n ¶e par, n = 8+(n¡8). Se n ¶e¶³mpar, n = 9+(n¡9).
10. (a) Mostre que sendo p(x) = x2¡x+41, tem-se p(x) primo para cada inteiro x
tal que 0 · x · 40. Mostre, entretanto, que p(41) ¶e um inteiro composto.
(b) (Goldbach) Mostre que se f(x) = anx
n + an¡1x
n¡1 + ¢ ¢ ¢ + a1x + a0, com
n ¸ 1 e an 6= 0, sendo os coe¯cientes an; : : : ; a0 todos inteiros, ent~ao existe
um inteiro a tal que f(a) ¶e composto.
Sugest~ao: Assuma que f(a) ¶e primo para todo inteiro a. Considere o n¶umero
primo p = f(0) = a0. Demonstre que ent~ao f(kp) = p, para todo inteiro k.