Numeros primos

1
N´ meros Primos: onde est˜o? Por que encontr´-los? u a a Ana Cristina Vieira
MAT/UFMG
Primos
• Defini¸ao: Livro VII dos Elementos de Euclides de Alexandria (360 a.C - 295 a.C). c˜ Dado qualquer n´mero inteiro n, divisores inteiros de n: 1, n, −1 e −n. Quest˜o: u a existem outros divisores positivos de n al´m de 1 e n? e Defini¸˜o: Um n´mero inteiro n > 1 ´ primo se seus unicos divisores (positivos) ca u e ´ s˜o 1 e n. a • Caso n > 1 n˜o seja primo, dizemos que ele ´ composto. Note que o n´mero 1 n˜o a e u a
´ classificado nem como primo, nem como composto. e • Quest˜o: Existe uma f´rmula para gerar n´meros primos, ou seja, ´ poss´ a o u e ıvel determinar uma fun¸˜o f , tal que dado um n´mero natural n˜o nulo n, f (n) seja ca u a um n´mero primo? u n

• Fermat (1601-1665) conjecturou que todos os n´meros da forma F (n) = 22 + 1, u onde n ´ um inteiro positivo, s˜o primos. e a
Por exemplo:
F (1) = 5, F (2) = 17, F (3) = 257, F (4) = 65537 s˜o todos primos (Fermat n˜o conseguiu decidir se F (5) era primo). a a
• Em 1732, Euler (1707-1783) mostrou que F (5) (um inteiro de 10 algarismos) ´ e divis´ por 641 e portanto n˜o ´ primo. ıvel a e n • Os n´meros da forma 22 + 1 que s˜o primos s˜o chamados primos de Fermat. u a a 1

2

3

• Os unicos primos de Fermat conhecidos at´ hoje s˜o 22 + 1, 22 + 1, 22 + 1 e
´
e a 4
22 + 1.
• Resultado: n˜o existe um polinˆmio em uma vari´vel, com coeficientes racionais, a o a que produza somente n´meros primos. u • Este resultado n˜o exclui a existˆncia de: a e
a) fun¸oes polinomiais em uma vari´vel que gere n´meros primos, mas n˜o todos; c˜ a u a
b) fun¸oes n˜o polinomiais que gerem n´meros primos, todos ou n˜o; c˜ a u a

2
c) fun¸oes polinomiais em mais de uma vari´vel que produzam n´meros primos, c˜ a u todos ou n˜o. a Embora muitos professores e estudantes de Matem´tica desconhe¸am este fato, exa c istem fun¸oes com cada uma das