Baixe Livro de Teoria dos Números e outras Notas de estudo em PDF para Matemática, somente na Docsity! UNIVERSIDADE DO ESTADO DO PARÁ CENTRO DE CIÊNCIAS SOCIAIS E EDUCAÇÃO DEPARTAMENTO DE MATEMÁTICA, ESTATÍSTICA E INFORMÁTICA. LICENCIATURA EM MATEMÁTICA MODALIDADE A DISTÂNCIA DISCIPLINA: TEORIA DOS NÚMEROS CONTÉUDO PROGRAMÁTICO: INTRODUÇÃO AO ESTUDO DA TEORIA DOS NÚMEROS: UNIDADE I – NÚMEROS INTEIROS: 1.1 - Números inteiros. 1.2 - Propiedades dos inteiros; 1.3 - Valor absoluto de um inteiro; 1.4 - Questões Resolvidas e Propostas. UNIDADE II – INDUÇÃO MATAMÁTICA: 2.1 - Elemento mínimo de um conjunto de inteiros. 2.2 - Princípio da boa ordenação; 2.3 - Princípio de indução finita; 2.4 - Indução matemática; 2.5 - Exemplos de demonstração por indução matemática e outras formas de indução matemática; 2.6 - Questões Resolvidas e Propostas. UNIDADE III – DIVISIBILIDADE: 3.1 - Relação de divisibilidade em Z. 3.2 - Conjunto dos divisores de um inteiro; 3.3 - Divisores comuns de dois inteiros; 3.4 - Algoritmo da divisão; 3.5 - Paridade de um inteiro; 3.6 - Questões Resolvidas e Propostas. UNIDADE IV – MÁXIMO DIVISOR COMUM: 4.1 - Máximo divisor comum de dois inteiros. 4.2 - Existência e unicidade do mdc; 4.3 - Inteiros primo entre si; 4.4 - Caracterização do mdc de dois inteiros; 4.5 - Mdc de vários inteiros; 4.6 - Questões Resolvidas e Propostas. UNIDADE V – ALGORITMO DE EUCLIDES MÍNIMO MÚLTIPLO COMUM: 5.1 - Algoritmo de EUCLIDES. 5.2 - Múltiplos comuns de dois inteiros; 5.3 - Mínimo múltiplo comum de dois inteiros; 5.4 - Relação entre o mdc e o mmc; 5.5 - Mmc de vários inteiros; 5.6 - Questões Resolvidas e Propostas. UNIDADE VI – NÚMEROS PRIMOS: 6.1 - Números primos e compostos. 6.2 - Teorema fundamental da Aritmética; 6.3 - Formula que dão primos; 6.4 - Crivo de ERATÓSTENES; 6.5 - Primos gêmeos; 6.6 - Seqüências de inteiros consecutivos compostos; 6.7 - Conjectura de GOLDBACH; 6.8 - Método de fatoração de FERMAT; 6.9 - Questões Resolvidas e Propostas. em vários campos, de acordo com os métodos que são usados e das questões que são investigadas, a saber: 1) Teoria elementar dos números: utiliza somente os métodos elementares da aritmética para a verificação e comprovação das propriedades essenciais do conjunto dos números inteiros e em particular as propriedades dos números primos. 2) Teoria analítica dos números: utiliza a análise real e análise complexa, especialmente para estudar as propriedades dos números primos. 3) Teoria algébrica dos números: utiliza álgebra abstrata e estuda os números algébricos. 4) Teoria geométrica dos números: utiliza métodos geométricos, algébricos e analíticos. Nesta notas faremos o estudo da primeira Teoria, um conceito chave em Teoria elementar dos Números é o conceito de divisibilidade. Enquanto nos números reais, por exemplo, pode-se dividir qualquer número por outro (não nulo), obtendo como resultado um número real, nos inteiros é diferente. Um inteiro a só é divisível pelo inteiro b quando existir um inteiro c tal que a = bc. Nesse caso, diz-se também que b é um divisor de a, ou que b divide a, ou ainda que a é múltiplo de b. Por exemplo, 8 é divisível por 2, mas não é por 3. Mesmo que a não seja divisível por b, pode-se sempre encontrar, de modo único, inteiros c (quociente) e r (resto) tais que a = bc + r. Todo inteiro a é divisível por 1, -1, a, -a. Estes são os divisores triviais de a. Um inteiro é dito primo quando só possui os divisores triviais. Um inteiro de valor absoluto maior que 1 e que não seja primo (isto é, possua divisores não triviais) é dito composto. Por exemplo: São primos: 2, - 2, 3, -3, 17, .... São compostos 6 = 2x3, -8 = (-2) x 4, ... Os números 0, 1 e –1 não são primos nem compostos. Euclides foi o primeiro a demonstrar que existe uma infinidade de números primos. O máximo divisor comum dos inteiros não nulos a e b tem a propriedade de ser múltiplo de qualquer divisor comum de a e b e pode ser encontrado pelo algoritmo de Euclides. Quando o máximo divisor comum de a e b for 1, então seus únicos divisores comuns são 1 e –1. Nesse caso, a e b são ditos primos entre si, ou relativamente primos. Por exemplo, 9 e 14 são primos entre si. As propriedades mais cruciais dos números inteiros, e que não têm similares nos reais ou nos complexos, são o Princípio da Boa Ordenação, segundo o qual qualquer conjunto não vazio de inteiros limitado inferiormente possui um elemento mínimo, e o Princípio de Indução, segundo o qual se uma propriedade P(n), referente ao inteiro n, for verdadeira para n = a, e a veracidade de P(n) acarretar a veracidade de P(n + 1), então P(n) é verdadeira para todo inteiro maior que ou igual a a. A partir das propriedades usuais da adição e da multiplicação de inteiros, da relação <, e do Princípio da Boa Ordenação (ou do de Indução, que lhe é equivalente), é possível construir toda a Teoria dos Números. Um de seus resultados mais importantes é o Teorema Fundamental da Aritmética, segundo o qual todo inteiro (diferente de 0, 1 e –1) pode ser escrito de modo único como um produto de fatores primos. Uma das características da Teoria dos Números é que ela inclui problemas extremamente simples de enunciar e ao mesmo tempo incrivelmente difíceis de resolver. Um exemplo é a conjectura de Feuerbach: "todo número par é a soma de dois números primos"; ninguém até hoje conseguiu decidir se isto é verdadeiro ou falso. Outro exemplo é o famoso Último Teorema de Fermat: "Dado um inteiro n maior que 2, é impossível encontrar inteiros não nulos x, y, z tais que x n + y n = z n ". Este teorema, enunciado no século XVII por Fermat, que só foi demonstrado em 1995, por Wiles. Gauss, o "príncipe dos matemáticos", dizia que a Matemática era a rainha das ciências, e a Aritmética, a rainha das Matemáticas. Gauss desenvolveu muita a Teoria dos Números. Aos 22 anos, em 1799, publicou em latim suas "Investigações Aritméticas", onde introduziu o importante conceito de congruência para números inteiros. O matemático inglês Hardy, grande especialista em Teoria dos Números, orgulhava-se, em 1940, de que "nenhuma descoberta sua havia feito, nem provavelmente viria a fazer, direta ou indiretamente, alguma diferença para o conforto da humanidade". No entanto, 50 anos depois, um obscuro matemático americano descobriria uma falha no recém lançado processador Pentium, ao realizar cálculos "inúteis" sobre primos gêmeos (números primos que diferem de 2). Mas já no próprio momento em que Hardy escrevia aquela frase, durante a segunda guerra mundial, três americanos desenvolviam um sistema de código secreto, chamado SRA, baseado nas dificuldades insuperáveis para descobrir os fatores primos de um número muito grande. Criava-se um novo ramo a Criptografia, a ciência dos códigos, fortemente baseado em Teoria dos Números. Com o advento dos computadores e da computação algébrica, a Criptografia ganhou um novo impulso. Neste momento, a proliferação de senhas bancárias e de cartões de crédito, bem como a crescente necessidade de criptografar dados confidenciais que inundam a Internet, faz da Criptografia um dos ramos mais em moda da Matemática aplicada. E um dos mais úteis, para desespero póstumo de Hardy. UNIDADE I – NÚMEROS INTEIROS 1 - Introdução: A noção de número está, através dos tempos, associada a todos os tipos de atividades humanas. A primeira concepção de número data do período paleolítico. Poucos progressos se fizeram neste campo até se dar a transição para o período neolítico, durante o qual já existia uma atividade comercial importante entre diversas povoações. Esta atividade promoveu a formação de linguagens, cujas palavras exprimiam coisas muito concretas e poucas abstrações, mas onde já havia lugar para alguns termos numéricos simples. Estes termos numéricos destinavam-se apenas a estabelecer a distinção entre um, dois e muitos. Depois de durante milênios ter utilizado os números para contar, medir, calcular, o homem começou a especular sobre a natureza e propriedades dos próprios números. Desta curiosidade nasceu a Teoria dos Números, um dos ramos mais profundos da matemática. A Teoria dos Números nasceu cerca de 600 anos antes de Cristo quando Pitágoras e os seus discípulos começaram a estudar as propriedades dos números inteiros. Os pitagóricos rendiam verdadeiro culto místico ao conceito de número, considerando-o como essência das coisas. Acreditavam que tudo no universo estava relacionado com números inteiros ou razões de números inteiros (em linguagem atual, números racionais). Aliás, na antiguidade a designação número aplicava-se só aos inteiros maiores do que um. Esta crença foi profundamente abalada quando usaram o Teorema de Pitágoras para calcular a medida da diagonal de um quadrado unitário. Com efeito, a diagonal divide o quadrado em dois triângulos retângulos isósceles cujos catetos têm comprimento um e assim, pelo teorema de Pitágoras, a medida da hipotenusa é igual à raiz quadrada de dois, que não pode ser expresso como quociente de inteiros. Ao descobrirem que a diagonal de um quadrado de lado 1 não era uma razão entre dois inteiros (em linguagem atual, que a raiz quadrada de 2 é um número irracional) os Pitagóricos consideraram quebrada a harmonia do universo, já que não podiam aceitar a raiz quadrada de dois como um número, mas não podiam negar que esta raiz era a medida da diagonal de um quadrado unitário. Convencidos de que os deuses os castigariam caso divulgassem aquilo que lhes parecia uma imperfeição divina, tentaram ocultar a sua descoberta. Segundo reza a lenda, o primeiro membro da seita pitagórica que divulgou esta descoberta morreu afogado. Este fato teve grandes repercussões na história da ciência que se fizeram sentir até finais do século XIX. De cada vez que as necessidades do cálculo levavam a introduzir novos entes numéricos gerava-se uma enorme desconfiança à sua volta, o que levava a atribuir-lhes designações curiosas. Assim, os números irracionais eram designados por números inexprimíveis e por números incalculáveis. Durante muitos séculos os números reais (fracionarias ou racionais e irracionais) Questões Resolvidas 01) Calcular a soma dos “n” primeiros inteiros positivos. Solução: Vamos escrever a soma dos n primeiros números inteiros positivos em ordem crescente e a mesma soma em ordem decrescente, temos: S = 1 + 2 + 3 + 4 + ........ + n – 3 + n – 2 + n – 1 + n S = n + n – 1 + n – 2 + n – 3 + ........ + 4 + 3 + 2 + 1 Somando as duas igualdades: 2S = (n + 1) + (n + 1) + (n + 1) + (n + 1) + .............. + (n + 1) + (n + 1) + (n + 1) + (n + 1) Observe que serão n parcelas iguais a (n + 1). Portanto, 2S = n(n + 1)  S = n(n + 1)/2. 02) Calcular o inteiro positivo n, sabendo que 3 n+2 2 n+3 = 2592. Solução: Decompondo 2592, obtém-se 3 4 .2 5 . Portanto, n + 2 = 4  n = 2, ou 5 = n + 3  n = 2. Pois a forma de decomposição em fatores primos é única. 03) Achar um inteiro positivo de dois algarismos que seja igual ao quádruplo da soma dos seus algarismos. Solução: Um número de algarismos a e b, na base 10 é expresso por 10a + b. Portanto, 10a + b = 4(a + b)  6a = 3b  b = 2a. Ou seja, qualquer número de dois algarismos, onde o algarismo das unidades é o dobro do algarismo das unidades. Assim, temos: 12, 24, 36, etc. 04) Achar o menor e o maior inteiro positivo de n algarismos. Solução: Menor: 1º algarismo igual a 1 e os demais (n – 1) iguais a zero. Portanto, 1 x 10 n – 1 . Maior: todos os n algarismos iguais a 9, ou 1 seguido de n zeros menos 1 1.10 n – 1 Observação: Considerando, n = 5. Menor 10000 = 1.10 5 – 1 = 1.10 4 Maior 99999 = 100000 – 1 = 1.10 5 – 1. 05) Achar todas as soluções inteiras e positivas da equação: x 2 – y 2 = 88. Solução: x 2 – y 2 = 88  (x + y) (x – y) = 88. Como x e y são inteiros positivos, (x + y) e (x – y) são dois números inteiros cujo produto é 88. Assim, (1) x + y = 88 e x – y = 1; (2) x + y = 44 e x – y = 2; (3) x + y = 22 e x – y = 4; (4) x + y = 11 e x – y = 8. Cada par de duas equações formam um sistema. Para resolver o sistema basta somar as duas equações, o que resultaria em 2x = soma dos números. Como essa soma tem que ser par (x é inteiro), resulta apenas as possibilidades 2 e 3. Portanto, 2x = 46  x = 23 e y = 44 – 23 = 21 ou 2x = 26  x = 13 e y = 22 – 13 = 9. Resposta: (x = 23, y = 21) e (x = 13, y = 9). 06) O produto de um inteiro positivo de três algarismos por 7 termina à direita por 638. Achar esse inteiro. Solução: Para facilitar o raciocínio, construamos a tabela de multiplicação por 7. 7 x 1 = 7, 7 x 2 = 14, 7 x 3 = 21, 7 x 4 = 28, 7 x 5 = 35, 7 x 6 = 42, 7 x 7 = 49, 7 x 8 = 56, 7 x 9 = 63. Como o algarismo das unidades é 8, o único valor possível para o algarismos das unidades do número é 4. Ao efetuar a multiplicação do algarismo das unidades, que é 4 por 8, vão duas unidades para a casa das dezenas. Assim, o algarismo das dezenas deve ser tal que ao multiplicar por 7 e somar 2, resulte num final igual a 3. Portanto, o algarismo das dezenas é 3, pois 7 x 3 + 2 = 23. Da mesma forma vão duas unidades para a casa das centenas. O algarismo aí deve ser de forma que, ao somar 2 (vindo das dezenas) resulte em 6. Portanto, deve ser um múltiplo de 7 terminado em 4. Isto permite concluir que o algarismo das centenas é 2 , pois 2 x 7 + 2 = 16. Portanto, o número é 234. 07) Um livro tem 1235 páginas. Determinar o número de vezes que o algarismo 1 aparece na numeração da páginas deste livro. Solução: De 1 a 100, o algarismo 1 aparece 10 vezes nas unidades (1, 11, 21,... 91) e 10 vezes nas dezenas (10, 11, 12, ...19). Portanto a cada centena o algarismo 1 aparece 20 vezes. Em 1235 temos 12 centenas. Portanto o algarismo 1 aparecerá 20 x 12 = 240 vezes na posição das unidades e dezenas. De 100 a 200, o algarismo 1 aparece 100 vezes na posição das centenas. Isto se repete de 1100 a 1200. Portanto, 200 vezes na posição das centenas. De 1200 a 1236, o algarismo 1 aparece 4 vezes nas unidades e 10 vezes nas dezenas. Totalizando 14 vezes. De 1000 a 1235, o algarismo 1 aparece 236 vezes na posição dos milhares. Portanto: 240 + 200 + 14 + 236 = 690 vezes. 08) Achar o inteiro que deve ser somado a cada um dos inteiros 2, 6 e 14 para que, nesta ordem, formem uma proporção contínua. Solução: Uma proporção contínua é aquela que tem os meios ou os extremos iguais. Pela definição podemos ter (a) (2 + x)/(6 + x) = (6 + x)/(14 + x) ou (2 + x)/(6 + x) = (14 + x)/(2 + x). Na situação (a), (6 + x) 6 + x) = (2 + x) (14 + x) => 36 + 12x + 2x = 28 + 16x + 2x  4x = 8  x = 2. Na situação (b) (2 + x) (2 + x) = (6 + x) (14 + x)  4 + 4x + 2x = 84 + 20x + 2x  16x = - 80  x = - 5. R: 2 ou –5. 09) Achar o menor inteiro cujo produto por 21 é um inteiro formado apenas por 4 algarismo. Solução: O número é o menor múltiplo de 21 maior que 1000. Portanto: 1000 = 47 x 21 + 13. Portanto, o número é 48 x 21 = 1008. 10) Escreve-se a seqüência natural dos inteiros positivos, sem separar os algarismos: 123456789101112131415... Determinar: (a) O 435º algarismo. Solução: De 1 a 9 são escritos 9 algarismos. De 10 a 99, são dois algarismos em cada número  2 x 90 = 180 algarismos. Portanto, até 100 são escritos: 9 + 180 + 3 = 192. Para chegar ao algarismo que ocupa o 435º lugar serão necessários mais 435 – 192 = 243 algarismos. Como a partir de 100 são usados 3 algarismos teríamos 243 3 = 81 números após o 100. Portanto, o número é 181 e o algarismo que ocupa a posição é o 1. (b) O 1756º algarismo. Solução: Da mesma forma 1756 – 192 = 1564  1564 3 = 521 e sobra 1 algarismo. Portanto teríamos até a 100 + 521 = 621. Como sobra 1 algarismo, o próximo é o 6 do número 622. (c) O 12387º algarismo. Solução: Até 1000 seriam 9 + 90 x 2 + 900 x 3 + 4 = 2889. 12387 – 2889 = 9498  9498 4 = 2374 e sobram dois algarismo. Portanto, o último número inteiro é 1000 + 2374 = 3374. A sobra de dois algarismos implica que o último algarismo será 3, o segundo algarismo de 3375. 11) Mostrar que o produto de dois fatores entre 10 e 20 é o décuplo da soma do primeiro com as unidades do segundo mais o produto das unidades dos dois. Solução: Sejam os números 10 + b e 10 + c, com 0 < b < 10 e 0 < c < 10. Nestas condições 10 + b e 10 + c estarão compreendidos entre 10 e 20 e b e c serão os algarismos das unidades. Efetuando o produto temos: (10 + b) (10 + b) = 100 + 10b + 10c + bc = 10[(10 + b) + c] + bc. (10 + b) + c é a soma do primeiro com as unidades do segundo, bc é o produto dos dois e 10[(10 + b) + c] é o décuplo da soma do primeiro com as unidades do segundo. UNIDADE II – INDUÇÃO MATEMÁTICA 2.1 - Introdução: O Princípio da Indução é um eficiente instrumento para a demonstração de fatos referentes aos números naturais. Por isso deve-se adquirir prática em sua utilização. Por outro lado, é importante também conhecer seu significado e sua posição dentro do arcabouço da Matemática. Entender o Princípio da Indução é praticamente o mesmo que entender os números naturais. Apresentamos abaixo uma breve exposição sobre os números naturais, onde o Princípio da Indução se insere adequadamente e mostra sua força teórica antes de ser utilizado na lista de exercícios propostos ao final. 2.2 - A Seqüência dos Números Naturais: Os números naturais constituem um modelo matemático, uma escala padrão, que nos permite a operação de contagem. A seqüência desses números é uma livre e antiga criação do espírito humano. Comparar conjuntos de objetos com essa escala abstrata ideal é o processo que torna mais precisa a noção de quantidade; esse processo (a contagem) pressupõe, portanto o conhecimento da seqüência numérica. Sabemos que os números naturais são 1, 2, 3, 4, 5,… A totalidade desses números constitui um conjunto, que indicaremos com o símbolo N e que chamaremos de conjunto dos naturais. Portanto N = {1, 2, 3, 4, 5,…}. Evidentemente, o que acabamos de dizer só faz sentido quando já se sabe o que é um número natural. Façamos de conta que esse conceito nos é desconhecido e procuremos investigar o que há de essencial na seqüência 1, 2, 3, 4, 5… . Deve-se a Giussepe Peano (1858 - 1932) a constatação de que se pode elaborar toda a teoria dos números naturais a partir de quatro fatos básicos, conhecidos atualmente como os axiomas de Peano. Noutras palavras, o conjunto N dos números naturais possui quatro propriedades fundamentais, das quais resultam, como conseqüências lógicas, todas as afirmações verdadeiras que se podem fazer sobre esses números. 2.3 - Elemento Mínimo: Definição 1.1 - Seja A um conjunto de inteiros. Chama-se elemento mínimo de A um elemento a A tal que a x para todo x A. Notação: a = min A. min A = a se, e somente se, (a A e ( x A) a x). Teorema: Se a é elemento mínimo de A, então este elemento é único. 2.4 - Princípio da Boa Ordenação (PBO). Todo conjunto não vazio A, de inteiros não negativos, possui elemento mínimo. A Z+, A , existe min A. 2.5 - Indução Matemática: Teorema: Seja P(n) uma proposição associada a cada inteiro positivo n e que satisfaz às duas seguintes condições: 1) P(1) é verdadeira. 2) Para todo inteiro k, se P(k) é verdadeira, então P(k + 1) também é verdadeira. Nestas condições, a proposição P(n) é verdadeira para todo inteiro positivo n. 2.6 - Princípio da Indução Finita (PIF). Teorema: Seja S um subconjunto do conjunto N dos inteiros positivos (S N) que satisfaz as duas seguintes propriedades: 1) 1 pertence a S (1 S). 2) Para todo inteiro positivo k, se k S, então (k + 1) S; 3) Nestas condições, S é o conjunto N dos inteiros positivos: S = N. 2.7 - Outra Forma da Indução Matemática: Teorema: Seja r um número inteiro positivo fixo e seja P(n) uma proposição associada a cada inteiro n r e que satisfaça às duas seguintes condições: 1) P(r) é verdadeira. 2) Para todo inteiro k r, se P(k) é verdadeiro, então P(k + 1) é verdadeiro; 3) Nestas condições, P(n) é verdadeira para todo inteiro n r. Questões Resolvidas 01) Demonstrar por "indução matemática", as questões abaixo: 1) 1 2 + 2 2 + 3 2 + ... + n 2 = 6 )1n2)(1n(n n N. Solução: P(1) é verdadeira, pois 1 2 = 6 3.2.1 . Suponhamos que para P(k) é verdadeira: 1 2 + 2 2 + 3 2 + ... + k 2 = 6 )1k2)(1k(k . Somando (k + 1) 2 a ambos os membros: 1 2 + 2 2 + 3 2 + ... + k 2 + (1 + k) 2 = 6 )1k2)(1k(k + (k + 1) 2 = 6 )1k(6)1k2)(1k(k 2 = 6 )1k(6)1k2(k)1k( = 6 )6k6kk2)(1k( 2 = 6 )3k2)(2k)(1k( Logo P(k + 1) é verdadeira. 2) 1 3 + 2 3 + 3 3 + ... + n 3 = 4 )1n(n 22 n N. Solução: P(1) é verdadeira, pois 1 3 = 4 )11(1 22 . Suponhamos que para P(k) é verdadeira: 1 3 + 2 3 + 3 3 + ... + k 3 = 4 )1k(k 22 Somando (k + 1) 3 a ambos os membros 1 3 + 2 3 + 3 3 + ... + k 3 + (k + 1) 3 = 4 )1k(k 22 + (k + 1) 3 = 4 )1k(4)1k(k 322 = 4 )1k(4k)1k( 22 = 4 )4k4k()1k( 22 = 4 )2k()1k( 22 Logo P(k + 1) é verdadeira. 3) 1 2 + 3 2 + 5 2 + ... + (2n – 1) 2 = 3 )1n4(n 2 n N. Solução: P(1) é verdadeira, pois 1 2 = 3 )11.4(1 2 Suponhamos que para P(k) é verdadeira: 1 2 + 3 2 + 5 2 + ... + (2k – 1) 2 = 3 )1k4(k 2 Somando (2k + 1) 2 a ambos os membros 1 2 + 3 2 + 5 2 + ... + (2k – 1) 2 + (2k + 1) 2 = 3 )1k4(k 2 + (2k + 1) 2 = 3 )1k2(3)1k2)(1k2(k 2 = 3 )1k2(3)1k2(k)1k2( = 3 )3k5k2)(1k2( 2 = 3 )3k2)(1k)(1k2( = 3 )3k2)(1k2)(1k( Logo P(k + 1) é verdadeira. 4) 1 3 + 3 3 + 5 3 + ... + (2n –1) 3 = n 2 (2n 2 – 1) Solução: P(1) é verdadeira, pois 1 3 = 1 2 (2.1 2 – 1). Suponhamos que para P(k) é verdadeira: 1 3 + 3 3 + 5 3 + ... + (2k –1) 3 = k 2 (2k 2 – 1). Somando (2k + 1) 3 a ambos os membros 1 3 + 3 3 + 5 3 + ... + (2k –1) 3 + (2k + 1) 3 = k 2 (2k 2 – 1) + (2k + 1) 3 = 2k 4 – k 2 + 8k 3 + 12k 2 + 6k + 1 = 2k 4 + 8k 3 + 11k 2 + 6k + 1 = (k + 1)(2k 3 + 6k 2 + 5k + 1) = (k + 1)(k + 1)(2k 2 + 4k + 1) = (k + 1) 2 (2(k + 1) 2 – 1) Logo P(k + 1) é verdadeira. Questões Propostas 01) Demonstrar por “indução matemática”, as questões abaixo: 1) 1 + 3 + 5 + ... + (2n –1) = n 2 n  . 10) 2n 1 ... 9 1 4 1 1 2 – n 1 , n  . 2) 1 2 n n 1 1 1 1 1 n 2 2 2 2   . 11) 1 2 n n 2 2 2 1 1 , n 3 3 3 3   . 3) n + 1 2 n 1 r1 r r r , n 1 r   . 12) n(n 1) 1 2 3 n , n 2   . 4) (n 1)(4 + 3n) 2 5 8 (2 3n) , n 2   . 13) 0 1 2 n 1 n2 2 2 2 2 1, n  . 5) 2 2 2 2 n(n 1)(2n + 1) 1 2 3 n , n 6   . 14) 2 3 3 3 3 n(n 1)1 2 3 n n 2   . 6) 6 | n(n +1)(n + 2) n  . 15) 4 3 3 3 3 n1 2 3 n , n 4   . 7) 2 | (n 2 + n) n  . 16) n(1 a) 1 na, n , a , a 1.  8) 1 1 1 1 n , n 1 2 2 3 3 4 n (n+1) n 1   17) 3 | (22n –1) n  . 9) 1 1 1 (1 1) 1 1 1 n 1, n 2 3 n   .18) 3 | (n3 + 2n) n  . 02) Usando o principio da "indução matemática", demonstrar: 1) O número de diagonais de um polígono convexo de n lados é: n n(n 3) d 2 . 2) A soma das medidas dos ângulos internos de um polígono convexo de n lados é: 0 nS (n 2) 180 . 3) Se A é um conjunto finito com n elementos, então (A) , conjunto das partes de A, tem 2 n elementos. 4) Prove que a soma de uma PG ou razão q de n termos e primeiro termo a1 é dado por n 1 n a (q 1) S q 1 . 5) Prove que uma P.G. de primeiro termo a1 e razão q o produto (Pn) dos n primeiros termos é dado por n(n - 1) n 2 n 1P a q , n 1. 6) Prove que numa PA. de primeiro termo a1 e razão r a soma (Sn) dos n primeiros termos é dado por n 1 n(n 1) S na r 2 . 7) Para n+ nr , θ e n 0, mostre que r (cosθ + isen θ) r (cosnθ + isen nθ)  , onde i2 = -1. 8) Sendo z um número complexo não-nulo e n 0 , mostre que n n( ) ( )z z . 9) Prove que numa o termo geral da P. A. é dado pela formula n 1a a (n 1)r . 10) Prove que 0 1 nn n n-1 n n n n n (a + b) a a b b , para n .C C C  11) Seja cosθ senθ A sen θ cosθ . Determine A n , para n 1. 12) Para x  e n 1, mostre que sen nx n sen x . 13) Demonstrar a lei de De Morgan (A B) ' A' B' , sobre n conjuntos. UNIDADE III – DIVISIBILIDADE 3.1 - Introdução: Sabemos, desde a escola básica, que quando um número inteiro e dividido por um segundo número inteiro não nulo, o quociente pode ou não ser um numero inteiro. Esta observação nos leva a seguinte definição. 3.2 - Divisibilidade: Definição 3.2 - Sejam a e b dois inteiros, com a 0. Diz-se que a divide b se, e somente se, existe um inteiro q tal que b = aq. Se a divide b também se diz que a é divisor de b, que b é múltiplo de a, que a é um fator de b ou que b é divisível por a. Notação: “a | b” (a 0 divide b e portanto, a notação “a | b” significa que a 0 não divide b). A relação “a divide b (a | b)” denomina-se relação de divisibilidade em  . Observação: Se a | b, então –a | b. Teorema 3.1: Quaisquer que sejam os inteiros a, b e c tem-se: (1) a | 0, a 0, 1 | a e a | a, a 0. (2) Se a | 1, então a = 1. (3) Se a | b e se c | d, então ac | bd. (4) Se a | b e se b | c, então a | c. (5) Se a | b e se b | a, então a = b. (6) Se a | b com b 0, então | a | | b |. (7) Se a | b e se a | c, então a |(bx + cy) para todos x e y em  . 3.3 - Conjunto de divisores de um inteiro: D(a) = {x  *| x | a}. 3.4 - Divisores comuns de dois inteiros: Definição 3.3: Chama-se divisor comum de dois inteiros a e b todo inteiro d 0 tal que d | a e d | b. Notação: D(a, b) = {x  * | x | a e x | b} Propriedade; D(a, b) = D(a) D(b). Obs.: D(a, b) ; D(0, 0) =  *. 3.5 - Algoritmo da Divisão: Teorema 3.2: Se a e b são dois inteiros, com b > 0, então existem e são únicos os inteiros q e r que satisfazem às condições: a = bq + r e 0 r < b. Corolário 3.2: Se a e b são dois inteiros com b 0, existem e são únicos os inteiros q e r que satisfazem às condições: a = bq + r, 0 r < | b |. 10) Na divisão do inteiro a = 427 por um inteiro positivo b o quociente é 12 e o resto é r. Achar o divisor b e o resto r. Solução:: De acordo com o algoritmo da divisão 427 = 12b + r, 0 r b ; onde 427 é o dividendo, b o divisor , 12 o quociente e r o resto. Desta igualdade tiramos: 427 –12b = r e daí 0 427 –12b < b. Somando 12b aos três membros da desigualdade, obtemos: 12b 427 < 13b. Da desigualdade 12b 427, tiramos b 35, 5 ou b 35. Da desigualdade 427 < 13b tiramos b > 32,8 ou b 33. Assim os valores para b são os inteiros no intervalo 33,35 ou 33, 34 e 35. Para b = 33, r = 427 – 12 x 33 = 31. Para b = 34, r = 427 – 12 x 34 = 19. Para b = 35, r = 427 – 12 x 35 = 7. 11) Achar um inteiro de quatro algarismos, quadrado perfeito, divisível por 27 e terminado em 6. Solução: Se a, b, c ... são fatores primos, os expoentes desses fatores devem ser par. Como 27 = 3 3 , deve-se ter pelo menos mais um 3 como fator. Portanto, o número deve ser múltiplo de 27 x 3 ou de 81. Para que o número termine em 6, devemos multiplicar 81 por um quadrado (pois 81 já é quadrado), terminado em 6, pois 81 termina em 1. Assim, temos as possibilidades 81 x 16 = 1296 e 81 x 36 = 2916. Se o número tivesse 6 fatores iguais a 3, ele deveria ser múltiplo de 729. Para que terminasse em 6, deveriamos ter 729 x a, com a terminado em 4. Como os menores quadrados terminados em quatro são 4 e 64, teríamo: 729 x 4 = 2916 e 729 x 64 = 46656 que tem 5 algarismos. Para 8 fatores iguais a 3, o número deveria ser múltiplo de 6561 = 38. Para que o número terminasse em 6, deveriamos ter 6561 x a, com a terminado em 4. Como os menores quadrados terminados em quatro são 4 e 64, teríamos 6561 x 4 = 26244 que contém cinco algarismos. Para 10 fatores iguais a 3, teríamos 310 > 10000, que terá mais de 4 algarismos. Portanto, os únicos números são 1296 e 2916. 12) Demonstrar que se m e n são inteiros ímpares, então 8 | (m 4 + n 4 – 2). Solução: se m e n são ímpares, podemos escrever: m = 2k + 1 e n = 2k’ + 1. Temos então: m 4 + n 4 - 2 = (2k + 1) 4 + (2k’ + 1) 4 – 2 = [(2k) 4 + 4(2k) 3 + 6(2k) 2 + 4(2k) + 1] + [(2k’) 4 + 4(2k') 3 + 6(2k’) 2 + 4(2k’)+1] – 2 = 16(k 4 + k’ 4 ) + 32(k 3 – k’ 3 ) + 24(k 2 + k’ 2 ) + 8(k + k’) + 2 – 2 = 8[2(k 4 + k’ 4 ) + 4(k 3 – k’ 3 ) + 3(k 2 + k’ 2 ) + (k + k’)]. Como 2(k 4 + k’ 4 ) + 4(k 3 – k’ 3 ) + 3(k 2 + k’ 2 ) + (k + k’)]. É um inteiro (multiplicação e adição de inteiros), podemos escrever: m 4 + n 4 - 2 = 8q, q inteiro  8 | (m 4 + n 4 – 2). Questões Propostas 01) Mostrar que, se a | b, então (-a) | b e a | (-b) e (-a) | (-b). 02) Sejam a, b e c inteiros. Mostrar: a) se a | b, então a | bc. b) Se a | b e se a | c, então a 2 | bc. c) a | b se, e somente se, ac | bc, (c 0). 03) Mostrar que um inteiro qualquer da forma 6k + 5 também é da forma 3k + 2. 04) Mostrar que o cubo de um inteiro qualquer é de uma das formas: 9k, 9k + 1 e 9k + 8. 05) Mostrar que, se a | (2x – 3y) e se a | (4x – 5y), então a | y. 06) Determinar os inteiros positivos que divididos por 17 deixam um resto igual ao quadrado do quociente. R: 18, 38, 60 e 84. 07) Na divisão do inteiro 525 por um inteiro positivo o resto é 27. Achar os inteiros que podem ser o divisor e o quociente. R: b = 498 e q = 1; b = 249 e q = 2; b = 166 e q = 3 e b = 83 e q = 6. 08) Na divisão de dois inteiros positivos o quociente é 16 e o resto o maior possível. Achar os dois inteiros, sabendo que a sua soma é 341. R: a = 322, b = 19. 09) Achar os inteiros positivos menores que 150 e que divididos por 39 deixam um resto igual ao quociente. R: q = 1, 2, 3 e a = 40, 80, 120. 10) Seja d um divisor de n (d | n). Mostrar que cd | n se, e somente se, c | n d . 11) Mostrar que para todo inteiro n, existem inteiros k e r tais que n = 3k + r e r = –1, 0, 1. 12) Mostrar que todo inteiro ímpar, quadrado perfeito, é da forma 4n + 1. 13) Na divisão de 392 por 45, determinar: a) o maior inteiro que se pode somar ao dividendo sem alterar o quociente. R: 12. b) o maior inteiro que se pode subtrair do dividendo sem alterar o quociente. R: 32. 14) Numa divisão de dois inteiros, o quociente é 16 e o resto 167. Determinar o maior inteiro que se pode somar ao dividendo e ao divisor sem alterar o quociente. R: 11. 15) Achar o maior inteiro de quatro algarismos divisível por 13 e o menor inteiro de cinco algarismos divisível por 15. R: maior 9997 e o menor é 10.005. UNIDADE IV – MÁXIMO DIVISOR COMUM - M. D. C 4.1 - Introdução: Fazem parte do ensino fundamental, entre outras, as noções de Máximo Divisor Comum (MDC), Mínimo Múltiplo Comum (MMC), Números primos e Fatoração, que compõem uma parcela significativa da Teoria Elementar dos Números. No caso específico M.D.C, pretendemos mostrar a relevância destes através da abordagem de exercícios para o aprofundamento teórico e após o estudo do M.M.C veremos aplicações de forma contextualizada. 4.2 - Máximo Divisor Comum: Definição 4.1 - Dados dois ou mais números inteiros não nulos denominamos máximo divisor comum destes números ao maior número inteiro que é divisor simultaneamente de todos os números dados. O mdc é o maior elemento da intersecção dos conjuntos dos divisores positivos dos números dados. Definição 4.2 - Sejam a e b dois inteiros não conjuntamente nulos (a 0 ou b 0). Chama-se máximo divisor comum de a e b o inteiro positivo d (d > 0) que satisfaz às condições: 1) d | a e d | b. 2) Se c | a e c | b, então c d. Notação: d = mdc(a, b). 4.3 - Existência e Unicidade do MDC: Teorema 4.1 - Se a e b são inteiros não conjuntamente nulos (a 0 ou b 0), então existe e é único o mdc(a,b); além disso, existem inteiros x e y tais que mdc(a, b) = ax + by, isto é, o mdc(a, b) é uma combinação linear de a e b. Teorema 4.2 - Se a e b são dois inteiros não conjuntamente nulos (a 0 ou b 0), então o conjunto de todos os múltiplos do mdc(a, b) = d é T = {ax + by | x,y Z}. 4.4 - Inteiros Primos entre si: Definição 4.3 - Sejam a e b dois inteiros não conjuntamente nulos (a 0 ou b 0). Diz-se que a e b são primos entre si se, e somente se, o mdc(a, b) = 1. Teorema 4.3 - Dois inteiros a e b, não conjuntamente nulos (a 0 ou b 0), são primos entre si se, e somente se, existe inteiros x e y tais que ax + by = 1. Corolário 4.1 - Se o mdc(a, b) = d, então mdc a b , d d = 1. Corolário 4.2 - Se a | b e se mdc(b, c) = 1, então o mdc(a, c) = 1. Corolário 4.3 - Se a | c, se b | c e se mdc(a, b) = 1, então ab | c. Corolário 4.4 - Se mdc(a, b) = 1 = mdc(a, c), então o mdc(a, bc) = 1. Solução: Se 6 = mdc(a, b) temos que 6 | a e 6 | b ou a = 6q1 e b = 6q2. Substituindo na igualdade a b = 756, temos 6q16q2 = 756. Daí obtemos que q1q2 = 21. Do mesmo modo, como q1 e q2 são primos entre si, devemos encontrar inteiros positivos cujo produto dê 21. Os valores são: q1 = 1 e q2 = 21 e q1 = 3 e q2 = 7. Destes valores tiramos os valores de a e b: a = 6 e b = 126 e a = 18 e b = 42. 10) Demonstrar que, se n = abc + 1, então o mdc (n, a) = mdc(n, b) = mdc(n, c) = 1. Solução: Provemos que mdc(n, a) = 1. O mesmo pode ser feito para b e c. Seja d = mdc(n, a). Então d | n e d | a. Podemos dizer, portanto, que d | abc, múltiplo de a. Como d | n e d | abc, então d | 1, pois n – abc = 1. Logo d = 1. 11) O mdc(a, 4) = 2 = mdc(b, 4). Demonstrar que o mdc(a + b, 4) = 4. Solução: Temos mdc(a, 4) = 2 e mdc(b, 4) = 2. Concluímos que a e b são números pares e não são múltiplos de 4 , pois se o fossem, 2 não seria o mdc entre eles. Logo o resto da divisão de a e b por 4 é 2. Assim a = 4q1 + 2 e b = 4q2 + 2. Somando membro a membro estas desigualdades, temos a + b = 4q1 + 2 + 4q2 + 2 ou a + b = 4 (q1 + q2 + 1). Logo, 4 | (a + b) e por conseguinte mdc(a + b, 4) = 4. 12) Sendo a e b dois inteiros não conjuntamente nulos (a 0 ou b 0), mostrar: mdc(a, b) = mdc(-a, b) = mdc(a, -b) = mdc(-a, -b). Solução: Se c | a então a = qc. Temos que - a = (-q)c  c | (-a)  todo divisor de a é divisor de (-a)  maior divisor de a é também o maior divisor de –a. O mesmo ocorre com b e –b. Portanto, podemos concluir que o maior divisor comum de (a e b), é também de (–a e b), de (a e –b) e o de (- a, -b). Assim, mdc(a, b) = mdc(-a, b) = mdc(a, -b) = mdc(-a, -b). 13) Demonstrar que mdc(mdc(a, b), b) = mdc(a, b). Solução: A definição do mdc de três números mdc(a, b, c) = mdc(mdc(a, b), c), quaisquer que sejam a, b e c. Fazendo c = b, temos mdc(mdc(a, b), b) = mdc(a, b, b) = mdc(a, mdc(b, b)) = mdc(a, b) pois mdc(b, b) = b. 14) Demonstrar que o mdc(n + k, k) = 1 se e somente se o mdc(n, k) = 1. Solução: Se mdc(n + k, k) = 1, então existem os inteiros x e y, tais que (n + k)x+ ky = 1  nx + k(a + b) = 1  (n, k) = 1. Por outro lado, se mdc(n, k) = 1, então existem a e b tais que na + kb = 1. Fazendo a = x e b = x + y, teremos nx + k(x + y) = 1  (n + k)x + ky = 1  mdc(n + k), k) = 1. 15) Calcular o mdc(a + b, a – b) sabendo que a e b são inteiros primos entre si. Solução: Se a e b são primos entre si, não podem ser ambos pares, pois o mdc seria 2 ou múltiplo de 2. Portanto, a e b são ambos ímpares ou são de paridades diferentes. (1º caso) a e b com paridades diferentes – (a = 2k + 1 b = 2k’) Temos então: a + b = 2k + 1 + 2k’ = 2(k + k’) + 1 = 2n + 1  a + b é ímpar. a – b = 2k + 1 – 2k’ = 2(k – k’) + 1 = 2m + 1  a – b é ímpar. Portanto, o mdc(a + b, a – b) é um número ímpar. Seja então mdc(a + b, a – b) = 2k + 1  existem x e y tais que (a + b)x + (a – b)y = 2k + 1  [(a + b)/(2k+1)]x + [(a – b)/(2k + 1)]y = 1  (a + b)/(2k + 1) e (a – b)/(k + 1) são primos entre si. Fazendo r = (a + b)/(2k + 1) e s = (a – b)/(2k + 1), resulta: a + b = r(2k + 1) (i) e a – b = s(2k + 1) (ii).Como (a + b), (a – b) e (2k + 1) são ímpares, r e s também são ímpares. Além disso r e s ímpares, r + s e r – s são pares. Somando membro a membro as igualdades (i) e (ii), resulta: (1) 2a = (2k + 1)(r + s)  a = (2k + 1)[(r + s)/2] pois s + r é par (inteiro), portanto 2 | (r + s). Assim, existe o inteiro (r + s)/2, tal que a = (2k + 1)[(r + s)/2)  2k + 1 | a. Subtraindo membro a membro as igualdades (i) e (ii), (2) 2b = (2k + 1)(r – s)  b = (2k + 1)[(r – s)/2]. (r – s) é par. Portanto, (r – s)/2 é inteiro. Assim, existe o inteiro (r – s)/2, tal que b = (2k + 1)[(r – s)/2]  2k + 1 | b. Ora, a e b são primos entre si. Portanto, o único divisor comum é 2k + 1. Disto permite-se escrever 2k + 1 = 1  1 = mdc(a + b, a – b). (2º caso) a e b são ímpares  a = 2k + 1 e b = 2k’ + 1. Temos, então: (a + b) = 2k + 1 + 2k’ + 1  (a + b) = 2(k + k’ + 1) (a – b) = 2k + 1 – 2k’ – 1 = 2(k – k’) Das igualdades acima, concluímos que (a + b) e (a – b) são pares. Portanto, o mdc é da forma 2k. Assim, existem x e y, tais que: (a + b)x + (a – b)y = 2k  r = (a + b)/2k e s = (a – b)/2k são primos entre si. (a + b) = 2kr (i) e (a – b) = 2ks (ii). Somando membro a membro, 2a = 2k(r + s)  a = k(r + s)  k | a. Subtraindo membro a membro, 2b = 2k(r – s)  b = k(r – s)  k | b. Como a e b são primos entre si, o único divisor comum de a e b é 1. Portanto, k = 1 e Mdc(a + b, a – b) = 2k  mdc(a + b, a – b) =2.1 = 2. Portanto, se a e b são primos então mdc(a + b, a – b) é 1 ou 2. 16) O mdc de dois inteiros positivos é 10 e o maior deles é 120. Determinar o outro inteiro. Solução: Seja a o outro número. “a” deve ser um múltiplo de 10 que não divide 120. Como o maior dos números e 120, a deve ser menor que 120. Os múltiplos de 10 que não dividem 120 são: 50, 70, 90 e 110. 17) O mdc(a, b) = p, sendo p um primo. Achar os possíveis valores do: ( a ) mdc(a 2 , b). Solução: Sejam a = p.a1.a2.a3 ...an, onde p, a1, a2, a3, ... an são os fatores primos de a e b = p.b1.b2.b3...bn, onde p, b1, b2, b3, ...bn são os fatores primos de b. Assim, a 2 = p.p.a1.a2.a2.a3a3...an.an  que a 2 e b são divisíveis ao mesmo tempo apenas por p.  mdc(a 2 , b) = p. ( b ) mdc(a 3 , b) = p, mesma conclusão acima. ( c ) mdc(a 2 , b 3 ) = p 2 . Pois aparecem 2 fatores iguais a p em a 2 e 3 fatores iguais a p em b 3 . 18) Sejam a e k inteiros não conjuntamente nulos. Demonstrar que mdc(a, a + k) | k. Solução: Seja m o mdc(a, a + k). Assim, existem os inteiros x e y tais que: a = mx e a + k = my. Subtraindo primeira igualdade da segunda resulta: (a + k) – a = my – mx  k = m(y – x). Como x e y são inteiros, y - x é inteiro. Portanto, existe o inteiro (y – x) tal que k = m(y – x)  m | k ou mdc(a, a + k) | k. 19) Seja o quadrado abaixo em que cada lado mede 3 cm. Quantos quadradinhos de 1cm² cabem no quadrado? R: 9 quadradinhos. Com o mesmo quadrado acima, obter o valor de 3². R: 3² = 9. 20) De quantos cubinhos de 1cm de lado, isto é, um centímetro cúbico, precisaremos para construir um cubo com 3cm de comprimento, 3cm de largura e 3cm de altura? R: 27 cubinhos. UNIDADE V – ALGORITMO DE EUCLIDES: MÍNIMO MÚLTIMPLO COMUM – M.M.C 5.1 - Introdução: Fazem parte do ensino fundamental, entre outras, as noções de Máximo Divisor Comum (MDC), Mínimo Múltiplo Comum (MMC), Números primos e Fatoração, que compõem uma parcela significativa da Teoria Elementar dos Números. No caso específico M.M.C, pretende-se mostrar a relevância destes através da abordagem de temas atuais onde aparecem e sua conexão com outras áreas do conhecimento. Com isso, visamos a contextualização e a interdisciplinaridade, ambas importantes para que o aluno veja a matemática como uma aliada na vida prática e sua relação com outras disciplinas. Neste sentido, busca-se que o aluno perceba que os números e a álgebra formam um sistema de códigos ligados especialmente a diversas aplicações. Definição 5.1 - Dados dois ou mais números inteiros não nulos denominamos mínimo múltiplo comum destes números dados ao menor número inteiro positivo que é múltiplo simultaneamente te todos os números dados. O mmc é o menor elemento da intersecção dos conjuntos dos múltiplos positivos dos números dados. Lema: 5.2 - Se a = bq + r, então mdc(a, b) = mdc(b, r): 5.3 - Algoritmo de Euclides: Sejam a e b dois inteiros não conjuntamente nulos (a 0 ou b 0) cujo máximo divisor comum se deseja determinar. 1) Se a 0, então mdc(a,0) = |a|. 2) Se a 0, então mdc(a,a) = |a|. 3) Se b | a, então o mdc(a,b) = |b|. 4) Se a não divide b e b não divide a, então a = bq + r e mdc(a, b) = mdc(b, r). Dispositivo prático para o cálculo do Máximo divisor comum de dois inteiros positivos a e b é denominado Algoritmo de Euclides. q1 q2 q3  qn qn - 1 a b r1 r2  rn - 1 rn r1 r2 r2 r4  0 Teorema 5.1 - Se k > 0, então o mdc(ka, kb) = k mdc(a, b). Corolário 5.1 - Para todo k 0, o mdc(ka, kb) = |k| mdc(a, b). 5.4 - Múltiplos Comuns de dois Inteiros: M(a) = {x Z | a | x} = {aq | q Z}. M(1) = M(–1) = Z. Definição 5.2 - Sejam a e b dois inteiros diferentes de zero (a 0 e b 0). Chama-se múltiplo comum de a e b todo inteiro x tal que a | x e b | x. M(a, b) = M(a) M(b). 5.5 - Mínimo Múltiplo Comum: Definição 5.3 - Sejam a e b dois inteiros diferentes de zero (a 0 e b 0). Chama-se mínimo múltiplo comum de a e b o inteiro positivo m (m > 0) que satisfaz às condições: 1. a | m e b | m. 2. se a | c e b | c, com c > 0, então m c. Notação: m = mmc(a, b). Observação: a) mmc(a, b) ab. b) Se a | b, então mmc(a, b) = |b|. 5.6 - MMC de Vários inteiros: O conceito de mínimo múltiplo comum, definido para dois inteiros a e b, estende-se de maneira natural a mais de dois inteiros. No caso de três inteiros a, b e c, diferentes de zero, o m.m.c(a, b, c) é o inteiro positivo m(m > 0) que satisfaz às condições: 1) a | m, b | m e c | m. 2) Se a | e, b | e, e se c | e, com e > 0, então m e. 5.7 - Relação Entre o MDC e o MMC: Teorema 5.2 - Para todo par de inteiros positivos a e b subsiste a relação mdc(a, b) mmc(a, b) = ab. Corolário 5.2 - Para todo par de inteiros positivos a e b, o mmc(a, b) = ab se, e somente se mdc(a, b) = 1. 5.7 - Regra Prática para obtenção do MDC e MMC de Vários inteiros: Podemos determinar o mdc e o mmc de dois ou mais números inteiros positivos procedendo do seguinte modo: 1º) Fatoramos os números, decompondo-se em fatores primos positivos; 2º) Calculamos o mdc multiplicando os fatores comuns aos números, tomando cada fator uma só vez e com o menor expoente que ele apresenta nas decomposições dos números dados; 3º) Calculamos o mmc multiplicando os fatores comuns e os não comuns aos números, tomando cada fator uma só vez e com o maior expoente que ele apresenta nas decomposições dos números dados; Exemplo: Dados as seguintes decomposições de inteiros a = 3 2 .19.71 2 , b = 2.3 5 .19.61 e c = 2 4 .19 2 .71, determine: a) MDC(a, b) = 3 2 .19 b) MMC(a, b) = 2 4 . 3 5 .19 2 .61.71 2 c) MMC(a, c) = 2 4 . 3 2 .19 2 .71 2 d) MDC(a, b, c) = 19 e) MDC(b, c) = 2.19 Questões Resolvidas 01) Usando o algoritmo de Euclides, achar os inteiros x e y que verifiquem cada uma das seguintes igualdades: a) mdc(56, 72) = 56x + 72y mdc(56, 72) = 8  8 = 56x + 72y 72 = 56.1 + 16 56 = 16.3 + 8 16 = 8.2 + 0 b) mdc(24, 138) = 24x + 138y 138 = 24.5 + 18 24 = 18.1 + 6 18 = 6.3 + 0 (mdc = 6) 02) Achar inteiros x, y e z que verifiquem as seguintes igualdades: 1) 11x + 19y + 3z = 1 2) 56x + 6y + 32z = 2 3) 6x + 3y + 15z = 9 4) 14x + 7y + 21z = 4 Solução: 01) Achando o mdc(11, 19) 1 1 2 1 2 19 11 8 3 2 1 8 3 2 1 0 Usando o algoritmo da divisão, podemos escrever: 19 = 11 x 1 + 8 11 = 8 x 1 + 3 8 = 3 x 2 + 2 3 = 2 x 1 + 1 2 = 1 x 2 Desprezando a última igualdade, eliminemos os restos, a partir da penúltima igualdade: 1 = 3 – 2 1 = 3 – (8 – 3 x 2) 1 = 3 x 3 – 8 1 = (11 – 8) x 3 – 8 1 = 11 x 3 – 8 x 4 1 = 11 x 3 – (19 – 11) x 4 1 = 11 x 7 – 19 x 4 Tomando a penúltima igualdade; 8 = 56 – 16.3. Tirando o valor de 16 na primeira igualdade e substituindo na penúltima: 8 = 56 – (72 – 56.1).3  8 = 56 + 56.3 – 72.3 8 = 56.4 + 72(-3). Portanto, x = 4 e y = -3. 6 = 24 – 18.1 6 = 24 – (138 – 24.5).1 6 = 24 + 24.5 – 138.1 6 = 24.6 + 138(-1)  x = 6 e y = -1 Pelo processo anterior acha-se o mdc(624, 504) que é 24. A seguir acha-se o mdc(24, 90) que é 6. R: 6. Determinar os inteiros positivos a e b sabendo: 10) ab = 4032 e o mmc(a, b) = 336. 11) mdc(a, b) = 8 e o mmc(a, b) = 560. Soluções: 10) Como mmc(a, b) = 336, temos 336 = a k1 e 336 = b k2 .Multiplicando membro a membro estas duas igualdades, temos: 336 x 336 = a b k1 k2. Substituindo o valor de a b = 4032 nesta última igualdade, temos: 112896 = 4032 k1 k2 ou k1 k2 = 28. Assim, como k1 e k2 são primos entre si, devemos procurar dois inteiros primos entre si, cujo produto é 28. Encontramos k1 = 1 e k2 = 28, k1 = 4 e k2 = 7. Com estes valores temos a = 336 e b = 12 e a = 84 e b = 48. 11) Temos: mdc(a, b) mmc(a, b) = a b. Então a b = 8 560. Temos, portanto um problema já resolvido sobre mdc. A resposta será: a = 8, b = 560; a = 16, b = 280; a = 40, b = 112; a = 56, b = 80. 12) Se a soma de dois números é 320 e o mínimo múltiplo comum entre eles é 600, quais são esses números? Qual é o máximo divisor comum entre eles? Solução: Se X e Y são os números procurados, eles devem ser divisores de 600, logo devem pertencer ao conjunto D(600): R: {1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 25, 30, 75, 100, 120, 150, 200, 300, 600}. Pares de números deste conjunto que somam 320, são: 300 e 20 ou 200 e 120. O primeiro par não serve, pois MMC (300, 20) = 300. Os números que servem são X = 200 e Y = 120, pois MMC (200, 120) = 600 e MDC (200, 120) = 40. 13) Se a diferença entre dois números naturais é 126 e o máximo divisor comum entre eles é 18, quais são esses números? Solução: Se X e Y são os números procurados, eles devem ser múltiplos de 18 e podem ser escritos na forma X = 18a e Y = 18b onde a e b devem ser determinados. Assim: 18a - 18b = 126, de onde segue que 18(a - b) = 18×7, o que é equivalente a: a - b = 7. Tomando a = 8 e b = 1 teremos X = 144 e Y = 18. 14) Se a soma de dois números naturais é 420 e o máximo divisor comum entre eles é 60, quais são esses números? Solução: Sejam X e Y os números procurados. Se MDC(X, Y)=60, os números X e Y devem ser múltiplos de 60, logo podem ser escritos na forma X = 60a e Y = 60b onde a e b são números inteiros positivos. Assim: 60a + 60b = 420, o que garante que a + b = 7. Devemos escolher números naturais tal que a + b = 7, e assim, temos várias opções. Se a = 6 e b = 1 então X =360 e Y = 60 Se a = 5 e b = 2 então X = 300 e Y = 120 Se a = 4 e b = 3 então X = 240 e Y = 180 Se a = 3 e b = 4 então X = 180 e Y = 240 Se a = 2 e b = 5 então X = 120 e Y = 300 Se a = 1 e b = 6 então X = 60 e Y = 360 Questões Propostas 01) Usando o algoritmo de Euclides, determinar o mdc (306, 657). 02) Usando o algoritmo de Euclides, determinar: a) mdc(285, 675, 405). R: 5. b) mdc(209, 299, 102). R:- 1. c) mdc(69, 398, 253). R: 23. 03) Usando o algoritmo de Euclides, achar inteiros x e y que verifiquem a seguinte igualdade: mdc(56, 72) = 56x + 72y. 04) Achar inteiros x e y que verifiquem a seguinte igualdade: a) 78x + 32y = 2 e) 238x + 51y = 3 b) 104x + 91y = 13 f) 52x + 13y = 1 c) 31x + 19y = 7 g) 145x + 58y = 87 d) 42x + 26y = 16 h) 17x + 5y = -2 05) Achar inteiros x, y e z que verifiquem a igualdade 198x + 288y + 512z = mdc(198, 288, 512). R: x = -5, y = -217, z = 124. 06) Calcular as soluções de todos os itens abaixo podendo ser obtidas a partir da propriedade mdc(a,b).mmc(a, b) = a.b. a) mmc(83, 68) R: 5644 b) mmc( 120, 110) R: 1320 c) mmc(86, 71) R: 6106 d) mmc(224, 192) R: 1344 e) mmc(1287, 507) R: 16731 f) mmc(143, 227) R: 32461 g) mmc(306, 657) R: 22338 07) Determinar a e b se, a + b = 589 e mmc a b a b ( , ) mdc( , ) 84 . R: a = 57 e b = 532; a = 217 e b = 372. 08) Demonstrar que se a e b são inteiros positivos tais que o mdc(a, b) = mmc(a, b) então a = b. 09) Sendo a e b inteiros positivos, demonstrar quo o mdc(a, b) sempre divide o mmc(a, b). 10) Quais os dois menores números pelos quais devemos dividir 252 e 234 para que os quocientes obtidos sejam iguais? R: 7 e 9. 11) Quais os números compreendidos entre 100 e 300 divisiveis ao mesmo tempo por 6, 9 e 15? R: 180 e 270. 12) Quais os dois números de três algarismo divisiveis ao mesmo tempo por 8, 9 e 10? R: 360 e 720. 13) Quais os dois menores números pelos quais devemos multiplicar 30 e 54 para que os produtos obtidos seja iguais? R: 9 e 5. 14) Calcular o número que, dividido por 12, 40 e 60 deixa sempre o mesmo resto 5? R: 125. 15) A editora do livro “Matemática” recebeu pedidos de três livrarias sendo que um pedido de 1300 livros, o segundo pedido de 1950 livros e o terceiro pedido de 3900 livros. A editora deseja remeter em n pacotes iguais de tal forma que n seja o menor possível. Calcule o valor de n. R: 650 livros em cada pacote, num total de 11 pacotes. 16) Três peças de tecido medem respectivamente, 180m, 252m e 324m. Pretende-se dividir em retalhos de igual comprimento. Qual deverá ser esse comprimento de modo que o número de retalhos seja o menor possível? Em quantos pedaços as peças serão dividas? R: O comprimento é de 36 m e o número de peças serão de 5, 7 e 9 pedaços. 17) Duas rodas dentadas se engrenam uma a outra, a primeira tem 48 dentes e demora 4 segundos em cada volta, a segunda tem 104 dentes. Colocam-se em movimento e se pergunta ao cabo de quanto tempo, se encontram na mesma posição inicial? R: 52 segundos. 18) Dois ciclistas correm sobre uma pista circular, partindo ao mesmo tempo de uma mesma linha. O primeiro realiza uma volta completa, em 30 minutos e o segundo em 36 minutos. Quantas voltas deverão dar cada um, para que tornem a encontrar-se, sobre a linha de partida? R: 6 e 5. 19) Um remédio deve ser tomado diariamente em intervalos regulares. O fabricante quer que a duração desses intervalos seja um número inteiro de horas (como 3 horas, por exemplo, e nunca três horas e meia). Além disso, o fabricante quer que os horários em que se deve tomar o remédio não mudem de um dia para outro. Existem várias possibilidades para a duração dos intervalos que satisfazem essas exigências do fabricante. Quais são elas? R: D(24) 1, 2, 3, 4, 6, 8, 12, 24 . h) quando dividido por 9 tem resto 8. R: 17. 08) Determine todos os possíveis números naturais n tais que: a) mmc(n, 54) = 54 R: D(54) 1, 2, 3, 6, 9, 18, 27, 54 b) mmc(n, 26) = 26 R: D(26) 1, 2, 13, 26 09) O mmc dois números naturais a e b é igual a 1260 e quando dividimos este mmc pelos números a e b o produto dos quocientes obtidos é igual a 90. Determine todos os números naturais a e b satisfazendo esta condição. R: a = 1260 e b = 14, a = 630 e b = 28 e a = 252 e b = 70. 10) O mmc dois números naturais é 300. Dividimos este mmc por a e b, os quocientes obtidos são tais que o seu produto vale 50. Determinem todos os pares de números a e b que satisfazem estas condições. R: a = 300 e b = 6 e a = 150 e b = 12. 11) Prove que o produto de três números consecutivos é divisível por 6. 12) Se o resto da divisão de um número primo por 3 é 1, mostre que na divisão deste número por 6 o resto também é 1. 13) Prove: se o resto da divisão de um número inteiro n por 6 é 5, então o resto da divisão de n por 3 é 2. 14) Considere a e b números naturais não primos entre si, cujo produto é 420. Determine mdc(a, b). R: 2. 15) Sejam m = 2 6 .3 3 .5 2 , n = 2 r .3 s .5 t e p = 2 5 .5 4 .7 3 . Escreva as condições que devem satisfazer r, s e t para que n seja divisor comum de m e p. R: r = 5, s = 0 e t = 2. 16) Seja 411752 43x , 264 31173y e 263 474152z . Determine: a) mdc (x,y) . R: 417 b) mdc (x,z) . R: 2.5 c) mdc (x,y,z) . R: 2.41 d) mmc(x,y,z) . R: 2 3 .3 4 .5 3 .17 6 .31 2 .41.47 2 e) mmc(x,y) . R: 2.3 4 .5 3 .17 6 .31 2 .41 f) mmc(x,z) . R: 2 3 .5 3 .17 4 .41 6 .47 2 17) Encontre mdc (a,b) e mmc(a,b) , através da decomposição em fatores primos: 1) a = 20.600, b = 3.300. R: mdc (a, b) = 2 2 .5 2 e mmc (a, b) = 2 3 .3.5 2 .11.103. 2) a = 147.875, b = 166.725. R: mdc (a, b) = 5 2 .13 e mmc (a, b) = 5 3 .7.13 2 .19. 18) Encontre os valores de x para os quais mdc(20 + x, x) = 4. R: os valores de x deverão ser divisível por 4. 19) Um professor dá aulas numa 7ª série, de 30 alunos, e numa 8ª série, de 18 alunos. Em cada sala, ele formou grupos, e de todos os grupos (tanto na 7ª como na 8ª) tinham o mesmo número de alunos. Qual é o maior número de alunos que cada grupo pode ter? R: Cada grupo pode ter no máximo 6 alunos. 20) Na minha escola, há 180 alunos na 5ª série, 168 na 6ª série, 144 na 7ª série e 120 na 8ª. Para uma feira de ciências, todas esses alunos serão organizados em grupos com o mesmo número de elementos, sem misturar alunos de série diferentes. a) Qual o número máximo de alunos que pode haver em cada grupo? R: Pode ter no máximo 12 pessoas. b) Quantos grupos serão formadas em cada uma das séries? R: 15 grupos na 5ª série; 14 grupos na 6ª série; 12 grupos na 7ª série e 10 grupos na 8ª série. 21) Um país tem eleições para presidente de 5 em 5 anos, e para governador de 4 em 4 anos. Em 1998, essas duas eleições coincidiram. Dê os anos das três próximas vezes em que elas voltarão a coincidir. R: 2018, 2038 e 2058. 22) Um país tem eleições para presidente de 4 em 4 anos, e para senador de 6 em 6 anos. Em 1997, houve eleições para presidente, e em 1988 para senador. As eleições poderão cair alguma vez no mesmo ano? Explique sua resposta. R: não. 23) Muitos cometas nos visitam de tempos em tempos. Um certo cometa passa pela terra de 12 em 12 anos. Outro passa de 32 em 32 anos. Em 1913, os dois passaram por aqui. Qual é a próxima ocasião em que os dois passarão pela Terra no mesmo ano? R: 2009. 24) Um cometa A passa pela terra de 26 em 26 anos. O cometa B passa de 32 em 32 anos. Ambos visitaram a Terra em 1930. Pergunta-se: a) Qual será a próxima ocasião em que os dois visitarão a Terra no mesmo ano? R: 2346. b) Depois de 1930, quantas serão as passagens do cometa a até que os dois visitem a Terra ao mesmo ano? R: 16 passagens o cometa A e 13 passagens o cometa B. 25) Alguns cometam visitam a Terra periodicamente. Um cometa A visita terra de 12 em 12 anos. O cometa B passa de 32 em 32 anos. Ambos visitaram a Terra em 1910. Qual é a próxima ocasião em que os dois passarão pela Terra no mesmo ano? R: 2006. 26) Uma árvore de Natal tem três tipos de luzes. As vermelhas acendem a cada 8 segundos, as verdes a cada 10 segundos e as amarelas a cada 12 segundos. Se elas acenderem todas juntas num determinado momento, depois de quantos segundos ascenderão juntas novamente? R: 120 segundos. 27) Numa competição, partiram juntos dois ciclistas. O primeiro leva 20 segundos para dar uma volta completa na pista e o segundo leva 18 segundos. Eles estarão juntos novamente depois de quantos segundos? R: 180 segundos. 28) Uma certa Irmã recebe periodicamente a visita de seus três filhos, Sérgio a visita a cada 15 dias, Marta a cada 20 dias e Rodrigo a cada 24 dias. Como hoje é dia de seu aniversário, os três filhos foram vê-la. Daqui a quantos dias coincidira a visita dos três filhos? R: 120 dias. 29) No terminal de ônibus ABCD, chegam ônibus da Vila Romana a cada 30 minutos e da Vila Inglesa a cada 40 minutos. De quanto em quanto tempo os horários dos ônibus coincidem? R: 120 minutos. 30) Uma avenida mede 4500 metros. A partir do inicio da avenida, a cada 250 metros há uma parada de ônibus, e a cada 225 metros uma para de bonde. Pergunta-se: a) A que distância do inicio da avenida ocorre a primeira coincidência das paradas de ônibus e de bonde? R: 2250m. b) Quantos são os pontos comuns de paradas de ônibus e de bonde? R: 2 paradas comuns. 31) Durante um evento, o organizador pretende distribuir, como brindes, a alguns dos participantes, caixas (kits), com o mesmo conteúdo, formado de camisetas e chaveiros. Sabe-se que ele possui exatamente 200 camisetas e 120 chaveiros. a) Decomponha os números 200 e 120 em fatores primos? R: 200 = 2 3 .5 2 e 120 = 2.3.5 b) Determine os números máximos de caixas, com o mesmo conteúdo, que o organizador conseguirá formar utilizando todos os chaveiros e camisetas disponíveis? R: 40. 32) (UnB) Quatro pessoas saem de uma praça a caminhar numa mesma hora. Elas repetirão várias vezes o mesmo percurso, e seus percursos duram respectivamente, 5 min, 9 min, 10 min e 15 min. Após quantos minutos elas estarão juntas na praça pela primeira vez? R: 90. 33) (UFRJ) Uma escola deseja distribuir cadernos entre os seus 480 alunos, de forma que cada um deles receba o mesmo número de cadernos e não haja sobras. Os cadernos são adquiridos pela 50) (UFMG) Três atletas correm numa pista circular e gastam, respectivamente, 2,4 min, 2,0 min e 1,6 min, para completar uma volta na pista. Eles partem do mesmo local e no mesmo instante. Após algum tempo, os três atletas se encontram, pela primeira vez, no local da largada. Nesse momento, o atleta mais veloz estará completando: R: 15 voltas. 51) (Cesgranrio-RJ) Certo botânico desenvolveu em laboratório 3 variedades de uma mesma planta V1, V2 e V3, que se desenvolvem cada uma a seu tempo, de acordo com a tabela abaixo. Plantando- se as 3 variedades no mesmo dia, confiando-se na exatidão, não ocorrendo nenhum fato que modifique os critérios da experiência tabulada e levando-se em conta que, a cada dia de colheita, outra semente da mesma variedade será plantada, o número mínimo de sementes necessário para que a colheita das três variedades ocorra simultaneamente será: Variedades Tempo de germinação (em semanas após o plantio) Tempo de floração (em semanas após a germinação) Tempo para única colheita (em semanas após a floração) V1 4 3 1 V2 2 3 1 V3 1 2 1 R: 24 52) Numa escola pretende-se distribuir, em partes iguais, 36 puzzles e 90 livros pelas bibliotecas das varias turmas. Qual o número Maximo de turmas que a escola pode ter, para que essa distribuição possa ser feita? Para esse numero Maximo, quantos puzzles e quantos livros receberão cada biblioteca de turma? R: 53) Três amigas, a Ana, a Patrícia e a Lena tiveram folga dos respectivos empregos no sábado passado. Sabendo que a Ana tem folga a um sábado de 6 em 6 semanas, a Patrícia de 3 em 3 semanas e a Lena de 4 em 4 semanas, quantas semanas vão passar até que as três amigas estejam de folga, em simultâneo, a um sábado? R: 54) Duas rodas gigantes começam girar, num mesmo instante, com uma pessoa na posição mais baixa em cada uma. A primeira dá uma volta em 30 segundos e a segunda dá uma volta em 35 segundos. As duas pessoas estarão ambas novamente na posição mais baixa após: R: 55) Três cidades A, B e C, realizam grandes festas: de 5 em 5 meses em A, de 8 em 8 meses em B e de 12 em 12 meses em C. Essas festas coincidiram em setembro de 1982. Coincidirão novamente em: R: UNIDADE VI – NÚMEROS PRIMOS 6.1 - Introdução: No ano de 2002 três matemáticos indianos descobriram um algoritmo de primariedade, que informa se um dado número é primo ou não. Essa descoberta divulgada pela imprensa causou uma preocupação mundial devido os códigos criptográficos que utilizam os números primos. Já tinha lido sobre criptografia e sabia da sua importância para a proteção das informações, o que despertou o meu interesse sobre o alcance desta descoberta, e na medida que a pesquisa se desenvolvia outros movimentos em torno dos números primos apareciam, envolvendo desde matemáticos e técnicos de computação profissionais até usuários de computadores domésticos. O número é a entidade mais importante da Matemática estando na origem de diversos ramos desta ciência. Entre os seres vivos, o homem é um dos poucos que possui senso numérico. Por isso, desde os primórdios da raça humana os números já estavam presentes, tendo surgido para auxiliar o homem a controlar quantidades a partir do contraste entre pouco e muito, resultando na criação dos primeiros sistemas de contagem. Juntamente com a linguagem, a escrita e outras habilidades, o número está no conjunto das criações humanas em que se baseou o desenvolvimento das nossas sociedades. Nesta unidade, falaremos sobre números, mas de um tipo especial os números primos. É um assunto em que muitos especialistas em segurança eletrônica de dados tem conhecimento, e a grande maioria das pessoas não sabem que a inviolabilidade dos seus dados pessoais depende em parte destes números. Os números primos, um conhecimento sem aplicação desde as civilizações mais antigas, são a base dos códigos de segurança de informação para computadores. Como estamos vivendo, segundo alguns historiadores e sociólogos na "Era da Informação" pode-se perceber sua importância para a nossa vida diária, embora não apareçam de forma explícita. A propósito, podemos citar a frase do matemático Nicolai Lobachevsky (1793-1856) "Não há ramo da Matemática, por abstrato que seja, que não possa um dia vir a ser aplicado nos fenômenos do mundo real". Os primos são apresentados pela primeira vez aos alunos na 5 a série e depois são quase esquecidos. No nível médio, apesar do aluno estar mais amadurecido para a Matemática, eles não reaparecem, embora pudessem ajudar na fixação do conteúdo específico, assim como devido ao fascínio que exercem por conta das curiosidades e mistérios que os envolvem, despertar no aluno o gosto por problemas da Teoria dos Números. Cabe ressaltar, que os números primos tem ganhado importância por causa das aplicações na criptografia, deixando de ser uma mera curiosidade. Desta forma, um papel de destaque está reservado para o conhecimento matemático, já que ele é a "porta de entrada" para o mundo tecnológico. Segundo Ubiratan D' Ambrosio (1996)" a educação para a cidadania, que é um dos grandes objetivos da educação de hoje, exige uma apreciação do conhecimento moderno, impregnado de ciência e tecnologia". Os números primos são um exemplo para os alunos, de como podemos a partir de uma definição antiga e relativamente simples, construir uma teoria que foi sendo enriquecida ao longo do tempo de outros conhecimentos, culminando no seu aproveitamento em aplicações tecnológicas de última geração. 6.2 - Números Primos: Definição 6.1 - Dizemos que um número inteiro positivo p maior que 1 é primo, se, e somente se, p possui exatamente dois divisores positivos distintos, ou seja, 1, p . Exemplo: O número 2 é primo, pois os divisores positivos de 2 são 1, 2 . E mais, 2 é o único número primo par, pois se existe primo par maior que 2, seria da forma N = 2q (q 1). Portanto, 1, 2 e q são divisores de N, o que torna absurdo, pois N é primo. Um inteiro maior que 1 e que não é primo diz-se composto. Teorema 6.1: Se um número primo p não divide um inteiro a, então a e p são primos entre si. Corolário 6.1: Se p é um primo tal que p | ab, então p | a ou p | b. Corolário 6.2: Se p é um primo tal que p | a1a2a3 ... an, então existe um índice k, com 1 k n tal que p | ak.. Corolário 6.3: Se os inteiros p, q1,q2 ,..., qn são todos primos e se p | q1q2 ... qn, então existe um índice k, com 1 k n tal que p = qk.. Teorema 6.2: - Todo inteiro composto possui um divisor primo. 6.3 - Teorema Fundamental da Aritmética: Teorema 6.3 Todo inteiro positivo n > 1 é igual a um produto de fatores primos. Corolário 6.4: A decomposição de um inteiro positivo n > 1 como produto de fatores primos é única, a menos da ordem dos fatores. Corolário 6.5: Todo inteiro positivo b > 1 admite uma única decomposição da forma n = r21 k r k 2 k 1 p...pp onde, para i =1,2,..., r cada ki é um inteiro positivo e cada pi é um primo, com p1 < p2 < ... < pr, denominada decomposição canônica do inteiro positivo n > 1. Exemplo 6.1: Definir mdc e mmc dos números 588 e 936 pela decomposição canônica. Teorema 6.4 - (de Euclides) - Há um número infinito de primos. Teorema 6.5 - Se um inteiro positivo a > 1 é composto, então a possui um divisor primo p a . 6.4 - Crivo de Erastóstenes: Solução: Vamos decompor o número em um produto de fatores maiores que um n 4 + 4 = n 4 + 4 + 4n 2 – 4n 2 (somando e subtraindo 4n 2 para formar um quadrado perfeito) n 4 + 4 = (n 2 + 2) 2 – 4n 2 (fatoremos a diferença entre dois quadrados) n 4 + 4 = (n 2 + 2 + 2n)(n2 + 2 – 2n). Sendo n > 1 os dois fatores são maiores que 1. 10) Mostrar que, se n > 4, é composto, então n divide (n – 1)!. Solução: Como n é composto, ele pode ser decomposto como produto de dois inteiros a e b: n = a b , com 1 < a < n e 1 < b < n. Suponhamos que a b e consideremos a < b. Temos: 1 < a < b < n, ou 1 < a < b n – 1. Logo (n – 1)! = 1.2.a.b. (n–1) sendo a e b fatores de (n–1)!. Deste modo ab = n divide (n–1)!. Se a = b, n = a 2 e como n > 4, temos a 2 > 4 ou a > 2 e a 2 > 2 a ou 2 a < n = a 2 . Assim 2 a n – 1 e como a < 2 a, a e 2 a são fatores de (n–1)! Logo: (n–1)! = 1.2.3...a ...2 a ... (n–1). Portanto a 2 é um fator de (n–1)!. E assim, a 2 = n divide (n–1)! 11) Demonstrar que o inteiro positivo a > 1 é um quadrado perfeito se e somente se todos os expoentes dos fatores primos da sua decomposição canônica são inteiros pares. Solução: Seja a é um quadrado perfeito então a tem a forma n 2 . Se n = n1 k1 .n2 k2 .n3 k3 . ... nn kn , onde n1 k1 .n2 k2 .n3 k3 . ... nn kn é a decomposição canônica em fatores primos de n, teremos n 2 = (n1 k1 .n2 k2 .n3 k3 . ... nn kn ) 2 = n1 2k1 .n2 2k2 .n3 2k3 . ... nn 2kn . Como todos os expoentes são da forma 2k, conclui-se que todos os expoentes são pares. Seja então ni um fator primo de n cujo expoente não seja par. Neste caso, o fator teria expoente da forma 2k + 1. Ora, ni 2k + 1 = ni 2k . ni. ni 2k tem expoente para, portanto está de acordo com o que foi dito anteriormente. Para que fosse quadrado, ni deveria ter dois fatores primos iguais. Como ni é primo isto não é possível. Portanto, todo número é quadrado perfeito, se e somente se, todos os expoentes dos fatores primos na decomposição canônica for par. 12) Demonstrar que, se o inteiro n é composto, então 2 n – 1 também é composto. Solução: Evidentemente se trata de n positivo, pois se n < 0, n – 1 é negativo e 2 n – 1 não será um inteiro. Assim, para n > 0 e n composto, n > 3. Teremos então n – 1 > 2  2 n – 1 = 2 k , k = n – 1 > 2 inteiro: k – 2 > 0  (k – 1) > 0. Ora, 2 n – 1 = 2 k = 2(2 k – 1 ) que é múltiplo de 2 (não se esqueça que k – 1 > 0)  2 n – 1 é composto. 13) Mostrar que são primos gêmeos: ( a ) 1949 e 1951 Solução: Primos gêmeos são dois primos que são ímpares consecutivos. 1949 e 1951 são dois ímpares consecutivos. Devemos verificar se ambos são primos. 1949 e 1951. Como ambos não são divisíveis por 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41 e 43, os dois são primos. Portanto são primos gêmeos. Questões Propostas 01) Achar os cinco menores primos da forma n 2 – 2. R: 2, 7, 23, 47 e 79. 02) Achar três primos ímpares cuja soma seja: ( a ) 81. R: (3, 5, 73) ( b ) 125. R: (5, 13, 107) 03) Achar todos os pares de primos p e q, tais que p – q = 3. R: p = 5 e q = 2. 04) Determinar se são primos os números. ( a ) 169 R: é composto. ( b ) 197 R: é primo ( c ) 239 R: é primo ( d ) 473 R: é composto 05) Achar a decomposição canônica do inteiro 5040. R: 2 4 . 3 2 . 5 . 7 06) Achar o mdc(a, b) e mmc(a, b) sabendo a = 2 30 . 5 21 . 19 . 23 3 e b = 2 6 . 3 . 7 4 . 11 2 . 19 5 . 23 7 . R: Mdc(a, b) = 2 6 . 19. 23 3 e (a, b) = 2 30 .3.5 21 .7 4 .11 2 .19 5 .23 7 . 07) Mostrar que são primos gêmeos: ( a ) 1997 e 1999. R: são primos gêmeos. 08) Achar todos os primos gêmeos entre 400 e 500. R:- 491 e 421, 461 e 463. 09) Achar uma sequência de quatro inteiros positivos consecutivos e compostos. R: 5! + 2, 5! + 3, 5! + 4, 5! + 5 10) Verificar a conjectura de Goldbach para os seguintes inteiros pares: ( a ) 32 ( b ) 100 ( c ) 456 ( d ) 1024 11) Verificar que todo par entre 4 e 100 é a soma de dois primos. 12) Achar o menor inteiro positivo n tal que 2n 2 + 29 é um inteiro composto. R: 1 13) Mostar que a soma de inteiros positivos ímpares e consecutivos é sempre um inteiro composto. 14) Usando a decomposição canônica dos inteiros 507 e 1287, achar o mdc(507, 1287) e o mmc(507, 1287). R: mdc = 39 e mmc = 16731. 15) Mostrar que o único primo da forma n 3 – 1 é 7. R: o único n 3 – 1 primo é 7. 16) Mostrar que todo inteiro da forma 8 n + 1, com n > 1, é composto. 17) Mostrar que se n 2 + 2 é primo então 3 | n. 18) Mostrar, mediante um exemplo, que a seguinte conjectura é falsa: “Todo inteiro positivo pode-se escrever sob a forma a 2 + p, onde o inteiro a > 0 e p é um inteiro primo ou 1”. 19) Demonstrar as seguintes propriedades: ( a ) Todo primo da forma 3n + 1 é também da forma 6m + 1. ( b ) Todo inteiro da forma 3n + 2 tem um fator primo desta forma. ( c ) Se p > 5 é um primo, então p 2 + 2 é composto. ( d ) Se p é um primo e se p | a n , então p n | a n . ( e ) Todo inteiro n > 11 pode ser expresso como a soma de dois inteiros compostos. ( f ) Se p > q > 5 e se p e q são ambos primos, então 24 | p 2 – q 2 . ( g ) Se p 5 é um primo ímpar, então p 2 – 1 ou p 2 + 1 é divisível por 10. 20) Verificar que todo inteiro pode escrever-se sob a forma 2 k m, onde o inteiro k > 0 e m é um inteiro ímpar. 21) Demonstrar que, se o inteiro n > 2, então existe um primo p tal que n < p < n!. 22) Demonstrar que todo primo ímpar é da forma 4k + 1 ou 4k – 1, onde k é um inteiro positivo. Questões Resolvidas Determinar todas as soluções inteiras das seguintes equações diofantinas lineares: 01) 56x + 72y = 40 Solução: Determinemos o mdc (72, 56). Como o mdc (56, 72) = 8 divide 40, a equação possui solução. Usando o algoritmo da divisão, temos: 72 = 56 x 1 + 16 56 = 16 x 3 + 8 16 = 8 x 2 Vamos escrever o mdc 8 como combinação linear de 56 e 72. 8 = 56 – 16 x 3 = 56 – (72 – 56) x 3 = 56 x 4 – 72 x 3 = 56(4) + 72 (–3) Como queremos resolver a equação 56x + 72y = 40 multipliquemos a última igualdade acima por 5 40 = 56(20) + 72(–15).Logo xo = 20 e yo = –15, dando a solução geral: x = 20 + (72/8)t e y = –15 – (56/8)t ou x = 20 + 9t e y = –15 – 7t. 02) 24x + 138y = 18 Solução: Determinemos o mdc (138, 24). Usando o algoritmo da divisão, temos: 138 = 24 x 5 + 18 24 = 18 x 1 + 6 18 = 6 x 3 Vamos escrever o mdc 6, como combinação linear de 24 e 138 6 = 24 – 18 = 24 – (138 – 24 x 5) = 24 x 6 – 138 = 24(6) + 138(–1) Como queremos resolver a equação 24x + 138y = 18, multipliquemos a igualdade acima por 3 18 = 24(18) + 138(–3): Logo xo = 18 e yo = –3, dando a solução geral: x = 18 + (138/6)t e y = –3 – (24/6)t ou x = 18 + 23t e y = –3 – 4t. 3) 221x + 91y = 117 Solução: Determinemos o mdc (221, 91). Como o mdc (221, 91) = 13 divide 117, a equação possui solução. Usando o algoritmo da divisão, temos: 221 = 91 x 2 + 39 91 = 39 x 2 + 13 39 = 13 x 3 Vamos escrever o mdc 13 como combinação linear de 221 e 91 13 = 91 – 39 x 2 = 91 – (221 – 91 x 2) x 2 = 91 x 5 – 221 x 2 = 221(–2) + 91(5) Como queremos resolver a equação 221x + 91y = 117, multipliquemos a igualdade acima por 9. 117 = 221(–18) + 91(45). Logo xo = –18 e yo = 45 dando a solução geral: x = –18 + (91/13)t e y = 45 – (221/13)t ou x = –18 + 7t e y = 45 – 17t. 04) 84x – 438y = 156 Solução: Determinemos o mdc (438, 84). Como o mdc (438, 84) = 6 divide 156, a equação possui solução. Usando o algoritmo da divisão, temos: 438 = 84 x 5 + 18 84 = 18 x 4 + 12 18 = 12 x 1 + 6 12 = 6 x 2 Vamos escrever o mdc 6 como combinação linear de 84 e –438 6 = 18 – 12 = 18 – (84 – 18 x 4) = 18 x 5 – 84 = (438 – 84 x 5) x 5 – 84 = 438 x 5 – 84 x 26 ou 6 = 84(–26) – 438(–5) Como queremos resolver a equação 84x – 438y = 156 multipliquemos a igualdade acima por 26. 156 = 84(–676) - 438(–130). Logo xo = –676 e yo = –130, dando a solução geral: x = –676 –(438/6)t e y = –130 –(84/6)t ou x = –676 –73t e y = –130 – 14t. 05) 57x – 99y = 77 Solução: Determinemos o mdc (57, 99). Como o mdc (57, 99) = 3 não divide 77, a equação não possui solução. 06) 11x + 30y = 31 Solução: Determinemos o mdc (11, 30). Como o mdc (11, 30) = 1 divide 31, a equação possui solução. Usando o algoritmo da divisão, temos: 30 = 11 x 2 + 8 11 = 8 x 1 + 3 8 = 3 x 2 + 2 3 = 2 x 1 + 1 2 = 1 x 2 Vamos escrever o mdc 1 como combinação linear de 11 e 30. 1 = 3 – 2 = 3 – (8 – 3 x 2) = 3 x 3 – 8 = (11 – 8) x 3 – 8 =11 x 3 – 8 x 4 = = 11 x 3 – (30 –11 x 2) x 4 1 = 11 x 11 – 30 x 4 = 11(11) + 30(–4) Como queremos resolver a equação 11x + 30y = 31 multipliquemos a igualdade acima por 31 31 = 11(341) + 30(–124). Logo xo = 341 e yo = –124, dando a solução geral: x = 341 + 30t e y = –124 – 11t. 07) 27x – 18y = 54 Solução: Determinemos o mdc (27, 18). Como o mdc.(27, 18) = 9 divide 54, a equação possui solução. Usando o algoritmo da divisão, temos: 27 = 18 x 1 + 9 18 = 9 x 2 Vamos escrever o mdc 9 como combinação linear de 27 e –18. Da primeira desigualdade tiramos: t > –70,58 ou t – 70 Da segunda desigualdade tiramos: t < –70 ou t – 71. Portanto não há soluções positivas. 06) 54x + 21y = 906 Solução: A solução geral desta equação é: x = 604 + 7t e y = –1510 – 18t Como queremos as soluções positivas, devemos ter: 604 + 7t > 0 e–1510 – 18t > 0 Da primeira desigualdade tiramos: t > – 86,28 ou t – 86 Da segunda desigualdade tiramos: t < – 83,88 ou t – 84, o que nos dá o intervalo –86,–84 ou t = –86, t = –85 e t = –84 dando os valores: Para t = –86, x = 2 e y = 38 Para t = –85, x = 9 e y = 20 Para t = –84, x = 16 e y = 2 07) 123x + 360y = 99 Solução: A solução geral desta equação é: x = 1353 + 120t e y = –462 – 41t Como queremos as soluções positivas, devemos ter: 1353 + 120t > 0 e –462 – 41t > 0 Da primeira desigualdade tiramos: t > –11,27 ou t –11 Da segunda desigualdade tiramos: t < –11, 26 ou t -12. Portanto a equação não possui soluções positivas. 08) 158x – 57y = 7 Solução: A solução geral desta equação é: x = –154 – 57t e y = –427 – 158t Como queremos as soluções positivas, devemos ter: –154 – 57t > 0 e –427 – 158t > 0 Da primeira desigualdade tiramos: t < – 2,7 ou t – 3 Da segunda desigualdade tiramos: t < - 2,7 ou t - 3. Então todos os valores de t - 3 satisfazem o problema, dando infinitas soluções positivas. Questões Propostas 01) Determinar todas as soluções inteiras e positivas das seguintes equações diofantinas lineares: 01) 90x - 28y = 22 R: x = 13, y = 41. 02) 40x - 65y = 135 R: x = 5, y = 1. 03) 18x - 20y = -8 R: x = 4, y = 4. 04) 8x - 13y = 23 R: Não existem soluções positivas. 05) 3x + 4y = 20 R: x = 4, y = 2. 06) 50x - 56y = 74 R: x = 25, y = 21. 07) 8x - 13y = 23 R: x = 11, y = 5. 08) 5x - 2y = 2 R: x = 2, y = 4. 09) 24x + 138y = 18 R: Não existem soluções positivas. 10) 93x + 81y = 3 R: Não existem soluções positivas. 11) 43x + 128y = 1 R: Não existem soluções positivas. 12) 16x + 7y = 601 R: x = 3, y = 79 e x = 31, y = 15. 13) 47x + 29y = 1288 R: x = 20, y = 12. 14) 30x + 17y = 201 R: x = 5, y = 3. 15) 17x + 13y = 100 R: Não existem soluções positivas. 16) 12x + 18y = 50 R: Não admite solução. 17) 60x + 18y = 67 R: Não admite solução. 18) 1402x + 1969y = 1 R: Não existem soluções positivas. 19) 102x + 1001y = 533 R: Não existem soluções positivas. 20) 33x + 25y = 0 R: x = 0, y = 0. 21) 56x + 634y = 168 R: x = 0, y = 2. 22) 5x + 7y = 14 R: 25) 172x + 20y = 1000 R: 26) 18x + 5y = 48 R: 27) 39x + 26y = 105 R: 28) 14x + 22y = 50 R: 02) Encontre as soluções das seguintes equações diofantinas: 01) 2x - 10y + 35z = 0 R: x = 0, y = 0 e z = 0. 02) 2x + 3y + 5z = 7 R: x = 7, y = -14 e z = 7. 03) 1521x + 1955y + 455z = 221 R: x = 7956, y = -84.442 e z = 336.141. 04) 101x - 102y + 103z = 1 R: x = 1, y = -100 e z = -100. 05) 12x + 21y + 9z + 15w = 9 R: x = 2, y = -1, z = -1 e w = 1. 03) Determinar o menor inteiro positivo que dividido por 8 e por 15 deixa os restos 6 e 13, respectivamente. R: 188. 04) Exprimir 100 como soma de dois inteiros positivos de modo que o primeiro seja divisível por 7 e o segundo seja divisível por 11. R: 56 e 44. 05) Determinar as duas menores frações positivas que tenham 13 e 17 para denominadores e cuja soma seja igual a 305|221. R: 8|13 e 13|17. 06) Determine duas frações cujos denominadores sejam 12 e 16 e cuja soma seja 10|48. R: 1|12 e 2|16. 07) Demonstrar que se a e b são inteiros positivos primos entre si, então a equação diofantina ax – by = c, têm um número infinito de soluções inteiras e positivas. 08) Um grupo de pessoas gastou 1000 dólares num hotel. Sabendo-se que apenas alguns dos homens estavam acompanhados pelas esposas e que cada homem gastou 19 dólares e cada mulher gastou 13 dólares, pede-se determinar quantas mulheres e quantos homens estavam no hotel? R: 41 homens e 17 mulheres. 09) Ache o inteiro estritamente positivo com a seguinte propriedade da resto 6 quando dividido por 11 e resto 3 quando dividido por 7?. R: 17. 10) Determine todos os múltiplos de 11 e de 9 cuja a soma é igual a: a) 79. R: não existe. b) 80. R: 36 e 44. c) 270. R: 99 e 171; 72 e 198. 11) Determine o menor inteiro positivo que tem restos 11 e 35 quando dividido respectivamente por 37 e 48. R: 899. 12) O valor da entrada de um cinema e R$ 8,00 e da meia entrada R$ 5,00. Qual é o menor número de pessoas que pode assistir a uma sessão de maneira que a arrecadação da bilheteria seja R$ 500,00. R: Este problema não tem uma única solução. As soluções possíveis são: x = 5 e y = 92 ou x = 60 e y = 4. 13) Ao entrar num bosque alguns viajantes avistaram 37 montes de maça. Após serem retiradas 17 frutas, o restante foi dividido igualmente entre 79 pessoas. Quantas frutas coube a cada pessoa? R: 4 para cada pessoa. 14) Dispondo de 100 reais, quais são as quantias que se podem gastar comprando selos de R$ 5,00 e de R$ 7,00. R: x = 6 e y = 10. 15) Numa criação de coelhos e galinhas contaram-se 400 pés. Quantas são as galinhas e quantos são os coelhos, sabendo que a diferença entre esses dois números seja a menor possível? R: 99 coelhos e 2 galinhas. 16) Um grupo de pessoas gastou 690 dólares num hotel. Sabendo-se que apenas alguns dos homens estavam acompanhados pelas esposas e que cada homem gastou 18 dólares e cada mulher gastou 15 dólares, pede-se determinar quantas mulheres e quantos homens estavam no hotel. R: Este problema não tem uma única solução. As soluções possíveis são: 25 homens e 16 mulheres ou 30 homens e 10 mulheres ou 35 homens e 4 mulheres. UNIDADE VIII – CONGRUÊNCIAS 8.1 - Introdução: O conceito de congruência, bem como a notação através da qual essa noção tornou um dos instrumentos mais poderosos da teoria dos números, foi introduzido por Karl Friedrich Gauss (1777 – 1855), em sua obra Disquisitions arithmeticae em 1801. Para dar uma idéia da noção de congruência consideremos a seguinte questão, talvez ingênua mas ilustrativa: Se hoje é sexta-feira, que dia da semana será daqui a 1520 dias? Para organizar o raciocínio, indiquemos por o dia de hoje (sexta - feira), e por 1 o dia de amanha (sábado), e assim por diante. A partir dessa escolha, podemos construir a seguinte tabela: Sexta Sábado Domingo Segunda Terça Quarta Quinta 0 1 2 3 4 5 6 7 8 9 10 11 12 13        Nossa questão agora se resume em saber que coluna se encontra o número 1520. Para isso basta observar que dois números da seqüência 0, 1, 2, , estão na mesma coluna se, e somente se, sua diferença é divisível por 7. Suponhamos que o número 1520 se encontre na coluna encabeçada pelo número a (0 a 6) , logo 1520 - a = 7q. Para algum inteiro positivo q. donde obtemos 1520 = 7q + a, com (0 a 6) , Ora, pela unicidade do resto na divisão euclidiana, segue dessa igualdade que o resto da divisão de 1520 por 7. é portanto 1520 = 217 7 + 1, desta forma conclui-se que o resto é 1 e que portanto 1520 esta na segunda coluna. Logo, daqui a 1520 dias será um sábado. 8.2 - Congruências: Definição 8.1 - Sejam a e b inteiros quaisquer e seja m um inteiro positivo fixo. Diz-se que a é congruente a b módulo m se, e somente se, m divide a diferença a – b. Em outros termos a é congruente a b módulo m se, e somente se, existe um inteiro k tal que a – b = km. Notação: a b (mod m) Simbolicamente: a b (mod m) se, e somente se, m | ( a – b ). Exemplos 8.1 - 3 24 (mod 7); –31 11 (mod 6); –15 –63 (mod 8). Definição 8.2 - Se m não divide a diferença a – b, então, diz-se que a, é incongruente a b módulo m. Notação: a b (mod m). Observações: 1) Dois inteiros quaisquer são congruentes módulo 1. 2) Dois inteiros são congruentes módulo 2, se ambos são pares ou ambos ímpares. 3) a 0 (mod m) se, e somente se, m | a. Exemplos 8.2: 1) Mostrar que n 7 (mod 12) então, n 3 (mod 4) n Z. 2) Mostrar que n2 0 (mod 4) ou n2 1 (mod 4) n Z. 8.3 - Caracterização de Inteiros Congruentes: Teorema 8.1 - Dois inteiros a e b são congruentes módulo m se, e somente se, a e b deixam o mesmo resto quando divididos por m. 8.4 - Propriedades das Congruências: Teorema 8.2- Seja m um inteiro positivo fixo (m > 0) e sejam a, b e c inteiros quaisquer. Subsistem as propriedades: 1) a a (mod m). 2) Se a b (mod m), então b a (mod m). 3) Se a b (mod m) e se b c(mod m), então a c (mod m) Teorema 8.3 - Seja m um inteiro positivo fixo (m > 0) e sejam a, b dois inteiros quaisquer. Subsistem as seguintes propriedades: 1) Se a b (mod m) e se n | m, com n > 0, então a b (mod n). 2) Se a b (mod m) e se c > 0, então ac bc (mod mc). 3) Se a b (mod m) e se a, b, m são todos divisíveis pelo inteiro d > 0, então d b d a m mod d . Teorema 8.4 - Seja m um inteiro positivo fixo (m > 0) e sejam a, b, c, d inteiros quaisquer. Subsistem as seguintes propriedades: 1) Se a b (mod m) e se c d (mod m), então a + c b + d (mod m) e ac bd (mod m). 2) Se a b (mod m), então a + c b + c (mod m) e ac bc (mod m). 3) Se a b (mod m), então an bn (mod m) para todo inteiro positivo n. Exemplos 8.3 - Mostrar que: a) Se a b (mod m), então –a –b (mod m). b) Se a + b c (mod m) então a c – b (mod m). Teorema 8.5 - Se ac bc (mod m) e se o mdc(c, m) = d, então a b m mod d . Corolário 8.1 - Se ac bc (mod m) e se o mdc (c, m) = 1, então a b (mod m). Corolário 8.2 - Se ac bc (mod p), com p primo, e se p não divide c, então a b (mod p). 8.4 - Sistemas Completos de Restos: Definição 8.3 - Chama-se sistema completo de restos módulo m todo conjunto S = {r1, r2,..., rm} de m inteiros tal que um inteiro qualquer a é congruente módulo m a um único elemento de S. Exemplos 8.3 - {1, 2, 3}, {0, 1, 2}, { –1, 0, 1}, {1, 5, 9} são sistemas completo de restos módulo 3. Teorema 8.6 - O conjunto S = {0, 1, 2, ..., n–1 } é um sistema completo de restos módulo m. Corolário 8.3 - Se S = {r1, r2,..., rm} é um sistema completo de restos módulo m, então os elementos de S são congruentes módulo m aos inteiros 0, 1, 2, ... , m – 1, tomados numa certa ordem. Questões Resolvidas 01) Achar o menor inteiro positivo que represente a soma: ( a ) 5 + 3 + 2 + 1 + 8 (mod. 7). Solução: 5 + 2 0 (mod.7), 3 + 1 4 (mod. 7) 8 1 (mod. 7). Portanto 5 + 3 + 2 + 1 + 8 0 + 4 + 1 5 (mod. 7) R: 5 ( b ) 2 + 3 – 1 + 7 – 2 (mod.4). Solução: 2 + 3 1 (mod. 4) e -1 + 7 – 2 = 4 0 (mod. 4). Portanto: 2 + 3 – 1 + 7 – 2 1 + 0 1 (mod. 4) R. 1 02) Sabendo que 1066 1776 (mod m), achar todos os possíveis valores do módulo m. Solução: Como m | (1066 – 1776) devemos achar todos os divisores positivos de –710. Logo os divisores positivos de –710 são: 1, 2, 5, 10, 71, 142, 355 e 710. 03) Exprimir que “n é ímpar” de três outras maneiras. Solução: 01) n 1 (mod. 2) 02) n - 1 (mod. 2) 03) n = 2k + 1 04) n = 2k – 1 04) Mostrar que todo primo (exceto 2) é congruente módulo 4 a 1 ou 3. Solução: Se p é primo, diferente de 2, então ele é ímpar. Dividindo p por 4 obtemos os restos 1 ou 3. Assim p = 4q + 1 ou p = 4q + 3. Na primeira igualdade p – 1 = 4q, então p 1 (mod 4) e na segunda igualdade p – 3 = 4q , dando p 3 (mod 4). 05) Mostrar que 11 10 1 (mod 100). Solução: 11 2 21 (mod 100); 11 4 21 2 41 (mod 100); 11 8 41 2 81 (mod 100) 11 10 = 11 2 . 11 8 21 . 81 1 (mod 100). 06) Mostrar que todo primo (exceto 2 e 3) é congruente módulo 6 a 1 ou 5. 2) 19 8n –1 é divisível por 17. R: r = 1. 14) Achar os restos da divisão por 7 do número: 1) 2 3 10010 10 10 1010 + 10 + 10 +........+ 10 . R: r = 4. 2) 1 6 + 2 6 +.......+100 6 . R: r = 2. 3) 1 7 + 2 7 +.......+100 7 . R: r = 3. 4) 2222 5555 + 5555 2222 . R: r = 0. 15) Achar os restos da divisão por 4 do número: 1) 1 + 2 + 2 2 +........+2 19 . R: r = 3. 2) 1 5 + 2 5 +.......+100 5 . R: r = 0. 16) Determinar quais dos seguintes conjuntos são sistemas completos de restos módulo 6. a) {1, 2, 3, 4, 5}. R: Não é, porque possui somente 5 elementos. b) {0, 5, 10, 15, 20, 25}. R: Portanto é um sistema completo de restos módulo 6. c) {–4, –3, –2, –1, 0, 1}. R: Portanto é um sistema completo de restos módulo 6. d) {17, –4, 6, 7, 10, 3}. R: Portanto é um sistema completo de restos módulo 6. 17) Achar um sistema completo de restos {p1, p2, ... p7} módulo 7, tal que todo pi é primo. R: r = {2, 3, 5, 7, 11, 13, 28}. 18) Achar um sistema completo de restos módulo 7 formado só de múltiplos não negativos de 4. R: r = { 36, 40, 44, 48, 52, 56, 60}. 19) Encontrar um sistema completo de restos módulo 11 formado somente por múltiplo de 6. R: r: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 . 20) Encontrar um sistema completo de restos módulo 7 onde todos os elementos são primos: R: r: 0, 1, 2, 3, 4, 5, 6 . 21) Dado um primo p é sempre possível encontrar um sistema completo de restos módulo p formado só por primos? Justificar. Sua resposta. R: UNIDADE XI – CONGRUÊNCIAS LINEARES 9.1 - Introdução: Usamos congruências rotineiramente em nossa vida. Por exemplo, na contagem das horas, fazemos uso de congruência modulo 12 ou modulo 24. Na contagem de minutos e segundos, usamos congruência modulo 60. Nos calendários, na contagem dos dias da semana fazemos uso, de certa forma, da congruência modulo, e na contagem dos meses, empregamos congruência modulo 12. Os hodômetros dos carros, usados para marcar quilômetros rodados, geralmente trabalham modulo 100.000. Veremos nesta unidade como resolve congruências lineares e aplicando na resolução de equações diofantinas. 9.2 - Congruências Lineares: Definição 9.1: Chama-se congruência linear toda equação da forma ax b (mod m), onde a e b são inteiros quaisquer e m um inteiro positivo. Todo inteiro x0 tal que ax0 b (mod m) diz-se uma solução da congruência linear. Observação 9.1 - Se x0 é uma solução da congruência linear ax b (mod m), então todos os inteiros x0 + km, onde k é um inteiro arbitrário, também são soluções da congruência linear. Observação 9.2 - Duas soluções x0 e x1 da congruência ax b (mod m) congruente módulo m isto é, x0 x1 (mod m) não são consideradas soluções distintas. O número de soluções da congruência é dado pelo número de soluções mutuamente incongruente módulo m. 9.3 - Condição de Existência de Soluções: Teorema 9.1 - A congruência linear ax b (mod m) tem solução se, e somente se, d divide b, sendo d = mdc(a, m). logo 0 0 0 0ax b my ou ax my = b . 9.4 - Soluções da Congruência ax b (mod m): Teorema 9.2 - Se d divide b, sendo d = mdc(a, m), então a congruência linear ax b (mod m) tem precisamente d soluções mutuamente incongruentes módulo m, dada pela fórmula: x = xo + m d t, 0 t d – 1. Corolário 9.1 - Se o mdc(a, m) = 1, então a congruência linear ax b (mod m) tem uma única solução módulo m. 9.5 - Resolução de Equações Diofantinas Lineares por Congruências: Uma equação diofantina linear, é uma equação da forma ax + by = c em que a, b, c, são números inteiros. e de acordo com o Teorema 7.1 A equação diofantina linear ax + by = c tem solução se, e somente se, d = mdc (a, b) divide c. Uma solução de uma equação diofantina linear é um par de inteiros x0, y0 que satisfaz a equação, então: ax0 + by0 = c e ax0 - c = - by o que implica: ax0 b (mod m), Assim sendo, para obter uma solução particular da equação diofantina linear, basta determinar uma solução qualquer x = x0 da congruência linear ax c (mod b), e substituir este valor x0 de x na equação ax + by = c afim de encontrar o valor correspondente y0 de y, isto é, tal que ax0 + by0 = c. Obviamente, também se pode obter uma solução particular da equação diofantina linear, determinando uma solução qualquer y = y0 da congruência linear. bx c (mod a). Questões Resolvidas 01) Resolver as seguintes congruências lineares: a) 2x 1 (mod 17). Solução: O mdc(2, 17) = 1 e 1 | 1, logo a congruência possui uma solução. 2x 1 (mod 17); 1 2.9 (mod 17); 2x 2.9 (mod 17); x 9 (mod 17) b) 3x 1 (mod 17). Solução: O mdc(3, 17) = 1 e 1 | 1, logo a congruência possui uma solução. 3x 1 (mod 17); 1 3.6 (mod 17); 3x 3.6 (mod 17); x 6 (mod 17) c) 3x 6 (mod 18). Solução: O mdc(3, 18) = 3, e 3 | 6, logo a congruência possui três soluções. Dividindo por 3 a congruência dada, obtemos: x 2 (mod 6) Assim a solução geral é x = 2 + 6t, t = 0, 1 e 2 dando x = 2, x = 8 e x = 14 d) 25x 15 (mod 29). Solução: O mdc(25, 29) = 1 e 1 | 15, logo a congruência possui uma solução 25x 15 (mod 29) dividindo por 5, temos: 5x 3 (mod 29); 3 5.18 (mod 29) 5x 5.18 (mod 29); x 18 (mod 29) e) 5x 2 (mod 26). Solução: O mdc(5, 26) = 1, logo a congruência possui uma solução 5x 2 (mod 26); 2 5.16 (mod 26); 5x 5.16 (mod 26); x 16 (mod 26) f) 6x 15 (mod 21). Solução: O mdc(6, 21) = 3 e 3 | 15, logo a congruência possui três soluções 6x 15 (mod 21). Dividindo por 3, temos : 2x 5 (mod 7); 5 2.6 (mod 7) 2x 2.6 (mod 7); x 6 (mod 7). A solução geral é: x = 6 + 7t, t = 0, 1 e 2, dando: 4) 37x 16(mod 19) R: 5) 5x 20(mod 15) R: 6) 3x 1(mod 25) R: 7) 9x 1(mod 65) R: 8) 6x 10 (mod 22) R: 9) 14x 1(mod 77) R: 10) 15x 9 (mod 12) R: 11) 6x 10 (mod 22) R: 12) 9x 12 (mod 21) R: UNIDADE X – SISTEMAS CONGRUÊNCIAS LINEARES 10.1 - Introdução: No século um, o matemático chinês chamado Sun-Tsu se perguntou? Que número ser a esse de forma que quando dividido por 3, o resto é 2; quando dividido por 5, o resto é 3, e quando dividido por 7, o resto é 2?. A pergunta é Qual é a solução para o seguinte sistema de congruências? x 2 (mod 3) x 3 (mod 5) x 2 (mod 7) Definição 10.1 - Um sistema de congruências lineares é um sistema da forma abaixo: 1 1 1 2 2 2 r r r A x B (mod m ) A x B (mod m ) A x B (mod m )  Arx Br (mod mr) onde Ai, i = 1,2, ..., r são inteiros supostamente não nulos. Uma solução do sistema é um inteiro x0 que é solução de cada uma das congruências que dele fazem partes. Exemplo 10.1: 3x 1 (mod 5) 2x 3 (mod 9). Teorema 10.1 - Um sistema x a1 (mod m1); x a2 (mod m2) admite solução se, e somente se, a1 – a2 é divisível por d = mdc(m1, m2). Neste caso, se x0 é uma solução particular do sistema e se m = mmc(m1, m2) então x = x0 (mod m) é sua solução geral. Corolário 10.1 - Um sistema de congruências lineares x a1 (mod m1); x a2 (mod m2); ... ; x ar (mod mr) admite solução se, e somente se, ai – aj é divisível por dij = mdc(mi, mj). Nesse caso se x0 é uma solução particular, então a solução geral do sistema é dada por x x0 (mod m) onde m = mmc(m1, m2, ... , mr). Exemplo 10.2: x 1 (mod 5); x 3 (mod 4); x 9 (mod 6). Teorema 10.2 - (do Resto Chinês): Sejam m1, m2,..., mr números inteiros maiores que zero e tais que mdc(mi, mj) = 1, i j. Façamos m = m1m2...mr e sejam b1, b2, ... , br, respectivamente, soluções das congruências lineares jm m y 1 (mod mj). Então o sistema x a1 (mod m1); x a2 (mod m2); ... ; x ar (mod mr) admite soluções para quaisquer a1, a2, ... , ar  e sua solução geral é dada por: 1 1 2 2 r r 1 2 r M M M x a b a b ... a b (mod m). m m m  Este algoritmo, utilizado para resolver sistemas de congruências lineares, é muito antigo e foi inventado, independentemente, pelos chineses e pelos gregos, para resolver problemas de astronomia. O algoritmo chinês do resto tem este nome porque um dos primeiros lugares em que aparece foi no livro Manual de aritmética do mestre Sun-Tsu, escrito entre 287 d.C. e 473 d.C. Exemplo: x 1 (mod 2); x 2 (mod 3); x 3 (mod 5). Questões Resolvidas 01) Resolver os seguintes sistemas de congruências lineares: a) x 1 (mod 2), x 1 (mod 3). Solução: Como o mdc(2, 3) = 1 o sistema possui solução. A solução geral da 1a. é x = 1 + 2a, substituindo este valor na 2a, obtemos 1 + 2 a 1 (mod 3); 2 a 0 (mod 3); a 0 (mod 3). Logo a = 3b; substituindo este valor em x = 1 + 2a, temos x = 1 + 2(3b), dando x = 1 + 6b que é a solução geral do sistema ou x 1(mod 6) . b) x 5 (mod 12), x 7 (mod 19). Solução: Como mdc(12, 19) = 1 o sistema possui solução. A solução geral da 1a. é x = 5 + 12a; substituindo este valor na 2a, obtemos: 5 + 12 a 7 (mod 19); 12 a 2 (mod 19); 6 a 1 (mod 19); 1 6.16 (mod 19) 6; a 6.16 (mod 19); a 16 (mod 19). A solução geral é a = 16 + 19b; substituindo este valor em x = 5 + 12 a, temos x = 5 + 12(16 + 19b), dando x = 197 + 228b, que é a solução do sistema ou x 197(mod 228) . 02) Resolver os seguintes sistemas de congruências lineares: a) x 3 (mod 5), x 5 (mod 7), x 7 (mod 11). Solução: Como mdc(5, 7) = mdc(5, 11) = mdc(7, 11) = 1 o sistema possui solução. A solução geral da 1a. é x = 3 + 5 a, substituindo este valor na 2a, obtemos 3 + 5 a 5 (mod 7); 5 a 2 (mod 7); 2 5.6 (mod 7); 5 a 5.6 (mod 7) a 6 (mod 7) dando a solução geral a = 6 + 7b; substituindo este valor em x = 3 + 5 a temos: x = 3 + 5(6 + 7b) = 33 + 35b. Substituindo este valor na 3 a equação, temos: 33 + 35b 7 (mod 11); 35b –26 (mod 11); 35b 2b (mod 11); 2b –26 (mod 11). b –13 (mod 11) dando a solução b = –13 + 11c. Substituindo este valor na expressão x = 33 + 35 b, temos x = 33 + 35(–13 + 11c) = –422 + 385c que é a solução geral do sistema x 348(mod 385) . b) x 1 (mod 5), x 5 (mod 7), x 7 (mod 11). Solução: Como o mdc(5, 7) = mdc(5, 11) = mdc(7, 11) = 1 o sistema possui solução. A solução geral da 1a congruência é: x = 1 + 5 a.; substituindo este valor na 2a., obtemos 1 + 5 a 5 (mod 7); 5 a 4 (mod 7); 4 5.5 (mod 7); 5 a 5.5 (mod 7) a 5 (mod 7), dando a solução geral a = 5 + 7b; substituindo este valor em x = 1 + 5 a, obtemos x = 1 + 5(5 + 7b) = 26 + 35b; substituindo este valor na 3a congruência, temos: De 4x 1 (mod 7), x 2 (mod 7). De 5x 9 (mod 11), x 4 (mod 11). Vamos resolver pelo método do resto chinês: a1 = 3, a2 = 3, a3 = 2, a4 = 4, m1= 5 , m2 = 2, m3 = 7, m4 = 11. m = m1 m2 m3 m4 = 5.2.7.11 = 770. 1 m m = 2.7.11 = 154, 154b1 1 (mod 5), b1 = - 1. 2 m m = 5.7.11 = 385, 385b2 1 (mod 2), b2 = 1. 3 m m = 5.2.11 = 110, 110b3 1 (mod 7), b3 = 3. 4 m m = 5.2.7 = 70, 70b4 1 (mod 11), b4 = 3. A solução é: x 3.(–1).154 + 3.1.385 + 2.3.110 + 4.3.70 (mod 770) ou x 653 (mod 770). 4) Resolver os seguintes sistemas de congruências lineares: 1) x 8 (mod 9), x 2 (mod 3), x 5 (mod 7). Solução: Como o mdc(9, 3) = 3 e 3 | (8 - 2), mdc(9, 7) = mdc(3, 7) = 1 o sistema possui solução. A solução geral da 1a congruência é: x = 8 + 9 a , substituindo este valor na 2a congruência, obtemos: 8 + 9 a 2 (mod 3); 9 a –6 (mod 3); 3 a - 2 (mod 1); a 1 (mod 7), dando a solução geral a = 1 + b; substituindo este valor em x = 8 + 9 a, temos: x = 8 + 9(1 + b) = 17 + 9b; substituindo este valor na 3a congruência, temos: 17 + 9b 5 (mod 7); 9b –12 (mod 7); 3b – 4 (mod 7); – 4 3 (mod 7); 3b 3 (mod 7); b 1 (mod 7); dando a solução geral b = 1 + 7c; substituindo este valor em x = 17 + 9b, temos x = 17 + 9(1 + 7c) = 26 + 63c que é a solução geral do sistema. 2) x 4 (mod 6), x 13 (mod 15), x 8 (mod 14), x 1 (mod 7). Solução: Como o mdc(6, 15) = 3 e 3 | (13 - 4), mdc(6, 14) = 2 e 2 | (8 – 4), mdc(6, 7) = mdc(15, 14) = mdc(15, 7) = 1 e mdc(14, 7) = 7 e 7 | (8 – 1) o sistema possui solução. A solução geral da 1a congruência é: x = 4 + 6 a; substituindo este valor na 2a congruência, obtemos: 4 + 6 a 13 (mod 15); 6 a 9 (mod 15); 2 a 3 (mod 5); 3 8 (mod 5); 2 a 8 (mod 5); a 4 (mod 5); dando a solução geral a = 4 + 5b; substituindo este valor em x = 4 + 6 a, temos x = 4 + 6(4 + 5b) = 28 + 30b; substituindo este valor na 3a congruência, temos: 28 + 30b 8 (mod 14); 30b –20 (mod 14); 3b – 2 (mod 7); – 2 12 (mod 7); 3b 12 (mod 7); b 4 (mod 7); dando a solução geral b = 4 + 7c; substituindo este valor em x =28 + 30b, temos: x = 28 + 30(4 + 7c). x = 148 + 210c; substituindo este valor na 4a congruência, temos: 148 + 210c 1 (mod 7); 210c – 147 (mod 7); 30c –21 (mod 1); –21 30 (mod 1); 30c 30 (mod 1); c 1 (mod 1); dando a solução geral c = 1 + d; substituindo este valor em x =148 + 210c; temos: x = 148 + 210(1 + d) = 358 + 210c que é a solução geral do sistema. 3) x 0 (mod 3), x 1 (mod 4), 17x 9 (mod 23) Solução: Como o mdc(3, 4) = mdc(3, 23) = mdc(4, 23) = 1 o sistema possui solução. A congruência 17x 9 (mod 23) pode ser transformada em x 10 (mod 23) A solução geral da 1a congruência é: x = 3 a; substituindo este valor na 2a congruência, obtemos 3 a 1 (mod 4); 1 9 (mod 4); 3 a 9 (mod 4); a 3 (mod 4); dando a solução geral a = 3 + 4b; substituindo este valor em x =3 a, temos; x = 3(3 + 4b); x = 9 + 12b; substituindo este valor na 3a congruência, temos: 9 + 12b 10 (mod 23); 12b 1 (mod 23); 1 12.2 (mod 23); 12b 12.2 (mod 23); b 2 (mod 23); dando a solução geral b = 2 + 23c; substituindo este valor em x = 9 + 12b, temos: x = 9 + 12(2 + 23c) = 33 + 276c que é a solução geral do sistema. Questões Propostas 01) Resolver os seguintes sistemas de congruências lineares: 01) 3x 1(mod 7) 5x 2(mod11) 4x 3(mod13) R: x 810(mod 1001) 11) x 1(mod 10) x 4(mod 11) x 6(mod 13) R: x 851(mod 1430) 02) x 8(mod 9) x 2(mod 3) x 5(mod 7) R: x 26(mod 63) 12) x 2 (mod 5) x 3 (mod 6) x 8 (mod 9) R: 03) x 1(mod 3) x 2(mod 5) x 3(mod 7) R: x 52(mod 105) 13) x 1 (mod 4) x 3 (mod 6) x 6 (mod 9) R: 04) x 2(mod11) x 4(mod12) x 5(mod13) R: x 772(mod 1716) 14) x 7 (mod 15) x 4 (mod 32) x 7 (mod 11) R: 05) x 3(mod11) x 5(mod19) x 10(mod 29) R: x 4128(mod 6061) 15) 21x 15(mod 45) 27x 33(mod 48) 22x 18(mod 46) R: 06) x 5(mod 7) x 1(mod 9) x 6(mod10) R: x 26(mod 630) 16) x 2(mod 3) x 3(mod 5) x 2(mod 7) R 07) x 1(mod 2) x 2(mod 3) x 5(mod 7) R: x 5(mod 42) 17) x 8(mod5) x 5(mod3) x 11(mod 7) x 2(mod 4) R: x 158(mod 420) 08) 2x 1(mod 5) 3x 2(mod 7) 5x 7(mod11) R: x 283(mod 385) 18) x 2(mod 3) x 3(mod 4) x 4(mod 5) x 5(mod 6) R: x 119(mod 360) 09) x 7(mod11) 3x 5(mod13) 7x 4(mod 5) R: x 227(mod 715) 19) x 1(mod 3) x 3(mod 5) x 5(mod8) x 7(mod11) R: 10) x 3(mod10) x 11(mod13) x 15(mod17) R: x 1103(mod 2210) 20) x 2(mod 4) x 3(mod5) x 4(mod 7) x 5(mod9) R acordou e fez exatamente aquilo que haviam feito os outros dois anteriormente. Na manha seguinte os três marinheiros dividiram novamente o monte de cocos em três partes e voltou a sobrar um coco que deram ao macaco. Quantos cocos havia inicialmente no monte? Com quantos cocos ficou cada um dos marinheiros? R: 14) Um grupo de 17 macacos guarda suas bananas em 11 cestas de igual conteúdo e em uma 12ª cesta contendo 6 bananas. Eles podem dividir o total de suas bananas em 17 grupos iguais. Qual é o menor número de bananas que eles podem possuir? R: 15) Generais Chineses contavam o número de soldados sobreviventes de uma batalha alinhando-os sucessivamente em filas de determinados tamanhos, contando cada vez o número de soldados restantes e calculando o total de sobreviventes à partir desses dados. Um general tinha inicialmente 1200 soldados antes de uma batalha; após a batalha, ao alinhá-los em filas de 5 soldados, restaram 3 soldados; ao alinhá-los em filas de 6 soldados, restaram também 3 soldados; ao alinhá-los em filas 7 soldados, restou 1 soldado; finalmente, ao alinhá-los em filas de 11 soldados, nenhum restou. Quantos soldados sobreviveram à batalha? R: UNIDADE XI – TEOREMA DE FERMAT e WILSON 11.1 - Introdução: Desde, pelo menos, 500 anos antes de Cristo, os chineses sabiam que, se p é um número primo, então p| 2 p -2. Coube a Pierre de Fermat, no século XVII, generalizar este resultado, enunciando um pequeno, mas notável teorema que se constitui no resultado central desta unidade. Nesta unidade estudaremos algumas propriedades referentes a congruências modulo números primos que são as aplicações do pequeno teorema de Fermat e o teorema Wilson e sua relevância no estudo da teoria dos números. 11.2 - Teorema de Fermat: Teorema 11.1 - (de Fermat) - Se p é um primo e se p não divide a, então a p-1 1 (mod p). Corolário 11.1 - Se p é primo, então a p a (mod p) qualquer que seja o inteiro a. Exemplo 11.1 - Verificar o teorema de Fermat para a = 3 e p = 7. Exemplo 11.2 - Mostrar que 5 38 4 (mod 11). Exemplo 11.3 - Mostrar que 117 é composto. Teorema 11.2: Se p e q são primos distintos tais que a p a (mod q) e a q a (mod p), então: a p.q a (mod p.q). Exemplo 11.4 - Mostrar que 2 340 1 (mod 341). 11.2 - Teorema de Wilson: Teorema 11.3 - (de Wilson)- Se p é primo, então (p – 1)! –1 (mod p) Teorema 11.4 - Se (n – 1)! –1 (mod n), então n é primo. Obs: O teorema de Wilson e o seu recíproco dão um critério para se reconhecer se um inteiro dado é primo um inteiro n > 1 é primo se e somente se, (n – 1)! –1 (mod n). Entretanto, para inteiros grandes este critério é impraticável e por isso apenas tem utilização teórica. Exemplo 11.5 - Verificar o teorema de Wilson com p = 7. Exemplo 11.6 - Reconhecer se o inteiro 11 é primo. Questões Resolvidas 01) Verificar o teorema de Fermat com a = 2 e p = 13. Solução: Temos que mostrar que 2 12 1 (mod 13). 2 4 3 (mod 13); 2 8 9 (mod 13); 2 12 = 2 4 .2 8 3.9 1 (mod 13) 02) Verificar o teorema de Wilson para p = 5. Solução: Temos que mostrar que (5 – 1)! –1 (mod 5) 2.3 1 (mod 5); 2.3.4 4 (mod 5); 4 –1 (mod 5); logo 4! –1 (mod 5) 03) Mostrar que 8 é composto usando o teorema de Wilson: Solução: (8 – 1)! = 2.3.4.5.6.7 0 (mod 8); portanto, como (8 – 1)! não é congruente a –1 concluímos que 8 não é primo. 04) Mostrar que 19 é primo usando o recíproco do teorema de Wilson. Solução: (19 – 1)! = 2.3.4...17.18. Vamos ver a que número é congruente este fatorial. 2.3.4 = 5 (mod 19); 5.6 11 ((mod 19); 7.8 –1 (mod 19); 9.10 –5 (mod 19) 11.12 –1 (mod 19); 13.14 11 (mod 19); 15.16 12 (mod 19); 7.18 2 (mod 19). Assim 6! = 2.3.4.5.6 5.11 17 –2 (mod 19); 8! = 6!.7.8 –2.(–1) 2 (mod 19); 10! = 8!.9.10 2.(–5) 9 (mod 19); 12! = 10!.11.12 9.(–1) –9 (mod 19); 14! = 12!.13.14 –9.11 –4 (mod 19). 16! = 14!.15.16 –4.12 9 (mod 19); 18! = 16!.17.18 9.2 18 –1 (mod 19). 05) Reconhecer se 17 é primo usando o teorema de Wilson: Solução: Temos que verificar se (17–1)! –1 (mod 17). Temos: 4! 7 (mod 17); 5.6 13 (mod (17); 6! = 4!.5.6 7.13 6 (mod 17) 7.8 5 (mod 17); 8! = 6!.7.8 6.5 –4 (mod 17); 9.10 = 5 (mod 17) 10! = 8!.9.10 –4.5 –3 (mod 17); 11.12 13 (mod 17) 12! = 10!.11.12 –3.13 –5 (mod 17); 13.14 12 (mod 17) 14! = 12!.13.14 –5.12 8 (mod 17); 15.16 2 (mod 17) 16! = 14!.15.16 8.2 16 –1 (mod 17) 06) Verificar: a) 18 6 1 (mod 49) Solução: 18 2 30 (mod 49); 18 4 30.30 18 (mod 49). 18 6 = 18 2 .18 4 30.18 1 (mod 49) b) 18 6 1 (mod 343) Solução: 18 3 = 5832 1 (mod 343); 18 6 1 (mod 343). 7) Achar o resto da divisão de 15! por 17. Solução: 16! –1 (mod 17) pelo teorema de Wilson; –1 16 (mod 17) então, 16! 16 (mod 17); daí 15!.16 16 (mod 17). Podemos cancelar o fator 16, desde que mdc(16, 17) = 1 e portanto 15! 1 (mod 17). Concluímos que o resto procurado é 1. 8) Mostrar que, se o mdc(a, 35) = 1, então a 12 1 (mod 35). Solução: 35 = 5.7 e portanto mdc(a, 5) = mdc(a, 7) = 1. Aplicando o teorema de Fermat: a 4 1 (mod 5); a 12 1 (mod 5) logo 5 | (a 12 –1) a 6 1 (mod 7); a 12 1 (mod 7) logo 7 | (a 12 – 1). Como mdc(5, 7) = 1 então, 35 = 5.7 | (a 12 – 1) o que demonstra a 12 1 (mod 35) 9) Demonstrar que, para todo inteiro a, se tem: margem de uma edição do livro de Diofanto ao lado do problema 8, livro II, que é o problema da decomposição de um quadrado em soma de dois outros. Ele afirma que isto é impossível para cubos e potências superiores e afirma que possui uma demonstração elegante para este fato e que não cabe na margem. Ele também propõem este problema para outros matemáticos da época Frenicle, Wallis, ..... O problema é mostrar que a equação F[n], a n + b n = c n , n inteiro maior que 2, não possui soluções não triviais no sentido de que pelo menos um dos números a, b ou c é zero. É fácil de verificar que basta mostrar que F[n] não tem solução para n = 4, e para primos diferentes de 2. O caso n = 4 foi resolvido por Fermat onde ele exibe seu método a qual denomina método da descida infinita. O problema se enuncia então mostrar que para todo primo impar p, F[p] não possui soluções não triviais. O problema pode ser dividido em dois casos: O primeiro é onde se requer que nenhum dos números a, b, e c sejam divisíveis por p, e o segundo é o caso onde precisamente um dos números é divisível por p. Para n = 3, o cubo de 5 mais o de seis difere muito pouco do de sete. Este problema foi proposto em 1637, e daí seguiu-se uma busca para reproduzir a demonstração de Fermat. Como Fermat errou na solução de outros problemas, admite-se a possibilidade dele também ter errado em sua afirmação, porem não sabemos qual era sua demonstração. PRIMEIRAS TENTATIVAS As primeiras tentativas foram feitas para p = 3. Euler, no inicio do século passado, apresentou a solução neste caso. Ele cometeu enganos porem depois de um estudo minucioso da divisibilidade de números da forma a 2 +3.b 2 ele obteve uma solução correta. Gauss apresenta também uma demonstração para este caso. Com Gauss, 1801 nasce a Teoria dos Números. O caso p = 5, foi demonstrado por G.L.Dirichlet em 1928. O caso p = 7 é de Lamé (1839). Sophie Germain, em 1823, foi a primeira a tentar uma solução geral ela mostra que se 2p+1 é também primo então o primeiro caso é valido. Isto introduz um novo problema existe um numero infinito de primos para os quais 2p + 1 é também primo? Até hoje não se sabe. Com este resultado Legendre consegue mostrar a validade do primeiro caso para todo primo menor que 100. Lamé e Cauchy apresentam demonstrações erradas. KUMMER Até o fim de 1993 o único teorema geral que se conseguiu é devido ao matemático alemão E. Kummer. Ele introduz a noção de primo regular, estes primos estão relacionados a certas condições de divisibilidade de uns números chamados números de Bernouilli, Kummer demonstra por volta de 1850, que F[p] é válido para todo primo regular. Infelizmente não se sabe se existem ou não infinitos primos regulares, sabe-se que existe um número infinito de primos não regulares. Os primos não regulares menores que 164 são 37, 59, 67, 101, 103, 131, 149, e 157. Aí surge com Kummer, Dirichlet e Dedekind a Teoria de Números Algébricos, teoria esta que falando grosseiramente trata de expressões contendo radicais. A noção de número primo e de decomposição é estendida a estes números. Isto sempre foi essencial em todos os casos demonstrados. Em 1816, e de novo em 1850 a Academia Francesa de Ciências ofereceu uma medalha de ouro e um prêmio de 3000 Francos a quem resolve-se o problema de Fermat. A medalha foi concedida a Kummer pelo seu brilhante trabalho neste teorema. No inicio deste Século, um matemático alemão Wohlfskehl a beira do suicídio descobriu o trabalho de Kummer sobre o teorema de Fermat e decidiu dedicar-se a sua leitura. Ele deixou sua fortuna na Königliche Gesellschaft der Wissenschaften, em Göttingen, Alemanha, oferecendo um prêmio de 100.000DM pelo solução deste problema, devido a inflação este prêmio está reduzido a 10.000DM. Este prêmio leva a Academia a ter que selecionar milhares de trabalhos apresentados anualmente, dentre os quais a grande maioria ou não fazem sentido, ou são muito elementares. Deve-se observar que Fermat era um matemático muito bom ele resolveu o caso n = 4 aplicando seu método denominado a “descente infinita”, e que qualquer solução que se Fermat tinha em mente deveria ter conteúdo matemático. FERMAT COMPUTACIONAL Depois de Kummer um grande números de matemáticos como Wagstaff, Morishima, Inkeri, Vandiver, Eichler, Brückner, tentaram desenvolver critérios para que pudéssemos verificar a validade de F[p] via computador. Estes critérios são complicados para mencionarmos aqui. Um deles porem é bem simples Wiefrich (1909). Se p 2 não divide 2p-1-1 então o primeiro caso do teorema de Fermat é verdadeiro. Até hoje só conhecemos dois números dentre todos os primos menores 3x109 para os quais isto não é verdade 1093 e 3511. Aí temos um novo problema existe um número infinito destas exceções? Desenvolveu-se também critérios para o estudo do caso II para primos não regulares, e com isto Wagstaff em 1976 mostra FLT para todo p < 125000. Em 1992 Buhlen verificou a validade de FLT para todos os primos menores que 4000000. Outra direção tomada foi de estudar o tamanho da solução, i.e.., se x é o menor valor de uma solução de F[p] qual é um estimativa de x, ou melhor qual é a estimativa do número que deve-se tentar para exibir um contra exemplo? Usando-se o resultado de Wagstaff a conclusão é que deveríamos tentar números com mais de 18x10 11 dígitos. Isto mostra que contra-exemplos está totalmente fora de nosso alcance. TEORIA DE CURVAS Na década dos 20, Mordell olha para o problema do ponto de vista de geometria algébrico F[p] é a equação de uma curva algébrica, e dizer que existe uma solução não trivial significa dizer que ela tem uma solução ou ponto com coordenadas racionais, ou simplesmente uma solução racional. O primeiro passo seria mostrar que estas curvas teriam somente um número finito de pontos racionais, desde que um dos seus invariantes, seu gênero seja maior que dois. Em 1983 o matemático alemão G. Faltings demonstrou esta conjectura, o que lhe valeu a Field Medal prêmio quadrienal ortografo nos Congressos Internacionais aos melhores trabalhos do período, equivalente ao prêmio Nobel para matemática. Seguindo a idéia de Faltings em trazer toda maquinaria moderna da geometria algébrica para a teoria de números, um grupo de matemáticos associa ao problema de Fermat uma curva algébrica especial que possui muita estrutura aritmética a curva elítica. As curvas de primeiro grau, equação linear em duas variáveis representa uma reta no plano as do segundo grau representam cônicas (elipse, hipérbole, parábola ou circunferência). Uma equação do terceiro grau representa uma cúbica, ela pode ser transformada ou em y = x(x+a)(x+b) ou em y 2 = x(x-a)(x+b). Esta última chama-se curva elítica, será indicada por E[a, b]. Elas tem este nome por estarem associadas as integrais elíticas, integrais estas que são duplamente periódicas. Elas também possuem uma operação natural de adição de pontos. A curva é não singular se a e b são distintos e diferentes de zero. Estudar a aritmética da curva significa estudar os pares de inteiros que satisfazem sua equação. Seja E uma curva elítica. Para cada primo p vamos chamar de n(p) o número de soluções de sua equação modulo p. Quando os números n(p) possuem uma fórmula aritmética de cálculo a curva chama-se modular. Em 1955 um matemático japonês chamado Tanyama postulou que toda curva elítica onde a e b são números racionais é uma curva modular. Um matemático alemão G. Frey em 1980 teve a idéia de associar a cada solução {a, b, c} de F[p] a curva elítica E[a n ,b n ] a qual tem uma estrutura algébrica muito estranha, e daí a suspeita de que tal curva não poderia existir e isto implicaria na não existência da solução de F[p]. Em 1986 K. Ribet mostra que a curva associada a F[p] não é modular, e daí a conjectura de Tanyiama implica em FLT !!!. No fundo o que Ribet fez foi mostrar que uma conjectura mais fraca, a de J P Serre, um dos grandes matemáticos deste século, se aplica a curva de Frey. ANDREW WILES. Andrew Wiles nasceu em 1954 na Inglaterra. Ele conta que quando tinha dez anos pegou na biblioteca um livro onde viu este problema e desde então se propôs a resolvê-lo. Deixou depois de varias tentativas amadora, o problema de lado foi estudar matemática em Cambridge com um grande especialista em teoria de números, John Coates. Veio para Harvard onde passou dois anos e resolveu dois problemas em aberto nesta área. Em seguida aceita uma posição de Professor em Princeton. Quando soube dos resultados de Ribet, ele ganhou confiança de que poderia resolve FLT e ao contrario do matemático comum ele decide se isolar por sete anos ate apresentar uma solução ao problema. Levou cinco anos para ter uma idéia da solução.