TEORIA DOS NÚMEROS - MÁXIMO DIVISOR COMUM (1)

MÁXIMO DIVISOR COMUM

6.1 – NÚMEROS PRIMOS E COMPOSTOS          Consideremos os números  positivos 12 e 19. Ao determinarmos os divisores positivos de 12 e de 19 teremos os seguintes conjuntos: D(12) = {1, 2, 3, 4, 6, 12} e D(19) = {1, 19}. Conforme pode ser visto, o inteiro positivo 12 tem, além dos divisores triviais 1 e 12 outros divisores. Entretanto, os divisores de 19 são apenas os triviais 1 e 19. Números como o 12 são chamados de números compostos e números como o 19 são chamados de números primos. Podemos assim, definir:          Um número inteiro positivo é denominado número primo, se e somente se, seus únicos divisores positivos forem 1 e ele mesmo. Um número não primo é chamado de número composto. 6.2 – DETERMINAÇÃO DE NÚMEROS PRIMOS – CRIVO DE ERATÓSTENES          Um procedimento útil para determinar os números primos até o inteiro positivo consiste em construir uma tabela onde são indicados todos os inteiros de 2 até n. A seguir, cortam-se todos os múltiplos dos números primos p, tais p<   n , isto é cortam os inteiros p, 2p, 3p ....          Tomando por exemplo os inteiros de 2 até 200, teremos: 14  <       < 15   como o primo mais próximo de   200 é 13, basta que se eliminem os múltiplos dos primos de 2 até 13.

Eliminados todos os múltiplos de 2 - 3 - 5 - 7 - 9 e 13, com exceção destes,sobram os números 2 - 3 - 5 - 7 - 13 - 17 -  19 - 23 - 29 -  31 -  37 - 43 - 47 - 53 - 59 -  61 - 67 - 83 - 89 - 97 - 101 - 103 - 107 - 109 - 113 - 121 - 127 - 131 - 139 - 149 - 151 - 157 - 163 - 167 - 171 - 173 - 179 - 181 - 187 - 193 - 197 e 199, que são os números primos menores que 200.         Para determinar se um número n é ou não primo, basta então dividir tal número pelos primos a partir de 2. Quando o quociente tornar-se menor que o divisor e nenhuma divisão der resto zero, o número é primo. Exemplo: verificar de 631 é ou não primo.         Dividindo 631 por 2, 3, 5, 7, 11, 13, 17, 19, 21, 23 e 29 todos os restos são diferentes de zero (as divisões não são exatas). Nas divisões por 2, 3, 5, ... 23, o quociente é maior que o divisor (maior que 2, 3, 5, ...23, respectivamente). Entretanto, na divisão por 29 o quociente é 21 (menor que 29). Assim, 631 é um número primo.         Já o número 437 é um composto pois ao dividi-lo por 19, o quociente é 23 e o resto é zero.         A tabela acima pode ser usada para verificar se um número até 2002 = 40000 é ou não primo. EXERCÍCIOS: 1 – Verifique se os números 169, 197, 239, 473, 917, 1013 são ou não primos. 6.3 – DECOMPOSIÇÃO EM FATORES PRIMOS          Todo número composto pode ser decomposto em 2 ou mais fatores. Tomando por exemplo o número 72, teremos  72 = 4 x 18  ou 72 = 3 x 4 x 6. Se continuarmos decompondo encontraremos  72 = 2 x 2 x 2 x 3 x 3 = 23 x 32. Como os fatores 2 e 3 são primos não há forma de continuar a decomposição. A decomposição de 72 na forma 2 x 2 x 2 x 3 x 3 é chamada de decomposição em fatores primos ou decomposição canônica.          Com relação à decomposição temos: - A decomposição canônica em fatores primos é única. - Todo número composto pode ser decomposto em fatores primos. - Se a forma da decomposição de um inteiro positivo N é p1a1.p2a2.p3a3...pnan, então o número de divisores inteiros de N é d(N) = (a1 + 1)(a2 + 1)(a3 + 1)...(an + 1) Exemplo: A decomposição canônica de 600 é   600 = 23 x 3 x 52. Isto implica que 600 tem (3 + 1)(1 + 1)(2 + 1) = 4 x 2 x 3 = 24 divisores ou d(600) = 24. EXERCÍCIOS 1 – Achar todos os primos da forma n2 – n. 2 – Achar três primos ímpares cuja soma seja (a) 81      (b) 125 3 – Achar todos os pares de primos p e q tais que p – q = 3. 4 – Achar todos os primos que são iguais a um quadrado perfeito menos 1. 5 – Ache a decomposição canônica de 5400. 6 – Quantos divisores positivos tem o número 5400?   7 – Na decomposição de um número positivo com 30 divisores positivos, a decomposição canônica fornece 25.3a. Determine o valor de a e o número.