Btukfyl

Foram assinalados vários aspectos a serem melhorados nesta página ou se(c)ção: As fontes não cobrem todo o texto. Texto necessita de revisão, devido a inconsistências e/ou dados de confiabilidade duvidosa. Necessita ser reciclada de acordo com o livro de estilo.

Número primo é qualquer número p{displaystyle p} cujo conjunto dos divisores não inversíveis não é vazio, e todos os seus elementos são produtos de p{displaystyle p} por números inteiros inversíveis. De acordo com esta definição, 0,{displaystyle 0,} 1{displaystyle 1} e −1{displaystyle -1} não são números primos.
Um número inteiro primo é aquele que tem somente quatro divisores distintos, p∈Z:{displaystyle pin mathbb {Z} :} ±1{displaystyle pm 1} e ±p.{displaystyle pm p.} Já um número natural primo tem unicamente dois divisores naturais distintos: o número um e ele mesmo.^[1]

Uma das questões pesquisadas sobre os números primos é de como eles se distribuem nos naturais, com que frequência isso ocorre e qual a distância que existe entre eles. Por exemplo, existem vários pares de números primos que se diferem em duas unidades: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43), (59, 61), (71, 73), (101, 103), (107, 109). Pares de números primos com essa propriedade são denominados de primos gêmeos. Não se sabe ainda se existem infinitos pares de números primos gêmeos.^[2]

A propriedade de ser um primo é chamada "primalidade", e a palavra "primo" também é utilizada como substantivo ou adjetivo, se um número inteiro tem módulo maior que um e não é primo, diz-se que é composto (0,{displaystyle 0,} 1{displaystyle 1} e −1{displaystyle -1} também não são compostos). Como "dois" é o único número primo par, o termo "primo ímpar" refere-se a todo primo maior do que dois.

Existem infinitos números primos, como demonstrado por Euclides por volta de 300 a.C..^[3]O conceito de número primo é muito importante na teoria dos números. Um dos resultados da teoria dos números é o Teorema Fundamental da Aritmética, que afirma que qualquer número natural diferente de 1 pode ser escrito de forma única (desconsiderando a ordem) como um produto de números primos (chamados fatores primos): este processo se chama decomposição em fatores primos (fatorização).

Existem 168 números primos positivos menores do que 1000^[4]. São eles: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 (sequência A000040 na OEIS).

Exemplos de decomposições:

• 4=2×2{displaystyle 4=2times 2}


• 6=2×3{displaystyle 6=2times 3}


• 8=2×2×2{displaystyle 8=2times 2times 2}


• 9=3×3{displaystyle 9=3times 3}


• 10=2×5{displaystyle 10=2times 5}


• 472.342.734.872.390.487=3×7×827×978.491×27.795.571{displaystyle 472.342.734.872.390.487=3times 7times 827times 978.491times 27.795.571}

Para todo primo p seja p# o produto de todos os números primos q inferiores ou iguais a p. De acordo com a terminologia empregada por Dubner (1987), p# é chamado o primorial de p. Temos dois problemas em aberto sobre a noção de primorial:^[5]

a) Existe uma infinidade de números primos p tais que p# + 1 seja primo?
b) Existe uma infinidade de números primos p tais que p# + 1 seja composto?

O que se sabe:

• O maior número primo conhecido da forma p# + 1 é 392113# + 1, com 169966 algarismos, foi descoberto por D. Heuer et al. Em 2001.


• A lista completa dos números primos p < 632700 tais que p# + 1 seja primo é a seguinte: P = 2, 3, 5, 7, 11, 31, 379, 1019, 1021, 2657, 3229, 4547, 4787, 11549, 13649, 18523, 23801, 24029, 42209, 145823, 366439 e 392113.


• Caldwell e Gallot publicaram em 2002 a lista para p < 120000. O primo 145823# + 1 foi descoberto em 2000 por A.E. Anderson, D.E. Robinson et al. O primo 366439# + 1 foi descoberto em 2001 por D. Heuer et al.


• 15877# – 1 é o maior primo encontrado da forma p# – 1; tem 6845 algarismos e estava incluído na lista de Caldwell e Gallot de 2002.


• A lista dos números primos p < 650000 tais que p# – 1 é primo é a seguinte: 3, 5, 11, 13, 41, 89, 317, 337, 991, 1873, 2053, 2377, 4093, 4297, 4583, 6569, 13033 e 15877.


• A lista para p < 120000 foi publicada em 2002 por Caldwell e Gallot, posteriormente nenhum outro primo p# – 1 foi descoberto.

Os átomos da aritmética |

Os gregos foram os primeiros a perceber que qualquer número natural, exceto o 1,{displaystyle 1,} pode ser gerado pela multiplicação de números primos, os chamados blocos de construção". A primeira pessoa, até onde se sabe, que produziu tabelas de números primos foi Eratóstenes, no terceiro século a.C. Ele escrevia inicialmente uma lista com todos os números de 1{displaystyle 1} a 100.{displaystyle 100.} Em seguida escolhia o primeiro primo, 2,{displaystyle 2,} e eliminava da lista todos os seus múltiplos. Passava ao número seguinte que não fora eliminado e procedia também eliminando todos os seus múltiplos. Desta forma Eratóstenes produziu tabelas de primos, mais tarde este procedimento passou a se chamar de crivo de Eratóstenes. Observe a ilustração a seguir:

• 
  

  

  
  

  
  

  Crivo de Eratóstenes
  

  
  

  
  

Assim obtemos: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, ...
A partir desse procedimento podemos simplificar a descobertas de primos usando o lema : Se um número natural n > 1 não é divisível por nenhum primo p tal que p2{displaystyle p^{2}} ≤ n , então ele é primo. (demonstrado adiante). Este lema fornece um teste de primalidade, pois, para verificar se um dado número n é primo, basta verificar que não é divisível por nenhum p que não supere n.{displaystyle {sqrt {n}}.}

Durante o século XVII os matemáticos descobriram o que acreditavam ser um método infalível para determinar se um número N{displaystyle N} era primo: calcule 2{displaystyle 2} elevado a potência N{displaystyle N} e divida-o por N,{displaystyle N,} se o resto for 2,{displaystyle 2,} então o número será primo. Em termos da calculadora-relógio de Gauss, esses matemáticos estavam tentando calcular 2N{displaystyle 2^{N}} em um relógio com N{displaystyle N} horas. Em 1819, o teste dos números primos foi eliminado, pois funciona para todos os números até 340,{displaystyle 340,} mas falha para 341=11×31.{displaystyle 341=11times 31.} Exceção descoberta com uma calculadora-relógio de Gauss contendo 341 horas utilizada para simplificar a análise de um número como 2341.{displaystyle 2^{341}.}

Teoremas sobre números primos |

Existem vários teoremas e estudos sobre os números primos, desde resultados tratados na matemática elementar, até conjecturas que não foram provadas. Todos os teoremas desta sessão tem como fonte o livro de HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.

Teorema 1: (Teorema Fundamental da Aritmética)^[6]Todo número natural maior do que 1{displaystyle 1} ou é primo ou se escreve de modo único (exceptuando a ordem dos fatores) como um produto de números primos.

Demonstração:

Tomemos a segunda forma do Princípio de Indução. Seja n=2,{displaystyle n=2,} sabemos que ele é primo. Suponha o resultado válido para todo número natural menor que n{displaystyle n} e vamos provar que vale para n.{displaystyle n.} Observe que que se n{displaystyle n} é primo, nada temos a provar. Sendo n{displaystyle n} composto, existem números naturais x{displaystyle x} e y{displaystyle y} tais que n=xy{displaystyle n=xy} com 1<x<n{displaystyle 1<x<n} e 1<y<n.{displaystyle 1<y<n.} Por hipótese de indução, existem primos a1,a2,a3,...,ak{displaystyle a_{1},a_{2},a_{3},...,a_{k}} e b1,b2,b3...,bw,{displaystyle b_{1},b_{2},b_{3}...,b_{w},} tais que x=a1a2a3...ak{displaystyle x=a_{1}a_{2}a_{3}...a_{k}} e y=b1b2b3...bw,{displaystyle y=b_{1}b_{2}b_{3}...b_{w},} logo n=a1a2a3...akb1b2b3...bw.{displaystyle n=a_{1}a_{2}a_{3}...a_{k}b_{1}b_{2}b_{3}...b_{w}.}

Provaremos agora a unicidade da escrita. Suponha que n=a1a2a3...ak=b1b2b3...bw,{displaystyle n=a_{1}a_{2}a_{3}...a_{k}=b_{1}b_{2}b_{3}...b_{w},} onde os ai{displaystyle a_{i}} e bj{displaystyle b_{j}} são números primos. Como a1|b1b2b3...bw,{displaystyle a_{1}|b_{1}b_{2}b_{3}...b_{w},} temos que a1=bw,{displaystyle a_{1}=b_{w},} para algum w{displaystyle w} (provaremos mais adiante), que por conveniência, podemos supor que seja b1,{displaystyle b_{1},} logo teremos então que a2a3...ak=b2b3...bw{displaystyle a_{2}a_{3}...a_{k}=b_{2}b_{3}...b_{w}} (já que temos a1=b1{displaystyle a_{1}=b_{1}}). De forma análoga, podemos afirmar que como a2|b2b3b4...bw{displaystyle a_{2}|b_{2}b_{3}b_{4}...b_{w}} temos que a2=bw,{displaystyle a_{2}=b_{w},} para algum w,{displaystyle w,} que por conveniência, podemos supor que seja b2,{displaystyle b_{2},} assim teremos a3a4...ak=b3b4...bw.{displaystyle a_{3}a_{4}...a_{k}=b_{3}b_{4}...b_{w}.} Como a3.a4.a5...ak<n,{displaystyle a_{3}._{a}4_{.}a_{5}...a_{k}<n,} a hipótese de indução acarreta em que k=w,{displaystyle k=w,} e os elementos ak{displaystyle a_{k}} e bw{displaystyle b_{w}} são iguais.

Teorema 2:^[7]

Dado um número natural n>1,{displaystyle n>1,} existem primos a1,a2,a3,...,ak,{displaystyle a_{1},a_{2},a_{3},...,a_{k},} e naturais u1,u2,u3...uw,{displaystyle u_{1},u_{2},u_{3}...u_{w},} univocamente determinados, tais que n=(a1)u1.(a2)u2.(a3)u3.....(ak)uk.{displaystyle n=(a_{1})^{u_{1}}.(a_{2})^{u_{2}}.(a_{3})^{u_{3}}.....(a_{k})^{u_{k}}.}

Demonstração:

Decorre do Teorema Fundamental da Aritmética, agrupando-se os primos repetidos e ordenando os primos em ordem crescente.

Teorema 3:^[8]

Sejam a=(p1)k1.{displaystyle a=(p_{1})^{k_{1}}.} (p2)k2.{displaystyle (p_{2})^{k_{2}}.} (p3)k3.{displaystyle (p_{3})^{k_{3}}.} … . (pn)kn,{displaystyle (p_{n})^{k_{n}},} b=(p1)w1.{displaystyle b=(p_{1})^{w_{1}}.} (p2)w2.{displaystyle (p_{2})^{w_{2}}.} (p3)w3.{displaystyle (p_{3})^{w_{3}}.} … . (pn)wn,{displaystyle (p_{n})^{w_{n}},} ri=min{ki,wi}{displaystyle r_{i}=min{k_{i},w_{i}}} e qi=max{ki,wi},{displaystyle q_{i}=max{k_{i},w_{i}},} com i=1,2,3,4...,n,{displaystyle i=1,2,3,4...,n,} tem-se que mdc(a,b)=(p1)r1.{displaystyle mdc(a,b)=(p_{1})^{r_{1}}.} (p2)r2.{displaystyle (p_{2})^{r_{2}}.} (p3)r3.{displaystyle (p_{3})^{r_{3}}.} … . (pn)rn{displaystyle (p_{n})^{r_{n}}} e mmc(a,b)=(p1)q1.{displaystyle mmc(a,b)=(p_{1})^{q_{1}}.} (p2)q2.{displaystyle (p_{2})^{q_{2}}.} (p3)q3.{displaystyle (p_{3})^{q_{3}}.} … . (pn)qn.{displaystyle (p_{n})^{q_{n}}.}

Demonstração:

Temos que (p1)r1.{displaystyle (p_{1})^{r_{1}}.} (p2)r2.{displaystyle (p_{2})^{r_{2}}.} (p3)r3.{displaystyle (p_{3})^{r_{3}}.} … . (pn)rn{displaystyle (p_{n})^{r_{n}}} é um divisor comum de a{displaystyle a} e b.{displaystyle b.} Seja c{displaystyle c} um divisor comum de a{displaystyle a} e b,{displaystyle b,} logo c=(p1)y1.{displaystyle c=(p_{1})^{y_{1}}.} (p2)y2.{displaystyle (p_{2})^{y_{2}}.} (p3)y3.{displaystyle (p_{3})^{y_{3}}.} … . (pn)yn,{displaystyle (p_{n})^{y_{n}},} onde yi{displaystyle y_{i}} ≤ min{ki,wi}{displaystyle min{k_{i},w_{i}}} e, portanto c|(p1)r1.{displaystyle c|(p_{1})^{r_{1}}.} (p2)r2.{displaystyle (p_{2})^{r_{2}}.} (p3)r3.{displaystyle (p_{3})^{r_{3}}.} … .(pn)rn.{displaystyle (p_{n})^{r_{n}}.} Do mesmo modo, prova-se o m.m.c.( Mínimo Múltiplo Comum).

Teorema 4:^[9]

Existem infinitos números primos.

Demonstração:

Suponha que exista apenas um número finito de números primos p1,p2,p3,...,pr.{displaystyle p_{1},p_{2},p_{3},...,p_{r}.} Considere o número natural n=(p1)(p2)(p3)....(pr)+1.{displaystyle n=(p_{1})(p_{2})(p_{3})....(p_{r})+1.} O número n{displaystyle n} possui um fator primo p{displaystyle p} que, portanto, deve ser um dos p1,p2,p3,...,pn,{displaystyle p_{1},p_{2},p_{3},...,p_{n},} Mas isso implica que p{displaystyle p} divide 1,{displaystyle 1,} o que é absurdo.

Teorema 5: (Pequeno Teorema de Fermat)^[10]

Dado um número primo p,{displaystyle p,} tem-se que p{displaystyle p} divide o número ap−a,{displaystyle a^{p}-a,} para todo a∈N{displaystyle ain N}.

Demonstração:

Vamos provar pelo Princípio da Indução Infinita. O resultado vale para a=1,{displaystyle a=1,} já que p|0.{displaystyle p|0.} Supondo valido para um natural a,{displaystyle a,} iremos provar que é válido para o natural a+1.{displaystyle a+1.}

(a+1)p{displaystyle (a+1)^{p}} – (a+1){displaystyle (a+1)} = ap{displaystyle a^{p}} – a{displaystyle a}+ (p1){displaystyle {begin{pmatrix}p\1end{pmatrix}}}ap−1{displaystyle a^{p-1}} + ... + (pp−1)a.{displaystyle {begin{pmatrix}p\p-1end{pmatrix}}a.} O segundo membro da igualdade é divisível por p{displaystyle p} (Lema 2), o resultado se segue.

Teorema 6: (Euclides-Euler)^[11]

Um número natural n{displaystyle n} é um número perfeito par se, e somente se, n{displaystyle n}= 2p−1{displaystyle 2^{p-1}}(2p{displaystyle 2^{p}}– 1{displaystyle 1}), onde 2p{displaystyle 2^{p}}– 1{displaystyle 1} é um primo de Mersenne.

Demonstração:

Suponha que n{displaystyle n}= 2p−1{displaystyle 2^{p-1}}(2p{displaystyle 2^{p}}– 1{displaystyle 1}), onde 2p−1{displaystyle 2^{p}-1} é um primo de Mersenne. Logo p>1{displaystyle p>1} e consequentemente, n{displaystyle n} é par. Como 2p−1{displaystyle 2^{p}-1} é ímpar, temos que mdc(2p−1,2p−1)=1.{displaystyle mdc(2^{p-1},2^{p}-1)=1.} Pela Proposição 5, Corolário 2 e Lema 3, temos: S(n)=S(2p−1(2p−1))=S(2p−1).S(2p−1)=2p−12−12p=2n.{displaystyle S(n)=S(2^{p-1}(2^{p}-1))=S(2^{p-1}).S(2^{p}-1)={frac {2^{p}-1}{2-1}}2^{p}=2n.} Portanto, n é perfeito. (Denota-se por S(n){displaystyle S(n)} a soma de todos os divisores de n{displaystyle n}).

Reciprocamente, suponha que n{displaystyle n} é perfeito e par. Seja 2p−1{displaystyle 2^{p-1}} a maior potência de 2{displaystyle 2} que divide n.{displaystyle n.} Logo, p>1,{displaystyle p>1,} e n=2p−1b,{displaystyle n=2^{p-1}b,} com b{displaystyle b} ímpar. Temos então que mdc(2p−1,b)=1{displaystyle mdc(2^{p-1},b)=1} e, pela Proposição 5 e Corolário 2, segue-se que S(n)=(2p−1).S(b).{displaystyle S(n)=(2^{p-1}).S(b).} Como S(n)=2n,{displaystyle S(n)=2n,} segue-se que (2p−1).S(b)=2pb.{displaystyle (2^{p-1}).S(b)=2^{p}b.}

Temos então, que (2p−1)|b,{displaystyle (2^{p}-1)|b,} pois mdc(2p,2p−1)=1.{displaystyle mdc(2^{p},2^{p-1})=1.} Logo, existe c∈N,{displaystyle cin N,} com c<b{displaystyle c<b} tal que b=c(2p−1).{displaystyle b=c(2^{p}-1).} Substituindo, segue-se: (2p−1).S(b)=2p.(2p−1).c;{displaystyle (2^{p-1}).S(b)=2^{p}.(2^{p-1}).c;} portanto, S(b)=2p.c.{displaystyle S(b)=2^{p}.c.} Como c{displaystyle c} e b{displaystyle b} são dois divisores distintos de b{displaystyle b} tais que c+b=2p.c.{displaystyle c+b=2^{p}.c.} Nesta situação, c=1.{displaystyle c=1.} De fato, suponha por absurdo que c≠1.{displaystyle cneq 1.} Temos então que S(b)≥1+c+b>c+b=2p.c,{displaystyle S(b)geq 1+c+b>c+b=2^{p}.c,} segue-se que 2pc=c+b<S(b)=2pc,{displaystyle 2^{p}c=c+b<S(b)=2^{p}c,} contradição. Logo, concluímos que S(b)=b+1,{displaystyle S(b)=b+1,} assim b{displaystyle b} é primo. Temos então que n=2p−1(2p−1){displaystyle n=2^{p-1}(2^{p}-1)} com 2p−1{displaystyle 2^{p}-1} primo.

Teorema 7: (Legendre)^[12]

Sejam n um número natural e p um número primo, Então Ep(n!)=[np]{displaystyle E_{p}(n!)={begin{bmatrix}{frac {n}{p}}end{bmatrix}}} + [np2]{displaystyle {begin{bmatrix}{frac {n}{p^{2}}}end{bmatrix}}} + [np3]{displaystyle {begin{bmatrix}{frac {n}{p^{3}}}end{bmatrix}}} + ⋯ . (Denotaremos Ep(m){displaystyle E_{p}(m)} pelo expoente de maior potência de p{displaystyle p} que divide m{displaystyle m} e por [np]{displaystyle {begin{bmatrix}{frac {n}{p}}end{bmatrix}}} o quociente da divisão de a por b, na divisão euclidiana)

Demonstração:

A soma apresentada no teorema é finita, pois existe um números natural r{displaystyle r} tal que pi>n{displaystyle p^{i}>n} para todo i≥r,{displaystyle igeq r,} portanto [np]=0,{displaystyle {begin{bmatrix}{frac {n}{p}}end{bmatrix}}=0,} se i≥r.{displaystyle igeq r.} Vamos demonstrar o resultado por indução sobre n.{displaystyle n.} A fórmula vale para n=0.{displaystyle n=0.} Suponha que vale para um natural m{displaystyle m} com m<n.{displaystyle m<n.} Sabemos que os múltiplos de p{displaystyle p} entre 1{displaystyle 1} e n{displaystyle n} são p,{displaystyle p,} 2p, ..., [np]{displaystyle {begin{bmatrix}{frac {n}{p}}end{bmatrix}}}p. Portanto, Ep(n!)=[np]{displaystyle E_{p}(n!)={begin{bmatrix}{frac {n}{p}}end{bmatrix}}} + Ep[np]!.{displaystyle E_{p}{begin{bmatrix}{frac {n}{p}}end{bmatrix}}!.} Pela hipótese de indução temos que Ep([np]!){displaystyle E_{p}{begin{pmatrix}{begin{bmatrix}{frac {n}{p}}end{bmatrix}}!end{pmatrix}}} = [[np]p]{displaystyle {begin{bmatrix}{frac {begin{bmatrix}{frac {n}{p}}end{bmatrix}}{p}}end{bmatrix}}} + [[np]p2]{displaystyle {begin{bmatrix}{frac {begin{bmatrix}{frac {n}{p}}end{bmatrix}}{p^{2}}}end{bmatrix}}} + [[np]p3]{displaystyle {begin{bmatrix}{frac {begin{bmatrix}{frac {n}{p}}end{bmatrix}}{p^{3}}}end{bmatrix}}} + ... . O resultado decorre da Proposição 6.

Teorema 8:^[13]

Sejam p,n∈N{displaystyle p,nin N}* com p{displaystyle p} primo. Suponha que n=nrpr+nr−1pr−1+...+n1p+n0{displaystyle n=n_{r}p^{r}+n_{r-1}p^{r-1}+...+n_{1}p+n_{0}} seja a representação p-ádica de n.{displaystyle n.} Então Ep(n!){displaystyle E_{p}(n!)} = n−(n0+n1+...+nr)p−1.{displaystyle {frac {n-(n_{0}+n_{1}+...+n_{r})}{p-1}}.}

Demonstração:

Sendo 0≤ni≤p,{displaystyle 0leq n_{i}leq p,} temos que [np]=nrpr−1+nr−1pr−2+...+n2p+n1,{displaystyle {begin{bmatrix}{frac {n}{p}}end{bmatrix}}=n_{r}p^{r-1}+n_{r-1}p^{r-2}+...+n_{2}p+n_{1},} [np2]=nrpr−2+nr−1pr−3+...+n2,{displaystyle {begin{bmatrix}{frac {n}{p^{2}}}end{bmatrix}}=n_{r}p^{r-2}+n_{r-1}p^{r-3}+...+n_{2},} ..., [npr]=nr.{displaystyle {begin{bmatrix}{frac {n}{p^{r}}}end{bmatrix}}=n_{r}.} Portanto, Ep(n!){displaystyle E_{p}(n!)} = [np]{displaystyle {begin{bmatrix}{frac {n}{p}}end{bmatrix}}} + [np2]{displaystyle {begin{bmatrix}{frac {n}{p^{2}}}end{bmatrix}}} + [np3]{displaystyle {begin{bmatrix}{frac {n}{p^{3}}}end{bmatrix}}} + ⋯ [npr]{displaystyle {begin{bmatrix}{frac {n}{p^{r}}}end{bmatrix}}} = nrpr−1p−1+nr−1pr−2−1p−1+...+n1{displaystyle n_{r}{frac {p^{r}-1}{p-1}}+n_{r-1}{frac {p^{r-2}-1}{p-1}}+...+n_{1}} = nrpr+nr−1pr−1+...+n1p+n0−(nr+nr−1+...+n1+n0)p−1{displaystyle {frac {n_{r}p^{r}+n_{r-1}p^{r-1}+...+n_{1}p+n_{0}-(n_{r}+n_{r-1}+...+n_{1}+n_{0})}{p-1}}} = n−(n0+n1+...+nr)p−1.{displaystyle {frac {n-(n_{0}+n_{1}+...+n_{r})}{p-1}}.}

Teorema 9:
Teorema de Vantieghems^[14][15]

Um número natural n é primo se, e somente se:

∏k=1n−1(2k−1)≡nmod(2n−1).{displaystyle prod _{k=1}^{n-1}left(2^{k}-1right)equiv nmod left(2^{n}-1right).}

∏k=1n−1(Xk−1)≡nmod(Xn−1)/(X−1).{displaystyle prod _{k=1}^{n-1}left(X^{k}-1right)equiv nmod left(X^{n}-1right)/left(X-1right).}

Exemplos:

1) Para n=7 temos o produto 1*3*7*15*31*63 = 615195. :
615195 = 7 mod 127.
7 é primo.

2) Para n=9 temos o produto 1*3*7*15*31*63*127*255 = 19923090075.
19923090075 = 301 mod 511.
9 é composto.

Lemas sobre números primos |

Todos os lemas desta sessão tem como fonte o livro de HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.

Lema 1:^[16]

Se um número natural n>1{displaystyle n>1} não é divisível por nenhum primo p{displaystyle p} tal que p2≤n,{displaystyle p^{2}leq n,} então ele é primo.

Demonstração:

Suponha, por absurdo, que n{displaystyle n} não seja divisível por nenhum número p{displaystyle p} tal que p2≤n{displaystyle p^{2}leq n} e que não seja primo. Seja q{displaystyle q} o menor número primo que divide n,{displaystyle n,} logo, n=q.k,{displaystyle n=q.k,} com q≤k,{displaystyle qleq k,} Desse modo temos q2≤qk=n,{displaystyle q^{2}leq qk=n,} o que mostra que n{displaystyle n} é divisível pelo número primo q{displaystyle q} tal que q2≤n,{displaystyle q^{2}leq n,} absurdo.

Lema 2: ^[17]

Seja p{displaystyle p} um número primo. Os números (pi),{displaystyle {begin{pmatrix}p\iend{pmatrix}},} onde 0<i<p,{displaystyle 0<i<p,} são todos divisíveis por p.{displaystyle p.}

Demonstração:

O resultado é válido para 1.{displaystyle 1.} Suponha então, 1<i<p.{displaystyle 1<i<p.} Neste caso, i!|p.(p−1).(p−2).....(p−i+1).{displaystyle i!|p.(p-1).(p-2).....(p-i+1).} Como o mdc(i!,p)=1,{displaystyle mdc(i!,p)=1,} concluímos que , i!|(p−1).(p−2).....(p−i+1),{displaystyle i!|(p-1).(p-2).....(p-i+1),} e o resultado se segue, pois (pi)=p.(p−1)(p−2)...(p−1+i)i!.{displaystyle {begin{pmatrix}p\iend{pmatrix}}=p.{frac {(p-1)(p-2)...(p-1+i)}{i!}}.}

Lema 3:^[18]

Seja n∈N{displaystyle nin N}*, Tem-se que s(n)=n+1{displaystyle s(n)=n+1} se, e somente se, n{displaystyle n} é um número primo.

Demonstração:

Se S(n)=n+1,{displaystyle S(n)=n+1,} segue-se que n>1{displaystyle n>1} e que os únicos divisores de n{displaystyle n} são 1{displaystyle 1} e n,{displaystyle n,} logo n{displaystyle n} é primo. Reciprocamente, se n{displaystyle n} é primo, pela Proposição 5, segue-se que S(n)=n2−1n−1=n+1.{displaystyle S(n)={frac {n^{2}-1}{n-1}}=n+1.}

Corolários sobre números primos |

Todos os corolários desta sessão tem como fonte o livro de HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.

Corolário 1:^[19]

Se p{displaystyle p} é um número primo e se a{displaystyle a} é um número natural não divisível por p,{displaystyle p,} então p{displaystyle p} divide ap−1−1{displaystyle a^{p-1}-1}

Demonstração:

Sabendo que p|ap−a{displaystyle p|a^{p}-a} (Pequeno Teorema de Fermat), então p|a(ap−1−1){displaystyle p|a(a^{p-1}-1)} e como mdc(a,p)=1,{displaystyle mdc(a,p)=1,} podemos concluir que p|ap−1−1.{displaystyle p|a^{p-1}-1.}

Corolário 2:^[20]

A função S(n){displaystyle S(n)} é multiplicativa, isto é, se mdc(n,m)=1{displaystyle mdc(n,m)=1} então S(n.m)=S(n).S(m).{displaystyle S(n.m)=S(n).S(m).}

Demonstração:

Segue-se diretamente da demonstração da Proposição 5.

Proposições sobre números primos |

Todos as proposições desta sessão tem como fonte o livro de HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.

Proposição 1:^[21]

Sejam a,b,p∈N{displaystyle a,b,pin N}*, com p{displaystyle p} primo. Se p|ab,{displaystyle p|ab,} então p|a{displaystyle p|a} ou p|b.{displaystyle p|b.}

Demonstração:

Se p|ab{displaystyle p|ab} e p∤a{displaystyle pnmid a} então p|b.{displaystyle p|b.} Mas se p∤a,{displaystyle pnmid a,} temos que mdc(a,b)=1.{displaystyle mdc(a,b)=1.}

Proposição 2:^[22]

Seja n1=a1u1.a2u2.a3u3....akuk.{displaystyle n_{1}=a_{1}^{u_{1}}.a_{2}^{u_{2}}.a_{3}^{u_{3}}....a_{k}^{u_{k}}.} um número natural escrito decomposto em números primos. Se n2|n1{displaystyle n_{2}|n_{1}} então n2=a1v1.a2v2.a3v3....akvk,{displaystyle n_{2}=a_{1}^{v_{1}}.a_{2}^{v_{2}}.a_{3}^{v_{3}}....a_{k}^{v_{k}},} onde 0≤vi≤ui,{displaystyle 0leq v_{i}leq u_{i},} para i{displaystyle i} natural.

Demonstração:

Seja n2{displaystyle n_{2}} um divisor de n1{displaystyle n_{1}} e seja av{displaystyle a^{v}} a potência de um primo a,{displaystyle a,} presente na decomposição de n2{displaystyle n_{2}} em um produto de seus fatores primos. Sabendo que av|n1{displaystyle a^{v}|n_{1}} segue que av{displaystyle a^{v}} divide algum aiv1{displaystyle a_{i}^{v_{1}}} por ser primo com os demais ajv1{displaystyle a_{j}^{v_{1}}} e, consequentemente, p=pi{displaystyle p=p_{i}} e v<ui.{displaystyle v<u_{i}.}

Proposição 3:^[23]

Sejam a{displaystyle a} e n{displaystyle n} números naturais maiores do que 1.{displaystyle 1.} Se an+1{displaystyle a^{n}+1} é primo, então a{displaystyle a} é par e n=2m,{displaystyle n=2^{m},} com m∈N.{displaystyle min N.}

Demonstração:

Suponha que an+1{displaystyle a^{n}+1} seja primo, onde a>1{displaystyle a>1} e n>1.{displaystyle n>1.} Logo a{displaystyle a} tem que ser par, pois caso contrário, an+1{displaystyle a^{n}+1} seria par e maior do que dois, o que contraria o fato de ser primo. Se n{displaystyle n} tivesse um divisor primo p{displaystyle p} diferente de 2,{displaystyle 2,} teríamos n=kp{displaystyle n=kp} com k∈N{displaystyle kin N}*. Logo, ak+1|(ak)p+1=an+1,{displaystyle a^{k}+1|(a^{k})^{p}+1=a^{n}+1,} concretizando o fato desse último número ser primo. Isto implica que n{displaystyle n} é da forma 2m.{displaystyle 2^{m}.}

Proposição 4:^[24]

Sejam a{displaystyle a} e n{displaystyle n} números naturais maiores que 1.{displaystyle 1.} Se an−1{displaystyle a^{n}-1} é primo, então a=2{displaystyle a=2} e n{displaystyle n} é primo.

Demonstração:

Suponha que an−1{displaystyle a^{n}-1} seja primo, com a>1{displaystyle a>1} e n>1.{displaystyle n>1.} Suponha por absurdo, que a>2.{displaystyle a>2.} Logo a−1>1{displaystyle a-1>1} e a−1|an−1{displaystyle a-1|a^{n}-1} e, portanto, an−1{displaystyle a^{n}-1} não é primo, contradição. Consequentemente, a=2.{displaystyle a=2.} Por outro lado, suponha, que n{displaystyle n} não é primo. Temos n=rs{displaystyle n=rs} com r>1{displaystyle r>1} e s>1.{displaystyle s>1.} Como 2r−1{displaystyle 2^{r}-1} divide (2r)s−1=2n−1,{displaystyle (2^{r})^{s}-1=2n-1,} segue que 2n−1{displaystyle 2^{n}-1} não é primo, contradição, logo n{displaystyle n} é primo.

Proposição 5:^[25]

Seja n=a1u1.a2u2.a3u3....akuk{displaystyle n=a_{1}^{u_{1}}.a_{2}^{u_{2}}.a_{3}^{u_{3}}....a_{k}^{u_{k}}} onde a1,a2,a3,...,ak{displaystyle a_{1},a_{2},a_{3},...,a_{k}} são números primos e u1,u2,u3...uk∈N{displaystyle u_{1},u_{2},u_{3}...u_{k}in N}*. Então, S(n)=a1u1+1−1a1−1...akuk+1−1ak−1.{displaystyle S(n)={frac {a_{1}^{u_{1}+1}-1}{a_{1}-1}}...{frac {a_{k}^{u_{k}+1}-1}{a_{k}-1}}.}

Demonstração:

Considere a igualdade (1+a1+...+a1u1).{displaystyle (1+a_{1}+...+a_{1}^{u_{1}}).} .. (1+ak+...+akuk){displaystyle (1+a_{k}+...+a_{k}^{u_{k}})} = ∑a1w1...akwk,{displaystyle sum a_{1}^{w_{1}}...a_{k}^{w_{k}},} onde o somatório do primeiro membro da igualdade é tomado por todas as k-uplas (w1...wk{displaystyle w_{1}...w_{k}}) ao variar cada wi{displaystyle w_{i}} no intervalo 0≤wi≤ui,{displaystyle 0leq wileq u_{i},} para i=0,1,...,k.{displaystyle i=0,1,...,k.} Como tal somatório, pela Proposição 2, representa soma de todos os divisores de n,{displaystyle n,} a fórmula S(n){displaystyle S(n)} resulta aplicando a fórmula da soma de uma progressão geométrica a cada soma do segundo membro da igualdade.

Proposição 6:^[26]

Sejam a∈N{displaystyle ain N} e b,c∈N{displaystyle b,cin N}*, temos que [[ab]c]=[abc].{displaystyle {begin{bmatrix}{frac {begin{bmatrix}{frac {a}{b}}end{bmatrix}}{c}}end{bmatrix}}={begin{bmatrix}{frac {a}{bc}}end{bmatrix}}.} (Denotaremos por [ab]{displaystyle {begin{bmatrix}{frac {a}{b}}end{bmatrix}}} o quociente da divisão de a{displaystyle a} por b,{displaystyle b,} na divisão euclidiana).

Demonstração:

Sejam q1=[ab]{displaystyle q_{1}={begin{bmatrix}{frac {a}{b}}end{bmatrix}}} e q2=[[ab]c].{displaystyle q_{2}={begin{bmatrix}{frac {begin{bmatrix}{frac {a}{b}}end{bmatrix}}{c}}end{bmatrix}}.} Logo, a=bq1+r1,{displaystyle a=bq_{1}+r_{1},} com r1≤b−1{displaystyle r_{1}leq b-1} e [ab]=q1=cq2+r2,{displaystyle {begin{bmatrix}{frac {a}{b}}end{bmatrix}}=q_{1}=cq_{2}+r_{2},} com r2≤c−1.{displaystyle r_{2}leq c-1.} Portanto, a=bq1+r1=b(cq2+r2)+r1=bcq2+br2+r1.{displaystyle a=bq_{1}+r_{1}=b(cq_{2}+r_{2})+r_{1}=bcq_{2}+br_{2}+r_{1}.} Como br2+r1≤b(c−1)+b−1=bc−1,{displaystyle br_{2}+r_{1}leq b(c-1)+b-1=bc-1,} segue-se que q2{displaystyle q_{2}} é o quociente da divisão de a{displaystyle a} por bc,{displaystyle bc,} ou seja, q2=[abc].{displaystyle q_{2}={begin{bmatrix}{frac {a}{bc}}end{bmatrix}}.}

Teoria dos números |

Ver artigo principal: Teoria dos números

Sabe-se que, à medida que avançamos na sequência dos números inteiros, os primos tornam-se cada vez mais raros. Isto levanta duas questões:

O conjunto dos números primos seria finito ou infinito?

SEGUNDO EUCLIDES^[27]

Suponhamos que a sucessão p1=2,p2=3,...,pr{displaystyle p_{1}=2,p_{2}=3,...,p_{r}} dos r{displaystyle r} números primos seja finita. Tomemos k=p1.p2.p3.....pr+1{displaystyle k=p_{1}.p_{2}.p_{3}.....p_{r}+1} e seja p um número primo que divide k.{displaystyle k.} O número p{displaystyle p} não pode ser igual a nenhum dos números p1,p2,...,pr{displaystyle p_{1},p_{2},...,p_{r}} porque então mele dividiria a diferença k−p1.p2.p3.....pr=1,{displaystyle k-p_{1}.p_{2}.p_{3}.....p_{r}=1,} o que é impossível, Assim p{displaystyle p} é um número primo que não pertence à sucessão e, por consequência, p1,p2,...,pr{displaystyle p_{1},p_{2},...,p_{r}} não pode formar o conjunto de todos os números primos.

SEGUNDO KUMMER (uma variante da demonstração de Euclides)^[28]

Suponha que exista um número finito de úmeros primos p1<p2<p3<...<pn;{displaystyle p_{1}<p_{2}<p_{3}<...<p_{n};} seja w=p1.p2.p3.....pn>2.{displaystyle w=p_{1}.p_{2}.p_{3}.....p_{n}>2.} O inteiro w−1,{displaystyle w-1,} sendo o produto de fatores primos, teria então um fator primo pi,{displaystyle p_{i},} que dividiria também w;{displaystyle w;} então, pi{displaystyle p_{i}} dividiria 1=w−(m−1),{displaystyle 1=w-(m-1),} o que é absurdo.

SEGUNDO HERMITE^[29]

Para todo número natural n{displaystyle n} existe um número primo p>n.{displaystyle p>n.} Para isto basta escolher um número p{displaystyle p} qualquer dividindo n!+1{displaystyle n!+1}(teorema fundamental da aritmética). Se tivermos (n!+1)−1{displaystyle (n!+1)-1} então p<n{displaystyle p<n} divide n!,{displaystyle n!,} comop{displaystyle p} divide n!+1,{displaystyle n!+1,} logo p{displaystyle p} dividiria 1,{displaystyle 1,} absurdo.

SEGUNDO GOLDBACH^[30]

Suponha uma sucessão infinita a1,a2,a3,...{displaystyle a_{1},a_{2},a_{3},...} de naturais primos entre si, dois a dois, nenhum deles tem fator primo em comum. Se p1{displaystyle p_{1}} é um fator primo de a1,{displaystyle a_{1},} p2{displaystyle p_{2}} é um fator primo de a2,...,pn{displaystyle a_{2},...,p_{n}} é um fator primo de an,{displaystyle a_{n},} então p1,p2,p3,...,pn{displaystyle p_{1},p_{2},p_{3},...,p_{n}} são todos distintos. Os números de Fermat Fn=22n+1{displaystyle F_{n}=2^{2^{n}}+1} (para n≥0{displaystyle ngeq 0}) são, dois a dois, primos entre si. Por recorrência sobre m{displaystyle m} demonstra-se que Fn−2=F0.F1.F3.....Fm−1,{displaystyle F_{n}-2=F_{0}.F_{1}.F_{3}.....F_{m-1},} então, se n<m,{displaystyle n<m,} Fn{displaystyle F_{n}} divide Fm−2,{displaystyle F_{m}-2,} Se existisse um número primo p que dividisse Fn{displaystyle F_{n}} e Fm,{displaystyle F_{m},} dividiria Fm−2,{displaystyle F_{m}-2,} portanto dividiria 2,{displaystyle 2,} então p=2.{displaystyle p=2.} O que é impossível porque Fm{displaystyle F_{m}} é ímpar.

Dado um número natural n,{displaystyle n,} qual é a proporção de números primos entre os números menores que n?{displaystyle n?}

• A resposta à primeira questão é que o conjunto dos primos é infinito, um resultado conhecido na parte central dos Elementos de Euclides, que lida com as propriedades dos números. Na proposição 20, Euclides explica uma verdade simples porém fundamental sobre os números primos: existe um número infinito deles. Pode-se demonstrar, em notação moderna, da seguinte forma:

Supondo que o número de primos seja finito e sejam p1, p2, p3, ..., pn{displaystyle p_{1}, p_{2}, p_{3}, ..., p_{n}} os primos. Seja P{displaystyle P} o número tal que

P{displaystyle P}

∏i=1npi+1,{displaystyle prod _{i=1}^{n}p_{i}+1,}

∏{displaystyle prod }

Se P{displaystyle P} é um número primo, é necessariamente diferente dos primos p1, p2, p3, ..., pn,{displaystyle p_{1}, p_{2}, p_{3}, ..., p_{n},} pois sua divisão por qualquer um deles tem um resto de 1.

Por outro lado, se P{displaystyle P} é composto, existe um número primo q{displaystyle q} tal que q{displaystyle q} é divisor de P.{displaystyle P.}

Mas obviamente q≠ p1,p2,...,pn.{displaystyle qneq p_{1},;p_{2},;...,;p_{n}.} Logo existe um novo número primo.

Há um novo número primo, seja P{displaystyle P} primo ou composto; este processo pode ser repetido indefinidamente, logo há um número infinito de números primos.

Uma outra prova envolve considerar um número inteiro n>1.{displaystyle n>1.} Temos n+1{displaystyle n+1} que, necessariamente, é coprimo de n{displaystyle n} (números coprimos são os que não têm nenhum fator comum maior do que 1{displaystyle 1}). Provamos isto imaginando que a divisão do menor pelo maior tem resultado 0{displaystyle 0} e resto n{displaystyle n} e do maior pelo menor tem resultado 1{displaystyle 1} e resto 1.{displaystyle 1.} Assim, n(n+1){displaystyle n(n+1)} tem, necessariamente, ao menos dois factores primos.

Tomemos o sucessor deste, que representamos como n(n+1)+1.{displaystyle n(n+1)+1.} Pelo mesmo raciocínio, ele é coprimo a n(n+1).{displaystyle n(n+1).} Ao multiplicar os dois números, temos [n(n+1)]∗[n+(n+1)+1].{displaystyle [n(n+1)]*[n+(n+1)+1].} Como um de seus fatores tem pelo menos dois factores primos diferentes e é coprimo ao outro, o resultado da multiplicação tem pelo menos três factores primos distintos. Este raciocínio também pode ser infinitamente estendido.

• A resposta para a segunda pergunta acima é que essa proporção é aproximadamente nln⁡(n),{displaystyle {frac {n}{ln(n)}},} onde ln{displaystyle ln } é o logaritmo natural.


• Para qualquer número inteiro k,{displaystyle k,} existem k{displaystyle k} números inteiros consecutivos todos compostos.


• O produto de qualquer sequência de k{displaystyle k} números inteiros consecutivos é divisível por k!{displaystyle k!}
  


• Se k{displaystyle k} não é primo, então k{displaystyle k} possui, necessariamente, um fator primo menor do que ou igual a k.{displaystyle {sqrt {k}}.}
  


• Todo inteiro maior que 1 pode ser representado de maneira única como o produto de fatores primos

Grupos e sequências de números primos |

Pierre de Fermat (1601-1665) descobriu que todo número primo da forma 4n+1,{displaystyle 4n+1,} tal como 5,13,17,29,37,41,{displaystyle 5,13,17,29,37,41,} etc., é a soma de dois quadrados. Por exemplo:

5=12+22,{displaystyle 5=1^{2}+2^{2},}

13=22+32,{displaystyle 13=2^{2}+3^{2},}

17=12+42,{displaystyle 17=1^{2}+4^{2},}

29=22+52,{displaystyle 29=2^{2}+5^{2},}

37=12+62,{displaystyle 37=1^{2}+6^{2},}

41=42+52.{displaystyle 41=4^{2}+5^{2}.}

Hoje são conhecidos dois grupos de números primos:

• 
  (4n+1){displaystyle (4n+1)} - que podem sempre ser escritos na forma (x2+y2{displaystyle x^{2}+y^{2}}); e


• 
  (4n−1){displaystyle (4n-1)} - nunca podem ser escritos na forma (x2+y2{displaystyle x^{2}+y^{2}}).

Tratando-se de números primos é perigoso fazer uma generalização apenas com base numa observação, não solidamente comprovada matematicamente. Vejamos o exemplo:

31{displaystyle 31}, 331,3.331,33.331,333.331,3.333.331{displaystyle 331,3.331,33.331,333.331,3.333.331} e 33.333.331{displaystyle 33.333.331} são primos
mas 333.333.331{displaystyle 333.333.331} não é, pois 333.333.331=17x19.607.843.{displaystyle 333.333.331=17x19.607.843.}

Um olhar mais atento na forma como se distribuem os números primos revela que não há uma regularidade nesta distribuição. Por exemplo existem longos buracos entre os números primos, o número 370.261{displaystyle 370.261} é seguido de cento e onze^[31] números compostos e não existem^[32] primos entre os números 20.831.323{displaystyle 20.831.323} e 20.831.533.{displaystyle 20.831.533.}

Algumas fórmulas produzem muitos números primos, por exemplo x2−x+41{displaystyle x^{2}-x+41} fornece primos quando x=0, 1, 2, ..., 40.{displaystyle x=0, 1, 2, ..., 40.} ^[33][34] Veja que para x = 41, a fórmula resulta em 412{displaystyle 41^{2}} que não é primo.

Não existe uma fórmula que forneça primos para todos os valores primos de x,{displaystyle x,} de fato em 1752 Goldbach provou que não há uma expressão polinomial em x{displaystyle x} com coeficientes inteiros que possa fornecer primos para todos os valores de x.{displaystyle x.}

Não se sabe se há uma expressão polinomial ax2+bx+c{displaystyle ax^{2}+bx+c} com a≠0{displaystyle aneq 0} que represente infinitos números primos. Dirichlet usou métodos para provar que se a,{displaystyle a,} 2b{displaystyle 2b} e c{displaystyle c} não têm fator primo em comum, a expressão polinomial a duas variáveis

ax2+2bxy+cy2{displaystyle ax^{2}+2bxy+cy^{2}}

x{displaystyle x}

y{displaystyle y}

Fermat pensou que a fórmula 22n+1{displaystyle 2^{2^{n}}+1} forneceria números primos para n=0, 1, 2, ....{displaystyle n=0, 1, 2, ....} Este números são chamados de números de Fermat e são comumente denotados por Fn.{displaystyle F_{n}.} Os cinco primeiros números são:

F0=3,F1=5,F2=17,F3=257eF4=65.537,{displaystyle F_{0}=3,;F_{1}=5,;F_{2}=17,;F_{3}=257;e;F_{4}=65.537,}

Aproximações para o n-ésimo primo |

Como consequência do teorema do número primo, uma expressão assintótica para o n-ésimo primo pn{displaystyle p_{n}} é:

pn∼nln⁡n.{displaystyle p_{n}sim nln n.}

Uma aproximação melhor é:

pn=nln⁡n+nln⁡ln⁡n−n+nln⁡n(ln⁡ln⁡n−2)−nln⁡ln⁡n2(ln⁡n)2(ln⁡ln⁡n−6)+O(n(ln⁡n)2).{displaystyle {p_{n}=nln n+nln ln n-n+{frac {n}{ln n}}left(ln ln n-2right)-{frac {nln ln n}{2(ln n)^{2}}}left(ln ln n-6right)+Oleft({frac {n}{(ln n)^{2}}}right).}}

O teorema de Rosser mostra que pn{displaystyle p_{n}} é maior que nln⁡n.{displaystyle nln n.} É possível melhorar esta aproximação com os limites ^[36][37]:

nln⁡n+n(ln⁡ln⁡n−1)<pn<nln⁡n+nln⁡ln⁡npara n≥6.{displaystyle nln n+n(ln ln n-1)<p_{n}<nln n+nln ln nquad {mbox{para }}ngeq 6.}

Maior número primo conhecido |

Em Janeiro de 2013, foi divulgado o maior número primo já calculado até então. Tem 17.425.170 dígitos e, se fosse escrito por extenso, ocuparia 3,4 mil páginas impressas com cinco mil caracteres cada. É o número 257885161−1{displaystyle 2^{57885161}-1}. Foi descoberto por Curtis Cooper, da Universidade Central do Missouri em Warrensburg, EUA, como parte do Great Internet Mersenne Prime Search (GIMPS), um projeto internacional de computação compartilhada desenhado para encontrar números primos de Mersene.^[38]

Em janeiro de 2016, um grupo de matemáticos da mesma universidade descobriu um número primo com 22.338.618 dígitos, que recebeu o nome "M74207281".^[39] É o número 274207281−1,{displaystyle 2^{74207281}-1,} que tem 5 milhões de dígitos a mais que o último conhecido.^[40] . O achado foi divulgado pelo programa GIMPS.

Em dezembro de 2017 um engenheiro eletrotécnico da empresa de entregas FedEx descobriu um número primo ainda maior: “M77232917”, como foi batizado, tem mais de 23 milhões de dígitos e apenas pode ser dividido por 1 ou por ele próprio. O homem que o descobriu chama-se Jonathan Pace, tem 51 anos, é norte-americano e também participa do GIMPS.^[41]

Ver também |

Referências

Bibliografia |

• 
  Hua, L. K. (2009). Additive Theory of Prime Numbers. Col: Translations of Mathematical Monographs. 13. [S.l.]: AMS Bookstore. ISBN 978-0-8218-4942-2 
  


• Marcus du Sautoy, Os mistérios dos números: Uma viagem pelos grandes enigmas da matemática (que até hoje ninguém foi capaz de resolver), Jorge Zahar Editor Ltda, 2013 ISBN 8-537-81099-1
  


• Luogeng Hua, Additive theory of prime numbers, American Mathematical Soc. ISBN 0-821-89750-0 (em inglês)


• Mary Jane Sterling, Álgebra I Para Leigos , Alta Books Editora, 2013 ISBN 8-576-08256-X
  


• Edward S. Wall, Teoria dos Números para Professores do Ensino Fundamental, McGraw Hill Brasil, 2014 ISBN 8-580-55353-9
  


• PAULO BOUHID, NÚMEROS CRUZADOS, biblioteca24horas ISBN 8-578-93055-X
  


• LAURA LEMAY, ROGERS CADENHEAD, APRENDA EM 21 DIAS JAVA 2 - TRADUÇÃO DA 4a ED. Elsevier Brasil ISBN 8-535-21685-5
  


• HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.


• RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.


• SANTOS, José Plínio de Oliveira. Introdução à teoria dos Números. 3ª ed. Rio de Janeiro: IMPA, 2012.


• LOVÁSZ, L. PELIKÁN, J. e VESZTERGOMBI, K. Matemática Discreta. 1ª ed. Rio de Janeiro: SBM, 2010.


• http://paginapessoal.utfpr.edu.br/rwprobst/formacao-academica/curriculo/primos.pdf

Ligações externas |

O wikilivro Teoria de números tem uma página intitulada Números primos

• Primos de Mersenne de maneira didática


• 
  Prime curiosat the prime pages


• The prime pages


• MacTutor history of prime numbers


• The "PRIMES is in P" FAQ


• Lista dos maiores números provavelmente primos


• The prime puzzles


• Uma tradução para o inglês da demonstração de Euclides da infinitude dos primos


• 
  Primesfrom WIMS is an online prime generator.


• Prime Spiral pattern


• 
  12 digit primesKnown 12-digit prime factors of Googolplex - 1


• An Introduction to Analytic Number Theory, by Ilan Vardi and Cyril Banderier


• Primos de Mersenne - Os maiores primos já encontrados

• Portal da matemática