1.3 NÚMEROS PRIMOS, MÁXIMO DIVISOR COMUM E MÍNIMO MÚLTIPLO COMUM

Estudamos nas páginas anteriores somente os critérios de divisibilidade por 2 , 3 , 4 , 5 , 8 , 9 e 11. Existem outros critérios, por exemplo, por 6 , por 7, mas acreditamos que para o momento não serão necessários. O que precisamos agora é conhecer alguns números primos. A definição de número primo é a seguinte:

    Algumas vezes não é necessário conhecermos os divisores de um número e sim quantos divisores tem o número. O problema dos armários que vem a seguir ilustra essa situação. Para resolvê-lo não é necessário conhecermos todos os divisores do número 100, basta saber que o número 100 tem 9 divisores (número ímpar de divisores).

EXEMPLO 3.1

    Numa escola, ao longo de um corredor comprido, estão enfileirados 100 armários, numerados consecutivamente de 1 a 100, com suas portas fechadas. Cem alunos da escola, também numerados de 1 a 100, resolvem fazer a seguinte brincadeira:

O aluno número 1 passa pelo corredor e abre todos os armários; em seguida o aluno número 2 passa e fecha todos os armários de número par; depois passa o aluno número 3 e inverte a posição das portas de todos os armários “múltiplos de três” isto é, ele os fecha se estiverem abertos e os abre se estiverem fechados; depois, é a vez do número 4 que inverte a posição das portas dos armários “múltiplos de 4”, e assim sucessivamente. Após a passagem dos 100 alunos, qual será o armário de maior número que estará fechado?

Dá para ter uma idéia por onde começar?

• O primeiro passo é tentar entender o problema fazendo tabelas ou desenhos. Vamos voltar ao enunciado.

    São 100 armários numerados e com suas portas fechadas.

    Os alunos mexem nas portas dos armários, abrindo se estiverem fechadas e fechando se estiverem abertas.

• De que modo mexem nas portas os cem alunos?

A resposta está no enunciado do problema:

  - o aluno número 1 passa pelo corredor e abre todos os armários;
  - o aluno número 2 passa e fecha todos os armários de número par e deixa os armários ímpares como estavam ;
  - o aluno número 3 e inverte a posição das portas de todos os armários “múltiplos de três”;
  - o número 4 inverte a posição das portas dos armários “múltiplos de 4”, e assim sucessivamente.

    Vamos fazer um quadro para visualizar melhor essas condições. Na primeira linha da tabela colocamos os armários numerados e na primeira coluna os alunos também numerados. Para a palavra fechado usamos a letra F e a letra A para aberto.

Examinemos o armário 4: o aluno número 1 abre esse armário, o aluno número 2 o fecha, o 3 não faz nada, o 4 o abre, o 5 não mexe, o 6 não mexe, etc.

Examinemos o armário 98: o aluno número 1 abre esse armário, o aluno número 2 fecha, o 3 não mexe, o 4 não mexe, o 5 não faz nada, o 6 não mexe, o 7 abre, o 8 não mexe, o 14 fecha, o 49 abre, o 98 fecha.

Examinemos o armário 99: o aluno número 1 abre esse armário, o aluno número 3 o fecha, o 9 abre, o 11 fecha, o 33 abre e o 99 fecha.

Portanto, mexem no armário 100 os alunos números: 1, 2, 4, 5, 10, 20, 25, 50 e 100. O aluno 1 abre, o aluno 2 fecha, o aluno 4 abre, 5 fecha, 10 abre, 20 fecha, 25 abre, 50 fecha e 100 abre.

Conclusão: depois de passarem os 100 alunos, o armário de número 100 estará aberto.

Como 10 é par, o armário de número 48 estará fechado

      Ainda sobre número de divisores.

      VIRANDO AS CARTAS

    Disponha de um naipe completo de um baralho, do Ás ao Rei, que corresponde numericamente do 1 ao 13.

• Comece colocando as cartas, por ordem, da esquerda para a direita, com a face numérica voltada para baixo.

• Siga os seguintes passos, por ordem, começando sempre da esquerda para a direita:

           1. Vire todas as cartas.
           2. Vire todas as cartas que são múltiplos de 2.
           3. Vire todas as cartas que são múltiplos de 3.
           4. Continue o processo, virando, sucessivamente, todas as cartas que são múltiplas de 4, 5, ... , de 13.

• Tente descobrir porque razão apareceu a seqüência: 1, 4 e 9.

    A comunicação entre computadores pela Internet cria novos desafios àqueles que trabalham com a criptografia. A cada dia torna-se necessário inventar novos códigos que sejam difíceis de decifrar. Os códigos usados em aplicações comerciais, e não na espionagem são denominados códigos de chave pública. Em um código de chave pública é possível codificar, mas é muito difícil decodificar, pois nem sempre o desfazer um processo é simples.

    Para a codificação do método de criptografia de chave pública é preciso conhecer um número não primo, produto de dois números primos e para decodificar é preciso conhecer os dois números primos. Parece tudo muito simples. Essa tarefa por enquanto é impossível, não existem critérios nem expressões que definam quaisquer números primos. Mesmo se os computadores mais poderosos do mundo fossem usados para decompor um imenso número não primo, seriam necessários vários anos para obter uma resposta. O problema fica então reduzido a responder duas questões:

1. Como fatorar um número tão grande?

2. Como determinar se um número é primo ou não?

                     Existem muitos algoritmos de fatoração, alguns são úteis para uma chave pública e
           outros para diferentes chaves. Muitas pesquisas ainda estão por fazer. As portas estão abertas

           para aqueles que gostam da Teoria dos Números.

Observando a tabela:

A afirmação falha para n=41. Também não é verdadeira para outros valores de n.

    Existem muitos números primos, há 168 números primos entre 1 e 1000, 135 entre 1000 e 2000 e 127 entre 2000 e 3000. Mesmo usando os computadores, há limitações para pesquisas de buscas de números primos. Euclides, 300 a.C. apresentou uma demonstração garantindo que o conjunto dos números primos é infinito.

    Vamos fornecer uma pequena tabela de números primos que pode auxiliar no cálculo do máximo divisor comum e na resolução de problemas. No “site” http://www.gregosetroianos.mat.br encontramos uma tabela com mais elementos.

             Um outro problema de números deixado por Fermat que ficou conhecido como o Último Teorema de Fermat só foi resolvido depois de 350 anos, em 1995, pelo matemático inglês Andrew Wiles, usando muita matemática sofisticada.

           Sugerimos aos alunos a leitura do interessante livro: de SINGH,Simon. O último teorema de Fermat: a história do enigma que confundiu as maiores mentes do mundo durante 358 anos. Tradução de Jorge Luiz Calife.- 2aed.- Rio de Janeiro: Record, 1998.


EXEMPLO 3.2