NÚMEROS PRIMOS : Construção de um critério de solução
Publicado em 13 de outubro de 2010 por Jandira Zanchi
Sabemos que os primeiros números primos são 1, 2, 3, 5 e 7 . Facilmente poderemos observar que todos os outros números primos, que se seguem a esses, poderão ser construídos a partir de duas listas. Em ambas a razão será 6, sendo 5 o primeiro termo de uma das listas, e sete o primeiro termo da outra. Em nenhuma das duas vão aparecer múltiplos de três, mas não teremos como evitar os múltiplos de 5, que serão descartados. Apresentamos, abaixo, as duas listas, que já não trazem os múltiplos de 5, e aonde assinalamos aqueles números que não são primos :
LISTA 1 :
5, 11, 17, 23, 29, 41, 53, 59, 71, 77, 83, 89, 101, 107, 113, 119, 131, 137, 143, 149, 161, 167, 173, 179, 191, 197, 203, 209, 221, 227, 233, 239, 251, 257, 263, 269, 281, 287, 293, 299, 305, 311, 317, 323, 329, 341, 347, 353, 359, 371, 377, 383, 389, 401, 407, 413, 419, 431, 437, 443, 449, 461, 467, 473, 479, 491, 497...
LISTA 2 :
7, 13, 19, 31, 37, 43, 49, 61, 67, 73, 79, 91, 97, 103, 109, 121, 127, 133, 139, 151, 157, 163, 169, 181, 187, 193, 199, 211, 217, 223, 229, 241, 247, 253, 259, 271, 277, 283, 289, 301, 307, 313, 319, 331. 337, 343, 349, 361, 367, 373, 379, 391, 397, 403, 409, 421, 427, 433, 439, 451, 457, 463, 469, 481, 487, 493, 499...
Vamos unir as duas listas e construir uma terceira , em ordem crescente, com os números que não são primos :
49, 77, 91, 119, 121, 133, 143, 161, 169, 187, 203, 209, 217, 221, 247, 253, 259, 287, 289, 299, 301, 319, 323, 329, 341, 361, 371, 377, 391, 403, 407, 413, 427, 437, 451, 469, 473, 481, 493, 497.
Das muitas observações que se poderiam fazer sobre os números dessas listas que não são primos, uma parece especialmente importante : cada um desses números será divisível pôr pelo menos um dos primos que o antecedem e cujo quadrado é menor do que este número. Sabemos que se um desses números se revela como um número não primo é porque é obtido pelo produto de dois números primos, evidentemente menores do que ele. O que se observa, porém, é mais interessante : se, pôr exemplo, 323, como de fato, não é primo, então 323 deve ser divisível pôr 7 ou 11 ou 13 ou 17, ou dois desses números, pois os quadrados serão respectivamente 49, 121, 169 e 289, todos números menores do que 323. A bem da verdade 323 é obtido
pelo produto de 17 pôr 19, e notaríamos que o quadrado de 19 é 361, número maior do 323. O que interessa, porém, é que pelo menos um dos números primos cujo quadrado é menor do que 323 aparece no produto. Verifiquemos a seguir a fatoração dos não primos até 500 :
Divisíveis por 7 :
49 = 7x7 287 = 7x41
77 = 7x11 301 = 7x43
91 = 7x13 329 = 7x47
119 = 7x17 371 = 7x53
133 = 7x19 413 = 7x59
161 = 7x23 469 = 7x67
203 = 7x29 497 = 7x71
217 = 7x31
259 = 7x37
Divisíveis por 11 :
121 = 11x11 319 = 11x29
143 = 11x13 341 = 11x31
187 = 11x17 407 = 11x37
209 = 11x19 451 = 11x41
253 = 11x23 473 = 11x43
Divisíveis por 13 :
169 = 13x13 377 = 13x29
221 = 13x17 403 = 13x31
247 = 13x19 481 = 13x37
299 = 13x23
Divisíveis por 17 :
289 = 17x17 391 = 17x23
323 = 17x19 493 = 17x29
Divisíveis por 19 :
361 = 19x19
Do que foi exposto concluímos que qualquer número não primo que esteja incluído nas duas listas deve ser obtido pelo produto de um primo cujo quadrado é menor do que ele. Abaixo examinamos essa ocorrência :
- 11x11= 121 ,7 é o primo anterior a 11, e seu quadrado é 49, logo se 121 x 49,
x pertence à nossa lista de não primos, x é divisível pôr 7, e x = yx7, aonde y é
um primo qualquer:
49 = 7x7, 77 = 11x7, 91 = 13x7, 119 = 17x7
- para 121 x169 , x deve ser obtido pelo produto de dois primos aonde pelo menos um deles é 7 ou 11, pois 13x13 = 169 :
121 = 11x11, 133 = 19x7, 143 = 13x11 , 161 = 23x7
- para 169 x 289 , x deverá ser múltiplo de 7, 11 ou 13 :
169 = 13x13 , 187 = 17x11, 203 = 29x17, 209 = 19x11, 217 = 31x7
221 = 17x13 , 247 = 19x13, 253 = 23x11, 259 = 37x7 , 287 = 41x7
- para 289 x 361 , x deverá ser múltiplo de 7, 11, 13 ou 17 :
289 = 17x17, 299 = 23x13, 301 = 43x7 , 319 = 29x11 , 323 = 19x17
329 = 47x7 , 341 = 31x11
- para 361 x 529 , x deverá ser múltiplo de 7, 11, 13, 17 ou 19 :
361 = 19x19, 371 = 53x7 , 377 = 29x13 , 391 = 23x17 , 403 = 31x13
407 = 37x11, 413 = 59x7 , 427 = 61x7 , 437 = 23x19 , 451 = 41x11
469 = 67x7 , 473 = 43x11, 481 = 37x13 , 493 = 29x17 , 497 = 71x7
CRITÉRIO : estamos em condição de formular um critério para a construção de listas de números primos, e em conseqüência, de números não primos , excluídas, evidentemente, as possibilidades do número, ímpar, ser múltiplo de 3 ou 5 :
1º) subtrairemos ou somaremos 1 ao número, e depois dividiremos o resultado pôr 6. Se o resto for 0, o número pode ser primo, pelo critério de construção das duas primeiras listas.
2º) dividiremos o número pelo números primos cujo quadrado for menor do que ele, ou, se x é o número examinado, x deve ser dividido pôr y, desde que y seja primo e
x yxy . Se x não for divisível pôr nenhum dos y, então x é primo, não sendo necessário fazer a divisão de x pôr qualquer número cujo quadrado seja maior do que ele.
Exemplos :
a) x = 1073 :
1º) 1073 +1 = 1074 : 6 = 179, logo 1073 é um candidato à primo.
2º) 1073 = 32,7 , logo 1073 deve ser dividido pelos números primos :
7,11,13,17,19,23,29 e 31. Verificaremos que 1073 : 29 = 27 , logo
1073 não é primo.
b) x = 727 : 1º) 727 ? 1 = 726 : 6 = 121, 727 é um candidato a primo.
2º) 727 = 26,96, logo 727 deve ser dividido pelos números primos:
7,11,13,17,19 e 23. Vamos verificar que 727 não é divisível pôr
nenhum desses números logo podemos afirmar que 727 é primo.
c) x = 3223 : 1º) 3223 ? 1 = 3222 : 6 = 537, 3223 é um candidato a primo.
2º} 3223 = 56,77, logo 3223 deve ser dividido pelos números primos :
7,11,13,17,19,23,29.31,37,41,43,47 e 53. Verificaremos que 3223
é divisível pôr 11, logo 3223 não é um número primo.
Essa é a única maneira de listarmos os números primos?
Podemos construir outras listas como as que iniciaram esse capítulo, sempre duas, de muitas maneiras:
a) uma curiosidade, seria usarmos o número 5 para construção fazendo duas listas, a primeira, dos múltiplos ímpares de 5, soma e subtraí 2 de cada múltiplo; a segunda, dos múltiplos pares de 5, soma e subtraí 1 de cada múltiplo, e nas duas listas vão aparecer múltiplos de 3, que descartaremos :
LISTA 1 : 3,7,13,17,23, 37,43,47,53,67....
LISTA 2 : 11,19,29,31,49,59,61,71....
Veremos que serão listados todos os candidatos a números primos à semelhança das duas primeiras listas construídas com A1 = 5, A1 = 7 e r = 3. Segue :
para os ímpares : 5 , 5 ? 2 = 3 , 5 + 2 = 7
15, 15 ? 2 = 13, 15 + 2 = 17
25, 25 ? 2 = 23, 25 + 2 = 27 ......
para os pares : 10, 10 ? 1 = 9 , 10 + 1 = 11
20, 20 ? 1 = 19, 20 + 1 = 21
30, 30 ? 1 = 29, 30 + 1 = 31....
b ) no Exemplo 2, abaixo, veremos listas construídas em que A1 = 1 e r =3, A1 = 2 e r = 3, no Exemplo 3 teremos A1 = 1 e r= 4, A1= 3 e r =4:
EXEMPLO 2 :
LISTA 1 : 5,8,11,14,17,20,23,26,29,32,35,38,41,44...
LISTA 2 : 7,10,13,16,19,22,25,28,31,34,37,40.43......
EXEMPLO 3 :
LISTA 1 : 5,9,13,17,21,25,29,33,37,41,45......
LISTA 2 : 7,11,15,19,23,27,31,35,39,43,47....
Veremos que todos os números primos vão aparecer, como anteriormente, listados em uma ou outra das listas. Porém, além dos múltiplos de 5, não conseguiremos evitar os múltiplos de 3 no exemplo 2 e os números pares no exemplo 1. Portanto a razão 6 oferece vantagens. Pôr outro lado usando a razão 6 é possível listarmos os ímpares candidatos a primo em uma única lista, fazendo um pequeno artifício: pensamos em cada múltiplo de 6 e dele tiramos um e somamos um, não conseguiremos novamente excluir os múltiplos de 5 ? que descartaremos ? mas teremos as duas listas que originaram o critério em uma só :
5,7,11,13,17,19, 23,29, 31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97....
pois : 06 , 6 ? 1 = 5 , 6 + 1 = 7
12 , 12 ? 1 = 11 , 12 + 1 = 13
18 , 18 ? 1 =17 , 18 + 1 = 19
24 , 24 ? 1 = 23 , 24 + 1 = 25 .......
Assim sendo nossa lista de números candidatos a números primos pode ser única :
5,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89.91.97.101, 103,107,109,113,119,121, 127,131,133,137,139,143,149,151,157,161,163,167,169,
173,179,181,187,191,193,197,199,203,209,211,217,221,223,227,229,233,239,241,
243,247,251,253,257,259,263,269,271,277,281,283,287,289,293,299,301,307,311,313,317,319,323,329,331,337,341,343,347,349,353,359,361,367,
371,373,377,379, 383,389,391, 397,401,403,407,409,413,419,421,427,431,433,437,439,443,449,451,
457,461,463,467,469,473,479,481,487,491,493,497,499...
aonde assinalamos, em negrito, os números que não são primos.
LISTA 1 :
5, 11, 17, 23, 29, 41, 53, 59, 71, 77, 83, 89, 101, 107, 113, 119, 131, 137, 143, 149, 161, 167, 173, 179, 191, 197, 203, 209, 221, 227, 233, 239, 251, 257, 263, 269, 281, 287, 293, 299, 305, 311, 317, 323, 329, 341, 347, 353, 359, 371, 377, 383, 389, 401, 407, 413, 419, 431, 437, 443, 449, 461, 467, 473, 479, 491, 497...
LISTA 2 :
7, 13, 19, 31, 37, 43, 49, 61, 67, 73, 79, 91, 97, 103, 109, 121, 127, 133, 139, 151, 157, 163, 169, 181, 187, 193, 199, 211, 217, 223, 229, 241, 247, 253, 259, 271, 277, 283, 289, 301, 307, 313, 319, 331. 337, 343, 349, 361, 367, 373, 379, 391, 397, 403, 409, 421, 427, 433, 439, 451, 457, 463, 469, 481, 487, 493, 499...
Vamos unir as duas listas e construir uma terceira , em ordem crescente, com os números que não são primos :
49, 77, 91, 119, 121, 133, 143, 161, 169, 187, 203, 209, 217, 221, 247, 253, 259, 287, 289, 299, 301, 319, 323, 329, 341, 361, 371, 377, 391, 403, 407, 413, 427, 437, 451, 469, 473, 481, 493, 497.
Das muitas observações que se poderiam fazer sobre os números dessas listas que não são primos, uma parece especialmente importante : cada um desses números será divisível pôr pelo menos um dos primos que o antecedem e cujo quadrado é menor do que este número. Sabemos que se um desses números se revela como um número não primo é porque é obtido pelo produto de dois números primos, evidentemente menores do que ele. O que se observa, porém, é mais interessante : se, pôr exemplo, 323, como de fato, não é primo, então 323 deve ser divisível pôr 7 ou 11 ou 13 ou 17, ou dois desses números, pois os quadrados serão respectivamente 49, 121, 169 e 289, todos números menores do que 323. A bem da verdade 323 é obtido
pelo produto de 17 pôr 19, e notaríamos que o quadrado de 19 é 361, número maior do 323. O que interessa, porém, é que pelo menos um dos números primos cujo quadrado é menor do que 323 aparece no produto. Verifiquemos a seguir a fatoração dos não primos até 500 :
Divisíveis por 7 :
49 = 7x7 287 = 7x41
77 = 7x11 301 = 7x43
91 = 7x13 329 = 7x47
119 = 7x17 371 = 7x53
133 = 7x19 413 = 7x59
161 = 7x23 469 = 7x67
203 = 7x29 497 = 7x71
217 = 7x31
259 = 7x37
Divisíveis por 11 :
121 = 11x11 319 = 11x29
143 = 11x13 341 = 11x31
187 = 11x17 407 = 11x37
209 = 11x19 451 = 11x41
253 = 11x23 473 = 11x43
Divisíveis por 13 :
169 = 13x13 377 = 13x29
221 = 13x17 403 = 13x31
247 = 13x19 481 = 13x37
299 = 13x23
Divisíveis por 17 :
289 = 17x17 391 = 17x23
323 = 17x19 493 = 17x29
Divisíveis por 19 :
361 = 19x19
Do que foi exposto concluímos que qualquer número não primo que esteja incluído nas duas listas deve ser obtido pelo produto de um primo cujo quadrado é menor do que ele. Abaixo examinamos essa ocorrência :
- 11x11= 121 ,7 é o primo anterior a 11, e seu quadrado é 49, logo se 121 x 49,
x pertence à nossa lista de não primos, x é divisível pôr 7, e x = yx7, aonde y é
um primo qualquer:
49 = 7x7, 77 = 11x7, 91 = 13x7, 119 = 17x7
- para 121 x169 , x deve ser obtido pelo produto de dois primos aonde pelo menos um deles é 7 ou 11, pois 13x13 = 169 :
121 = 11x11, 133 = 19x7, 143 = 13x11 , 161 = 23x7
- para 169 x 289 , x deverá ser múltiplo de 7, 11 ou 13 :
169 = 13x13 , 187 = 17x11, 203 = 29x17, 209 = 19x11, 217 = 31x7
221 = 17x13 , 247 = 19x13, 253 = 23x11, 259 = 37x7 , 287 = 41x7
- para 289 x 361 , x deverá ser múltiplo de 7, 11, 13 ou 17 :
289 = 17x17, 299 = 23x13, 301 = 43x7 , 319 = 29x11 , 323 = 19x17
329 = 47x7 , 341 = 31x11
- para 361 x 529 , x deverá ser múltiplo de 7, 11, 13, 17 ou 19 :
361 = 19x19, 371 = 53x7 , 377 = 29x13 , 391 = 23x17 , 403 = 31x13
407 = 37x11, 413 = 59x7 , 427 = 61x7 , 437 = 23x19 , 451 = 41x11
469 = 67x7 , 473 = 43x11, 481 = 37x13 , 493 = 29x17 , 497 = 71x7
CRITÉRIO : estamos em condição de formular um critério para a construção de listas de números primos, e em conseqüência, de números não primos , excluídas, evidentemente, as possibilidades do número, ímpar, ser múltiplo de 3 ou 5 :
1º) subtrairemos ou somaremos 1 ao número, e depois dividiremos o resultado pôr 6. Se o resto for 0, o número pode ser primo, pelo critério de construção das duas primeiras listas.
2º) dividiremos o número pelo números primos cujo quadrado for menor do que ele, ou, se x é o número examinado, x deve ser dividido pôr y, desde que y seja primo e
x yxy . Se x não for divisível pôr nenhum dos y, então x é primo, não sendo necessário fazer a divisão de x pôr qualquer número cujo quadrado seja maior do que ele.
Exemplos :
a) x = 1073 :
1º) 1073 +1 = 1074 : 6 = 179, logo 1073 é um candidato à primo.
2º) 1073 = 32,7 , logo 1073 deve ser dividido pelos números primos :
7,11,13,17,19,23,29 e 31. Verificaremos que 1073 : 29 = 27 , logo
1073 não é primo.
b) x = 727 : 1º) 727 ? 1 = 726 : 6 = 121, 727 é um candidato a primo.
2º) 727 = 26,96, logo 727 deve ser dividido pelos números primos:
7,11,13,17,19 e 23. Vamos verificar que 727 não é divisível pôr
nenhum desses números logo podemos afirmar que 727 é primo.
c) x = 3223 : 1º) 3223 ? 1 = 3222 : 6 = 537, 3223 é um candidato a primo.
2º} 3223 = 56,77, logo 3223 deve ser dividido pelos números primos :
7,11,13,17,19,23,29.31,37,41,43,47 e 53. Verificaremos que 3223
é divisível pôr 11, logo 3223 não é um número primo.
Essa é a única maneira de listarmos os números primos?
Podemos construir outras listas como as que iniciaram esse capítulo, sempre duas, de muitas maneiras:
a) uma curiosidade, seria usarmos o número 5 para construção fazendo duas listas, a primeira, dos múltiplos ímpares de 5, soma e subtraí 2 de cada múltiplo; a segunda, dos múltiplos pares de 5, soma e subtraí 1 de cada múltiplo, e nas duas listas vão aparecer múltiplos de 3, que descartaremos :
LISTA 1 : 3,7,13,17,23, 37,43,47,53,67....
LISTA 2 : 11,19,29,31,49,59,61,71....
Veremos que serão listados todos os candidatos a números primos à semelhança das duas primeiras listas construídas com A1 = 5, A1 = 7 e r = 3. Segue :
para os ímpares : 5 , 5 ? 2 = 3 , 5 + 2 = 7
15, 15 ? 2 = 13, 15 + 2 = 17
25, 25 ? 2 = 23, 25 + 2 = 27 ......
para os pares : 10, 10 ? 1 = 9 , 10 + 1 = 11
20, 20 ? 1 = 19, 20 + 1 = 21
30, 30 ? 1 = 29, 30 + 1 = 31....
b ) no Exemplo 2, abaixo, veremos listas construídas em que A1 = 1 e r =3, A1 = 2 e r = 3, no Exemplo 3 teremos A1 = 1 e r= 4, A1= 3 e r =4:
EXEMPLO 2 :
LISTA 1 : 5,8,11,14,17,20,23,26,29,32,35,38,41,44...
LISTA 2 : 7,10,13,16,19,22,25,28,31,34,37,40.43......
EXEMPLO 3 :
LISTA 1 : 5,9,13,17,21,25,29,33,37,41,45......
LISTA 2 : 7,11,15,19,23,27,31,35,39,43,47....
Veremos que todos os números primos vão aparecer, como anteriormente, listados em uma ou outra das listas. Porém, além dos múltiplos de 5, não conseguiremos evitar os múltiplos de 3 no exemplo 2 e os números pares no exemplo 1. Portanto a razão 6 oferece vantagens. Pôr outro lado usando a razão 6 é possível listarmos os ímpares candidatos a primo em uma única lista, fazendo um pequeno artifício: pensamos em cada múltiplo de 6 e dele tiramos um e somamos um, não conseguiremos novamente excluir os múltiplos de 5 ? que descartaremos ? mas teremos as duas listas que originaram o critério em uma só :
5,7,11,13,17,19, 23,29, 31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89,91,97....
pois : 06 , 6 ? 1 = 5 , 6 + 1 = 7
12 , 12 ? 1 = 11 , 12 + 1 = 13
18 , 18 ? 1 =17 , 18 + 1 = 19
24 , 24 ? 1 = 23 , 24 + 1 = 25 .......
Assim sendo nossa lista de números candidatos a números primos pode ser única :
5,7,11,13,17,19,23,29,31,37,41,43,47,49,53,59,61,67,71,73,77,79,83,89.91.97.101, 103,107,109,113,119,121, 127,131,133,137,139,143,149,151,157,161,163,167,169,
173,179,181,187,191,193,197,199,203,209,211,217,221,223,227,229,233,239,241,
243,247,251,253,257,259,263,269,271,277,281,283,287,289,293,299,301,307,311,313,317,319,323,329,331,337,341,343,347,349,353,359,361,367,
371,373,377,379, 383,389,391, 397,401,403,407,409,413,419,421,427,431,433,437,439,443,449,451,
457,461,463,467,469,473,479,481,487,491,493,497,499...
aonde assinalamos, em negrito, os números que não são primos.