Um pouco sobre os números primos: Teorema Fundamental da Aritmética

 Um dos Teoremas mais importantes ensinados no Ensino Fundamental é o Teorema Fundamental da Aritmética - TFA. Contudo, mesmo em turmas mais avançadas, não se vê sequer uma demonstração ou justificativa do TFA. Então, o presente post será exposto uma demonstração elementar do TFA. Usaremos como base axiomática o Princípio da Boa Ordenação - PBO. Tal princípio diz que dado um subconjunto $X$ não vazio de $\mathbb{N}$ então $X$ possui o menor elemento ou elemento mínimo de $X$. 

Lema 1: O menor divisor positivo maior do que $1$ de um número natural $n$ é um número primo. 

Demonstração.

Seja $D$ o conjunto dos divisores positivos de um número natural $n$. Observe que, $D\setminus \{1\}\neq \varnothing$, pois $n \in D\setminus\{1\}$. Logo, pelo PBO existe $p_0 \in D\setminus\{1\}$ tal que $p_0 \leq x$ para todo $x \in D\setminus \{1\}$. Suponha por absurdo que $p_0$ não é primo. Então existe um natural positivo $d$ não trivial tal que $d|p_0 \Rightarrow d|n$. Portanto, $d\in D\setminus \{1\}$. Contudo, $d<p_0$ o que é uma contradição, pois $p_0$ é o menor elemento de $D\setminus \{1\}$. Logo, $p_0$ é um número primo. $\square$

TFA parte 1 (existência). Todo número natural $n>1$ é um número primo ou pode ser escrito como o produto de números primos. 

Demonstração.

Seja $n>1$ um número natural. Se $n$ é primo não precisamos fazer nada. Pelo Lema 1 seu menor divisor não trivial é um primo $p_1$. Logo, $n$ pode ser escrito da forma 

$$n=k_1\cdot p_1, k_1 \in \mathbb{N}.$$

Se $k_1=1$ então $n=p_1$ e encerramos o processo. Caso contrário pegamos o menor divisor positivo não trivial de $k_1$ que, pelo Lema 1 é um primo $p_2$. Logo, 

$$n=k_2\cdot p_1\cdot p_2, k_2 \in \mathbb{N}.$$

Se $k_2=1$ então $n=p_1\cdot p_2$ e terminamos, caso contrário repetimos o procedimento. Em algum momento esse processo terminará, pois, $n>k_1>k_2>\cdots>k_j>\cdots>1$. Em outras palavras, como $k_j \in [1,n)$ e esse é um intervalo finito de números naturais em algum momento teremos um $i$ tal que $k_i=1$. Logo, para cada $n$ temos

$$n=p_1\cdot p_2\cdot p_3\cdots p_i ,$$

com $p_1,p_2, ...,p_i$ primos. $\square$

Proposição 1 Sejam $a,b \neq 0$ naturais. Se $p$ é primo e $p|ab$ então $p|a$ ou $p|b$. 

Demonstração. 

Suponha, por absurdo, que $ab$ é o menor produto tal que $p\not |a$ e $p\not | b$, mas $p|ab$. Observe que, $mdc(a,p)=1$ e $mdc(b,p)=1$. Então, existem $k_1,k_2,r_1,r_2 \in \mathbb{N}$ tais que $a=pk_1+r_1$ e $b=pk_2+r_2$ com $0< r_1,r_2<p$, como $a$ e $p$ são coprimos isso implica que $mdc(r_1,p)=1$, de modo análogo, $mdc(r_2,p)=1$. Por outro lado, $ab=p^2k_1k_2+p(k_1+k_2)+r_1r_2.$ Por hipótese, $p|ab$ logo, $$p|ab \Rightarrow p|(ab-(p^2k_1k_2+p(k_1+k_2)) \Rightarrow p|r_1r_2.$$ Porém, $r_1r_2<ab$, contradição. Logo, se $p$ é primo e $p|ab$ então $p|a$ ou $p|b$. $\square$ 

Corolário 1 Se $p$ é primo e $p|(a_1a_2\cdot ... \cdot a_k)$, então $p|a_i$ para algum $i\in \{1,2,...,k\}$. 

Demonstração. 

Suponha que $p|(a_1a_2\cdot ... \cdot a_k)$. Note que, $p$ divide $a_1\cdot(a_2a_3\cdot ... \cdot a_k)$. Pela Proposição 1 isso implica que $p|a_1$ ou $p|(a_2a_3\cdot ... \cdot a_k)$. Se $p|a_1$ terminamos. Caso contrário, $p$ divide $a_2\cdot (a_3a_4\cdot ... \cdot a_k)$. E, novamente, utilizando a Proposição 1 temos que $p|a_2$ ou $p|(a_3a_4\cdot ... \cdot a_k)$. Se $p$ divide $a_2$ encerramos o processo. Caso contrário, replicamos a técnica e nos valemos novamente da Proposição 1. Em algum momento o processo termina para algum $a_i$, isto é, $p|a_i$. Pois $k$ é finito e esse processo não pode ocorrer para sempre. Na pior hipótese chagamos em $a_{k-1}a_k$ ao reaplicarmos o procedimento $k-2$ vezes. E assim, concluímos que ou $p|a_{k-1}$ ou $p|a_k$, pela proposição 1. $\square$

TFA parte 2 (unicidade). Todo número natural $n>1$ é primo ou pode ser escrito de forma única, a menos da ordem de seus fatores, como o produto de números primos. 

Demonstração. 

Suponha, por absurdo, que $n$ é o menor número que possui duas fatorações distintas em fatores primos. Em outras palavras, $n=p_1p_2\cdots p_s=q_1q_2\cdots q_r$ onde $p_i$ e $q_j$ são primos para cada $i,j \in \mathbb{N}$. Pelo Corolário 1, $p_1|q_j$ para algum $j$. Pode-se supor, sem perde de generalidade, que $p_1|q_1$. Portanto, $p_1 \in \{1,q_1\}$, visto que, $q_1$ é primo, logo, possui apenas dois divisores. Além disso, $p_1>1$ pois $p_1$ é primo. Consequentemente, $p_1=q_1$. Assim, 

$$\dfrac{n}{p_1}=p_2p_3\cdots p_s=q_2q_3\cdots q_r.$$

Logo, $n/p_1$ possui duas decomposições distintas em fatores primos, porém, $n/p_1<n$. Contradição. $\square$ 

Desafios 

3) (OBMEP - banco de questões 2010) Qual é o maior fator primo de $2016$?

4) (OBMEP - banco de questões 2010) Se $a, b$ e $c$ são números inteiros positivos tais que $3a = 4b = 7c$, qual é o menor valor possível de $a + b + c$?

Referências

MARTINEZ, F. B. et al. Teoria dos Números: um passeio com primos e outros números. IMPA, Rio de Janeiro, 5ª edição, 2018.

Banco de Questões. Disponível em: OBMEP - Banco de Questões. 

Um pouco sobre os números primos: Um algoritmo para determinar a primalidade de um número natural

Sabemos que existem infinitos números primos. Mas, como podemos determinar se um número natural $n$ é primo ou composto? Uma possibilidade é testar candidatos a divisores e exibir um divisor não trivial, isto é, um divisor diferente de $1$ e $n$. Neste post nos restringimos aos divisores inteiros positivos. Mas não precisamos exaurir a lista de todos os inteiros de $2$ até $n-1$. Podemos nos valer do  Crivo de Eratóstenes. No nosso caso vamos usar um versão mais fraca.

Proposição [1] Se $n$ é composto então existe um divisor $d$ não trivial tal que $d\leq\sqrt{n}$. 

Demonstração. 

Suponha por absurdo que $n$ é um número composto e que não possui divisor não trivial menor ou igual do que $\sqrt{n}$. Portanto, existem $a,b \in \mathbb{N}$ tais que $n=a\cdot b$ e $a,b>1.$ Por outro lado, $a>\sqrt{n}$ e $b>\sqrt{n}$, assim, $n=a\cdot b>\sqrt{n}\cdot \sqrt{n}=n$. Contradição. Logo, $n$ possui pelo menos um divisor não trivial menor ou igual do que $\sqrt{n}.\,\,\, \square$

Por outro lado, se $n$ é primo ele não possui divisor não trivial menor ou igual do que $\sqrt{n}$. Então basta buscar candidatos a divisores de $2$ até $[\sqrt{n}]$, onde $[\sqrt{n}]$ é o maior inteiro positivo menor ou igual do que $\sqrt {n}$. Podemos simplificar mais ainda testando o dois e em seguida somente os ímpares da nossa lista restrita. A seguir vamos exibir um código em C que determina se o número é primo ou composto adaptado de um código disponibilizado pelo IME.

Algoritmo 

________________________________________________________

#include <stdio.h>

int main() 

{ 

int num,divisor,ehprimo,cont,resultado, resto;

printf("Por favor digite um numero inteiro==>"); 

scanf("%d",&num);

if((num<=1)||(num!=2 && num%2==0)) 

 { 

 ehprimo=0; 

 printf ("\n seu número ou é par e distinto de 2 ou é menor que 2.");

 } 

else 

 { 

 ehprimo=1; 

 } 

divisor=1;

cont=0;

resultado=num;

while((ehprimo==1)&&(divisor<=resultado)&&(num!=2)) 

 {

 divisor=divisor+2;

 resultado=num/divisor;

 resto=num%divisor; 

 printf("\n candidato a divisor %d, parte inteiro %d",divisor,resultado);

 

 printf(", resto %d ",resto); 

 cont ++;

 if(num%divisor==0)

{ 

 ehprimo=0;

 } 

 else 

 { 

 ehprimo=1; 

 } 

 } 

 if((num%2!=0)&&(num>1))

 {

 printf ("\n foram realizadas %d divisões",cont);

 }

if(ehprimo==1) 

 { 

 printf("\n %d eh primo", num); 

 } 

else 

 { 

 printf("\nO %d nao eh primo.",num);

 } 

return 0; 

}

________________________________________________________

O código funciona, porém, tem custo computacional $O(\sqrt{n}).$

Desafio

2) (OIbM 2014) Dado um conjunto $X$ e uma função $f:X \to X$ denotamos, para cada $x \in X, f^1(x)=f(x)$ e, para cada $j \geq 1, f^{f(j+1)}(x)=f(f^j(x))$. Dizemos que $a \in X$ é um ponto fixo de $f$ se $f(a)=a$. Para cada número real $x$, definimos $\pi(x)$ como o número de primos positivos menores ou iguais a $x$. Dado um número positivo $n$, dizemos que $f:\{1,2,3,...,n\} \to \{1,2,3,...,n\}$ é catracha se $f^{f(k)}(k)=k$ para todo $k\in\{1,2,3,...,n\}$. Prove que:

a) Se $f$ é catracha, então $f$ tem pelo menos $\pi(n)-\pi(\sqrt{n})+1$ pontos fixos. 

b) Se $n\geq 36$, então existe uma função catracha com exatamente $\pi(n)-\pi(\sqrt{n})+1$ pontos fixos. 

Referências 

MAC-110 -  Numero Primo  - Três solucoes para o mesmo problema. Disponível em: ime.usp.br/~yw/2012/mac110/material/primo.html.

MARTINEZ, F. B. et al. Teoria dos Números: um passeio com primos e outros números. IMPA, Rio de Janeiro, 5ª edição, 2018.

Provas e gabaritos. Disponível em: OBM - Olimpíada Brasileira de Matemática. 

Um pouco sobre os números primos: Infinitude dos números primordiais

Número primo é todo número natural maior do que $1$ que possui exatamente dois divisores o $1$ e ele próprio. São exemplos de primos os números $2,3,5,7$ e $11$. Se um número não é primo ele é composto. Vamos discutir sobre a infinitude da quantidade de tais números. Muitas vezes essa informação é dada como um dogma na escola de tal modo que parece óbvio a existência de infinitos números primos e esse não é um fato trivial.

Bem, mas por que se questionar sobre a infinitude dos números primos? À primeira vista, pode-se conjecturar que não existem infinitos números primos. De fato, de $1$ até $10$ existem $4$ números primos, isto é, 40% dos $10$ primeiros números naturais são primos. De $1$ até $100$ temos 25 primos, de 40% passamos a ter uma proporção de 25%. Já de $1$ até $1000$ notamos $168$ números primos, assim a proporção de números primos neste intervalo é $16,8$%. Se continuarmos vamos notar que menos de $3,77$% do primeiro trilhão de números são primos. Isso dá a ideia de que eles se tornam mais raros. 

Densidade dos números primos. 

De sorte que, $1/\ln(x)$ é a densidade média dos números primos no intervalo de $1$ até $x$. Então, possivelmente se tornam tão raros que sumam, visto que, $1/ln(x) \to 0$ quando $x \to + \infty$. Outro fato que colabora para suspeitarmos da infinitude dos primos é o fato de existirem desertos de números primos. Podemos criar intervalos tão grandes quanto queremos de números consecutivos compostos. Basta considerarmos o conjunto,

$$A=\{(n+1)!+2, (n+1)!+3, (n+1)!+4, ..., (n+1)!+(n+1)\}.$$

Com $n \in \mathbb{N}$. Este subconjunto dos naturais é formado por $n$ números consecutivos compostos. De fato, podemos garantir que $(n+1)!+2$ é divisível por $2$, que o $(n+1)!+3$ é divisível por $3$ e assim sucessivamente. Bem, como exemplo numérico podemos criar uma sequência de $1000$ números consecutivos e compostos,

$$B=\{1001!+2, 1001!+3, ..., 1001!+1000, 1001!+1001\}.$$

Por fim a verdade:

Apesar de todos os possíveis indícios gerados por nossa investigação acima, sabemos que nossa suspeita é falsa. A demonstração a seguir é creditada a Euclides, mas não é, de fato, dele. A demonstração de Euclides é construtiva, então nossa demonstração é na realidade uma adaptação. Por simplicidade faremos por redução ao absurdo.

Demonstração:

Suponha por absurdo que há uma quantidade finita de números primos. Seja o conjunto $P=\{p_1,p_2,...,p_n\}$ onde $p_i$ é primo para todo $i=1,2,...,n$ e $p_1=2<p_2<....<p_n$. Isto é, $P$ é o conjunto de todos os números primos. Agora considere,

$$N=p_1p_2...p_n.$$

Também consideremos o número natural $N+1$. Por hipótese $N+1$ não é primo pois $p_n$ é o maior número primo e $N+1>p_n \Rightarrow N+1 \notin P$. Então, pelo Teorema fundamental da Aritmética existe pelo menos um $p_i \in P$ para algum $i$, tal que $p_i|(N+1).$ Mas, por outro lado $p_i| N \Rightarrow p_i|(N+1)-N \Rightarrow p_i|1$, o que é um absurdo pois $p_i>1$. Portanto, existem infinitos números primos.$\,\,\,\square$

 

Um pequeno desafio:

1) Mostre que existem infinitos primos da forma $4k+3$ com $k \in \mathbb{N}.$

A solução será postada em breve! 

Referências 

MARTINEZ, F. B. et al. Teoria dos Números: um passeio com primos e outros números. IMPA, Rio de Janeiro, 5ª edição, 2018.