n es divisible por un número primo (es decir, él mismo) y ya está. Se n no é primo, então, como se analisa no exemplo 4.1.2b, n r0s0 onde r0 e s0 s...

n es divisible por un número primo (es decir, él mismo) y ya está. Se n no é primo, então, como se analisa no exemplo 4.1.2b, n r0s0 onde r0 e s0 são números inteiros e 1 r0 n e 1 s0 n. O que se deduz pela definição de divisibilidade que r0 n. Se r0 é primo, então r0 é um número primo que divide a n e já está. Se r0 não é primo, então r0 r1s1 onde r1 e s1 são números inteiros e 1 r1 r0 e 1 s1 r0. O que se deduz pela definição de divisibilidade que r1 r0. Mas já sabemos que r0 n. Em consequência, por transitividade da divisibilidade, r1 n. Se r1 é primo, então r1 é um número primo que divide a n e já está. Se r1 não é primo, então r1 r2s2 onde r2 e s2 são números inteiros e 1 r2 r1 e 1 s2 r1. O que se deduz pela definição de divisibilidade que r2 r1. Mas já sabemos que r1 n. Em consequência, por transitividade da divisibilidade, r2 n. Se r2 é primo, então r2 é um número primo que divide a n e já está. Se r2 não é primo, então podemos repetir o processo anterior fatorizando a r2 como r3s3. Podemos continuar de esta maneira, fatorizando os fatores sucessivos de n até que encontremos um fator primo. Devemos ter sucesso em um número finito de passos, já que cada novo fator é menor que o anterior (que é menor que n) e maior que 1 e há poucos inteiros n que estritamente se encontram entre 1 e n. Assim se obtém uma sucessão r0, r1, r2, . . . , rk, onde k 0, 1 rk rk ฀1 . . . r2 r1 r0 n e ri n para cada i 0, 1, 2, . . . , k. A condição de terminação é que rk deve ser primo. Por tanto rk é um número primo que divide a n. [Isto é o que se queria demonstrar.] Contraexemplos e divisibilidade Para demonstrar que uma propriedade de divisibilidade proposta não é uma verdade universal, só é necessário encontrar um par de números inteiros para os quais é falso. Exemplo 4.3.7 Comprovação de uma propriedade de divisibilidade proposta ¿É o seguinte enunciado verdadeiro ou falso? Para todos os números inteiros a e b, se a b e b a então a b. Solução Este enunciado é falso. ¿Pode pensar em um único contraexemplo concentrando-se durante um minuto ou algo assim? O análise seguinte descreve um processo mental que pode tomar uns poucos segundos. No entanto, é útil poder usarlo conscientemente, para resolver os problemas mais difíceis. Para descobrir a verdade ou falsidade de um enunciado como a que se acaba de dar, comece como se estivesse tratando de prová-lo. Ponto de partida: Suponhamos que a e b são números inteiros tais que a b e b a. Pergunte-se: ¿Devo supor que a b, ou poderia suceder que a b para alguma a e b? Concéntrese na suposição. ¿O que significa? Por definição de divisibilidade, as condições a b e b a significam que b ka e a lb para alguns inteiros k e l. ¿Deve seguir que a b, ou se podem encontrar números inteiros a e b que satisfaçam estas equações para as que a b? As equações implicam que b ka k(lb) (kl)b Já que b a, b 0 e assim você pode eliminar a b do extremo esquerdo e do lado direito para obter 1 kl. Em outras palavras, k e l são divisores de 1. Mas, por o teorema 4.3.2, os únicos divisores de 1 são 1 e ฀ 1. Assim k e l são ambos 1 ou ambos ฀1. Se k l 1, então b a. Mas Estrictamente falando, este enunciado se justifica por um axioma dos números inteiros chamado o princípio da boa ordem, que se analisa na seção 5.4. O teorema 4.3.4 também se pode provar com indução matemática forte, tal como se mostra no exemplo 5.4.1. si k l ฀1, então b ฀a e assim a b. Este análise sugere que você pode encontrar um contraexemplo tomando b ฀a. Apresentamos uma resposta formal: Proposta da propriedade de divisibilidade: Para todos os números inteiros a e b, se a b e b a então a b. Contraexemplo: Seja a 2 e b ฀2. Então, a b já que 2 (฀2) e b a já que (฀2) 2, mas a b já que 2 ฀2. Por tanto, o enunciado é falso. A busca de uma demonstração com frequência le ajudará a descobrir um contraexemplo (supondo que o enunciado que estão tratando de demonstrar é, de fato, falso). Pelo contrário, ao tratar de encontrar um contraexemplo para o enunciado, pode chegar a darse conta de para que razão é verdadeiro (se é, de fato, verdadeiro). O importante é manter uma mente aberta até que esteja convencido pela evidência de seu próprio raciocínio cuidadoso. Teorema de fatorização única de inteiros O enunciado mais completo sobre divisibilidade de inteiros se encontra no teorema de fatorização única de inteiros. Devido a sua importância este teorema também se conhece como o teorema fundamental da aritmética. Aunque Euclides, viveu ao redor do 300 a.C., parece haver estado familiarizado com o teorema, o primeiro em estabelecê-lo precisamente foi o grande matemático alemão Carl Friedrich Gauss (rima com house(casa em inglês)) em 1801. O teorema de fatorização única de números inteiros, diz que qualquer número inteiro maior que 1 é primo ou se pode escrever como um produto de números primos de uma forma que é única, exceto, quizá, por a ordem em que se escrevem os primos. Por exemplo, 72 2 2 2 3 3 2 3 3 2 2 3 2 2 3 2 e assim sucesivamente. Os três 2 e dois 3 se pode escrever em qualquer ordem, mas qualquer fatorização de 72 como produto de primos deverá conter exatamente três 2 e dois 3; nenhum outro conjunto de números primos, além de três 2 e dois 3 multiplicados dão 72. Teorema 4.3.5 Teorema de fatorização única de números inteiros (teorema fundamental da aritmética) Dado qualquer número inteiro n 1, existe um inteiro positivo k, de números primos distintos, p1, p2, . . . pk e números inteiros positivos e1, e2, . . . ek tal que n pe1 1 pe2 2 pe3 3 pek k e qualquer outra expressão para n como produto de números primos é idêntico a este, exceto, quizá, por a ordem em que se escrevem os fatores. A demonstração do teorema de fatorização única se descreve nos exercícios para as seções 5.4 e 8.4. Devido ao teorema de fatorização única, qualquer inteiro n 1 se pode pôr em uma forma fatorizada estándar em a que os fatores primos se escrevem em ordem ascendente de esquerda a direita. Nota Este teorema é a razão de por que não se le permite ao número 1 ser primo. Se 1 fuese primo, então as factorizações não seriam únicas. Por exemplo, 6 2 3 1 2 3 e assim sucesivamente. Definição Dado qualquer número inteiro n 1, a forma fatorizada estándar de n é uma expressão de a forma n pe1 1 pe2 2 pe3 3 pek k onde k é um inteiro positivo, p1, p2, . . . pk são números primos, e1, e2, . . . ek são inteiros positivos e p1 p2 . . . pk. Exemplo 4.3.8 Escritura de números inteiros em a forma fatorizada estándar Escreva 3 300 em a forma fatorizada estándar. Solução Primeiro encontre todos os fatores de 3 300. Depois escreva em ordem ascendente: 3 300 100 33 4 25 3 11 2 2 5 5 3 11 22 31 52 111. Exemplo 4.3.9 Uso de a factorização única para resolver um problema Suponhamos que m é um inteiro tal que 8 7 6 5 4 3 2 m 17 16 15 14 13