O que é Número primo? — Matemática

Definição 64.5 Matemática do ensino fundamental · Capítulo 64 — Aritmética: divisores e números primos

Um número primo é um inteiro $\geq 2$ cujos únicos divisores são $1$ e ele mesmo. Os primos abaixo de $30$ são

2,\ 3,\ 5,\ 7,\ 11,\ 13,\ 17,\ 19,\ 23,\ 29 .

O número $1$ não é primo (por convenção), e um inteiro $\geq 2$ que não é primo se diz composto.

A árvore de fatores de 360: cada passo separa o menor fator primo (em vermelho). Lendo as folhas vermelhas e o 5 final: 360 = 23 × 32 × 5. — A árvore de fatores de $360$ : cada passo separa o menor fator primo (em vermelho). Lendo as folhas vermelhas e o $5$ final: $360 = 2^3 \times 3^2 \times 5$ .

Ler no capítulo →

Definição 6.12 Matemática universitária — Graduação 1 · Capítulo 6 — Aritmética dos Inteiros

Um inteiro $p \geq 2$ é primo quando os seus únicos divisores positivos são $1$ e $p$ . Para $p$ primo e $a \in \Z$ : ou $p \mid a$ , ou $\gcd(p, a) = 1$ . Consequentemente (Teorema 6.8), vale o lema de Euclides: se $p \mid ab$ , então $p \mid a$ ou $p \mid b$ .

Exemplos

Exemplo 6.24 (A recíproca de Fermat falha: $341$ )

O pequeno teorema de Fermat dá um teste barato de composicionalidade: se $a^{n-1} \not\equiv 1 \pmod n$ para algum $a$ primo com $n$ , então $n$ não é primo. O teste poderia também certificar a primalidade? Não: tome $n = 341 = 11 \times 31$ , composto, e $a = 2$ . Como $2^{10} = 1024 = 3 \times 341 + 1$ ,

2^{10} \equiv 1 \pmod{341} \qquad\Longrightarrow\qquad 2^{340} = \bigl(2^{10}\bigr)^{34} \equiv 1 \pmod{341} :

o composto $341$ passa no teste de Fermat na base $2$ (é o menor pseudoprimo desse tipo). A base $3$ o desmascara ( $3^{340} \not\equiv 1$ ), e o teste prático de primalidade, portanto, roda o teste em várias bases, com refinamentos — as versões industriais dessa ideia são o que certifica os grandes primos da Observação 6.27. Moral: uma implicação e a sua recíproca vivem vidas separadas (Observação 1.10), mesmo para teoremas.

Ler no capítulo →

Exemplos

Termos relacionados