Saltar para o conteúdo
Topos Uranos
Português

Números primos e o teorema fundamental da aritmética

Resumo

Esta aula estuda os números primos, os átomos da multiplicação dos naturais. Demonstra que todo natural maior que 11 tem um divisor primo, apresenta o crivo de Eratóstenes e a razão pela qual basta crivar até a raiz quadrada, e prova com Euclides que os primos são infinitos. Demonstra depois o lema de Euclides, segundo o qual um primo que divide um produto divide algum de seus fatores, e com ele o teorema fundamental da aritmética: todo natural maior que 11 se escreve como produto de primos de uma única maneira. Da fatoração se deduzem o número de divisores de um natural, a caracterização dos quadrados perfeitos e a irracionalidade da raiz quadrada de todo natural que não seja um quadrado perfeito.

Objetivos de aprendizagem

  1. Distinguir os números primos dos compostos e demonstrar que todo natural maior que 11 tem um divisor primo.
  2. Aplicar o crivo de Eratóstenes e justificar por que basta riscar os múltiplos dos primos não maiores que a raiz quadrada do limite.
  3. Demonstrar a infinitude dos primos, o lema de Euclides e a existência e a unicidade da fatoração em primos.
  4. Usar a fatoração para contar e enumerar divisores, reconhecer quadrados perfeitos e demonstrar a irracionalidade de raízes quadradas.

Números primos e números compostos

Na aula sobre a divisibilidade e a divisão com resto viu-se que todo natural nn é divisível por 11 e por si mesmo. Alguns naturais não admitem outros divisores além desses dois; são as peças das quais, por multiplicação, se compõem todos os demais.

Definição (número primo). Um natural pp é primo se p>1p > 1 e seus únicos divisores são 11 e pp. Um natural n>1n > 1 que não é primo se chama composto: escreve-se como n=abn = ab, com 1<a<n1 < a < n e 1<b<n1 < b < n. O número 11 não é primo nem composto.

Os primos menores que 5050 são os quinze seguintes:

2,3,5,7,11,13,17,19,23,29,31,37,41,43,472, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

O 22 é o único primo par, porque todo outro número par tem o divisor 22, distinto de 11 e de si mesmo. A exclusão do 11 não é um capricho da definição: se 11 fosse primo, a fatoração em primos deixaria de ser única, porque 6=2⋅3=1⋅2⋅36 = 2 \cdot 3 = 1 \cdot 2 \cdot 3, e o teorema central desta aula teria de ser enunciado com uma exceção.

O princípio da boa ordenação

As demonstrações desta aula apoiam-se em uma forma do princípio de indução que é especialmente cômoda para raciocinar sobre divisores: o princípio da boa ordenação, segundo o qual todo conjunto não vazio de números naturais tem um menor elemento. Ele foi deduzido da indução forte na aula sobre somatórios, progressões e indução, e aqui é usado sem repetir sua demonstração.

Todo natural maior que 1 tem um divisor primo

O primeiro resultado da aula garante que nenhum natural maior que 11 escapa aos primos: sempre há um que o divide, e ele é encontrado entre os menores divisores.

ProposiçãoO menor divisor maior que 1 é primo

Todo natural n>1n > 1 tem um divisor primo: o menor divisor de nn maior que 11 é primo. Se, além disso, nn é composto, seu menor divisor primo pp cumpre p2≤np^2 \leq n. A figura marca na reta os divisores de n=91=7⋅13n = 91 = 7 \cdot 13.

Demonstração

  1. D={d∈N:d∣n∧d>1},n∈D,m=min⁡D\dato{D}{D = \{ d \in \mathbb{N} : d \mid n \wedge d > 1 \}}, \quad n \in D, \quad m = \min D

    O conjunto dos divisores de nn maiores que 11 não é vazio, porque contém o próprio nn; pelo princípio da boa ordenação, tem um menor elemento mm.

  2. a∣m∧m∣n→a∈D,a<ma \mid m \wedge m \mid n \rightarrow \resaltar{a \in D}, \quad \resaltar{a < m}

    Se mm fosse composto, m=abm = ab com 1<a<m1 < a < m, o fator aa dividiria mm e, pela transitividade da divisibilidade, nn: seria um elemento de DD menor que mm, contra a escolha de mm. Portanto, mm é primo.

  3. n=pk,k∈D\dato{k}{n = pk, \quad k \in D}

    Seja agora nn composto, e seja pp seu menor divisor primo, que é o menor elemento de DD. Escrevemos n=pkn = pk; como nn não é primo, k≠1k \neq 1, e kk também divide nn.

  4. p2=p⋅p≤p⋅k=np^2 = p \cdot p \leq \resaltar{p \cdot k} = n

    Pela minimalidade de pp, tem-se k≥pk \geq p, e pela monotonia do produto obtém-se a cota.

Portanto, para decidir se um natural nn é primo basta testar os primos pp com p2≤np^2 \leq n: se nenhum o divide, nn é primo. Por exemplo, para 221221 basta testar os primos até 1313, porque 172=289>22117^2 = 289 > 221: não é divisível por 22, 33, 55, 77 nem 1111, mas sim por 1313, e 221=13⋅17221 = 13 \cdot 17. Em contrapartida, 211211 não é divisível por nenhum dos primos 22, 33, 55, 77, 1111 e 1313, e como 172=289>21117^2 = 289 > 211, o número 211211 é primo.