Arquivos de Impressão: Tamanho A4 (pdf), Tamanho A5 (pdf), Texto (txt).
Definição 1. Um inteiro p > 1 é chamado número primo se não possui um divisor d satisfazendo 1 < d < p. Se um inteiro a > 1 não é primo, ele é chamado de número composto. Um inteiro m é chamado de composto se |m| não é primo.
O próximo teorema nos diz que os primos são as "peças" fundamentais dos números inteiros:
Teorema 2. Todo inteiro n, maior que 1, pode ser expresso como o produto de número primo.
Demonstração. Se o inteiro n é um primo, então ele mesmo é o produto de um único fator primo. Se o inteiro n não é primo, existe uma decomposição do tipo: n = n1n2 com 1 < n1 < n e 1 < n2 < n. Repetindo o argumento para n1 e n2, podemos escrever n como o produto de primos ou podemos obter parcelas menores escrevendo n como um produto de naturais. Como não existe uma sucessão infinita de naturais cada vez menores, após um número finito de operações desse tipo, poderemos escrever n como um produto de números primos.
Quantos números primos existem?
Teorema 3. (Euclides) Existem infinitos números primos.
Demonstração. Suponha, por absurdo, que exita apenas uma quantidade finita de primos: p1, p2, ... , pn. Considere o número X = p1p2 …pn + 1. Pelo teorema anterior, esse número deve ser o produto de alguns elementos do conjunto de todos os números primos. Entretanto, nenhum dos primos pi divide X.
Exemplo 4. Existe um bloco de 1000 inteiros consecutivos não contendo nenhum primo?
Sim. Um exemplo é o conjunto 1001! + 2, 1001! + 3, ... , 1001! + 1001. Veja i | 1001! + i para todo i = 2, 3, ... , 1001.
Exemplo 5. (Torneio das Cidades) Existe um bloco de 1000 inteiros consecutivos contendo apenas um primo?
Para cada bloco de 1000 números consecutivos, contemos sua quantidade de números primos. Por exemplo, no bloco 1, 2, 3, ... , 1000, temos 168 números primos (mas só usaremos o fato de que existem mais de dois primos nesse bloco). Comparando os blocos consecutivos k + 1, k + 2, ... , k + 1000 e k + 2, k + 3, ... , k + 1001, ou o número de números primos aumenta em uma unidade, ou fica constante ou diminui em uma unidade. Analisando todos os blocos consecutivos desde 1, 2, ... , 1000 até 1001! + 2, 1001! + 3, ... , 1001! + 1001, o número de números primos deve ser igual à 1 em algum deles. Para ver isso, usaremos um argumento de continuidade discreta: Começando com o número 168 e realizando alterações de no máximo uma unidade na quantidade de primos em cada bloco, para chegarmos no número 0, necessariamente deveremos passar pelo número 1 em algum momento.
Relembremos um importante resultado da aula passada:
Teorema 6. (Bachet-Bèzout) Se d = mdc(a, b), então existem inteiros x e y tais que ax + by = d.
Proposição 7. Sejam a, b e c inteiros positivos com a | bc e mdc(a, b) = 1. Então, a | c.
Demonstração. Pelo teorema anterior, existem x e y inteiros tais que ax + by = 1. Assim, acx + bcy = c. Como a | acx e a | bcy, podemos concluir que a | c.
Em particular, se p é um número primo e p | ab, então p | a ou p | b. Podemos usar esse fato para garantir a unicidade em nosso primeiro teorema, obtendo o importante:
Teorema 8. (Teorema Fundamental da Aritmética) A fatoração de qualquer inteiro n > 1, em fatores primos, é única a menos da ordem dos fatores.
Exemplo 9. (Rússia 1995) É possível colocarmos 1995 números naturais ao redor de um círculo de modo que para quaisquer dois números vizinhos a razão entre o maior e o menor seja um número primo?
Não, é impossível. Suponha, por absurdo, que isso seja possível e denotemos por a0, a1, ... , a1995 = a0 tais inteiros. Então, para k = 1, ... , 1995, [(ak−1)/(ak)] é primo ou o inverso de um primo. Suponha que a primeira situação ocorra m vezes e a segunda ocorra 1995 − m vezes entre esses quocientes. Como o produto de todos os números da forma [(ak−1)/(ak)], para k = 1, ... , 1995 é igual à 1, podemos concluir que o produto de m primos deve ser igual ao produto de 1995 − m primos. Em virtude da fatoração única, m = 1995 − m. Um absurdo pois 1995 é ímpar.
Proposição 10. Se as fatorações em primos de n e m são:
|
Então, mdc(m, n) = p1γ1 p2γ2 ... pkγk e mmc(m, n) = p1θ1 p2θ2 ... pkθk, onde γi é o menor dentre {αi, βi} e θi é o maior dentre {αi, βi}.
Proposição 11. Se a e b são inteiros positivos, mostre que mmc(a, b) mdc(a, b) = ab.
Demonstração. Basta usar a proposição anterior e observar que:
|
Exemplo 12. (Torneio das Cidades 1998) É possível que mmc(a, b) = mmc(a + c, b + c) para algum conjunto {a, b, c} de inteiros positivos?
Não. Suponha que a + c e b + c possuem algum divisor primo p. Como p | mmc(a+c, b+c), caso existam tais inteiros, devemos ter que p | mmc(a, b). Assim, usando que pelo menos um dentre a e b é divisível por p podemos concluir que c também é divisível por p. Então, podemos cancelar o fator p:
|
Efetuando alguns cancelamentos, podemos supor então que a+c e b+c não possuem fatores primos em comum. Obtivemos um absurdo pois:
|
Exemplo 13. (OCM 2005) Determinar os inteiros n > 2 que são divisíveis por todos os primos menores que n.
Como mdc(n, n − 1) = 1, se n − 1 possui algum fator primo, ele não dividirá n. Assim, n − 1 < 2. Consequentemente não existe tal inteiro.
Exemplo 14. Mostre que n4 + n2 + 1 é composto para n > 1.
Veja que n4 + n2 + 1 = n4 + 2n2 + 1 − n2 = (n2 + 1)2 − n2 = (n2 + n + 1)(n2 − n + 1). Para n > 1, n2 − n + 1 = n(n − 1) + 1 > 1 e assim n4 + n2 + 1 é o produto de dois inteiros maiores que 1.
Exemplo 15. Mostre que n4 + 4n é composto para todo n > 1.
Se n é par, certamente o número em questão é divisível por 4. Para o caso em que n é impar, iremos usar a fatoração:
|
Para n da forma 4k + 1, faça a = n e b = 4k. Para n da forma 4k + 3, faça a = n e b = 22k + 1.
Exemplo 16. Se 2n + 1 é um primo ímpar para algum inteiro positivo n, prove que n é uma potência de 2.
Já vimos que an − 1 = (a − 1)(an−1 + an−2 + …+ 1). Se n é impar,
|
Sendo assim, se n possuísse algum divisor primo ímpar p com n = pb, poderíamos escrever: 2n + 1 = (a + 1)(an−1 − an−2 + …− a + 1), onde a = 2b. Como an−1 − an−2 + …− a + 1 > 1, o número 2n + 1 não seria primo.
Exemplo 17. Dados que p, p + 10 e p + 14 são números primos, encontre p.
Vamos analisar os possíveis restos na divisão por 3 de p. Se p deixa resto 1, então p + 14 é um múltiplo de 3 maior que 3 e consequentemente não poderá ser um número primo. Se o resto é 2, então p + 10 é um múltiplo de 3 maior que 3 e também não poderá ser um número primo. Assim, o resto de p por 3 é 0 e consequentemente p = 3.
Exemplo 18. ( Áustria-Polônia) Dados naturais n e a > 3 ímpar, mostre que a2n − 1 tem pelo menos n + 1 divisores primos distintos.
Usando a fatoração da diferença de quadrados, temos que:
|
Assim, a2m + 1 | a2k − 1 se k > m. Como a é impar, podemos concluir que:
|
|
temos o produto de pelo menos n inteiros primos entre si e consequentemente seus fatores primos são distintos. Para cada termo [((a2i + 1))/2], temos um fator primo pi + 1 diferente de 2. Daí, a2n − 1 possui pelo menos n + 1 fatores primos distintos, a saber, {2, p1, p2, …, pn}.
Exemplo 19. (Rioplatense 1999) Sejam p1, p2, ... , pk primos distintos. Considere todos os inteiros positivos que utilizam apenas esses primos (não necessariamente todos) em sua fatoração em números primos, formando assim uma seqüência infinita
|
Demonstre que, para cada natural c, existe um natural n tal que
|
Suponha, por absurdo, que exista c > 0 tal que an + 1 − an ≤ c, ∀n ∈ N. Isso significa que as diferenças entre os termos consecutivos de (an)n ≥ 1 pertencem ao conjunto {1, 2, …, c}, logo são finitas. Sejam d1, d2, ... , dr essas diferenças. Seja αi o maior expoente de pi que aparece na fatoração de todos os dj.
Considere então o número M = p1α1 + 1 p2α2 + 1 …pkαk + 1. É claro que M pertence à seqüência, ou seja, M = an, para algum n. Vejamos quem será an + 1. Por hipótese, existe i tal que an + 1 − an = di. Como an + 1 > an, existe um primo pj que divide an + 1 com expoente maior ou igual a αj + 1. Caso contrário,
|
absurdo. Daí, pjαj + 1 | an ⇒ pjαj + 1 | di, novamente um absurdo, pela maximalidade de αj.
Logo, o conjunto de todas as diferenças não pode ser finito e, portanto, dado qualquer c > 0, existe um natural n tal que an + 1 − an > c.
Problema 20. Dado que p, 2p + 1 e 4p2 + 1 são números primos, encontre p.
Problema 21. Dado o par de primos p e 8p2 + 1, encontre p.
Problema 22. Dado o par de primos p e p2 + 2, prove que p3 + 2 também é um número primo.
Problema 23. Dado que p, 4p2 + 1 e 6p2 + 1 são números primos, encontre p.
Problema 24. Os números de Fermat são os números da forma 22n + 1. Prove que o conjunto dos divisores primos dos termos da seqüência de Fermat é infinito.
Problema 25. Mostre que todo inteiro n pode ser escrito de maneira única na forma n = ab, onde a é um inteiro livre de quadrado e b é um quadrado perfeito. Um inteiro é dito livre de quadrado se não é divisível por nenhum quadrado perfeito maior que 1.
Problema 26. Prove que todo primo maior que 3 é da forma 6k + 1 ou 6k + 5.
Problema 27. Prove que todo inteiro da forma 3k + 2 tem um fator primo da mesma forma.
Problema 28. Prove que existem infinitos primos da forma 4k + 3 e 6k + 5.
Problema 29. Prove que se n é composto, então possui um fator primo p ≤ √n.
Problema 30. (OBM 1998) São dados 15 números naturais maiores que 1 e menores que 1998 tais que dois quaisquer são primos entre si. Mostre que pelo menos um desses 15 números é primo.
Problema 31. Mostre que n | (n − 1)! para todo número composto n.
Problema 32. Suponha que n > 1. Mostre que a soma dos inteiros positivos não excedendo n divide o produto dos inteiros positivos não excedendo n se, e somente se, n é composto.
Exemplo 33. (Rússia 1995) Encontre todos os primos p para os quais p2 + 11 tenha exatamente seis divisores distintos, incluindo 1 e p2 + 11.
Problema 34. (Irlanda 2002 ) Encontre todas as soluções inteiras positivas de p (p + 3) + q(q + 3) = n(n + 3), onde p, q são primos.
Exemplo 35. Prove que qualquer quadrado perfeito positivo tem mais divisores que deixam resto 1 na divisão por 3 do que divisores que deixam resto 2 na divisão por 3.
19. Analisemos o resto de p na divisão por 3. Se p deixar resto 1, o número 2p + 1 será divisível por 3. Se p deixar resto 2, o número 4p + 1 será divisível por 3. Em ambos os casos, 2p + 1, 4p + 1 > 3 e obtemos assim um absurdo.
20. Analisemos o resto de p na divisão por 3. Se p deixa resto 1 ou 2, p2 deixa resto 1 e consequentemente 8p2 + 1 deixa resto 0 por 3 mas certamente é maior que 3. Um absurdo, logo p = 3.
21. Analisemos o resto na divisão por 3. Se p não é múltiplo de 3, p2 + 2 é divisível por 3 e maior que 3. Um absurdo, logo p = 3 e p3 + 2 = 29.
22. Analise os restos na divisão por 5.
23. Iremos usar a fatoração do exemplo 17:
|
|
produzindo que quaisquer dois números de Fermat distintos são primos entre si e isso necessariamente implica que o conjunto de seus divisores primos é infinito.
24. Analise os restos na divisão por 2 e 3.
27. Tente imitar a prova de Euclides para a existência de infinitos primos.
29. Se n é composto, podemos escrever n = ab com 1 < a ≤ b ≤ < . Assim, a2 ≤ n e a ≤ √n. Para terminar, basta considerar qualquer divisor primo de a.
30. Dado 1 < n < 1998, se ele não for primo, usando o exercício anterior, ele tem que ter um fator primo menor que 1998, ou seja, um fator primo menor que 45. Como só existem 14 primos menores que 45, e são 15 números, um deles será primo.
31. Escreva n = ab e analise as aparições de a e b no produto (n − 1) ·(n − 2) …2 ·1.
33. Se p ≠ 3, 3 | p2 + 11. Analogamente, se p ≠ 2, 4 | p2 + 11. Assim, exceto nesses dois casos, 12 | p2 + 11 e podemos encontrar mais que 6 divisores distintos: {1, 2, 3, 4, 6, 12, p2 + 11}. Agora, teste p = 2 e p = 3 para verificar que p = 3 é a única solução.
|
a decomposição de n em fatores primos, onde cada pi deixa resto 1 por 3 e cada qj deixa resto 2 por 3. Então
|
Um divisor de n2 deixa resto 1 por 3 se e somente se possuir uma quantidade par de primos qj, contados com repetição. Mais especificamente, se e somente se a soma dos expoentes de q1, ..., qm for par. Assim, a quantidade de divisores dessa forma é igual a:
|
Enquanto para se obter um divisor que deixe resto 2 por 3, precisamos de uma quantidade ímpar de fatores primos da forma 3k + 2. Assim, a quantidade de divisores dessa forma é:
|
Daí, segue facilmente que D1 > D2.