Anotaes sobre nmeros primos co u

Rodrigo Carlos Silva de Lima

Universidade Federal Fluminense - UFF-RJ

[Link]@[Link]

Sumrio a
1 Primos 1.1 1.2 1.3 1.4 Innitude dos primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Funao (x) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . c Primos e polinmios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . o Lista dos primeiros primos . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.4.1 1.4.2 3 4 6 9 9

Pequeno Teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . 10 Teorema de Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

Cap tulo 1 Primos

Denio 1 (Divisores triviais). Dado um nmero s, sabemos que 1|s e s|s. Chamaremos ca u esses nmeros de divisores triviais. u Denio 2. Um nmero natural p > 0 dito primo quando possui apenas dois divisores . ca u e Como sempre 1|p e p|p tem-se que o conjunto dos seus divisores {1, p}, isto , os divisores e e dos primos so apenas os triviais. a Denio 3. Um nmero n > 1 ser dito composto se ele no primo. ca u a a e Corolrio 1. O nmero composto n possui 1 e n como divisores, por no ser primo ele a u a deve possuir pelo menos mais um divisor s tal que 1 < s < n. Como s|n existe k N tal que n = k.s e 1 < k < n , se k = s, n ir possuir pelo menos 4 divisores. a Corolrio 2. Todo primo maior que 2 a e mpar, pois os nmeros pares maiores que 2 u possuem mais de 2 divisores, sendo s > 2 um nmero par temos os divisores triviais e 2|s, u logo temos pelo menos trs divisores 1, 2 e s. e Exemplo 1. Sejam a, b e p nmeros primos positivos. Se 1 soluo de ax2 +bx = p2, u e ca quanto vale a2 + b2 . Vale a b = p 2, se p = 2 tem-se a = b logo a2 + b2 = 2a2 para qualquer a primo. Se p = 2 ento p a e mpar, ento p 2 a e mpar, a e b no podem ser ambos a mpares se no o resultado a b seria par, ento um deles deve ser par, e o unico primo par 2, a a a e 3

CAP ITULO 1. PRIMOS

no pode ser 2, pois se no 2 b negativo, ento vale b = 2 de onde segue a 2 = p 2 a a e a implicando a = p, o resultado de a2 + b2 = p2 + 22 = p2 + 4. Propriedade 1. Um nmero natural n > 1 primo ou divis por um nmero primo. u e vel u Demonstrao. 2 primo, ento a base da induo est provada. ca e a ca a Suponha que a propriedade vale para todo k natural tal que 1 k n, vamos provar que vale para n + 1. Se n + 1 primo a propriedade est demonstrada, caso n + 1 seja composto existem e a k, s N tal que s|(n + 1) com n + 1 = k.s e 1 < s < n + 1 da 1 s n ento s primo a e ou divis por um nmero primo (pela hiptese da induo), em qualquer caso existe vel u o ca u N tal que s = u.p onde p primo, da n + 1 = k.s = k.u.p implicando que p|(n + 1). e Propriedade 2. Dado um natural n, n + 1 primo com n, logo n + 1 primo ou tem e e fatores primos distintos de n. Demonstrao. ca Propriedade 3. Tome os s primeiros primos, ento u = ( a maior que cada pk . Demonstrao. Se s primo ento s > pk , se no ,ele possui algum fator primo, que ca e a a no pode ser nenhum dos pk pois s 1modpk , como ele no divis por nenhum dos a a e vel primeiros s primos ento ele deve ser divis por um primo de ordem maior que s que a vel e maior que cada pk .
s k=1

pk ) + 1 possui fator primo

1.1

Innitude dos primos

Propriedade 4. Existem innitos nmeros primos. u Demonstrao. Suponha que existam (pk )n ,n primos, vamos mostrar que existe ca 1 mais um primo distinto dos anteriores . Considere s=(
n

pk ) +1

k=1 =a

CAP ITULO 1. PRIMOS

se esse nmero primo a demonstrao termina, se no, ele composto e ir existir um u e ca a e a nmero primo p tal que p|s, tal p no pode ser nenhum dos pk dados pois se pk |s ento u a a pk |(s a) = 1 que absurdo, assim ele possui um fator primo p = pk . e Uma maneira de denotar tal fato escrever e lim (n) = . Exemplo 2. O produto de primos consecutivos adicionados de 1 no so sempre primos a a 2 + 1 = 3 primo e 2.3 + 1 = 7 primo e 2.3.5 + 1 = 31 primo e [Link] + 1 = 211 primo e [Link].11 + 1 = 2311 primo e [Link].11.13 + 1 = 30031 = 509.59 no primo a e [Link].11.13.17 + 1 = 510511 = 19.97.277 no primo a e Propriedade 5. Existe sempre um primo entre n e n! para n > 2. Demonstrao. Seja a sequncia de termo ca e xn = n! 1 n , temos que x2 = 2 1 2 = 1 , x3 = 3! 1 3 = 6 4 = 2 e xn = n.n! 1 > 0 para n > 1, logo xn crescente para n > 1 e como vale x3 = 2 tem-se que n! 1 n > 0 para e n > 2, isto , n! 1 > n para n > 2. Como vale n! 1 < n!, segue e n < n! 1 < n!. Dado qualquer nmero k [2, n]N , k (n!1) pois n!1 1 mod k. Logo nenhum u primo menor ou igual a n divide n! 1, assim deve haver um primo p tal que n < p < n! e p|(n! 1). Denio 4 (Nmeros vizinhos). Dado um nmero s, os nmeros s + 1 e s 1 so dito ca u u u a nmeros vizinhos ao nmero s. Nesse caso dizemos que s vizinho de s + 1 e s 1. u u e

CAP ITULO 1. PRIMOS

Propriedade 6. Todo nmero primo p > 3 vizinho de um mltiplo de 6. u e u Demonstrao. Dado um primo p > 3, ento 3 p e 2 p, pela diviso euclidiana ca a a de p por 6 temos que p = 6k, 6k + 1, 6k + 2, 6k + 3, 6k + 4 ou 6k + 5, no podendo ser a a primeira (6 divide) a terceira (2 divide), a quarta (3divide) , nem a quinta opao (2 c divide), resta ento p = 6k + 1 ou p = 6k + 5. No primeiro caso p 1 = 6k e no segundo a p + 1 = 6k + 6, ambos mltiplos de 6. u Propriedade 7. Existem innitos primos da forma 6k + 5. Demonstrao.(depois) ca Suponha que exista uma quantidade nita de primos da forma 6k + 5, digamos (pk )n , 1 tome s=6
n k=1

pk + 5

tal nmero no pode ser primo, pois seria da forma 6k + 5 e ter u a amos n + 1 primos da forma 6k + 5, pois s > pk para cada k In . Propriedade 8. Para qualquer inteiro positivo n, existem n inteiros consecutivos todos compostos. Demonstrao. Considere a sequncia de termo ak = (n + 1)! + k de k = 2 at ca e e k = n + 1, temos n + 2 2 = n termos e cada um deles divis por k, 1 e (n + 1)! + k, e vel logo so nmeros compostos. a u

1.2

Funo (x) ca

Denio 5. Denimos a funao (x) da seguinte maneira: Dado um nmero x real e o ca c u conjunto (x) = {p primo |p x} , denimos e (x) = |(x)|. Isto , dado um nmero real x, (x) fornece a quantidade de nmeros primos que satise u u fazem p x.

CAP ITULO 1. PRIMOS

Corolrio 3. a (x) =

k (x)

1.

Exemplo 3. (2) = 1, pois h apenas o 2 como primo. (3) = 2, temos os primos 2 e 3, a (4) = 2. Denio 6 (Enumerao crescente pk ). Denotaremos sempre por pk a enumeraao cresca ca c cente dos nmeros primos. u Propriedade 9.
k (n) (n)

k=

pk .

k=1

Demonstrao. O conjunto (n) possui (n) elementos, ento tomamos a enuca a (n) pk o produto dos e merao pk de seus elementos, de onde segue o resultado. Ento ca a primos p n. Propriedade 10.
(n) k=1

n onde pk o k-simo primo. e e

pk

k=1

Demonstrao. E claro que se n primo vale a relaao, pois n ser um fator do ca e c a produto. Seja
(n)

s=

pk + 1

k=1

nenhum primo p n pode dividir s, pois sempre ir deixar resto 1, ento deve haver a a algum primo u maior que n que divida1 , isto , u > n , u|s ento existe l inteiro tal que e a s = l.u como l 1 multiplicando por u segue s = lu u > n, da
(n)

n< de onde segue

pk + 1

k=1

(n)

n
1

pk .

k=1

E necessrio que s = 1, ento o produto no pode ser vazio, isto n = 1, 0. a a a e

CAP ITULO 1. PRIMOS

A identidade vale tambm para n = 1, pois nesse caso o produto vazio vale 1 e temos e 1 1 e vale para n = 0 pois o produto vazio e 0 < 1. Ento a identidade vale para todo e a n natural. O produto
(n)

pk chamado primorial e denotado por n, mostramos ento que vale e a n n.

k=1

Propriedade 11. A sequncia ((n)) no decrescente. e e a Demonstrao. Considere ca (n) = (n + 1) (n) Se n + 1 primo, temos que (n + 1) = (n) + 1, pois adicionamos um primo ao conjunto e se n + 1 no primo, temos que (n + 1) = (n), logo em todo caso vale (n) 0, logo a e a sequncia no decrescente. e e a Propriedade 12. A sequncia (n) no decrescente. e e a Demonstrao. ca
(n+1)

n =

(n)

pk

pk

k=1

k=1

Vale (n + 1) = (n) ou (n + 1) = (n) + 1, no primeiro caso a diferena zero, no c e segundo caso

(n)+1

n =

(n)

pk

(n)

pk =

(n)

pk

pk + p(n+1) > 0

k=1

k=1

k=1

k=1

ento temos n 0, a sequncia no decrescente. a e e a Corolrio 4. Vale sempre a

(n)

(n)

pk

k=1

pois vale pk 2, tomamos o produto em ambos lados. Propriedade 13. Vale

(n)

n< para n > 2.

pk

k=1

CAP ITULO 1. PRIMOS

Demonstrao. Seja ca
(n)

s=

pk 1

k=1

para n = 2 temos s = 2 1 = 1 que no possui fatores primos e para s = 3 tem-se a 2.3 1 = 6 1 = 5 que possui fator primos, como o produto no decrescente garantimos e a que para n > 2 s ter fatores primos, porm nenhum fator primo p n divide s, pois a e deixa resto 1, ento algum fator primo p > n divide s o que implica s > n. a
(n)

n<

pk 1
(n)

k=1

1+n< logo vale tambm e

pk

k=1

(n)

n<

pk

k=1 (n1)

n<

pk

k=1

Corolrio 5. n no pode ser escrito como produto dos fatores primos menor que ele. a a

1.3

Primos e polinmios o

Propriedade 14. x2 x + 41 retorna primos para x [0, 40]N . Propriedade 15. x2 79x + 1601 retorna primos para x [0, 79]N .

1.4

Lista dos primeiros primos

2 3 3 5 4 7 5 6 7 8 9 10 11 12 13 14 15 16 17 37 41 43 47 53 59 11 13 17 19 23 29 31

n 1 p 2

18 19 20 21 22 23 24 25 61 67 71 73 79 83 89 97

CAP ITULO 1. PRIMOS

10

1.4.1

Pequeno Teorema de Fermat

Teorema 1 (Pequeno Teorema de Fermat). Sejam p um nmero primo, a um inteiro, u ento a ap a mod p . Demonstrao. Vamos demonstrar primeiro para a natural por induao, para a = 0 ca c temos 0p = 0 0 mod p. Considerando agora vlido para a a ap a mod p , vamos demonstrar para a + 1 temos ( ) ( ) p p1 ( ) (p) p 0 p k p p p k (a + 1) = a = a + a + a 1 + ap mod p k 0 k p k=0 k=1 ( ) p onde abrimos o limite inferior e superior do somatrio e usamos que P | o para 1 k k p 1 usando a hiptese temos o (a + 1)p 1 + ap 1 + a mod p logo (a + 1)p 1 + a mod p .

Agora se a um inteiro negativo e p primo e mpar, temos a < 0, a > 0, temos (a)p = ap a mod p que equivalente a e ap a mod p , agora se a inteiro negativo e p = 2 o unico primo par, temos a 0 mod 2 ou e a 1 mod 2, no primeiro caso a2 0 amod p, no segundo a2 1 a mod p em ambos temos a2 a mod 2 logo a demonstraao est completa. c a

CAP ITULO 1. PRIMOS

11

1.4.2

Teorema de Wilson

Propriedade 16 (Teorema de Wilson). p primo sse e (p 1)! 1 mod p.

Demonstrao. Para p = 2 a propriedade vale, suponha ento p > 2, p primo. Tome ca a A = {2 k p 2, k N }, vale
p2 k=1

k1

mod p

pois para cada k A existe k = k A tal que k.k 1 mod p, da

p1 k=1

k p 1 1 mod p

ento a (p 1)! 1 Corolrio 6. Vale que a

n (s+1)p1 s=0 k=sp+1

mod p.

k (1)n+1

mod p

onde p primo . e
n p1 n p1 n s=0

(k + sp)

(k)

(1) (1)n+1

mod p

s=0 k=1

s=0 k=1

Exemplo 4. Calcular o resto da diviso de 63! por 71. Como 71 primo vale o teorema a e de Wilson, ento a 70! 1 mod 71 vamos fazer as contas em Z71 . [Link].[Link]! = 1 70 = 70 71 = 1 logo 69 = 2, 68 = 3, 67 = 4, 66 = 5, 65 = 6, 64 = 7 (1)(2)(3)(4)(5)(6)(7)63! = (1)

CAP ITULO 1. PRIMOS

12

anulando (1) e simplicando (2)(3)(4)(5)(6)(7)63! = 1 = [Link].63! = 1 Como 70 = 1, multiplicamos por 70 em ambos lados e simplicamos os outros nmeros u 32 .23 .63! = 70 sabemos que 72 = 1 = 2.36, ento 36 inverso de 2, multiplicamos ento por 363 em a e a ambos lados, cando 32 .63! = 70.363 362 = 1296 = 1278 +18 = 18, da 363 = 18.36 = 648 = 639 +9 = 9 ento a
=71.18 71.9

32 (63)! = 70.32 como 9 possui inverso em Z71 implica (63)! = 70. Teorema 2 (Teorema de Wolstenholme). Seja p > 3 um primo p2 divide o numerador p1 1 da fraao irredut de c vel = Hp1 . k k=1 Demonstrao. Dividiremos a demonstraao em passos. ca c 1. Primeiro mostramos que p divide o numerador.
p1 1 k=1

11 1 1 p = + = k 2 k=1 k p k 2 k=1 (k)(p k)

p1 p1

onde usamos o truque de Gauss2 tal soma pode ser escrita como
p1

pA onde (p 1)!

2 (p 1)! A= , logo p divide o numerador. Agora iremos provar que p2 divide o k(p k) k=1 numerador, mostrando que p|A.

1 f (k) = f (k) + f (p k), que consiste em somar de trs para frente e de frente para trs os a a 2 k=1 k=1 mesmos termos e dividir a soma por dois.
p1 2

p1

CAP ITULO 1. PRIMOS

13

2. Para qualquer k {1, . . . , p 1} vale que

(p 1)! (k 2 )1 mod p pois k(p k) mod p

(p 1)! = x Z x(p k)k = (p 1)! 1 k(p k) pelo teorema de Wilson como p 0 mod p temos xk 2 1 mod p xk 2 1 como quer amos demonstrar. 3. Do item acima temos como corolrio que a
2 2 (p 1)! A= (k 2 )1 k(p k) k=1 k=1 p1 p1

mod p x (k 2 )1

mod p

mod p

4. Vale que

p1 k=1

k 2 0 mod p, pois pela frmula geral tem-se o

p1 k=1

k2 =

(p 1)(p)(2(p 1) + 11) 6

onde a ultima expresso divis por p, pois p > 3. a e vel 5. Como existe bijeo entre {1, . . . , p 1} e {1, . . . , (p 1)1 } ento ca a
p1 k=1 p1 (k 1 )2 0 mod p k 2 k=1

6. Finalmente, usando os item anteriores vamos mostrar que p|A, mostrando que 2A 0 mod p.
2 2 1 2 2A = (k ) + (k 1 )2 = p1 p1

k=1
2 p1

k=1
2 p1

(k ) +

1 2

((k)1 )2 =

k=1

k=1

alterando a ordem da soma no segundo somatrio ( somando de trs para frente ) o a =

2 p1

(k 1 )2 +

p1

((k 1

k=1

k=1

p 1 1 2 ) ) = 2

CAP ITULO 1. PRIMOS

14

= usando p 0 mod p

p1

(k ) +

1 2

p1 k=1+ p1 2

((k p)1 )2 =

k=1

2 = (k 1 )2 +

p1

p1 k=1+ p1 2

((k)1 )2 =

p1 k=1

((k)1 )2 0

mod p

k=1

portanto 2A 0 mod p como p no divide 2, ento p|A como quer a a amos demonstrar. Temos ento a
p1 1 k=1

p2 B . (p 1)!