O que é um numero primo

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 p 2 {\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 2 N {\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=11\times 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 2 341 . {\displaystyle 2^{341}.}  

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)[5] 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 = x y {\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 a 1 , a 2 , a 3 , . . . , a k {\displaystyle a_{1},a_{2},a_{3},...,a_{k}}   e b 1 , b 2 , b 3 . . . , b w , {\displaystyle b_{1},b_{2},b_{3}...,b_{w},}   tais que x = a 1 a 2 a 3 . . . a k {\displaystyle x=a_{1}a_{2}a_{3}...a_{k}}   e y = b 1 b 2 b 3 . . . b w , {\displaystyle y=b_{1}b_{2}b_{3}...b_{w},}   logo n = a 1 a 2 a 3 . . . a k b 1 b 2 b 3 . . . b w . {\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 = a 1 a 2 a 3 . . . a k = b 1 b 2 b 3 . . . b w , {\displaystyle n=a_{1}a_{2}a_{3}...a_{k}=b_{1}b_{2}b_{3}...b_{w},}   onde os a i {\displaystyle a_{i}}   e b j {\displaystyle b_{j}}   são números primos. Como a 1 | b 1 b 2 b 3 . . . b w , {\displaystyle a_{1}|b_{1}b_{2}b_{3}...b_{w},}   temos que a 1 = b w , {\displaystyle a_{1}=b_{w},}   para algum w {\displaystyle w}   (provaremos mais adiante), que por conveniência, podemos supor que seja b 1 , {\displaystyle b_{1},}   logo teremos então que a 2 a 3 . . . a k = b 2 b 3 . . . b w {\displaystyle a_{2}a_{3}...a_{k}=b_{2}b_{3}...b_{w}}   (já que temos a 1 = b 1 {\displaystyle a_{1}=b_{1}}  ). De forma análoga, podemos afirmar que como a 2 | b 2 b 3 b 4 . . . b w {\displaystyle a_{2}|b_{2}b_{3}b_{4}...b_{w}}   temos que a 2 = b w , {\displaystyle a_{2}=b_{w},}   para algum w , {\displaystyle w,}   que por conveniência, podemos supor que seja b 2 , {\displaystyle b_{2},}   assim teremos a 3 a 4 . . . a k = b 3 b 4 . . . b w . {\displaystyle a_{3}a_{4}...a_{k}=b_{3}b_{4}...b_{w}.}   Como a 3 . a 4 . a 5 . . . a k < 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 a k {\displaystyle a_{k}}   e b w {\displaystyle b_{w}}   são iguais.

Teorema 2:[6]

Dado um número natural n > 1 , {\displaystyle n>1,}   existem primos a 1 , a 2 , a 3 , . . . , a k , {\displaystyle a_{1},a_{2},a_{3},...,a_{k},}   e naturais u 1 , u 2 , u 3 . . . u w , {\displaystyle u_{1},u_{2},u_{3}...u_{w},}   univocamente determinados, tais que n = ( a 1 ) u 1 . ( a 2 ) u 2 . ( a 3 ) u 3 . . . . . ( a k ) u k . {\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:[7]

Sejam a = ( p 1 ) k 1 . {\displaystyle a=(p_{1})^{k_{1}}.}   ( p 2 ) k 2 . {\displaystyle (p_{2})^{k_{2}}.}   ( p 3 ) k 3 . {\displaystyle (p_{3})^{k_{3}}.}   … . ( p n ) k n , {\displaystyle (p_{n})^{k_{n}},}   b = ( p 1 ) w 1 . {\displaystyle b=(p_{1})^{w_{1}}.}   ( p 2 ) w 2 . {\displaystyle (p_{2})^{w_{2}}.}   ( p 3 ) w 3 . {\displaystyle (p_{3})^{w_{3}}.}   … . ( p n ) w n , {\displaystyle (p_{n})^{w_{n}},}   r i = m i n { k i , w i } {\displaystyle r_{i}=min\{k_{i},w_{i}\}}   e q i = m a x { k i , w i } , {\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 m d c ( a , b ) = ( p 1 ) r 1 . {\displaystyle mdc(a,b)=(p_{1})^{r_{1}}.}   ( p 2 ) r 2 . {\displaystyle (p_{2})^{r_{2}}.}   ( p 3 ) r 3 . {\displaystyle (p_{3})^{r_{3}}.}   … . ( p n ) r n {\displaystyle (p_{n})^{r_{n}}}   e m m c ( a , b ) = ( p 1 ) q 1 . {\displaystyle mmc(a,b)=(p_{1})^{q_{1}}.}   ( p 2 ) q 2 . {\displaystyle (p_{2})^{q_{2}}.}   ( p 3 ) q 3 . {\displaystyle (p_{3})^{q_{3}}.}   … . ( p n ) q n . {\displaystyle (p_{n})^{q_{n}}.}  

Demonstração:

Temos que ( p 1 ) r 1 . {\displaystyle (p_{1})^{r_{1}}.}   ( p 2 ) r 2 . {\displaystyle (p_{2})^{r_{2}}.}   ( p 3 ) r 3 . {\displaystyle (p_{3})^{r_{3}}.}   … . ( p n ) r n {\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 = ( p 1 ) y 1 . {\displaystyle c=(p_{1})^{y_{1}}.}   ( p 2 ) y 2 . {\displaystyle (p_{2})^{y_{2}}.}   ( p 3 ) y 3 . {\displaystyle (p_{3})^{y_{3}}.}   … . ( p n ) y n , {\displaystyle (p_{n})^{y_{n}},}   onde y i {\displaystyle y_{i}}   ≤ m i n { k i , w i } {\displaystyle min\{k_{i},w_{i}\}}   e, portanto c | ( p 1 ) r 1 . {\displaystyle c|(p_{1})^{r_{1}}.}   ( p 2 ) r 2 . {\displaystyle (p_{2})^{r_{2}}.}   ( p 3 ) r 3 . {\displaystyle (p_{3})^{r_{3}}.}   … . ( p n ) r n . {\displaystyle (p_{n})^{r_{n}}.}   Do mesmo modo, prova-se o m.m.c.( Mínimo Múltiplo Comum).

Teorema 4:[8]

Existem infinitos números primos.

Demonstração:

Suponha que exista apenas um número finito de números primos p 1 , p 2 , p 3 , . . . , p r . {\displaystyle p_{1},p_{2},p_{3},...,p_{r}.}   Considere o número natural n = ( p 1 ) ( p 2 ) ( p 3 ) . . . . ( p r ) + 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 p 1 , p 2 , p 3 , . . . , p n , {\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)[9]

Dado um número primo p , {\displaystyle p,}   tem-se que p {\displaystyle p}   divide o número a p − a , {\displaystyle a^{p}-a,}   para todo a ∈ N {\displaystyle a\in 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)}   = a p {\displaystyle a^{p}}   – a {\displaystyle a}  + ( p 1 ) {\displaystyle {\begin{pmatrix}p\\1\end{pmatrix}}}   a p − 1 {\displaystyle a^{p-1}}   + ... + ( p p − 1 ) a . {\displaystyle {\begin{pmatrix}p\\p-1\end{pmatrix}}a.}   O segundo membro da igualdade é divisível por p {\displaystyle p}   (Lema 2), o resultado se segue.

Teorema 6: (Euclides-Euler)[10]

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

Demonstração:

Suponha que n {\displaystyle n}  = 2 p − 1 {\displaystyle 2^{p-1}}  ( 2 p {\displaystyle 2^{p}}  – 1 {\displaystyle 1}  ), onde 2 p − 1 {\displaystyle 2^{p}-1}   é um primo de Mersenne. Logo p > 1 {\displaystyle p>1}   e consequentemente, n {\displaystyle n}   é par. Como 2 p − 1 {\displaystyle 2^{p}-1}   é ímpar, temos que m d c ( 2 p − 1 , 2 p − 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 ( 2 p − 1 ( 2 p − 1 ) ) = S ( 2 p − 1 ) . S ( 2 p − 1 ) = 2 p − 1 2 − 1 2 p = 2 n . {\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 2 p − 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 = 2 p − 1 b , {\displaystyle n=2^{p-1}b,}   com b {\displaystyle b}   ímpar. Temos então que m d c ( 2 p − 1 , b ) = 1 {\displaystyle mdc(2^{p-1},b)=1}   e, pela Proposição 5 e Corolário 2, segue-se que S ( n ) = ( 2 p − 1 ) . S ( b ) . {\displaystyle S(n)=(2^{p-1}).S(b).}   Como S ( n ) = 2 n , {\displaystyle S(n)=2n,}   segue-se que ( 2 p − 1 ) . S ( b ) = 2 p b . {\displaystyle (2^{p-1}).S(b)=2^{p}b.}  

Temos então, que ( 2 p − 1 ) | b , {\displaystyle (2^{p}-1)|b,}   pois m d c ( 2 p , 2 p − 1 ) = 1. {\displaystyle mdc(2^{p},2^{p-1})=1.}   Logo, existe c ∈ N , {\displaystyle c\in N,}   com c < b {\displaystyle c<b}   tal que b = c ( 2 p − 1 ) . {\displaystyle b=c(2^{p}-1).}   Substituindo, segue-se: ( 2 p − 1 ) . S ( b ) = 2 p . ( 2 p − 1 ) . c ; {\displaystyle (2^{p-1}).S(b)=2^{p}.(2^{p-1}).c;}   portanto, S ( b ) = 2 p . 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 = 2 p . c . {\displaystyle c+b=2^{p}.c.}   Nesta situação, c = 1. {\displaystyle c=1.}   De fato, suponha por absurdo que c ≠ 1. {\displaystyle c\neq 1.}   Temos então que S ( b ) ≥ 1 + c + b > c + b = 2 p . c , {\displaystyle S(b)\geq 1+c+b>c+b=2^{p}.c,}   segue-se que 2 p c = c + b < S ( b ) = 2 p c , {\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 = 2 p − 1 ( 2 p − 1 ) {\displaystyle n=2^{p-1}(2^{p}-1)}   com 2 p − 1 {\displaystyle 2^{p}-1}   primo.

Teorema 7: (Legendre)[11]

Sejam n um número natural e p um número primo, Então E p ( n ! ) = [ n p ] {\displaystyle E_{p}(n!)={\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}}   + [ n p 2 ] {\displaystyle {\begin{bmatrix}{\frac {n}{p^{2}}}\end{bmatrix}}}   + [ n p 3 ] {\displaystyle {\begin{bmatrix}{\frac {n}{p^{3}}}\end{bmatrix}}}   + ⋯ . (Denotaremos E p ( m ) {\displaystyle E_{p}(m)}   pelo expoente de maior potência de p {\displaystyle p}   que divide m {\displaystyle m}   e por [ n p ] {\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 p i > n {\displaystyle p^{i}>n}   para todo i ≥ r , {\displaystyle i\geq r,}   portanto [ n p ] = 0 , {\displaystyle {\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}=0,}   se i ≥ r . {\displaystyle i\geq 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, ..., [ n p ] {\displaystyle {\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}}  p. Portanto, E p ( n ! ) = [ n p ] {\displaystyle E_{p}(n!)={\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}}   + E p [ n p ] ! . {\displaystyle E_{p}{\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}!.}   Pela hipótese de indução temos que E p ( [ n p ] ! ) {\displaystyle E_{p}{\begin{pmatrix}{\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}!\end{pmatrix}}}   = [ [ n p ] p ] {\displaystyle {\begin{bmatrix}{\frac {\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}{p}}\end{bmatrix}}}   + [ [ n p ] p 2 ] {\displaystyle {\begin{bmatrix}{\frac {\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}{p^{2}}}\end{bmatrix}}}   + [ [ n p ] p 3 ] {\displaystyle {\begin{bmatrix}{\frac {\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}{p^{3}}}\end{bmatrix}}}   + ... . O resultado decorre da Proposição 6.

Teorema 8:[12]

Sejam p , n ∈ N {\displaystyle p,n\in N}  * com p {\displaystyle p}   primo. Suponha que n = n r p r + n r − 1 p r − 1 + . . . + n 1 p + n 0 {\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 E p ( n ! ) {\displaystyle E_{p}(n!)}   = n − ( n 0 + n 1 + . . . + n r ) p − 1 . {\displaystyle {\frac {n-(n_{0}+n_{1}+...+n_{r})}{p-1}}.}  

Demonstração:

Sendo 0 ≤ n i ≤ p , {\displaystyle 0\leq n_{i}\leq p,}   temos que [ n p ] = n r p r − 1 + n r − 1 p r − 2 + . . . + n 2 p + n 1 , {\displaystyle {\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}=n_{r}p^{r-1}+n_{r-1}p^{r-2}+...+n_{2}p+n_{1},}   [ n p 2 ] = n r p r − 2 + n r − 1 p r − 3 + . . . + n 2 , {\displaystyle {\begin{bmatrix}{\frac {n}{p^{2}}}\end{bmatrix}}=n_{r}p^{r-2}+n_{r-1}p^{r-3}+...+n_{2},}   ..., [ n p r ] = n r . {\displaystyle {\begin{bmatrix}{\frac {n}{p^{r}}}\end{bmatrix}}=n_{r}.}   Portanto, E p ( n ! ) {\displaystyle E_{p}(n!)}   = [ n p ] {\displaystyle {\begin{bmatrix}{\frac {n}{p}}\end{bmatrix}}}   + [ n p 2 ] {\displaystyle {\begin{bmatrix}{\frac {n}{p^{2}}}\end{bmatrix}}}   + [ n p 3 ] {\displaystyle {\begin{bmatrix}{\frac {n}{p^{3}}}\end{bmatrix}}}   + ⋯ [ n p r ] {\displaystyle {\begin{bmatrix}{\frac {n}{p^{r}}}\end{bmatrix}}}   = n r p r − 1 p − 1 + n r − 1 p r − 2 − 1 p − 1 + . . . + n 1 {\displaystyle n_{r}{\frac {p^{r}-1}{p-1}}+n_{r-1}{\frac {p^{r-2}-1}{p-1}}+...+n_{1}}   = 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 {\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 − ( n 0 + n 1 + . . . + n r ) p − 1 . {\displaystyle {\frac {n-(n_{0}+n_{1}+...+n_{r})}{p-1}}.}  

Teorema 9: Teorema de Vantieghems[13][14]

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

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

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.

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:[15]

Se um número natural n > 1 {\displaystyle n>1}   não é divisível por nenhum primo p {\displaystyle p}   tal que p 2 ≤ 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 p 2 ≤ 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 q\leq k,}   Desse modo temos q 2 ≤ q k = 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 q 2 ≤ n , {\displaystyle q^{2}\leq n,}   absurdo.

Lema 2: [16]

Seja p {\displaystyle p}   um número primo. Os números ( p i ) , {\displaystyle {\begin{pmatrix}p\\i\end{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 m d c ( 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 ( p i ) = p . ( p − 1 ) ( p − 2 ) . . . ( p − 1 + i ) i ! . {\displaystyle {\begin{pmatrix}p\\i\end{pmatrix}}=p.{\frac {(p-1)(p-2)...(p-1+i)}{i!}}.}  

Lema 3:[17]

Seja n ∈ N {\displaystyle n\in 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 ) = n 2 − 1 n − 1 = n + 1. {\displaystyle S(n)={\frac {n^{2}-1}{n-1}}=n+1.}  

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:[18]

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 a p − 1 − 1 {\displaystyle a^{p-1}-1}  

Demonstração:

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

Corolário 2:[19]

A função S ( n ) {\displaystyle S(n)}   é multiplicativa, isto é, se m d c ( 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.

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:[20]

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

Demonstração:

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

Proposição 2:[21]

Seja n 1 = a 1 u 1 . a 2 u 2 . a 3 u 3 . . . . a k u k . {\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 n 2 | n 1 {\displaystyle n_{2}|n_{1}}   então n 2 = a 1 v 1 . a 2 v 2 . a 3 v 3 . . . . a k v k , {\displaystyle n_{2}=a_{1}^{v_{1}}.a_{2}^{v_{2}}.a_{3}^{v_{3}}....a_{k}^{v_{k}},}   onde 0 ≤ v i ≤ u i , {\displaystyle 0\leq v_{i}\leq u_{i},}   para i {\displaystyle i}   natural.

Demonstração:

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

Proposição 3:[22]

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

Demonstração:

Suponha que a n + 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, a n + 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 = k p {\displaystyle n=kp}   com k ∈ N {\displaystyle k\in N}  *. Logo, a k + 1 | ( a k ) p + 1 = a n + 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 2 m . {\displaystyle 2^{m}.}  

Proposição 4:[23]

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

Demonstração:

Suponha que a n − 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 | a n − 1 {\displaystyle a-1|a^{n}-1}   e, portanto, a n − 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 = r s {\displaystyle n=rs}   com r > 1 {\displaystyle r>1}   e s > 1. {\displaystyle s>1.}   Como 2 r − 1 {\displaystyle 2^{r}-1}   divide ( 2 r ) s − 1 = 2 n − 1 , {\displaystyle (2^{r})^{s}-1=2n-1,}   segue que 2 n − 1 {\displaystyle 2^{n}-1}   não é primo, contradição, logo n {\displaystyle n}   é primo.

Proposição 5:[24]

Seja n = a 1 u 1 . a 2 u 2 . a 3 u 3 . . . . a k u k {\displaystyle n=a_{1}^{u_{1}}.a_{2}^{u_{2}}.a_{3}^{u_{3}}....a_{k}^{u_{k}}}   onde a 1 , a 2 , a 3 , . . . , a k {\displaystyle a_{1},a_{2},a_{3},...,a_{k}}   são números primos e u 1 , u 2 , u 3 . . . u k ∈ N {\displaystyle u_{1},u_{2},u_{3}...u_{k}\in N}  *. Então, S ( n ) = a 1 u 1 + 1 − 1 a 1 − 1 . . . a k u k + 1 − 1 a k − 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 + a 1 + . . . + a 1 u 1 ) . {\displaystyle (1+a_{1}+...+a_{1}^{u_{1}}).}   .. ( 1 + a k + . . . + a k u k ) {\displaystyle (1+a_{k}+...+a_{k}^{u_{k}})}   = ∑ a 1 w 1 . . . a k w k , {\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 ( w 1 . . . w k {\displaystyle w_{1}...w_{k}}  ) ao variar cada w i {\displaystyle w_{i}}   no intervalo 0 ≤ w i ≤ u i , {\displaystyle 0\leq wi\leq 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:[25]

Sejam a ∈ N {\displaystyle a\in N}   e b , c ∈ N {\displaystyle b,c\in N}  *, temos que [ [ a b ] c ] = [ a b c ] . {\displaystyle {\begin{bmatrix}{\frac {\begin{bmatrix}{\frac {a}{b}}\end{bmatrix}}{c}}\end{bmatrix}}={\begin{bmatrix}{\frac {a}{bc}}\end{bmatrix}}.}   (Denotaremos por [ a b ] {\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 q 1 = [ a b ] {\displaystyle q_{1}={\begin{bmatrix}{\frac {a}{b}}\end{bmatrix}}}   e q 2 = [ [ a b ] c ] . {\displaystyle q_{2}={\begin{bmatrix}{\frac {\begin{bmatrix}{\frac {a}{b}}\end{bmatrix}}{c}}\end{bmatrix}}.}   Logo, a = b q 1 + r 1 , {\displaystyle a=bq_{1}+r_{1},}   com r 1 ≤ b − 1 {\displaystyle r_{1}\leq b-1}   e [ a b ] = q 1 = c q 2 + r 2 , {\displaystyle {\begin{bmatrix}{\frac {a}{b}}\end{bmatrix}}=q_{1}=cq_{2}+r_{2},}   com r 2 ≤ c − 1. {\displaystyle r_{2}\leq c-1.}   Portanto, a = b q 1 + r 1 = b ( c q 2 + r 2 ) + r 1 = b c q 2 + b r 2 + r 1 . {\displaystyle a=bq_{1}+r_{1}=b(cq_{2}+r_{2})+r_{1}=bcq_{2}+br_{2}+r_{1}.}   Como b r 2 + r 1 ≤ b ( c − 1 ) + b − 1 = b c − 1 , {\displaystyle br_{2}+r_{1}\leq b(c-1)+b-1=bc-1,}   segue-se que q 2 {\displaystyle q_{2}}   é o quociente da divisão de a {\displaystyle a}   por b c , {\displaystyle bc,}   ou seja, q 2 = [ a b c ] . {\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[26]

Suponhamos que a sucessão p 1 = 2 , p 2 = 3 , . . . , p r {\displaystyle p_{1}=2,p_{2}=3,...,p_{r}}   dos r {\displaystyle r}   números primos seja finita. Tomemos k = p 1 . p 2 . p 3 . . . . . p r + 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 p 1 , p 2 , . . . , p r {\displaystyle p_{1},p_{2},...,p_{r}}   porque então mele dividiria a diferença k − p 1 . p 2 . p 3 . . . . . p r = 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, p 1 , p 2 , . . . , p r {\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)[27]

Suponha que exista um número finito de úmeros primos p 1 < p 2 < p 3 < . . . < p n ; {\displaystyle p_{1}<p_{2}<p_{3}<...<p_{n};}   seja w = p 1 . p 2 . p 3 . . . . . p n > 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 p i , {\displaystyle p_{i},}   que dividiria também w ; {\displaystyle w;}   então, p i {\displaystyle p_{i}}   dividiria 1 = w − ( m − 1 ) , {\displaystyle 1=w-(m-1),}   o que é absurdo.

SEGUNDO HERMITE[28]

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!,}   como p {\displaystyle p}   divide n ! + 1 , {\displaystyle n!+1,}   logo p {\displaystyle p}   dividiria 1 , {\displaystyle 1,}   absurdo.

SEGUNDO GOLDBACH[29]

Suponha uma sucessão infinita a 1 , a 2 , a 3 , . . . {\displaystyle a_{1},a_{2},a_{3},...}   de naturais primos entre si, dois a dois, nenhum deles tem fator primo em comum. Se p 1 {\displaystyle p_{1}}   é um fator primo de a 1 , {\displaystyle a_{1},}   p 2 {\displaystyle p_{2}}   é um fator primo de a 2 , . . . , p n {\displaystyle a_{2},...,p_{n}}   é um fator primo de a n , {\displaystyle a_{n},}   então p 1 , p 2 , p 3 , . . . , p n {\displaystyle p_{1},p_{2},p_{3},...,p_{n}}   são todos distintos. Os números de Fermat F n = 2 2 n + 1 {\displaystyle F_{n}=2^{2^{n}}+1}   (para n ≥ 0 {\displaystyle n\geq 0}  ) são, dois a dois, primos entre si. Por recorrência sobre m {\displaystyle m}   demonstra-se que F n − 2 = F 0 . F 1 . F 3 . . . . . F m − 1 , {\displaystyle F_{n}-2=F_{0}.F_{1}.F_{3}.....F_{m-1},}   então, se n < m , {\displaystyle n<m,}   F n {\displaystyle F_{n}}   divide F m − 2 , {\displaystyle F_{m}-2,}   Se existisse um número primo p que dividisse F n {\displaystyle F_{n}}   e F m , {\displaystyle F_{m},}   dividiria F m − 2 , {\displaystyle F_{m}-2,}   portanto dividiria 2 , {\displaystyle 2,}   então p = 2. {\displaystyle p=2.}   O que é impossível porque F m {\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:

P {\displaystyle P}

• A resposta para a segunda pergunta acima é que essa proporção é aproximadamente n ln ⁡ ( 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

Pierre de Fermat (1601-1665) descobriu que todo número primo da forma 4 n + 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 = 1 2 + 2 2 , {\displaystyle 5=1^{2}+2^{2},}

13 = 2 2 + 3 2 , {\displaystyle 13=2^{2}+3^{2},}

17 = 1 2 + 4 2 , {\displaystyle 17=1^{2}+4^{2},}

29 = 2 2 + 5 2 , {\displaystyle 29=2^{2}+5^{2},}

37 = 1 2 + 6 2 , {\displaystyle 37=1^{2}+6^{2},}

41 = 4 2 + 5 2 . {\displaystyle 41=4^{2}+5^{2}.}

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

• ( 4 n + 1 ) {\displaystyle (4n+1)}   - que podem sempre ser escritos na forma ( x 2 + y 2 {\displaystyle x^{2}+y^{2}}  ); e
• ( 4 n − 1 ) {\displaystyle (4n-1)}   - nunca podem ser escritos na forma ( x 2 + y 2 {\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 = 17 x 19.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[30] números compostos e não existem[31] 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 x 2 − x + 41 {\displaystyle x^{2}-x+41}   fornece primos quando x = 0 ,   1 ,   2 ,   . . . ,   40. {\displaystyle x=0,\ 1,\ 2,\ ...,\ 40.}   [32][33] Veja que para x = 41, a fórmula resulta em 41 2 {\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 a x 2 + b x + c {\displaystyle ax^{2}+bx+c}   com a ≠ 0 {\displaystyle a\neq 0}   que represente infinitos números primos. Dirichlet usou métodos para provar que se a , {\displaystyle a,}   2 b {\displaystyle 2b}   e c {\displaystyle c}   não têm fator primo em comum, a expressão polinomial a duas variáveis

a x 2 + 2 b x y + c y 2 {\displaystyle ax^{2}+2bxy+cy^{2}}

Fermat pensou que a fórmula 2 2 n + 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 F n . {\displaystyle F_{n}.}   Os cinco primeiros números são:

F 0 = 3 , F 1 = 5 , F 2 = 17 , F 3 = 257 e F 4 = 65.537 , {\displaystyle F_{0}=3,\;F_{1}=5,\;F_{2}=17,\;F_{3}=257\;e\;F_{4}=65.537,}

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

p n ∼ n ln ⁡ n . {\displaystyle p_{n}\sim n\ln n.}

Uma aproximação melhor é:

p n = n ln ⁡ n + n ln ⁡ ln ⁡ n − n + n ln ⁡ n ( ln ⁡ ln ⁡ n − 2 ) − n ln ⁡ ln ⁡ n 2 ( ln ⁡ n ) 2 ( ln ⁡ ln ⁡ n − 6 ) + O ( n ( ln ⁡ n ) 2 ) . {\displaystyle {p_{n}=n\ln n+n\ln \ln n-n+{\frac {n}{\ln n}}\left(\ln \ln n-2\right)-{\frac {n\ln \ln n}{2(\ln n)^{2}}}\left(\ln \ln n-6\right)+O\left({\frac {n}{(\ln n)^{2}}}\right).}}

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

n ln ⁡ n + n ( ln ⁡ ln ⁡ n − 1 ) < p n < n ln ⁡ n + n ln ⁡ ln ⁡ n para n ≥ 6. {\displaystyle n\ln n+n(\ln \ln n-1)<p_{n}<n\ln n+n\ln \ln n\quad {\mbox{para}}n\geq 6.}

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 2 57885161 − 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.[37]

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".[38] É o número 2 74207281 − 1 , {\displaystyle 2^{74207281}-1,}   que tem 5 milhões de dígitos a mais que o último conhecido.[39] 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. O homem que o descobriu chama-se Jonathan Pace, tem 51 anos, é norte-americano e também participa do GIMPS.[40] Em dezembro de 2018 uma nova marca de maior número primo foi registrada, alcançando a quantidade de 24 milhões de dígitos.

• A estratégia evolutiva usada por cigarras do gênero "Magicicada" faz uso de números primos. Evolutivamente, à medida que algumas espécies foram alongando seus períodos de "hibernação", também os de seus predadores naturais foram se alongando. Foram favorecidas aquelas que só emergiam após número primo de anos (13, 17), pois isso reduz ao máximo as chances de encontrar seus predadores naturais[41]. Um exemplo para entender isso é: Imagine uma espécie de cigarra que vire ninfa a cada 2 anos, e uma outra a cada 4. Um predador natural de cigarras que fique hibernando 4 anos, quando sair de sua hibernação, terá como fonte de alimentação ambas espécies, aumentando a quantidade de comida disponível. Já com as cigarras que ficam hibernando um número primo de anos, seus predadores naturais terão que hibernar esse período de temp também, e terão menos opções de comida.

• Há uma espécie de bambu, "Phyllostachys bambusoides", que tem sua florada a cada 23 anos[42]. Cientistas acreditam que esse "número primo de tempo" para cada floração é um diferencial evolutivo dessa espécie frente as demais.

Começando com o trabalho de Hugh Montgomery e Freeman Dyson na década de 1970, matemáticos e físicos especularam que os zeros da função zeta Riemann estão conectados aos níveis de energia dos sistemas quânticos[43][44]. Os números primos também são significativos na ciência da informação quântica, graças a estruturas matemáticas como bases mutuamente imparciales e medidas de valor positivo de operadores positivos[45][46].

• Crivo de Eratóstenes
• Números primos gêmeos
• Elemento Primo
• Elemento Irredutível
• Função de contagem de números primos
• Teorema do número primo
• Teste de primalidade
• Certificado de Primalidade
• Função total de fatores primos não repetidos
• coprimo
• Primorial
• Série dos inversos dos primos
• Demonstração de Furstenberg da infinitude dos números primos
• Fator primo
• PrimeGrid
• Hipótese de Riemann sobre os números primos

1. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011 (pag. 90)
2. ↑ Euclides, Os Elementos, Livro IX, Proposição 20 [em linha]
3. ↑ «Números Primos». www.primos.mat.br. Consultado em 1 de julho de 2018 
4. ↑ RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012. (pag. 2 e 3)
5. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 83)
6. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 84)
7. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 85)
8. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 88)
9. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 92)
10. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 102)
11. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 105)
12. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 107)
13. ↑ Kilford, L.J.P. (2004). «A generalization of a necessary and sufficient condition for primality due to Vantieghem». Int. J. Math. Math. Sci. (69-72): 3889-3892. Zbl 1126.11307. arXiv:math/0402128  . An article with proof and generalizations
14. ↑ Vantieghem, E. (1991). «On a congruence only holding for primes». Indag. Math., New Ser. 2 (2): 253-255. Zbl 0734.11003 
15. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 89)
16. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 92)
17. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 102)
18. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011. (pag 93)
19. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 101)
20. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011. (pag. 83)
21. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 84)
22. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 97)
23. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 98)
24. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 101)
25. ↑ HEFEZ, Abramo. Elementos da Aritmética. 2ª ed. Rio de Janeiro: SBM, 2011.(pag. 104)
26. ↑ RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.(pag 1)
27. ↑ RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.(pag 3)
28. ↑ RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.(pag 4)
29. ↑ RIBENBOIM, Paulo. Números Primos. Velhos mistérios e novos recordes. 1ª ed. Rio de Janeiro: IMPA, 2012.(pag 4)
30. ↑ Conforme cálculo feito pelo Wolfram Alpha.
31. ↑ Conforme cálculo feito pelo Wolfram Alpha.
32. ↑ Hua (2009), p. 176-177"
33. ↑ Ver lista dos valores, calculada pelo Wolfram Alpha
34. ↑ Ernest Cesàro (1894). «Sur une formule empirique de M. Pervouchine». Comptes rendus hebdomadaires des séances de l'Académie des sciences. 119: 848–849  (em francês)
35. ↑ Eric Bach, Jeffrey Shallit (1996). Algorithmic Number Theory. 1. [S.l.]: MIT Press. p. 233. ISBN 0-262-02405-5 
36. ↑ Pierre Dusart (1999). «The kth prime is greater than k(ln k + ln ln k-1) for k>=2» (PDF). Mathematics of Computation. 68: 411–415 
37. ↑ «World's largest prime number discovered -- all 17 million digits» 
38. ↑ «Missouri Mathematicians Discover New Prime Number» 
39. ↑ BBC. «Largest known prime number discovered in Missouri» 
40. ↑ «Descoberto o maior número primo conhecido. Tem mais de 23 milhões de dígitos» 
41. ↑ ideiasesquecidas.com/ Cigarras e números primos
42. ↑ nationalgeographic.com/ Zimmer, Carl (May 15, 2015). "Bamboo Mathematicians". Phenomena: The Loom. National Geographic. Retrieved February 22, 2018.
43. ↑ Peterson, Ivars (June 28, 1999). «The Return of Zeta». MAA Online. Consultado em 14 de março de 2008. Cópia arquivada em October 20, 2007  Parâmetro desconhecido |url-status= ignorado (ajuda); Verifique data em: |arquivodata=, |data= (ajuda)
44. ↑ Hayes, Brian (2003). «Computing science: The spectrum of Riemannium». American Scientist. 91 (4): 296–300. JSTOR 27858239. doi:10.1511/2003.26.3349 
45. ↑ Bengtsson, Ingemar; Życzkowski, Karol (2017). Geometry of quantum states : an introduction to quantum entanglement Second ed. Cambridge: Cambridge University Press. pp. 313–354. ISBN 978-1-107-02625-4. OCLC 967938939 
46. ↑ Zhu, Huangjun (2010). «SIC POVMs and Clifford groups in prime dimensions». Journal of Physics A: Mathematical and Theoretical. 43 (30). 305305 páginas. Bibcode:2010JPhA...43D5305Z. arXiv:1003.3591 . doi:10.1088/1751-8113/43/30/305305 

• 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

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