Teoria dos números, Notas de estudo de Física

Baixe Teoria dos números e outras Notas de estudo em PDF para Física, somente na Docsity! João Filipe Queiró TEORIA DOS NÚMEROS Departamento de Matemática - Universidade de Coimbra 2008 As folhas que se seguem contêm um resumo das matérias estudadas na disciplina de Teoria dos Números. Esta disciplina constitui uma boa introdução ao racioćınio dedutivo, com as afirmações a serem rigorosamente demonstradas a partir de outras anteriores. No presente texto, o fim de uma demonstração é assinalado pelo śımbolo . O estudante, seja na demonstração de resultados teóricos seja na resolução de pro- blemas, deve exercitar-se na redacção de textos matemáticos e na correcta exposição de racioćınios lógicos. Referências bibliográficas: I. Niven, H. Zuckerman e H. Montgomery, An Introduction to the Theory of Numbers 5a ed., New York, John Wiley & Sons, 1991. G. Hardy e E. Wright, An Introduction to the Theory of Numbers 5a ed., Oxford, Clarendon Press, 1979. 1 Suporemos conhecida a relação de ordem usual nos inteiros, denotada pelo śımbolo <. Dados dois inteiros a e b distintos, tem-se que ou a < b ou b < a. A relação de ordem nos inteiros relaciona-se com as operações através das seguintes propriedades (onde a e b designam inteiros arbitrários): • a < b ∧ b < c =⇒ a < c • a < b =⇒ a + c < b + c ∀c∈Z • a < b =⇒ ac < bc ∀c∈N (Note-se que na segunda propriedade tem-se c ∈ Z, e na terceira c ∈ N.) Usaremos também o śımbolo ≤, assim definido: a ≤ b significa que a < b ∨ a = b. A relação ≤ tem propriedades análogas às da relação < . Admitiremos que em N é satisfeito o prinćıpio de boa ordenação, que afirma que qualquer subconjunto de N não vazio possui elemento mı́nimo: ∀S⊆N, S 6=∅ ∃m∈S ∀s∈S m ≤ s . Finalmente, admitiremos o prinćıpio de indução matemática, que afirma o seguinte: Seja P (n) uma afirmação sobre a variável natural n. Se P (1) é verdadeira e, para todo o k ∈ N, a verdade de P (k) implica a verdade de P (k + 1), então P (n) é verdadeira para todo o n ∈ N. Cada um destes dois prinćıpios pode ser demonstrado a partir do outro: Demonstração do prinćıpio de indução matemática a partir do prinćıpio de boa ordenação: Seja P (n) uma afirmação sobre a variável natural n tal que P (1) é verdadeira e, para todo o k ∈ N, a verdade de P (k) implica a verdade de P (k + 1). Vamos proceder por redução ao absurdo, isto é, vamos supor que P (n) não é verdadeira para todo o n ∈ N. 4 Então o conjunto S = {s ∈ N : P (s) não é verdadeira} é não vazio. Pelo prinćıpio de boa ordenação, S possui elemento mı́nimo. Chamemos m ao elemento mı́nimo de S. Como P (1) é verdadeira, m não pode ser 1, pelo que m−1 ∈ N. Como m − 1 < m e m é o mı́nimo de S, tem-se que m − 1 /∈ S, pelo que P (m − 1) é verdadeira. Mas então, pela hipótese, P (m − 1 + 1) também tem que ser verdadeira, o que está em contradição com o facto de m pertencer a S. Demonstração do prinćıpio de boa ordenação a partir do prinćıpio de indução matemática: Seja S um subconjunto de N não vazio. Seja P (n) a afirmação ∀s∈S n ≤ s . P (1) é verdadeira mas, como é evidente, P (n) não é verdadeira para todo o n ∈ N (por exemplo, sendo s ∈ S, seguramente P (s + 1) é falsa, pois s + 1 > s). Logo, pelo prinćıpio de indução, podemos afirmar que existe k ∈ N tal que P (k) é verdadeira e P (k + 1) é falsa. Vamos ver que tal k é necessariamente o mı́nimo de S. Por um lado, como P (k) é verdadeira, tem-se k ≤ s para todo o s ∈ S. Por outro lado, tem-se que k ∈ S; se não, ter-se-ia k < s para todo o s ∈ S, e portanto k + 1 ≤ s para todo o s ∈ S, e P (k + 1) seria verdadeira: contradição. Como k ∈ S e k ≤ s para todo o s ∈ S, tem-se que k é o mı́nimo de S. O prinćıpio de indução matemática tem várias variantes úteis, de que registamos duas. Primeira variante do prinćıpio de indução matemática: Seja P (n) uma afirmação so- bre a variável natural n. Se P (1) é verdadeira e, para todo o k ∈ N, a verdade de P (1), P (2), . . . , P (k) implica a verdade de P (k + 1), então P (n) é verdadeira para todo o n ∈ N. Segunda variante do prinćıpio de indução matemática: Seja a ∈ N. Seja P (n) uma afirmação sobre a variável natural n ≥ a. Se P (a) é verdadeira e, para todo o k ≥ a, a verdade de P (k) implica a verdade de P (k + 1), então P (n) é verdadeira para todo o n ≥ a. 5 Exerćıcio. Demonstre estas duas variantes do prinćıpio de indução matemática a partir do prinćıpio de boa ordenação. Como acima se disse, o conjunto de propriedades que reunimos até aqui é o ponto de partida para o nosso estudo dedutivo dos números inteiros. Mas seria posśıvel começar “mais de trás”, por exemplo com a chamada axiomática de Peano, que inicia o estudo do conjunto N a partir do seguinte conjunto de afirmações primitivas ou axiomas : • 1 ∈ N • A cada n ∈ N faz-se corresponder um único natural a que se chama o sucessor de n (notação: suc(n)) • ∀n∈N suc(n) 6= 1 • suc(m) = suc(n) =⇒ m = n • Se um subconjunto S de N satisfaz 1 ∈ S e k ∈ S ⇒ suc(k) ∈ S, então S = N. A partir destes axiomas é posśıvel definir todos os conceitos e demonstrar todas as propriedades acima mencionados.1 1O leitor interessado pode consultar, por exemplo, a obra de E. Landau Foundations of Analysis, 3rd ed., Chelsea, New York, 1966. 6 Sejam b e c dois inteiros. Um inteiro a é um divisor comum de b e c se os dividir a ambos. Se b e c forem ambos iguais a zero, todos os inteiros (não nulos) são divisores comuns de b e c. Mas se b e c não forem ambos nulos, o número de divisores comuns de b e c é finito. Definição. Sejam b e c inteiros não ambos nulos. Ao maior dos divisores comuns de b e c chama-se máximo divisor comum de b e c. A notação é (b, c). Observações. 1) O máximo divisor comum de dois inteiros não ambos nulos existe e é um inteiro positivo. 2) Outra notação habitual para o máximo divisor comum de b e c é mdc(b, c). Teorema. Sejam b e c inteiros não ambos nulos, e seja d o seu máximo divisor comum. Então existem inteiros x0 e y0 tais que d = bx0 + cy0 . Demonstração. Consideremos o conjunto C = {bx + cy : x, y ∈ Z} . Este conjunto contém de certeza inteiros positivos. Seja t o menor desses elementos positivos de C. Então t é da forma bx0 + cy0 para certos inteiros x0 e y0. Vamos ver que t = d. Comecemos por mostrar que t | b. Procedendo à divisão inteira de b por t obtemos b = qt + r, com 0 ≤ r < t. Tem-se que r = b− qt = b− q(bx0 + cy0) = b(1− qx0) + c(−qy0) que é um elemento do conjunto C. Se r fosse positivo, seria um elemento de C positivo menor do que t, contra a definição deste. Logo, r tem que ser zero, o que significa que a divisão de b por t é exacta, isto é, que t | b. Com um racioćınio análogo prova-se que t | c. Logo, t é um divisor comum de b e c. Para vermos que t = d basta observar que d, sendo um divisor comum de b e c, tem que dividir bx0 + cy0, isto é, tem que dividir t. Logo, tem-se d ≤ t. Como d é o máximo divisor comum de b e c, tem que ser d = t. 9 Observações. 1) Da demonstração deste teorema conclúımos que o máximo divisor comum de dois inteiros b e c tem as seguintes caracterizações alternativas: • é o menor elemento positivo do conjunto {bx + cy : x, y ∈ Z} e divide todos os elementos desse conjunto; • é um divisor comum positivo de b e c que é múltiplo de qualquer outro divisor comum de b e c. 2) Sendo b e c dois inteiros, se existirem x, y ∈ Z tais que bx + cy = 1, podemos concluir que (b, c) = 1, pela primeira das caracterizações alternativas do máximo divisor comum acima referidas. Se tivermos bx+ cy = t com t > 1 apenas podemos concluir que (b, c) | t. Proposição. Sejam b e c inteiros não ambos nulos. 1. Sendo m ∈ N, tem-se (mb,mc) = m(b, c). 2. Se t for um divisor comum positivo de b e c, tem-se ( b t , c t ) = 1 t (b, c) . Demonstração. 1. Tem-se (mb,mc) = min (N ∩ {mbx + mcy : x, y ∈ Z}) = m · min (N ∩ {bx + cy : x, y ∈ Z}) = m(b, c) . 2. Usando 1., vemos que (b, c) = ( t b t , t c t ) = t ( b t , c t ) o que prova a igualdade pretendida. Outras propriedades do máximo divisor comum: • (b, 0) = |b| • (b, c) = (c, b) = (b,−c) • ∀f∈Z (b, c) = (b, c + bf) Demonstração. Exerćıcio. 10 Proposição. c | ab ∧ (b, c) = 1 =⇒ c | a . Demonstração. Tem-se ab = qc e bx + cy = 1 para certos inteiros q, x, y. Vem então a = a(bx + cy) = abx + acy = qcx + acy = (qx + ay)c e, portanto, c | a. Corolário. b | a ∧ c | a ∧ (b, c) = 1 =⇒ bc | a . Demonstração. Exerćıcio. Definição. Se (b, c) = 1 dizemos que b e c são primos entre si (ou que b é primo com c). Teorema. (Algoritmo de Euclides para a determinação do máximo divisor comum.) Sejam b e c inteiros. Sem perda de generalidade, podemos supor b, c ∈ N e b > c. Proceda-se à seguinte sequência de divisões inteiras: b = q1c + r1 , 0 < r1 < c c = q2r1 + r2 , 0 < r2 < r1 r1 = q3r2 + r3 , 0 < r3 < r2 ... rk−2 = qkrk−1 + rk , 0 < rk < rk−1 rk−1 = qk+1rk . Então rk (o último resto não nulo) é o máximo divisor comum de b e c. Demonstração. Começamos por observar que, de facto, na sequência de divisões, os restos não podem permanecer sempre positivos, porque cada um é menor do que o anterior. Designemos o máximo divisor comum de b e c por d. Vamos ver que rk = d. Da última das igualdades acima indicadas conclúımos que rk | rk−1. Desse facto e da penúltima igualdade conclúımos que rk | rk−2. Da antepenúltima segue-se então que rk | rk−3. Prosseguindo desta forma, conclúımos que rk | c e, finalmente, da primeira igualdade, que rk | b. Então rk é um divisor comum de b e c e, portanto, rk | d. Como d | b e d | c, da primeira igualdade tira-se que d | r1. Da segunda sai então que d | r2. Prosseguindo desta forma, conclúımos que d | rk. Como rk | d e d | rk e ambos são positivos, tem-se que rk = d. 11 Os conceitos de máximo divisor comum e menor múltiplo comum definem-se também para mais de dois inteiros. Definição. Sejam b1, b2, . . . , bn inteiros não todos nulos. Ao maior dos divisores comuns de b1, b2, . . . , bn chama-se máximo divisor comum de b1, b2, . . . , bn. A notação é (b1, b2, . . . , bn). Proposição. Sejam b1, b2, . . . , bn inteiros não todos nulos, e seja d o seu máximo divisor comum. Então existem inteiros x1, x2, . . . , xn tais que d = b1x1 + b2x2 + · · ·+ bnxn . Além disso, d é o menor inteiro positivo que se escreve dessa forma. d pode ainda ser caracterizado como um divisor comum positivo de b1, b2, . . . , bn que é múltiplo de qualquer outro divisor comum de b1, b2, . . . , bn. Demonstração. Exerćıcio. Exerćıcio. Prove que (b1, b2, . . . , bn) = ((b1, b2, . . . , bn−1), bn) . Definição. Os inteiros b1, b2, . . . , bn dizem-se primos entre si se (b1, b2, . . . , bn) = 1. Os inteiros b1, b2, . . . , bn dizem-se primos dois a dois se (bi, bj) = 1 sempre que i 6= j. Exerćıcio. Prove que, se b1, b2, . . . , bn forem primos dois a dois, então são primos entre si. Dê um exemplo que mostre que a implicação rećıproca não é verdadeira. Definição. Sejam b1, b2, . . . , bn inteiros não nulos. Ao menor dos múltiplos comuns positivos de b1, b2, . . . , bn chama-se menor múltiplo comum de b1, b2, . . . , bn. A notação é [b1, b2, . . . , bn]. Proposição. O menor múltiplo comum de b1, b2, . . . , bn é um múltiplo comum positivo de b1, b2, . . . , bn que divide qualquer outro múltiplo comum de b1, b2, . . . , bn. Demonstração. Exerćıcio. 14 3 Os números primos Definição. Um número inteiro p > 1 diz-se um número primo se não existir nenhum divisor d de p satisfazendo 1 < d < p. Por outras palavras, um número inteiro p > 1 é primo se não tiver outros divisores positivos além de 1 e dele próprio. Se um número inteiro a > 1 não for primo diz-se composto. Exemplos. Os primeiros números primos são 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, . . . A importância dos números primos vem de que qualquer número natural (excepto 1) é um produto de números primos. Teorema. Qualquer número natural a > 1 é um produto de números primos. Demonstração. Seja a ∈ N, a > 1. Se a for primo, não há nada a provar (temos um produto com um só factor). Suponhamos que a é composto. Então a tem divisores entre 1 e a. Se m for o menor destes divisores, m é de certeza primo (porque, se não, teria divisores menores do que m que seriam também divisores de a). Designemos m por p1. Então tem-se a = p1a1 com p1 primo e 1 < a1 < a. Se a1 for primo, já chegámos à conclusão desejada. Se a1 for composto, repetindo o racioćınio anterior conclúımos que a1 tem um divisor primo p2 satisfazendo 1 < p2 < a1, donde a = p1p2a2 com p1 e p2 primos e 1 < a2 < a1 < a. Prosseguindo desta forma, obtemos números naturais a > a1 > a2 > · · ·. Como uma sucessão de números naturais não pode decrescer indefinidamente, há-de haver um momento em que um destes números é primo, digamos ps, pelo que a = p1p2 . . . ps . 15 Lema. Se um número primo dividir um produto de números inteiros, tem que dividir pelo menos um dos factores. Demonstração. Seja p um número primo. Vamos provar que, sendo n um natural qualquer ≥ 2, se p dividir um produto de n números inteiros, então tem que dividir pelo menos um dos factores. Vamos proceder por indução. O primeiro caso é n = 2. Sejam então a1, a2 dois inteiros quaisquer e suponhamos que p | a1a2. Se p dividir a1, não há mais nada a demonstrar. Se p não dividir a1, então p e a1 são primos entre si, porque p não tem outros divisores positivos senão 1 e ele próprio. Então, por uma proposição vista na secção anterior, de certeza que p | a2. Suponhamos agora que a afirmação é verdadeira para produtos de k factores e sejam a1, a2, . . . , ak+1 inteiros quaisquer tais que p | a1a2 · · · ak+1. Se p dividir ak+1, não há mais nada a demonstrar. Se p não dividir ak+1, então, pelo mesmo racioćınio do primeiro caso, p tem que dividir o produto a1a2 · · · ak e portanto, pela hipótese de indução, tem que dividir um dos inteiros a1, a2, . . . , ak. Teorema. (Teorema Fundamental da Aritmética) Qualquer número natural > 1 escreve- -se de forma única como um produto de números primos. Demonstração. Tomemos um número natural > 1 qualquer. Já sabemos que ele se escreve como um produto de números primos. Suponhamos que era posśıvel escrevê-lo como produto de números primos de duas maneiras diferentes: p1p2 · · · ps = q1q2 · · · qt factorizações em que podemos supor já retirados os factores comuns, de modo que não haja nenhum primo que figure em ambos os membros. Como p1 divide o primeiro membro, divide também o segundo, isto é, p | q1q2 · · · qt. Pelo lema anterior, segue-se que p1 tem que dividir um dos factores do segundo membro, digamos p | qj. Como ambos os números são primos, isto só pode acontecer se p1 = qj, o que contradiz o facto de não haver primos comuns nas duas factorizações. 16 São conhecidas várias demonstrações deste teorema. Uma demonstração muito simples foi descoberta recentemente: Segunda demonstração.1 Seja N1 um número natural qualquer maior que 1. Então N1 é de certeza diviśıvel por um número primo. Como N1 e N1 + 1 são primos entre si, o número N2 = N1(N1 + 1) tem que ser diviśıvel por dois números primos diferentes. Analogamente, como N2 e N2 +1 são primos entre si, o número N3 = N2(N2 +1) tem que ser diviśıvel por três números primos diferentes. Como este processo pode ser continuado indefinidamente, existe uma infinidade de números primos. Não existe nenhuma fórmula (pelo menos simples) que dê todos os números primos, nem nenhum processo geral prático de os identificar.2 Um processo sistemático de construir listas de primos é devido ao matemático grego Eratóstenes (276-194 a.C.). Lema. Se um número n for composto, tem de certeza um factor primo ≤ √n. Demonstração. O produto de dois (ou mais) números > √ n é maior que n. Crivo de Eratóstenes. Escrevemos alguns termos da sucessão dos números naturais a partir de 2. Sublinhamos o 2 e cortamos todos os seus múltiplos: 4, 6, 8,... . Agora sublinhamos o primeiro número não cortado, que é o 3, e cortamos todos os seus múltiplos ainda não cortados: 9, 15, 21,... . De novo sublinhamos o primeiro número não cortado, neste caso o 5, e cortamos todos os seus múltiplos ainda não cortados: 25, 35, 55,... . Prosseguindo desta forma é óbvio que vamos obtendo, sublinhados, os vários números primos. Se quisermos conhecer todos os primos até um dado número n, basta, pelo lema anterior, que repitamos o processo até sublinharmos um número ≥ √n. Depois disso, todos os números não cortados até n são primos e só resta sublinhá-los. 1 F. Saidak, A New Proof of Euclid’s Theorem, The American Mathematical Monthly 113 (2006), 937-938. 2 É por essa razão que é dif́ıcil encontrar números primos muito grandes. O maior número primo actualmente conhecido foi descoberto por Edson Smith em 23 de Agosto de 2008. O número é 243112609−1 . Tem 12978189 algarismos. Havia um prémio de 100000 dólares da Electronic Frontier Foundation para a primeira pessoa que descobrisse um número primo com dez milhões de algarismos. 19 Os números primos parecem distribuir-se irregularmente entre os números naturais. Por exemplo, por um lado conjectura-se (sem que ninguém o tenha conseguido provar até hoje) que há uma infinidade de pares de “primos gémeos”, isto é, pares de primos que diferem de duas unidades (como 3 e 5, 17 e 19, 4967 e 4969). Por outro lado, há lacunas de comprimento arbitrariamente grande na sucessão dos primos, como mostra o resultado seguinte. Proposição. Qualquer que seja k ∈ N, é posśıvel achar k números compostos seguidos. Demonstração. Os k números (k + 1)! + 2 , (k + 1)! + 3 , . . . , (k + 1)! + k , (k + 1)! + k + 1 são seguidos e são todos compostos (o primeiro é diviśıvel por 2, o segundo por 3, etc., até ao último, que é diviśıvel por k + 1). E, no entanto, existe uma grande regularidade na distribuição dos números primos. Isso nota-se se abstrairmos dos primos tomados individualmente e atentarmos apenas na frequência média com que eles surgem por entre os números naturais. Por exemplo: nos cinco primeiros milhares de números naturais existem, respectivamente, 168, 135, 127, 120 e 119 primos. Nos últimos cinco milhares antes de 10000000 aparecem, respectivamente, 62, 58, 67, 64 e 63. O que se constata analisando tabelas de primos é um ligeiro e gradual decrescimento do número de primos em cada milhar de números naturais. Precisemos estas observações: para cada número real positivo x, designemos por π(x) o número de primos que são ≤ x. Assim, por exemplo, π(1) = 0, π(7/2) = 2, π(10) = 4, π(11) = 5, etc. Obter uma expressão exacta para esta função seria tão dif́ıcil como obter uma fórmula para os primos. Mas vejamos qual é o seu comportamento “macroscópico”. Nas figuras seguintes1 temos representações gráficas da função π(x) para x ≤ 100 e x ≤ 50000 (usando unidades diferentes nos dois eixos para se ver melhor o que se passa). 1 D. Zagier, The First 50 Million Prime Numbers, The Mathematical Intelligencer 0 (1977), 7-19. 20 A regularidade com que π(x) cresce foi detectada por Gauss, ainda jovem. Analisando tabelas de primos, Gauss apercebeu-se da proximidade entre π(x) e a função x log x . 21 Observações. 1) As três primeiras propriedades significam que a relação de congruência módulo um natural m é uma relação de equivalência em Z. As classes de equivalência em que esta relação particiona o conjunto Z dos números inteiros chamam-se classes de congruência módulo m. Como os restos posśıveis na divisão por m são em número de m, vemos que há exactamente m classes de congruência módulo m. A classe de congruência módulo m de um inteiro a costuma representar-se por [a]m, ou simplesmente [a] se o natural m estiver impĺıcito do contexto. Outra notação comum para essa classe é a. O conjunto das classes de congruência módulo m designa-se por Zm. Os elementos de Zm são portanto os m conjuntos [0]m = {. . . , −3m, −2m, −m, 0, m, 2m, 3m, . . .} [1]m = {. . . , −3m + 1, −2m + 1, −m + 1, 1, m + 1, 2m + 1, 3m + 1, . . .} ... [m− 1]m = {. . . , −2m− 1, −m− 1, −1, m− 1, 2m− 1, 3m− 1, 4m− 1, . . .} 2) Da quinta propriedade indicada segue-se que se a ≡ b (modm) então ak ≡ bk (modm) para qualquer expoente k. Outras propriedades: • a ≡ b (modm) =⇒ (a,m) = (b,m) • a ≡ b (modm1) ∧ a ≡ b (modm2) =⇒ a ≡ b (mod [m1,m2]) Demonstração. Exerćıcio. Proposição. ax ≡ ay (modm) =⇒ x ≡ y (mod m (a,m) ). Demonstração. Ponhamos (a,m) = d. Então (a d , m d ) = 1, como sabemos. A hipótese diz-nos que m divide ax−ay = a(x− y), donde se tira facilmente que m d divide a d (x− y). Como m d e a d são primos entre si, segue-se que m d divide x− y, como pretendido. Corolário. ax ≡ ay (modm) ∧ (a,m) = 1 =⇒ x ≡ y (modm). 24 5 Os Teoremas de Euler e Fermat Definição. Seja m ∈ N. Um sistema completo de reśıduos módulo m é um conjunto de m inteiros que se obtém escolhendo um e um só elemento em cada classe de congruência módulo m. Por outras palavras, o conjunto {r1, r2, . . . , rm} é um sistema completo de reśıduos módulo m se ∀a∈Z ∃1ri a ≡ ri (modm) . Observação. Sendo {r1, r2, . . . , rm} um sistema completo de reśıduos módulo m tem-se que, se i 6= j, então ri não é congruente com rj módulo m. Definição. Seja m ∈ N. Um sistema reduzido de reśıduos módulo m é um conjunto {r1, r2, . . . , rk} de inteiros satisfazendo (ri,m) = 1 , i = 1, . . . , k i 6= j =⇒ ri não é congruente com rj módulo m ∀a∈Z,(a,m)=1 ∃1ri a ≡ ri (modm) . Observação. Da definição conclui-se imediatamente que um sistema reduzido de reśıduos módulo m se obtém tomando um sistema completo de reśıduos módulo m e retirando-lhe os elementos que não são primos com m. Teorema. Dado m ∈ N, todos os sistemas reduzidos de reśıduos módulo m têm o mesmo número de elementos. Demonstração. Sejam {r1, r2, . . . , rk} e {s1, s2, . . . , st} dois sistemas reduzidos de reśıduos módulo m. Vamos provar que k = t. Seja ri um elemento qualquer do primeiro sistema reduzido de reśıduos módulo m. Como (ri,m) = 1, existe um e um só elemento, digamos sj, do segundo sistema reduzido tal que ri ≡ sj (modm). E claro que a dois elementos diferentes do primeiro sistema não pode corresponder o mesmo elemento do segundo sistema, porque se isso acontecesse eles seriam congruentes módulo m, o que não pode ser. Logo, conseguimos definir uma função injectiva do primeiro sistema para o segundo, pelo que k ≤ t. Trocando os papéis dos dois sistemas e repetindo o racioćıcio conclúımos que t ≤ k. Logo, k = t. 25 Definição. Seja m ∈ N. Designamos por ϕ(m) o número de elementos de qualquer sistema reduzido de reśıduos módulo m. A ϕ costuma chamar-se função de Euler. Proposição. Dado m ∈ N, tem-se que ϕ(m) é igual ao número de naturais ≤ m que são primos com m. Demonstração. Basta considerar o sistema reduzido de reśıduos módulo m que se obtém do sistema completo {1, 2, . . . , m}. Exemplos. ϕ(1) = 1, ϕ(2) = 1, ϕ(3) = 2, ϕ(4) = 2, ϕ(5) = 4, ϕ(6) = 2, etc. Observação. Um número natural p é primo se e só se ϕ(p) = p− 1. Proposição. Seja {r1, r2, . . . , rϕ(m)} um sistema reduzido de reśıduos módulo m e seja a um inteiro tal que (a,m) = 1. Então {ar1, ar2, . . . , arϕ(m)} é também um sistema reduzido de reśıduos módulo m. Demonstração. Começamos por observar que (ari,m) = 1 para i = 1, . . . , ϕ(m). De facto, se m for primo com ri e também com a, não tem factores primos comuns com ri nem com a, e portanto também não os tem com o produto ari. Vejamos a seguir que, no conjunto {ar1, ar2, . . . , arϕ(m)}, não há dois inteiros congruentes módulo m. De facto, se ari ≡ arj (modm), ter-se-ia, por a e m serem primos entre si, ri ≡ rj (modm). Temos então ϕ(m) inteiros, primos com m e não congruentes dois a dois módulo m. Um tal conjunto é necessariamente um sistema reduzido de reśıduos módulo m, pois contém representantes de todas as classes de congruência módulo m cujos elementos são primos com m (recorde-se que a ≡ b (modm) =⇒ (a, m) = (b,m)). Proposição. Seja {r1, r2, . . . , rm} um sistema completo de reśıduos módulo m e seja a um inteiro tal que (a,m) = 1. Então {ar1, ar2, . . . , arm} é também um sistema completo de reśıduos módulo m. Demonstração. Exerćıcio. 26 isto é, o conjunto {x1 + kmd : k ∈ Z}. Vamos agora ver como descrever este mesmo conjunto em termos de classes de congruência módulo m. Proposição. Seja (a,m) = d e suponhamos que d | b. Sendo x1 uma solução da congruência ax ≡ b (modm), o conjunto das soluções é a união das d classes de congruência módulo m [x1]m , [ x1 + m d ] m , [ x1 + 2 m d ] m , . . . , [ x1 + (d− 1)m d ] m . Demonstração. Consideremos os d inteiros x1 + j m d , j = 0, 1, 2, . . . , d− 1. Conforme já visto, trata-se de soluções da congruência ax ≡ b (modm). Comecemos por ver que estes d inteiros são dois a dois incongruentes módulo m. Suponhamos que se tinha x1 + j m d ≡ x1 + j′ m d (modm) , com 0 ≤ j < j′ < d . Viria então que j m d ≡ j′ m d (modm) donde (j′ − j) m d ≡ 0 (mod m) o que é imposśıvel, porque 0 < j′−j < d. Conclúımos assim que as d classes de congruência módulo m referidas no enunciado são de facto todas distintas. Vejamos agora que qualquer outra solução de ax ≡ b (modm) pertence necessaria- mente a uma destas d classes de congruência módulo m. Seja x1 + t m d uma tal solução. Dividamos t por d: t = qd + r, com r ∈ {0, 1, 2, . . . , d− 1}. Vem então x1 + t m d = x1 + (qd + r) m d = x1 + qm + r m d ≡ x1 + r m d (modm) . Exemplo. A congruência 6x ≡ 3 (mod 15) tem soluções, porque (6, 15) = 3 e 3 | 3. As soluções são as mesmas que as da congruência 6 3 x ≡ 3 3 (mod 15 3 ), isto é, 2x ≡ 1 (mod 5). Uma solução desta é, por exemplo, 3. O conjunto completo das soluções é [3]5. Módulo 15 as soluções são as classes de congruência [3]15 , [8]15 , [13]15 . 29 Uma questão interessante envolvendo congruências de grau 1 é a resolução de várias congruências em simultâneo, todas com a mesma incógnita. O resultado seguinte aborda um caso especial deste problema. Teorema chinês dos restos. Sejam m1,m2, . . . ,mk naturais primos dois a dois e sejam a1, a2, . . . , ak inteiros quaisquer. Então, o sistema de congruências x ≡ a1 (modm1) x ≡ a2 (modm2) . . . x ≡ ak (modmk) tem solução. Quaisquer duas soluções são congruentes módulo m1m2 . . .mk. Demonstração. Como m1, m2, . . . ,mk são primos dois a dois, tem-se [m1,m2, . . . , mk] = m1m2 . . .mk, pelo que a segunda afirmação do enunciado é consequência de propriedades vistas da relação de congruência, já que se x′ e x′′ forem duas soluções do referido sistema de congruências tem-se x′ ≡ x′′ (modm1), x′ ≡ x′′ (modm2), ... , x′ ≡ x′′ (modmk). Vejamos agora a primeira parte. Ponhamos m = m1m2 . . . mk. Para cada j ∈ {1, 2, . . . , k}, tem-se m mj ∈ Z, claro, e ( m mj , mj) = 1 (porquê?). Então, para cada j, a congruência m mj x ≡ 1 (mod mj) tem solução. Seja bj uma solução dessa congruência. Tem-se, para cada j ∈ {1, 2, . . . , k}, por um lado m mj bj ≡ 1 (modmj) e por outro m mj bj ≡ 0 (modmi) se i 6= j porque, se i 6= j, o inteiro m mj é múltiplo de mi. Seja x0 = m m1 b1a1 + m m2 b2a2 + · · ·+ m mk bkak . Então, para cada j ∈ {1, 2, . . . , k}, tem-se x0 ≡ m mj bjaj ≡ aj (modmj) ou seja x0 é uma solução do sistema de congruências indicado no enunciado. O conjunto completo das soluções é então [x0]m. 30 7 O Teorema de Wilson. Testes de primalidade Lema. Seja p um número primo e a um inteiro. Se a2 ≡ 1 (mod p) então tem-se a ≡ 1 (mod p) ∨ a ≡ −1 (mod p). Demonstração. A condição a2 ≡ 1 (mod p) significa que p divide a2−1 = (a−1)(a+1). Como p é primo, tem que dividir pelo menos um dos factores deste produto, isto é, tem-se a ≡ 1 (mod p) ou a ≡ −1 (mod p). Teorema de Wilson. Se p é um número primo então (p− 1)! ≡ −1 (mod p). Demonstração. Para p = 2 ou p = 3, o teorema verifica-se trivialmente. Suponhamos então que p é um número primo ≥ 5. Tem-se que (p− 1)! = 2 · 3 · . . . · (p− 2) · (p− 1) . Como p− 1 ≡ −1 (mod p), para demonstrar o que se pretende bastará mostrar que 2 · 3 · . . . · (p− 2) ≡ 1 (mod p) . O produto no primeiro membro tem um número par de factores. Vamos ver que esses factores se podem “emparelhar” de modo que o produto dos dois números em cada par seja congruente com 1 módulo p. Seja a ∈ {2, 3, . . . , p − 2}. Então (a, p) = 1, pelo que existe x tal que ax ≡ 1 (mod p), e pela proposição anterior podemos tomar x ∈ {0, 1, . . . , p− 1}. Claramente x não pode ser 0 nem 1. E x também não pode ser p − 1, pois se fosse ter-se-ia a(p − 1) ≡ 1 (mod p), donde a ≡ −1 (mod p), o que não pode ser, porque a ∈ {2, 3, . . . , p− 2}. Logo, x ∈ {2, 3, . . . , p − 2}. Note-se que também não pode ser x = a, pois nesse caso ter-se-ia que a2 ≡ 1 (mod p) e então, pelo Lema, a teria que ser ≡ 1 ou ≡ p− 1. Mostrámos assim que, para cada a ∈ {2, 3, . . . , p − 2}, existe x 6= a no mesmo conjunto tal que ax ≡ 1 (mod p). E existe um só elemento nessas condições, pois se também ay ≡ 1 (mod p) com y ∈ {2, 3, . . . , p− 2} ter-se-ia ay ≡ ax (mod p) donde y = x. O rećıproco do Teorema de Wilson também é verdadeiro: 31 Demonstração da proposição. Sejam R = {r1, r2, . . . , rϕ(m)} um sistema reduzido de reśıduos módulo m, S = {s1, s2, . . . , sϕ(n)} um sistema reduzido de reśıduos módulo n e T = {t1, t2, . . . , tϕ(mn)} um sistema reduzido de reśıduos módulo mn. Consideremos um elemento qualquer tk do conjunto T . Sabemos que (tk, mn) = 1. Daqui segue-se que também (tk,m) = 1 e (tk, n) = 1 (porquê?). Pela definição de sistema reduzido de reśıduos, podemos então afirmar que ∃1ri tk ≡ ri (modm) e ∃1sj tk ≡ sj (modn) . Assim, a cada elemento tk do conjunto T corresponde por este processo um e um só par (ri, sj), com ri pertencente ao conjunto R e sj pertencente ao conjunto S. Note-se que a elementos diferentes do conjunto T correspondem pares diferentes: se a th (distinto de tk) também correspondesse o par (ri, sj), ter-se-ia th ≡ ri (modm) e th ≡ sj (modn), donde th ≡ tk (modm) e th ≡ tk (modn); como m e n são primos entre si, viria então th ≡ tk (modmn), contra o facto de ambos os números pertencerem a um mesmo sistema reduzido de reśıduos módulo mn. Reciprocamente, consideremos um par (ri, sj), com ri pertencente ao conjunto R e sj pertencente ao conjunto S. Pelo teorema chinês dos restos (aplicável porque m e n são primos entre si), podemos afirmar que existe um inteiro x satisfazendo x ≡ ri (modm) x ≡ sj (modn) Por uma propriedade das congruências, como (ri,m) = 1 e (sj, n) = 1 tem-se que (x,m) = 1 e (x, n) = 1. Daqui segue-se que também (x,mn) = 1 (porquê?). Logo, como T é um sistema reduzido de reśıduos módulo mn, existe um tk nesse conjunto tal que x ≡ tk (modmn) (e não podem existir dois elementos do sistema nessas condições, porque se existissem seriam congruentes módulo mn). Assim, a cada par (ri, sj) corresponde por este processo um e um só elemento tk. Resta notar que a pares diferentes correspondem elementos diferentes do conjunto T : se a (ri′ , sj′) (distinto de (ri, sj)) também correspon- desse o elemento tk, ter-se-ia ri′ ≡ ri (modm) e sj′ ≡ sj (modn), o que não pode ser, por R ser um sistema reduzido de reśıduos módulo m e S ser um sistema reduzido de reśıduos módulo n. Estabelecemos assim uma bijecção entre o conjunto T e o conjunto dos pares (ri, sj), com ri pertencente ao conjunto R e sj pertencente ao conjunto S. Este conjunto de pares, que é o produto cartesiano R× S, tem ϕ(m)ϕ(n) elementos. 34 Observação. Este resultado não é válido se m e n não forem primos entre si. Exemplo: ϕ(4) = 2, mas ϕ(2)ϕ(2) = 1. Teorema. Seja n um número natural > 1 e seja pα11 p α2 2 · · · pαkk a sua factorização como produto de números primos. Então tem-se ϕ(n) = (pα11 − pα1−11 )(pα22 − pα2−12 ) · · · (pαkk − pαk−1k ) . Demonstração. Aplicando repetidas vezes a última proposição, conclúımos que ϕ(n) = ϕ(pα11 )ϕ(p α2 2 ) · · ·ϕ(pαkk ) pelo que o resultado segue da primeira proposição desta secção. Exemplo. ϕ(360) = ϕ(23 · 32 · 5) = (23 − 22)(32 − 3)(5− 1) = 96. Uma outra função interessante em Teoria dos Números é a função σ assim definida: para cada número natural n, σ(n) é a soma dos divisores positivos de n, incluindo 1 e n. Exemplos. σ(1) = 1, σ(2) = 3, σ(3) = 4, σ(4) = 7, σ(5) = 6, σ(6) = 12, etc. Vamos ver que o cálculo de valores de σ(n) se torna muito simples se conhecermos a factorização de n como produto de primos. Proposição. Sendo p um número primo e α um número natural, tem-se σ(pα) = pα+1 − 1 p− 1 . Demonstração. Isto é consequência imediata do facto de que os divisores de pα são 1, p, p2, . . . , pα e de que 1 + p + p2 + · · ·+ pα = p α+1 − 1 p− 1 . 35 Proposição. A função σ é multiplicativa, isto é, se m e n forem números naturais primos entre si, tem-se σ(mn) = σ(m)σ(n) . Demonstração. Começamos por observar que, sendo m e n primos entre si, qualquer divisor d de mn se escreve de modo único na forma d = d′d′′ com d′ divisor de m e d′′ divisor de n. (Isto porque os conjuntos de primos que aparecem nas factorizações de m e n são disjuntos.) Reciprocamente, dados d′ divisor de m e d′′ divisor de n, é evidente que o produto d = d′d′′ é um divisor de mn. Logo, há uma bijecção entre o conjunto dos divisores d de mn e o conjunto dos pares (d′, d′′) em que d′ é divisor de m e d′′ é divisor de n, sendo cada elemento do primeiro conjunto igual ao produto dos elementos do par que lhe corresponde no segundo conjunto. Sejam d1, d2, . . . , dτ(mn) os divisores de mn, d ′ 1, d ′ 2, . . . , d ′ τ(m) os divisores de m e d′′1, d ′′ 2, . . . , d ′′ τ(n) os divisores de n. Tem-se σ(mn) = d1 + d2 + . . . + dτ(mn) . Como cada uma destas parcelas é igual ao produto de um divisor de m por um divisor de n, conforme vimos acima, tem-se que σ(mn) é igual à soma de todos os posśıveis produtos dessa forma, isto é, σ(mn) = d′1d ′′ 1 + d ′ 1d ′′ 2 + . . . + d ′ 1d ′′ τ(n)+ + d′2d ′′ 1 + d ′ 2d ′′ 2 + . . . + d ′ 2d ′′ τ(n)+ + · · · + + d′τ(m)d ′′ 1 + d ′ τ(m)d ′′ 2 + . . . + d ′ τ(m)d ′′ τ(n) = = d′1σ(n) + d ′ 2σ(n) + . . . + d ′ τ(m)σ(n) = = σ(m)σ(n) . Observação. Este resultado não é válido se m e n não forem primos entre si. Exemplo: σ(4) 6= σ(2)σ(2). 36 Proposição. Seja k ∈ N. Se 2k − 1 for um número primo, então k é primo. Demonstração. Usamos a factorização xa − 1 = (x− 1)(1 + x + x2 + · · ·+ xa−1) válida para qualquer número real x e qualquer número natural a. Suponhamos que k é composto, digamos k = ab, com a, b > 1. Tem-se então 2k − 1 = 2ab − 1 = (2b)a − 1 = (2b − 1)(1 + 2b + 22b + · · ·+ 2(a−1)b) e 2k − 1 seria composto, contra a hipótese. Põe-se assim um problema: para que primos p é que 2p − 1 é primo? A primeira pessoa a investigar a questão explicitamente foi um frade francês, Marin Mersenne, no século XVII. Por isso os números da forma 2p−1, com p primo, chamam-se hoje números de Mersenne. A notação mais comum para 2p − 1 é Mp. Para valores pequenos de p pode ver-se “à mão” se Mp é primo ou não. Quando p aumenta isso fica cada vez mais dif́ıcil. Para tal efeito é útil o resultado seguinte: Teste de Lucas-Lehmer. Defina-se a seguinte sucessão: u1 = 4, u2 = 4 2−2 = 14, u3 = 142−2 = 194, . . . , un = u2n−1−2, . . . Então, sendo p um primo > 2, tem-se que Mp é primo se e só se Mp|up−1. A demonstração do Teste de Lucas-Lehmer não é muito dif́ıcil, mas está fora do âmbito desta disciplina, pois usa conhecimentos da disciplina de Álgebra do 2o ano. Na tabela seguinte registam-se os primos de Mersenne descobertos até hoje (Setem- bro de 2008). Na primeira coluna indica-se o número de ordem dos sucessivos primos de Mersenne: o primeiro, o segundo, etc. Nos sete últimos números indicados encontra-se áı um ponto de interrogação, pois embora os p indicados nessas linhas (20996011, 24036583, 25964951, 30402457, 32582657, 37156667 e 43112609) dêem origem a primos de Mersenne, não se sabe de momento se se trata dos 40o, 41o, 42o, 43o, 44o, 45o e 46o primos de Mersenne. 39 A busca de números primos de Mersenne # p No de algarismos de Mp Ano Autor da descoberta 1 2 1 — — 2 3 1 — — 3 5 2 — — 4 7 3 — — 5 13 4 — — 6 17 6 1588 Cataldi 7 19 6 1588 Cataldi 8 31 10 1772 Euler 9 61 19 1883 Pervushin 10 89 27 1911 Powers 11 107 33 1914 Powers 12 127 39 1876 Lucas 13 521 157 1952 Robinson 14 607 183 1952 Robinson 15 1279 386 1952 Robinson 16 2203 664 1952 Robinson 17 2281 687 1952 Robinson 18 3217 969 1957 Riesel 19 4253 1281 1961 Hurwitz 20 4423 1332 1961 Hurwitz 21 9689 2917 1963 Gillies 22 9941 2993 1963 Gillies 23 11213 3376 1963 Gillies 24 19937 6002 1971 Tuckerman 25 21701 6533 1978 Noll e Nickel 26 23209 6987 1979 Noll 27 44497 13395 1979 Nelson e Slowinski 28 86243 25962 1982 Slowinski 29 110503 33265 1988 Colquitt e Welsh 30 132049 39751 1983 Slowinski 31 216091 65050 1985 Slowinski 32 756839 227832 1992 Slowinski e Gage 33 859433 258716 1994 Slowinski e Gage 34 1257787 378632 1996 Slowinski e Gage 35 1398269 420921 1996 Armengaud, Woltman, etc. 36 2976221 895932 1997 Spence, Woltman, etc. 37 3021377 909526 1998 Clarkson, Woltman, Kurowski, etc. 38 6972593 2098960 1999 Hajratwala, Woltman, Kurowski, etc. 39 13466917 4053946 2001 Cameron, Woltman, Kurowski, etc. ? 20996011 6320430 2003 Shafer, Woltman, Kurowski, etc. ? 24036583 7235733 2004 Findley, Woltman, Kurowski, etc. ? 25964951 7816230 2005 Nowak, Woltman, Kurowski, etc. ? 30402457 9152052 2005 Cooper, Boone, Woltman, Kurowski, etc. ? 32582657 9808358 2006 Cooper, Boone, Woltman, Kurowski, etc. ? 37156667 11185272 2008 Elvenich, Woltman, Kurowski, etc. ? 43112609 12978189 2008 Smith, Woltman, Kurowski, etc. 40 A partir de M521 todos os números de Mersenne primos foram descobertos usando com- putadores. A partir de M1398269 todos os números de Mersenne primos foram descobertos usando computadores funcionando em rede através da Internet. Qualquer pessoa com um computador pessoal ligado à Internet pode colaborar no esforço computacional, usando o Teste de Lucas-Lehmer, para descobrir novos números primos de Mersenne (ver www.mersenne.org). Exerćıcio. O número M29 = 2 29− 1 é composto. Usando um computador, factorize M29 como produto de números primos. Tal como os números da forma 2k − 1, também os números da forma 2k + 1, com k ∈ N, despertam interesse, nomeadamente para saber quais os números dessa forma que são primos. Algumas experiências com expoentes k pequenos sugerem que tal acontece precisamente quando k é uma potência de 2. Exerćıcio. Prove que, se 2k + 1 for um número primo, então k é uma potência de 2. (Sugestão: Utilize — depois de a demonstrar — a seguinte factorização, válida para qualquer número real x e qualquer número natural a: x2a+1 + 1 = (x + 1)(1− x + x2 − x3 + · · ·+ x2a−2 − x2a−1 + x2a) .) Será verdadeira a afirmação rećıproca? Se k for uma potência de 2, será 2k + 1 necessariamente um número primo? Exerćıcio. Verifique que 2k + 1 é um número primo para k = 1, k = 2, k = 4, k = 8 e k = 16. Exerćıcio. Usando um computador, mostre que o número 232 + 1 é composto. Os números da forma 22 n + 1 são conhecidos por números de Fermat. Com excepção dos cinco acima indicados, não se conhece nenhum número de Fermat que seja primo. 41 Uma consequência interessante da proposição é a seguinte, relativa a equações em que o coeficiente da maior potência da incógnita é igual 1: Corolário. As ráızes racionais de uma equação da forma xn + an−1xn−1 + · · ·+ a2x2 + a1x + a0 = 0 (onde an−1, . . . , a2, a1, a0 são números inteiros) são necessariamente inteiras. Demonstração. Isto é imediato, porque se um número racional b c for raiz da equação, o denominador c tem que dividir o coeficiente de xn, que é 1. Deste resultado, com um aspecto tão simples, deduz-se a irracionalidade da maior parte das ráızes, de qualquer ı́ndice, de números inteiros. Por exemplo: Proposição. Se um número inteiro a não for um quadrado perfeito, √ a é irracional. Demonstração. Basta mostrar que a equação x2−a = 0 não tem ráızes racionais. Como o coeficiente de x2 é 1, qualquer raiz racional tem, pelo Corolário, que ser inteira. Mas se houvesse uma raiz inteira, digamos b, ter-se-ia b2 = a e a seria um quadrado perfeito. Podemos assim afirmar que √ 2, √ 3, √ 5, √ 6, √ 7, √ 8, √ 10, etc., são números irracionais. Da mesma forma, podemos demonstrar a seguinte Proposição. Se um número inteiro a não for uma potência de expoente n de um número inteiro, n √ a é irracional. Podemos assim afirmar que números como 3 √ 2, 5 √ 8, etc., etc., são números irracionais. Observação. Resta notar que a busca de ráızes racionais de equações polinomiais com coeficientes racionais se reduz facilmente ao caso das equações polinomiais com coeficientes inteiros, porque podemos multiplicar ambos os membros de uma tal equação por um inteiro escolhido de forma a fazer “desaparecer” todos os denominadores, e esta operação não altera as ráızes da equação. 44 O segundo tema desta secção refere-se a uma técnica que pode por vezes ser usada para mostrar que certas equações não têm soluções. A técnica baseia-se numa observação trivial: se dois números inteiros forem iguais, então são congruentes módulo m qualquer que seja o número natural m. Em śımbolos: sendo a e b inteiros, a = b =⇒ [∀m∈N a ≡ b (modm) ] . Isto é equivalente a dizer que [∃m∈N a ≡/ b (modm) ] =⇒ a 6= b . Assim, dada uma equação Diofantina qualquer, se nós conseguirmos encontrar um número natural m tal que, substituindo na equação o sinal = pelo sinal de congruência módulo m, a congruência resultante não tenha soluções, então a equação original também não tem soluções. Exemplo. A equação x2 + y2 = 4z + 3 não tem soluções inteiras. Demonstração. Tomemos m = 4, isto é, substituamos a equação pela correspondente congruência módulo 4. A congruência fica x2 + y2 ≡ 3 (mod 4) . Vamos ver que não há valores inteiros de x e y que satisfaçam esta congruência. Para isso basta observar o seguinte: o quadrado de qualquer inteiro ou é ≡ 0 (mod 4) ou é ≡ 1 (mod 4). Isto porquê? Se o inteiro for par, digamos 2a, o seu quadrado é 4a2, que é ≡ 0 (mod 4). Se o inteiro for ı́mpar, digamos 2a + 1, o seu quadrado é 4a2 + 4a + 1, que é ≡ 1 (mod 4). Segue-se que uma soma de quadrados ou é ≡ 0 (mod 4), ou ≡ 1 (mod 4), ou ≡ 2 (mod 4). Logo, nunca é ≡ 3 (mod 4), isto é, não existem inteiros x e y que satisfaçam a congruência x2 + y2 ≡ 3 (mod 4) . Conclúımos assim que a equação x2 + y2 = 4z + 3 não tem soluções inteiras. Claro que o problema na aplicação desta técnica está em encontrar um m conveniente. Exerćıcio. Mostre que a equação x2 + y2 = 9z + 3 não tem soluções inteiras. 45 O terceiro tema desta secção consiste em estudar dois casos especiais da equação xn + yn = zn , conhecida por equação de Fermat. O primeiro caso que vamos estudar é o caso n = 2. Interessa-nos portanto encontrar as soluções inteiras da equação x2 + y2 = z2 e é evidente que basta procurar as soluções naturais. Uma interpretação geométrica desta questão é que estamos interessados em determinar triângulos rectângulos cujos lados têm medidas inteiras. Devido a esta interpretação geométrica, um trio (x, y, z) de números naturais satisfazendo x2 + y2 = z2 diz-se um trio pitagórico. Exemplo. (3, 4, 5) é um trio pitagórico, porque 32 + 42 = 52. Uma primeira observação é a seguinte: se (x, y, z) for um trio pitagórico e k for um número natural qualquer, é evidente que (kx, ky, kz) também é um trio pitagórico. Por exemplo, (6, 8, 10) é um trio pitagórico. Definição. Um trio pitagórico cujos elementos são primos entre si diz-se primitivo. Claramente, basta procurar os trios pitagóricos primitivos. Vamos de seguida ver uma sequência de condições que tais trios têm que satisfazer. Proposição 1. Se (x, y, z) for um trio pitagórico primitivo, x e y não podem ser ambos ı́mpares. Demonstração. Vamos por absurdo. Suponhamos que x e y são ambos ı́mpares, digamos x = 2a+1 e y = 2b+1. Então x2 +y2 ≡ 2 (mod 4). Por outro lado, como x2 e y2 também são ı́mpares, z2 é par, pelo que também z é par, digamos z = 2c. Então z2 = 4c2, pelo que z2 ≡ 0 (mod 4): contradição, uma vez que estamos a supor que x2 + y2 = z2. 46 Observemos que este b tem que ser par. Se b fosse ı́mpar, a seria par (porque a e b têm paridades diferentes), digamos a = 2k e b = 2h + 1. Viria então x2 = a2 − b2 = 4k2 − (4h2 + 4h + 1) = 4(k2 − h2 − h)− 1 ≡ −1 (mod 4) o que não pode ser, porque o quadrado de um número ı́mpar é sempre ≡ 1 (mod 4). Por outro lado, temos x2 + b2 = a2 e (x, b, a) = (x, (a, b)) = (x, 1) = 1. Logo, (x, b, a) é um trio pitagórico primitivo em que o segundo número é par. Aplicando de novo o Teorema sobre os trios pitagóricos, podemos afirmar que existem dois números naturais c e d, primos entre si, de paridades diferentes e com c > d, tais que x = c2 − d2 , b = 2cd , a = c2 + d2 . Daqui sai que y2 = 4cd(c2 + d2), isto é, 4cd(c2 + d2) é um quadrado perfeito. Notemos agora que c, d e c2 + d2 são primos dois a dois. Porquê? Já sabemos que (c, d) = 1. Designemos (c, c2 + d2) por δ. Como δ divide c, também divide c2. Daqui segue-se, como δ divide c2 + d2, que δ divide d2. Logo, δ divide (c2, d2), que é igual a 1 por (c, d) o ser. Portanto, δ = 1. Analogamente, tem-se que (d, c2 + d2) = 1. Como 4cd(c2 + d2) é um quadrado perfeito e c, d e c2 + d2 são primos dois a dois, conclúımos que c, d e c2 + d2 também são quadrados perfeitos (porquê?), digamos c = e2 , d = f 2 , c2 + d2 = g2 . Daqui tiramos, finalmente, que e4 + f 4 = g2 . Mas agora observemos que g ≤ g2 = c2 + d2 = a ≤ a2 < z . Ou seja, tem-se g < z. Isto é, a partir de um trio solução da equação x4 + y4 = z2 chegámos a outro trio solução da mesma equação em que o terceiro número é mais pe- queno que o terceiro número do trio original. Podemos agora repetir este processo e vamos obtendo números naturais sempre estritamente mais pequenos. Mas é evidente que isto não pode ser: não é posśıvel arranjar uma sucessão infinita de números naturais estritamente decrescente. 49 Podemos portanto concluir o seguinte: Teorema. A equação x4 + y4 = z2 não tem soluções inteiras. E temos a consequência imediata: Corolário. A equação x4 + y4 = z4 não tem soluções inteiras. Vemos assim que a equação de Fermat xn + yn = zn tem uma infinidade de soluções inteiras quando n = 2, mas não tem nenhuma solução inteira quando n = 4. Por volta de 1630, Fermat, estudando uma tradução francesa da Arithmetica de Dio- fanto, escreveu na margem do livro: “É imposśıvel escrever um cubo como soma de dois cubos, uma quarta potência como soma de duas quartas potências, e em geral uma potência de expoente maior que 2 como soma de duas potências de igual expoente. Descobri uma demonstração maravilhosa desse facto, mas esta margem é demasiado estreita para a conter.” Ou seja: Fermat afirmou que, para n>2, a equação xn+yn = zn não tem soluções inteiras. Nenhuma demonstração deste facto foi encontrada nos papéis de Fermat, e desde então muitos matemáticos tentaram demonstrar aquela afirmação, que começou a ser conhecida como o “Último Teorema de Fermat”, embora em rigor se tratasse apenas de uma conjectura. O próprio Fermat provou o teorema no caso n = 4, utilizando a técnica acima descrita, que ficou conhecida como o método da “descida infinita”. Em 1770, o súıço Euler provou o teorema no caso n = 3, que é bastante mais dif́ıcil do que o caso n = 4. Note-se que, depois de provado o teorema no caso n = 4, basta estudar o caso em que o expoente é um primo ı́mpar. Isto pela razão seguinte. Consideremos um expoente n qualquer > 2. Se n for um múltiplo de 4, digamos n = 4k, então a equação xn+yn = zn não tem de certeza soluções inteiras, porque, se as tivesse, também a equação com expoente 4 as teria, pois se n = 4k a equação xn + yn = zn é equivalente a (xk)4 + (yk)4 = (zk)4 . 50 Se n não for um múltiplo de 4, n é de certeza diviśıvel por um primo ı́mpar p, digamos n=qp. Se a equação xn+yn = zn tiver soluções inteiras, também a equação com expoente p as tem, pois sendo n = qp a equação xn+yn = zn é equivalente a (xq)p+(yq)p = (zq)p . Basta portanto estudar o caso em que o expoente é um primo ı́mpar. No século XIX, vários matemáticos foram provando o teorema para expoentes cada vez maiores. O alemão Dirichlet provou em 1825 que o teorema vale para n=5. O francês Lamé provou em 1839 que o teorema vale para n=7. O alemão Kummer introduziu técnicas algébricas novas que permitiram provar o teorema para outros valores de n. No século XX muitos autores publicaram demonstrações erradas do resultado geral. Em 1983, o alemão Faltings (então com 29 anos) provou que, para cada n > 2, a equação xn + yn = zn tem no máximo um número finito de soluções (trios de inteiros em que os números são primos entre si), o que foi um grande progresso no sentido da demonstração do resultado geral, que afirma que esse número é zero. Usando técnicas baseadas no trabalho de Kummer, em 1993 provou-se, com a ajuda de computadores, que o teorema é válido para todos os expoentes n ≤ 4000000. Finalmente, em 1995, o inglês Wiles, num trabalho extenso e dif́ıcil, demonstrou que o Último Teorema de Fermat é verdadeiro (para todos os expoentes n > 2).6 Os resultados e técnicas utilizados mostram que o Último Teorema de Fermat não é uma curiosidade iso- lada da Teoria dos Números, mas tem relações profundas com muitos outros importantes temas da Matemática. 6 Andrew Wiles, Modular elliptic curves and Fermat’s Last Theorem, Annals of Mathematics, vol. 141 (1995), p. 443-531. 51 Proposição. O sistema EAN permite detectar erros num só algarismo. Demonstração. Suponhamos que há um erro no algarismo ai, que está substitúıdo pelo algarismo a′i. Designemos por S a soma de controlo com os algarismos correctos. Então tem-se S ≡ 0 (mod 10) . Designemos agora por S ′ a soma de controlo com o algarismo a′i na posição de ai. Suponhamos que também se tinha S ′ ≡ 0 (mod 10) e calculemos a diferença S − S ′. Se i for ı́mpar, tem-se S − S ′ = ai − a′i. Como tanto S como S ′ satisfazem a condição de controlo, ter-se-ia ai − a′i ≡ 0 (mod 10) o que é imposśıvel, porque ai e a ′ i são números distintos entre 0 e 9. Se i for par, tem-se S − S ′ = 3(ai− a′i). Como tanto S como S ′ satisfazem a condição de controlo, ter-se-ia 3(ai − a′i) ≡ 0 (mod 10) . Daqui viria, como 3 e 10 são primos entre si, que também ai − a′i ≡ 0 (mod 10), o que é imposśıvel, pela mesma razão que atrás. Como as máquinas de leitura de códigos de barras praticamente nunca cometem outros erros além dos erros num só algarismo, o sistema EAN é satisfatório. Note-se que um sistema análogo ao EAN em que a condição de controlo fosse simplesmente 13∑ i=1 ai ≡ 0 (mod 10) também detectaria esses erros, como se vê imediatamente com um racioćınio análogo ao da demonstração vista. A vantagem da introdução dos coeficientes 3 do sistema EAN está em que, conforme vamos ver a seguir, ele detecta também a maioria dos erros de troca de dois algarismos consecutivos, que uma condição de controlo com todos os coeficientes iguais a 1 deixaria evidentemente escapar. 54 Proposição. O sistema EAN permite detectar os erros de troca de dois algarismos consecutivos desde que a diferença entre estes não seja 5 (ou −5). Demonstração. Suponhamos que há uma troca entre os algarismos ai e ai+1. Só interessa considerar o caso em que ai e ai+1 são distintos. Designemos por S a soma de controlo com os algarismos na posição certa. Então tem-se S ≡ 0 (mod 10) . Designemos agora por S ′ a soma de controlo com os algarismos ai e ai+1 trocados. Poderá ter-se S ′ ≡ 0 (mod 10)? Calculemos a diferença S − S ′. Se i for par, tem-se S − S ′ = 2(ai − ai+1). Se i for ı́mpar, tem-se S − S ′ = 2(ai+1 − ai). Tem-se então S ′ ≡ 0 (mod 10) ⇐⇒ S − S ′ ≡ 0 (mod 10) ⇐⇒ 10 | 2(ai − ai+1) ⇐⇒ ai − ai+1 = ±5 . Ou seja: a condição de controlo para o número com os algarismos ai e ai+1 trocados só é satisfeita se a diferença entre ai e ai+1 for 5 ou −5. O segundo sistema de que vamos falar é o ISBN (International Standard Book Number). Este sistema associa um número10 a todos (ou quase todos) os livros publicados no mundo. Esse número, composto por dez algarismos, pode ver-se normalmente na contra-capa e na ficha técnica no verso do frontisṕıcio do livro. Como é “constrúıdo” o número ISBN de cada livro? Um primeiro grupo de algarismos (que pode ter um, dois ou mais algarismos) identifica uma ĺıngua, um páıs ou um grupo de páıses ou regiões.11 Um segundo grupo, também de comprimento variável, identifica a empresa editora. O terceiro grupo de algarismos constitui o número do livro dentro do catálogo da empresa editora. O 10o e último algarismo é o algarismo de controlo. Como é calculado este? 10 De facto, como veremos, nem sempre é exactamente um número. 11 No caso de Portugal, este primeiro grupo tem os algarismos 972 (ou 989). 55 Designemos os dez algarismos por a1, a2, a3, a4, a5, a6, a7, a8, a9, a10. Formemos a soma de controlo 10a1 + 9a2 + 8a3 + 7a4 + 6a5 + 5a6 + 4a7 + 3a8 + 2a9 + a10 . A condição que impomos para a determinação de a10 é que esta soma seja diviśıvel por 11. Isto é, a10 é escolhido de forma que 10∑ i=1 (11− i) ai ≡ 0 (mod 11) . Esta condição determina univocamente o algarismo de controlo a10 a partir dos outros dez. Mas há aqui uma diferença relativamente ao sistema EAN. Como estamos a usar congruências módulo 11, os números de 0 a 9 não chegam para esgotar os valores posśıveis para a10: a condição de controlo pode fazer com que a10 seja igual a 10. Para usar apenas um śımbolo, adopta-se nesse caso para a10 a letra maiúscula X. Exerćıcio. Se os primeiros nove algarismos do número ISBN de um livro forem 972674315 qual é o algarismo de controlo? Vamos agora ver que propriedades de detecção de erros possui o sistema ISBN. Proposição. O sistema ISBN permite detectar erros num só algarismo. Demonstração. Suponhamos que há um erro no algarismo ai, que está substitúıdo pelo algarismo a′i. Designemos por S a soma de controlo com os algarismos correctos. Então tem-se S ≡ 0 (mod 11) . Designemos agora por S ′ a soma de controlo com o algarismo a′i na posição de ai. 56 10.2 O sistema criptográfico RSA A criptografia é a ciência que se ocupa das comunicações secretas, comunicações em que há um emissor e um receptor e se pretende que nenhum terceiro tenha acesso à informação transmitida. Para atingir este objectivo, a informação, ou mensagem, é cifrada, isto é, substitúıda por outra, conforme uma regra pré-estabelecida. O receptor tem que decifrar a informação recebida, de forma a reconstituir a mensagem original. A criptografia tem uma longa história, associada principalmente a comunicações militares. Uma das técnicas mais simples, e mais antigas, é a simples substituição de cada letra do alfabeto por outra de acordo com uma tabela fixa.12 Esta técnica não é muito eficaz, já que é simples decifrar mensagens cifradas desta forma usando tabelas de frequência das letras na ĺıngua em causa. Ao longo dos anos desenvolveram-se técnicas muito variadas e progressivamente mais sofisticadas, que não podemos analisar aqui.13 Um método recente, muito interessante, utiliza resultados elementares de Teoria dos Números, nomeadamente o Teorema de Euler, já estudado. Recorde-se que este teorema afirma que, sendo m um número natural, se a for um inteiro primo com m tem-se aϕ(m) ≡ 1 (modm), onde ϕ é a função de Euler. O resultado central é o seguinte: Proposição. Seja m um número natural e seja a um inteiro primo com m. Sendo k e h números naturais, tem-se que, se kh ≡ 1 (modϕ(m)), então akh ≡ a (modm). Demonstração. Se kh ≡ 1 (modϕ(m)) , tem-se kh = 1 + tϕ(m) para certo inteiro não-negativo t. Vem então akh = a1+tϕ(m) = a · atϕ(m) = a · (aϕ(m))t ≡ a (modm) onde usámos o Teorema de Euler. 12 Uma técnica de cifragem deste tipo, associada ao nome de Júlio César, consiste na substituição de cada letra pela letra que está três posições à frente no alfabeto: A por D, B por E, etc., até Z por C. 13 Uma referência simples é A. Sinkov, Elementary cryptanalysis: a mathematical approach, The Mathematical Association of America, Washington, 1966. 59 O método criptográfico que se baseia neste resultado parte de um número natural m, a escolher pelo receptor de uma forma que já se verá qual é. O receptor divulga também um número natural k primo com ϕ(m). Para enviar uma mensagem, começamos por representá-la por um inteiro a entre 0 e m− 1 e primo com m. Isto pode fazer-se de muitas maneiras, por exemplo representando cada letra da mensagem pelo seu código ASCII.14 Se necessário, divide-se a mensagem em vários blocos. A cifragem da mensagem a consiste em calcular ak módulo m. Mais precisamente, a mensagem cifrada é o resto b da divisão de ak por m. O receptor recebe a mensagem cifrada b. Como procede para a decifrar? Como k é primo com ϕ(m), a congruência kx ≡ 1 (modϕ(m)) tem solução. Seja h a menor solução positiva desta congruência (que se pode calcular usando o algoritmo de Eu- clides e adicionando múltiplos convenientes de ϕ(m)). Então tem-se kh ≡ 1 (modϕ(m)), donde, pela Proposição, akh ≡ a (modm), isto é, bh ≡ a (modm). Ou seja: para reaver a a partir de b, o receptor apenas tem de calcular bh módulo m. Mais precisamente, a mensagem decifrada a é o resto da divisão de bh por m. O que é interessante nisto é que o receptor divulga m e k, isto é, divulga publicamente a chave de cifragem para as mensagens que lhe são enviadas. Mas não divulga h, a chave necessária para a decifragem. Para isto fazer sentido é necessário que h seja muito dif́ıcil de calcular para outra pessoa que não o receptor. Tudo depende de uma boa escolha de m. Escolham-se dois números primos p e q muito grandes ao acaso e faça-se m = pq. O número m é tornado público mas os factores p e q são mantidos secretos pelo receptor. 14 American Standard Code for Information Interchange. 60 Pelas propriedades já estudadas da função ϕ, tem-se ϕ(m) = ϕ(p)ϕ(q) = (p− 1)(q − 1) . Para calcular h é necessário conhecer ϕ(m) e, portanto, é necessário conhecer p e q. Ora, se p e q forem muito grandes é muito dif́ıcil, mesmo usando computadores poderosos, obter os factores p e q a partir do seu produto m. Há assim uma assimetria entre os processos de cifragem e de decifragem. Saber cifrar uma mensagem utilizando este método não significa que se consiga depois decifrá-la. Este método criptográfico, dito “de chave pública”, é conhecido por método RSA, do nome dos três matemáticos que o inventaram.15 15 R. L. Rivest, A. Shamir e L. Adleman, A method for obtaining digital signatures and public-key cryptosystems, Communications of the Association for Computing Machinery, vol. 21 (1978), p. 120-126. 61