UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO DE MESQUITA FILHO” Instituto de Geociências e Ciências Exatas Câmpus de Rio Claro - SP Gabrielle Eduarda Perissotto O Algoritmo RSA e o Algoritmo RSA nos Inteiros Gaussianos Rio Claro - SP 2020 UNIVERSIDADE ESTADUAL PAULISTA “JÚLIO DE MESQUITA FILHO” Instituto de Geociências e Ciências Exatas Câmpus de Rio Claro - SP O Algoritmo RSA e o Algoritmo RSA nos Inteiros Gaussianos Gabrielle Eduarda Perissotto Dissertação apresentada como parte dos requisitos para ob- tenção do título de Mestre em Matemática, junto ao Programa de Pós-Graduação em Matemática, mestrado profissional, do Instituto de Geociências e Ciências Exatas da Universidade Estadual Paulista “Júlio de Mesquita Filho”, Câmpus de Rio Claro - SP. Orientadora Profa. Dra. Carina Alves Severo Rio Claro - SP 2020 P446a Perissotto, Gabrielle Eduarda O Algoritmo RSA e o Algoritmo RSA nos Inteiros Gaussianos / Gabrielle Eduarda Perissotto. -- Rio Claro, 2020 82 p. : il., tabs. Dissertação (mestrado profissional) - Universidade Estadual Paulista (Unesp), Instituto de Geociências e Ciências Exatas, Rio Claro Orientadora: Carina Alves Severo 1. Álgebra. 2. Criptografia. 3. Teoria dos números. 4. Números primos. 5. Numeros complexos. I. Título. Sistema de geração automática de fichas catalográficas da Unesp. Biblioteca do Instituto de Geociências e Ciências Exatas, Rio Claro. Dados fornecidos pelo autor(a). Essa ficha não pode ser modificada. TERMO DE APROVAÇÃO Gabrielle Eduarda Perissotto O ALGORITMO RSA E O ALGORITMO RSA NOS INTEIROS GAUSSIANOS Dissertação APROVADA como requisito parcial para a obtenção do grau de Mestre no Curso de Pós-Graduação em Matemática, mestrado pro- fissional, do Instituto de Geociências e Ciências Exatas da Universi- dade Estadual Paulista “Júlio de Mesquita Filho”, pela seguinte banca examinadora: Profa. Dra. Carina Alves Severo Orientadora Prof. Dr. Wladimir Seixas Departamento de Matemática - UFSCar (São Carlos) Profa. Dra. Cintya Wink de Oliveira Benedito Engenharia de Telecomunicações - UNESP (São João da Boa Vista) Rio Claro - SP, 27 de novembro de 2020 Aos meus pais: Gislene e José. Agradecimentos A Deus, por me permitir chegar até aqui, com sabedoria e perseverança, guiando sempre meus passos. A minha família, meu pai José, minha mãe Gislene e meu irmão Eduardo, por todo suporte e apoio necessário. Obrigada por todo incentivo aos estudos e por darem condições para que isso fosse possível. Aos meus professores, que compartilharam seus conhecimentos da melhor maneira e me inspiraram. Em especial, a minha orientadora, Prof. Dr. Carina Alves Severo, pela competência e seriedade na orientação deste estudo. Obrigada pelo seu empenho, por cada ensinamento e ajuda. Aos membros da banca examinadora, tanto de qualificação como de defesa deste traba- lho, minha gratidão pela dedicação na leitura deste e pelas sugestões, as quais contribuíram para a melhoria do mesmo. Aos meus amigos, por tornarem essa caminhada mais leve. Em particular, Fernando, por sempre estar ao meu lado e não me deixar desistir e Carla, por todo companheirismo e palavras de apoio. Obrigada! Não é o conhecimento, mas o ato de aprender, não a posse mas o ato de chegar lá, que concede a maior satisfação. Carl Friedrich Gauss. Resumo O objetivo deste trabalho é apresentar uma extensão do algoritmo RSA, originalmente desenvolvido para os números inteiros, para o conjunto dos inteiros gaussianos. Para atingir este propósito, o estudo da teoria por trás dos inteiros gaussianos torna-se necessária, a fim de garantir que todas as propriedades sejam preservadas e para que a construção do algoritmo seja possível. Palavras-chave: Criptografia, Inteiros Gaussianos, Teoria dos Números, Números Primos. Abstract The aim of this work is to present an extension of the RSA algorithm, originally deve- loped for integers, for Gaussian integers. To achieve this purpose, the study of the theory behind of Gaussian integers sets becomes necessary, in order to ensure that all properties are preserved and that the construction of the algorithm is possible. Keywords: Cryptography, Gaussian Integers, Number Theory, Prime Numbers. Lista de Figuras 2.1 Representação gráfica de z . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.2 Representação gráfica da norma de z e seu argumento. . . . . . . . . . . . 41 2.3 Representação dos vetores z e w . . . . . . . . . . . . . . . . . . . . . . . 45 2.4 Múltiplos de 3 + 2i . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.5 Interpretação geométrica da norma . . . . . . . . . . . . . . . . . . . . . . 46 2.6 Interpretação geométrica do Teorema 2.15 . . . . . . . . . . . . . . . . . . 48 2.7 Representação gráfica do Exemplo 2.26 . . . . . . . . . . . . . . . . . . . 50 Sumário Introdução 13 1 Os Números Inteiros 15 1.1 Operações em Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.2 Divisibilidade em Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.3 Máximo Divisor Comum . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.3.1 Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . . . 22 1.3.2 Algoritmo de Euclides estendido . . . . . . . . . . . . . . . . . . . 23 1.4 Números Primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.5 O Teorema Fundamental da Aritmética . . . . . . . . . . . . . . . . . . . . 26 1.6 Congruência Módulo m . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.7 Pequeno Teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.8 Função de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.9 Equações Diofantinas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2 Os Inteiros Gaussianos 36 2.1 Números Complexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.2 Os Inteiros Gaussianos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.2.1 Representação Gráfica dos Elementos de Z[i] . . . . . . . . . . . . 44 2.2.2 Função Norma em Z[i] . . . . . . . . . . . . . . . . . . . . . . . . 45 2.2.3 Unidades e Associados em Z[i] . . . . . . . . . . . . . . . . . . . 47 2.2.4 Divisibilidade em Z[i] . . . . . . . . . . . . . . . . . . . . . . . . 49 2.2.5 Teorema da Divisão em Z[i] . . . . . . . . . . . . . . . . . . . . . 51 2.2.6 O Algoritmo de Euclides em Z[i] . . . . . . . . . . . . . . . . . . 53 2.2.7 O Teorema de Bézout em Z[i] . . . . . . . . . . . . . . . . . . . . 56 2.2.8 Primos em Z[i] e Fatoração Única . . . . . . . . . . . . . . . . . . 58 2.2.9 Aritmética Modular em Z[i] . . . . . . . . . . . . . . . . . . . . . 65 3 Criptografia RSA 68 3.1 Um Pouco sobre a História . . . . . . . . . . . . . . . . . . . . . . . . . . 68 3.2 Pré-Codificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 3.3 Geração de Chaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.4 Encriptação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.5 Decriptação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 3.6 Funcionalidade do Sistema . . . . . . . . . . . . . . . . . . . . . . . . . . 74 3.7 Segurança do RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4 Criptografia RSA nos Inteiros Gaussianos 76 4.1 Pré-Codificação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.2 Geração de Chaves . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.3 Encriptação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.4 Decriptação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 5 Considerações Finais 80 Índice Remissivo 80 Referências 82 Introdução A criptografia é a ciência de escrever mensagens em cifras, estuda os métodos para co- dificar uma mensagem de modo que só seu destinatário legítimo consiga interpretá-la. É a arte dos “códigos secretos”, que todos já praticamos quando criança. O mais simples deste método consiste em substituir uma letra pela seguinte; isto é, transladar o alfabeto uma casa para diante. Naturalmente todo código vem acompanhado de duas receitas: uma para codi- ficar uma mensagem; outra para decodificar uma mensagem codificada. Decodificar é o que um usuário legítimo do código faz quando recebe uma mensagem codificada e deseja lê-la. Já decifrar significa ler uma mensagem codificada sem ser um usuário legítimo. Portanto, para decifrar é preciso “quebrar” o código. Porém, os primeiros códigos criados padeciam de um grande mal: eram muito fáceis de decifrar. Hoje em dia, a comunicação entre computadores pela Internet vem criando novos de- safios para a criptografia. Como é relativamente fácil interceptar mensagens enviadas por linha telefônica, torna-se necessário codificá-las, sempre que contenham informações sensí- veis. Isto inclui transações bancárias ou comerciais, ou até mesmo uma compra feita com cartão de crédito. Assim, tornou-se necessário inventar novos códigos, que fossem difíceis de decifrar; mesmo com a ajuda de um computador. Estes códigos foram criados para o uso em aplicações comerciais e são todos de chave pública. Em um código como esse, saber codificar não implica saber decodificar. Neste trabalho veremos que “desfazer” o processo de codificação pode não ser tão simples quanto parece. O mais conhecido dos métodos de criptografia de chave pública é o RSA. Há vários outros códigos de chave pública, mas esse é, atualmente, o mais usado em aplicações comer- ciais (COUTINHO, 2011). A descrição completa do método RSA só será possível depois do estudo de toda teoria matemática que o envolve. Desse modo, no Capítulo 1 abordaremos os principais resultados sobre os números inteiros, necessários para o desenvolvimento passo a passo do algoritmo RSA, o qual será apresentado no Capítulo 3. Com o objetivo de tornar o algoritmo RSA mais eficiente, neste trabalho apresentaremos uma extensão do método de criptografia RSA, inicialmente feito com os números inteiros, para os inteiros de Gauss. Gauss fez a extensão das propriedades de Z para Z[i], o anel 13 Introdução 14 formado pelos números complexos da forma a + bi, onde a e b pertence a Z e i2 = −1, e percebeu que grande parte da Teoria de Euclides poderia ser transportada para Z[i], o que consequentemente trouxe diversas contribuições para a Teoria dos Números. Assim, no Capítulo 2 faremos um estudo das principais definições, teoremas e propriedades sobre Z[i], para finalmente, no Capítulo 4, desenvolver todos as etapas do algoritmo RSA nos Inteiros Gaussianos. Todas as figuras deste trabalho foram confeccionadas utilizando o software livre Geogebra. 1 Os Números Inteiros No conjunto dos números naturais, N := {0, 1, 2, 3, · · ·}, a operação de subtração entre a e b só está definida se a ≥ b. Porém existem questões envolvendo essa operação em que b > a, por exemplo, relacionadas a gastar mais do que se tem. Com apenas R$10, 00, adquirindo um produto no valor de R$15, 00, como podemos expressar essa dívida? Ou seja, a subtração entre 10 e 15? Para enfrentar essas questões, foi preciso ampliar o conjunto dos números naturais, com adjunção de novos números, os números inteiros negativos, introduzidos a princípio para possibilitar uma resposta a uma subtração qualquer de dois elementos de N. Esse passo gerou naturalmente a necessidade de estender as operações e a relação de ordem de N a um novo conjunto, formado pelos números naturais e os números negativos, a saber: o conjunto dos números inteiros, denotado por Z := {· · · ,−3,−2,−1, 0, 1, 2, 3, · · ·}. Neste capítulo apresentamos algumas definições, propriedades e teoremas que estão rela- cionados com a aritmética dos inteiros, que serão ferramentas necessárias para o desenvolvi- mento do Capítulo 3. As principais referências utilizadas neste capítulo foram [1, 2, 3, 4, 5]. 1.1 Operações em Z No conjunto Z estão definidas as operações de soma e produto + : Z × Z → Z e · : Z × Z → Z (x, y) 7→ x+ y (x, y) 7→ x.y as quais satisfazem os seguintes axiomas. Para todo x, y, z pertencentes a Z: A1) (x+ y) + z = x+ (y + z) (associatividade da soma); A2) Existe 0 ∈ Z tal que x+ 0 = 0 + x = x (existência do elemento neutro); A3) Existe −x ∈ Z tal que x + (−x) = (−x) + x = 0 (existência de inverso aditivo (ou oposto) de cada x ∈ Z); A4) x+ y = y + x (comutatividade da soma); 15 Operações em Z 16 M1) (x · y) · z = x · (y · z) (associatividade do produto); M2) Existe 1 ∈ Z tal que x · 1 = 1 · x = x (existência da unidade em Z); M3) x · y = y · x (comutatividade do produto); D) x · (y + z) = x · y + x · z (distributividade do produto em relação à soma). Observação 1.1. Dado x ∈ Z, o axioma A3) garante a existência de um oposto para x com respeito à adição, denotado por −x. Definição 1.2 (Subtração em Z). Chama-se diferença de dois inteiros x e y à soma x+(−y). A subtração em Z é a operação − : Z × Z → Z, que associa cada par ordenado (x, y) à diferença x− y. Teorema 1.3. Para cada x, y, z em Z, valem as propriedades: 1. x+ y = x⇒ y = 0 (ou seja, 0 é o único elemento neutro da adição em Z); 2. x+ y = 0⇒ y = −x (ou seja, o oposto de um elemento x é único); 3. x+ y = x+ z ⇒ y = z (lei do cancelamento da adição); 4. −(−x) = x; 5. −(x+ y) = (−x) + (−y) = −x− y; 6. x · 0 = 0; 7. (−x)y = −(xy); 8. (−x)(−y) = xy; 9. (x− y)z = xz − yz. Observação 1.4. Os axiomas listados (A1, A2, A3, A4, M1, ...) ainda não são suficientes para caracterizar o conjunto Z de maneira única. Isto significa que existem outras estruturas algébricas familiares que também satisfazem às propriedades acima. Para caracterizar o conjunto dos números inteiros é introduzida uma relação de ordem≤ . Para maiores detalhes a referência [6] pode ser consultada. Divisibilidade em Z 17 1.2 Divisibilidade em Z O conjunto dos números inteiros é munido de diversas propriedades e definições, po- rém, apresentaremos apenas algumas, as quais são essenciais para o desenvolvimento deste trabalho. Esta seção contém os principais algoritmos utilizados para estudar o sistema de cripto- grafia RSA. Definição 1.5. Dados a, b ∈ Z, com a 6= 0, dizemos que a divide b, e escrevemos a | b, se existir k ∈ Z tal que b = ak. Caso a não divida b, escrevemos a - b. Seja a um inteiro não nulo. Se a dividir b, dizemos que a é um divisor de b, que b é divisível por a ou ainda que b é um múltiplo de a. Se a | b e a > 0, então a é um divisor positivo de b. Notemos que todo inteiro não nulo é um divisor de si mesmo e de 0. Exemplo 1.6. 4 | 28 pois existe um inteiro k = 7 tal que 28 = 4 · 7. Exemplo 1.7. 7 - 12 pois não existe um inteiro k tal que 12 = 7 · k. Proposição 1.8. Se a, b e c são inteiros, tais que a | b e b | c, então a | c. Demonstração. Sejam a, b e c inteiros. Como a | b e b | c, existem inteiros k1 e k2 tais que b = ak1 e c = bk2. Logo, c = (ak1)k2 = a(k1k2) e portanto, a | c. Exemplo 1.9. Como 2 | 8 e 8 | 16, então 2 | 16. Proposição 1.10. Se a, b e c são inteiros, tais que a | b e a | c, então a | (mb + nc), para quaisquer m,n ∈ Z. Demonstração. Sejam a, b e c inteiros. Como a|b e a|c, existem inteiros k1 e k2 tais que b = ak1 e c = ak2. Multiplicando ambas as equações respectivamente por m e n obtemos mb = mak1 e nc = nak2. Logo, mb + nc = mak1 + nak2 = a(mk1 + nk2). Portanto, a | (mb+ nc). Exemplo 1.11. Como 4 | 8 e 4 | 16, então 4 | (5 · 8 + (−1) · 16). Logo 4 | 24. Teorema 1.12. (Algoritmo da Divisão em Z) Dados a, b ∈ Z, b > 0, existe um único par de inteiros q e r que satisfazem a = q · b+ r, com 0 ≤ r < b. Demonstração. Seja b um número inteiro positivo não nulo. Se a pertence a Z, então a é múltiplo de b ou está situado entre dois múltiplos consecutivos de b, isto é, qb ≤ a < (q+1)b. Somando −qb em todos os termos dessa desigualdade obtemos: Divisibilidade em Z 18 qb− qb ≤ a− qb < qb+ b− qb⇒ 0 ≤ a− qb < b. Desta forma, tomando r = a− qb, segue que a = qb+ r, em que 0 ≤ r < b. Suponhamos agora, que existam inteiros q1, q2, r1, r2 , onde q1 6= q2 e r1 6= r2 e que satisfaçam às igualdades: a = q1b+ r1, com 0 ≤ r1 < b e a = q2b+ r2, com 0 ≤ r2 < b. Se b > r1 e b > r2, então b > r2−r1 e a = bq1+r1 = bq2+r2.Dessa forma, b(q2−q1) = r1−r2. Tomando k = (q2−q1), segue que r1−r2 = kb, com k pertencente em Z e então b | (r1−r2). Portanto b ≤ (r1 − r2), o que é um absurdo, pois contradiz a hipótese. Logo, r1 = r2. Concluímos que (q2−q1)b = 0. Sendo b 6= 0, temos que (q2−q1) = 0 e portanto q2 = q1. Na equação a = q ·b+r, com 0 ≤ r < b, os inteiros, q e r são chamados respectivamente de quociente e resto da divisão de a por b. Vale lembrar que b somente é divisor de a se r = 0. Neste caso, temos que a = bq e o quociente q na divisão exata de a por b pode ser indicado também por a b ou a/b. Exemplo 1.13. Sabe-se que na divisão de 326 por b > 0, o quociente é 14 e o resto é r. Vejamos como determinar os possíveis valores de b e r. Sabemos que a = qb+ r, 0 ≤ r < b. Assim, substituindo os valores dados, obtemos: 326 = 14b+ r, 0 ≤ r < b⇒ r = 326− 14b. Logo, 0 ≤ r < b⇒ 0 ≤ 326− 14b < b. Resolvendo essa desigualdade temos:{ 0 ≤ 326− 14b⇒ b ≤ 326 14 ; 326− 14b < b⇒ b > 326 15 . Dessa forma, os possíveis valores para b e r são: b = 22 e r = 18 ou b = 23 e r = 4. Exemplo 1.14. Sejam n > m inteiros positivos. Se o resto da divisão de n por m é r, então o resto da divisão de 2n − 1 por 2m − 1 é 2r − 1. De fato, podemos escrever n como n = mq + r, sendo q um número inteiro positivo. Vamos mostrar que existe um inteiro q′ tal que 0 ≤ 2r − 1 < 2m − 1 e 2n − 1 = (2m − 1)q′ + 2r − 1. Note que Máximo Divisor Comum 19 0 ≤ r < m⇒ 20 ≤ 2r < 2m ⇒ 0 ≤ 2r − 1 < 2m − 1. Mostremos, agora, que q′ é um número inteiro. Como 2n − 1 = (2m − 1)q′ + 2r − 1⇐⇒ q′ = (2n − 1)− (2r − 1) 2m − 1 ⇐⇒ q′ = 2n − 2r 2m − 1 , segue que 2n−2r = 2r(2n−r−1) = 2r(2mq−1). Mas, 2mq−1 = (2m−1)(2mq−1 + · · ·+1) e assim, q′ = 2r(2m − 1)(2mq−1 + · · ·+ 1) 2m − 1 = 2r(2mq−1 + · · ·+ 1). Portanto, q′ é um número inteiro, concluindo a nossa afirmação.1 1.3 Máximo Divisor Comum Quando falamos em máximo divisor comum de dois números inteiros, estamos interessa- dos em encontrar o maior inteiro que divide esses dois números. Por exemplo, sabemos que o número inteiro 8 divide 24 e também divide 32 e, além disso, como podemos verificar, 8 é o maior número inteiro positivo com essa propriedade. Sendo assim, dizemos, que 8 é o má- ximo divisor comum de 24 e 32, podendo ser denotado por (24, 32) = 8 oumdc(24, 32) = 8, isto nos leva a seguinte definição. Definição 1.15. O máximo divisor comum (mdc) de dois inteiros a e b (a e b diferentes de zero), denotado por mdc(a, b) ou (a, b), é o maior inteiro que divide a e b. Sendo assim, o mdc(a, b) é o inteiro positivo d que satisfaz às condições: 1. d | a e d | b; 2. se c | a e c | b, então c | d. Pela condição 1 da Definição 1.15, d é um divisor comum de a e b, e pela condição 2, d é o maior dentre todos os divisores comuns de a e b. Exemplo 1.16. Sejam a = 12 e b = 54. Vamos determinar mdc(12, 54). O conjunto dos divisores de a = 12 e de b = 54, os quais denotamos por D12 e D54, são: D12 = {±1,±2,±3,±4,±6,±12} e D54 = {±1,±2,±3,±6,±9,±18,±27,±54}. Como mdc(12, 54) é o maior inteiro que divide 12 e 54, para encontrar o máximo divisor comum entre estes números, basta determinar a intersecção D12 ∩D54 e tomar o maior número em módulo desse conjunto. Logo, D12,54 = D12 ∩D54 = {±1,±2,±3,±6}, que tem máximo igual a 6, que é o mdc(12, 54). 1Para a realização desse exemplo, foi utilizado a operação de potenciação e suas propriedades, para todo a, n e m em Z: i) an = a · . . . · a︸ ︷︷ ︸ n vezes , ii) a0 = 1, iii) an · am = an+m. Máximo Divisor Comum 20 Definição 1.17. Sejam a e b dois inteiros não nulos. Dizemos que a e b são primos entre si ou coprimos se, e somente se, mdc(a, b) = 1. Exemplo 1.18. Os inteiros 3 e 7, 9 e 11 são primos entre si, pois, temos: mdc(3, 7) = 1 e mdc(9, 11) = 1. Proposição 1.19. (Identidade de Bézout) Se d = mdc(a, b), então existem n0, m0 ∈ Z tais que d = n0a+m0b, ou seja, d é uma combinação linear de a e b. Demonstração. Seja o conjunto B = {na + mb | n,m ∈ Z}. Veja que B 6= ø. Sejam n0 e m0 em Z tais que c = n0a + m0b é o menor inteiro positivo pertencente a B, vamos provar que c | a e c | b. Para tanto, suponhamos que c - a. Pelo algoritmo da divisão (Teorema 1.12), existem q e r inteiros, tais que a = qc + r, 0 ≤ r < c. Tomando r = a − qc = a − q(n0a + m0b) = a(1 − n0q) + b(−m0q) , ou seja, r é um número inteiro positivo e r ∈ B uma vez que, (1− n0q) e (−m0q) ∈ Z. Daí, temos que, r ≥ c. Mas, r < c, o que é um absurdo. Logo, c | a. Analogamente, mostramos que c | b. Assim, c é um divisor comum, e como d = mdc(a, b), temos que c ≤ d. Resta ainda, mostrar que d = n0a + m0b. Vejamos que, se d = mdc(a, b) então d | a e d | b, o que implica que a = k1d e b = k2d com k1 e k2 em Z. Ainda, tomando c = n0a + m0b = n0(k1d) + m0(k2d) = d(n0k1 + m0k2), resulta em d | c. Além disso, c 6= 0 implica | d |≤| c | e como não é possível termos d < c, uma vez que d = mdc(a, b), então d = c, ou seja, d = n0a+m0b. Proposição 1.20. Sejam a e b números inteiros positivos. Se existem inteiros q e r tais que a = bq + r, 0 ≤ r < b, então mdc(a, b) = mdc(b, r). Demonstração. Sejam d1 = mdc(a, b) e d2 = mdc(b, r). Afirmamos que d1 ≤ d2. De fato, existem inteiros positivos k1 e k2 tais que: a = d1k1 e b = d1k2. Substituindo a e b na equação a = bq + r obtemos: r = d1k1 − d1k2q = d1(k1 − k2q), ou seja, d1 é um divisor comum de b e r. Mas d2 é o maior divisor de b e r e portanto, pela Proposição 1.19, d1 ≤ d2 como queríamos. Seguindo um argumento semelhante, podemos provar o inverso, ou seja, d2 ≤ d1, concluindo que d1 = d2. Teorema 1.21. Se a e b são inteiros não nulos, então eles serão primos entre si se, e somente se, existirem inteiros x e y tais que ax+ by = 1. Máximo Divisor Comum 21 Demonstração. (⇒) Se a e b são primos entre si, então mdc(a, b) = 1, consequentemente existem x e y tais que ax+ by = 1. (⇐) Se existem inteiros x e y, tais que ax + by = 1 e se mdc(a, b) = d, então d | a e d | b. Logo, d | (ax+ by) e como d | 1, resulta em d = 1, ou seja, mdc(a, b) = 1. Corolário 1.22. Se mdc(a, b) = d, então mdc ( a d , b d ) = 1. Demonstração. Vejamos que a d e b d são inteiros, pois d é um divisor comum de a e b. Sendo assim, se mdc(a, b) = d, então d | a, d | b e existem inteiros x e y tais que ax + by = d. Logo, a d x + b d y = 1, o que nos leva a conclusão, pelo Teorema 1.21, que os inteiros a d e b d são primos entre si e, portanto, mdc ( a d , b d ) = 1. Exemplo 1.23. Observe que mdc(16, 40) = 8 e mdc ( 16 8 , 40 8 ) = mdc(2, 5) = 1. Corolário 1.24. Se a | bc e mdc(a, b) = 1, então a | c. Demonstração. Como a | bc, segue que bc = ak com k inteiro e como a e b são primos entre si, ax + by = 1 para certos inteiros x e y. Multiplicando ambos os lados da igualdade por c temos cax+ cby = c. Agora, c = cax+ aky = a(cx+ ky) e, portanto, a | c. Um número natural d será dito mdc de dados números naturais a1, a2, . . . , an se possuir as seguintes propriedades: i) d é um divisor comum de a1, a2, . . . , an. ii) Se c é um divisor comum de a1, a2, . . . , an, então c | d. O mdc, quando existe, é certamente único e será representado por mdc(a1, a2, . . . , an). Proposição 1.25. Dados números naturais a1, a2, . . . , an, existe o seu mdc e mdc(a1, a2, . . . , an) = mdc(a1, a2, . . . , an−2,mdc(an−1, an)). Demonstração. Vamos provar a proposição por indução sobre n (n ≥ 2). Para n = 2, sabemos que o resultado é válido. Suponhamos que o resultado vale para n. Para provar que o resultado é válido n+ 1, basta mostrar que mdc(a1, a2, . . . , an, an+1) = mdc(a1, a2, . . . ,mdc(an, an+1)), Máximo Divisor Comum 22 pois isso provará também a existência. Seja d = mdc(a1, a2, . . . ,mdc(an, an+1)). Logo, d | a1, . . . , d | mdc(an, an+1). Por- tanto, d | a1, . . . , d | an−1, d | an e d | an+1. Por outro lado, seja c um divisor comum de a1, . . . , an, an+1, teremos que c é divisor comum de a1, . . . , an−1 e mdc(an, an+1) e portanto, c | d. Para calcular o mdc(a1, . . . , an), pode-se usar recursivamente o algoritmo de Euclides, que apresentamos na próxima seção. 1.3.1 Algoritmo de Euclides Muito importante nas etapas de encriptação e decriptação de mensagens do sistema RSA, apresentamos a seguir o Algoritmo de Euclides e na seção seguinte, o Algoritmo de Euclides estendido. Teorema 1.26 (Algoritmo de Euclides). Sejam r0 = a e r1 = b inteiros não-negativos com b 6= 0. Se o algoritmo da divisão for aplicado sucessivamente para se obter ri = qi+1ri+1 + ri+2, com 0 ≤ ri+2 < ri+1, para i = 0, 1, 2, ..., n− 1 e rn+1 = 0, então mdc(a, b) = rn, que é o último resto não-nulo. Demonstração. Primeiramente, vamos dividir a por b. Assim, podemos escrever a = bq1 + r2, com q1 e r2 inteiros. Logo, r0 = qr1+r2. Em seguida, vamos dividir r1 por r2, e obtemos r1 = q2r2 + r3. Fazemos isso sucessivamente até rn+1 = 0. Com isto, obtemos a seguinte sequência de equações a = q1b+ r2, 0 < r2 < r1, r1 = q2r2 + r3, 0 < r3 < r2, r2 = q3r3 + r4, 0 < r4 < r3, ... ... rn−2 = qn−1rn−1 + rn, 0 < rn < rn−1, rn−1 = qnrn + 0. Pela Proposição 1.19, segue que o máximo divisor comum de rn e rn−1 é rn. Aplicando a Proposição 1.19 várias vezes, segue que: rn = mdc(rn−1, rn) = mdc(rn−2, rn−1) = . . . = mdc(r1, r2) = mdc(r0, r1) = mdc(a, b). Portanto, mdc(a, b) = rn, que é o último resto não-nulo da sequência escrita. Exemplo 1.27. Utilizando o algoritmo de Euclides, vamos determinar o mdc(894, 326). Sejam r0 = 894 e r1 = 326. Aplicando o algoritmo da divisão sucessivas vezes, obtem-se Máximo Divisor Comum 23 894 = 326 · 2 + 242, 326 = 242 · 1 + 84, 242 = 84 · 2 + 74, 84 = 74 · 1 + 10, 74 = 10 · 7 + 4, 10 = 4 · 2 + 2, 4 = 2 · 2 + 0. Pelo algoritmo de Euclides, segue que mdc(894, 326) é o último resto não nulo, ou seja, mdc(894, 326) = 2. 1.3.2 Algoritmo de Euclides estendido O algoritmo de Euclides estendido consiste em encontrar α e β inteiros, tal que αa+ βb = mdc(a, b), com a e b em Z. Vamos supor que após o cálculo do mdc(a, b), obtemos a seguinte sequência de divisões: a = bq1 + r1 e r1 = ax1 + by1, b = r1q2 + r2 e r2 = ax2 + by2, r1 = r2q3 + r3 e r3 = ax3 + by3, r2 = r3q4 + r4 e r4 = ax4 + by4, r3 = r4q5 + r5 e r5 = ax5 + by5, ... e ..., rn−3 = rn−2qn− 1 + rn−1 e rn−1 = axn−1 + byn−1, rn−2 = rn−1qn e rn = 0. Os números x1, . . . , xn−1 e y1, . . . , yn−1 são inteiros a determinar. Seja a seguinte tabela com essas informações: Resto Quociente x y b ∗ x−1 y−1 a ∗ x0 y0 r1 q1 x1 y1 r2 q2 x2 y2 ... ... ... ... rn−2 qn−2 xn−2 yn−2 rn−1 qn−1 xn−1 yn−1 Máximo Divisor Comum 24 Consideremos a j-ésima linha e vamos dividir rj−2 por rj−1, para encontrarmos rj e qj de forma que rj−2 = rj−1qj + rj e 0 ≤ rj < rj − 1. Assim, rj = rj−2 − rj−1qj . Observando os valores de xj−2, xj−1, yj−2 e yj−1 nas linhas j−1 e j−2, podemos escrever rj−2 = axj−2 + byj−2 e rj−1 = axj−1 + byj−1. Desta forma, rj = (axj−2 + byj−2)− (axj−1 + byj−1)qj = a(xj−2 − qjxj−1) + b(yj−2 − qjyj−1). Portanto, xj = xj−2 − qjxj−1 e yj = yj−2 − qjyj−1. Para calcularmos os valores de xj e yj da tabela, basta sabermos os valores das duas linhas imediatamente acima, através de um processo recursivo. Para determinarmos x e y iniciais, de modo análogo ao feito acima, devemos ter a = ax−1 + by−1 e a = ax0 + by0. Com isto, podemos afirmar que x−1 = 1, y−1 = 0 e x0 = 1, y0 = 0. Assim, damos início a recursão. Como esse algoritmo nos fornece o máximo divisor comum correspondente ao resto n− 1, segue que mdc(a, b) = rn−1 = axn−1 + byn−1, ou seja, α = xn−1 e β = yn−1. Exemplo 1.28. Vamos determinar mdc(973, 101) e, em seguida, determinar α e β inteiros que satisfazem: 973α + 101β = mdc(973, 101). Para isso, utilizamos o algoritmo de Euclides estendido. Primeiramente, escrevemos a tabela, completando-a. Números Primos 25 Resto Quociente α β 973 ∗ 1 0 101 ∗ 0 1 64 9 (1− 0 · 9) = 1 (0− 1 · 9) = −9 37 1 (0− 1 · 1) = −1 (1− (−9) · 1) = 10 27 1 (1− (−1) · 1) = 2 (−9− 10 · 1) = −19 10 1 (−1− 2 · 1) = −3 (10− (−19) · 1) = 29 7 2 (2− (−3) · 2) = 8 (−19− 29 · 2) = −77 3 1 (−3− 8 · 1) = −11 (29− (−77) · 1) = 106 1 2 (8− (−11) · 2) = 30 (−77− 106 · 2) = −289 0 1 ∗ ∗ Portanto, mdc(973, 101) = 1, α = 30, β = −289 e 973 · 30 + 101 · (−289) = 1. 1.4 Números Primos No processo de geração de chaves do método de criptografia RSA, utilizaremos o con- ceito de números primos. Para isso, nessa seção apresentamos os principais resultados rela- cionados aos números primos em Z. Definição 1.29. O número p > 1 é um número primo se seus únicos divisores são ±1 e ±p. Qualquer número n > 1 tem pelo menos um divisor primo. Se n é primo, então esse divisor primo é o próprio n. De fato, se n não é primo, seja a > 1 seu menor divisor, n = ab, onde 1 < a 6 b. Se a não fosse primo, então a = a1a2 com 1 < a1 ≤ a2 < a e a1|n, contradizendo a minimalidade de a. Exemplo 1.30. Os menores números primos são 2, 3, 5, 7, 11, 13, 17, 19, 23, 29,· · · . Indicamos por P = {p ∈ N | p é primo}, o conjunto de todos os números primos. Proposição 1.31. Seja p ∈ P. Então ∀a, b ∈ N; p | ab⇒ p | a ou p | b, ou seja, um primo divide um produto, somente se ele divide um dos fatores. O Teorema Fundamental da Aritmética 26 Demonstração. Suponhamos que p | ab e p - a. Logo, p - a ⇒ mdc(p, a) = 1, portanto, pelo Corolário 1.24, p | b. Um número n > 1 que não é primo é chamado composto. Se n é um número composto, então ele tem um divisor primo menor que √ n. De fato, como acima, n = ab, onde 1 < a ≤ b e a é o menor divisor de n. Logo n > a2, e portanto a 6 √ n. Essa ideia pertence ao matemático da Grécia Antiga Eratóstenes (250 a.C.). Exemplo 1.32. Os menores números compostos são: 4, 6, 8, 9, 10, 12, 14, 15, 16, 18,· · · . Teorema 1.33. Todo inteiro composto possui um divisor primo. Demonstração. Seja n um inteiro composto. Consideremos A 6= 0 o conjunto de todos os divisores positivos de n, exceto os divisores 1 e n, isto é: A = {t : t | n; 1 < t < n; t ∈ N}. Pelo Princípio da Boa Ordem 2 , existe um elemento p ∈ A minimal, que vamos mostrar ser primo. Suponhamos que p seja composto, ou seja, admite pelo menos um divisor d tal que 1 < d < p, então d | p e p | n, o que implica d | n, isto é, p não seria o elemento mínimo de A, se fosse composto. Logo, p é primo. Exemplo 1.34. Veja que se 7 | ab então necessariamente um dos fatores a ou b (ou ambos) é múltiplo de 7, pois 7 é um número primo. Proposição 1.35. O conjunto dos números primos é infinito. Demonstração. É suficiente provarmos que o conjunto de números primos positivos é infi- nito. Suponhamos, por absurdo, que existem um número finito, p1, · · · , pn de primos positi- vos. Sem = p1 · · · pn+1, existe pelo Teorema 1.12, um primo p tal que p dividem. Se p = pi para algum i, então p divide 1, o que é uma contradição. 1.5 O Teorema Fundamental da Aritmética O Teorema Fundamental da Aritmética sustenta que todo inteiro positivo maior que 1 pode ser escrito como produto de números primos, sendo esta decomposição única a menos de permutações dos fatores. 2Princípio da Boa Orderm (PBO): Todo conjunto não vazio de inteiros positivos contém um elemento mínimo. O Teorema Fundamental da Aritmética 27 Os números primos são os elementos mínimos da estrutura multiplicativa dos inteiros. Vejamos um exemplo: 165 = 3 · 5 · 11 donde 3, 5 e 11 são “mínimos”, pois não podem ser fatorados. Teorema 1.36. (Teorema Fundamental da Aritmética) Todo inteiro n, n ≥ 2, pode ser es- crito na forma n = p1 · . . . · ps, para determinados primos positivos p1, . . . , ps, com s ≥ 1 e p1 ≤ p2 ≤ . . . ≤ ps. Além disso, os fatores primos p1, . . . , ps, satisfazendo as con- dições apresentadas, são únicos, isto é, se q1, . . . , qr, são também primos positivos com q1 ≤ q2 ≤ . . . ≤ qr e n = q1 · . . . · qr, então r = s e, além disso, pi = qj , para todo i, j ∈ {1, . . . , r}. Demonstração. Mostramos a existência da fatoração de n em primos. Se n = p é um número primo, a afirmação fica clara (r = 1). Agora, se n é composto, então, pelo Teorema 1.33, n possui um divisor primo p1 e temos: n = p1 · n1, 1 < n1 < n. Vejamos que, se na afirmação acima n1 é primo, então esta igualdade representa n como produto de fatores primos, e se, ao invés disso, n1 é composto, então pelo Teorema 1.33, n1 possui divisores p2, isto é, n1 = p2 · n2, e temos: n = p1 · p2 · n2, 1 < n2 < n. Assim sendo, temos a sequência decrescente: n > n1 > n2 > . . . > 1. Como existe um número finito de inteiros positivos menores que n e maiores que 1, existe necessariamente um nk (k ≥ 1) que é um primo ps (nk = ps) e por consequência teremos: n = p1 · p2 · . . . · ps. Por fim, mostramos a unicidade da fatoração de n, n ≥ 2. Suponhamos que p1 · p2 · . . . · ps = q1 · q2 · . . . · qr com p1, p2, . . . , ps, q1, q2, . . . , qr ∈ P e p1 ≤ p2 ≤ . . . ≤ ps assim como, q1 ≤ q2 ≤ . . . ≤ qr. Temos que p1 | q1 · q2 · . . . · qr donde concluímos, aplicando diversas vezes a Proposição 1.25, que p1 tem que dividir pelo menos um dos fatores q1, q2, . . . , qr. Então existe k (1 ≤ k ≤ r) com p1 | qk. Como p1 e qk são primos, temos que p1 = qk ≥ q1. De modo análogo, q1 | pl para algum l (1 ≤ l ≤ s) donde Congruência Módulo m 28 segue q1 = pl ≥ p1. Desta forma, p1 = q1. Agora, de p1 · p2 · . . . · ps = q1 · q2 · . . . · qr segue p2 · . . . · ps = q2 · . . . · qr. Por indução, concluímos que s − 1 = r − 1 (isto é, s = r) e p2 = q2, p3 = q3, . . . , ps = qr. Como p1 = q1, vale a unicidade da fatoração. Outra forma de escrever a fatoração é n = pe11 · . . . · pess = s∏ k=1 pekk . Podemos ainda representar um número inteiro como n = 2e23e3 . . . pep . . . onde o produto é tomado sobre todos os primos, que sabemos ser infinito, pela Proposi- ção 1.35. Ao longo deste trabalho escolheremos qualquer destas representações acima e as mesmas serão referidas como a fatoração canônica de n em números primos. Exemplo 1.37. A fatoração canônica do inteiro positivo n = 4.200 é dada pela igualdade: 4.200 = 23 · 3 · 52 · 7. Lema 1.38. Sejam m e n em N e mdc(m,n) = 1. Se mn = c2, então existem M e N com m = M2 e n = N2. Demonstração. Sejam m = r∏ k=1 pakk e n = s∏ k=1 qbkk as fatorações canônicas de m e n. Então os qk são diferentes dos pl pois mdc(m,n) = 1. Segue que mn = pa11 · . . . · parr · q b1 1 · . . . · qbss é a decomposição primária de mn. Como mn = c2 é quadrado perfeito, segue que todos os a1, . . . , ar, b1, . . . , bs são pares. Logo, m = M2 e n = N2 para M = r∏ k=1 p ak/2 k e N = s∏ k=1 q bk/2 k . 1.6 Congruência Módulo m A congruência módulo m é uma relação de equivalência, isto é, é reflexiva; simétrica e transitiva, no conjunto dos números inteiros, de tal forma que dados dois inteiros a e b, ao dividirmos por um número m (chamado módulo de congruência) deixam o mesmo resto. Através das propriedades de congruência, podemos encontrar o resto das divisões sem Congruência Módulo m 29 muitos esforços e de forma breve. É o que abordaremos nesta seção, que será de extrema importância para encriptar e decriptar mensagens codificadas. Definição 1.39. Dados a, b e m em Z, dizemos que a é congruente a b módulo m e denota- mos: a ≡ b (mod m), se m | (a− b), ou seja, a e b têm o mesmo resto na divisão por m. Se a não for congruente (ou incongruente) a b, módulo m, escrevemos a 6≡ b (mod m). Alternativamente temos que, dados três inteiros a, b e m, a ≡ b (mod m)⇔ m | (a− b)⇔ a− b = km⇔ a = b+ km, para algum k ∈ Z. Exemplo 1.40. Temos que 3 ≡ 24 (mod 7), pois 7 | (3 − 24). Por outro lado, 25 6≡ 12 (mod 7), pois 7 - (25− 12). Proposição 1.41. Para quaisquer a, b, c, d e m pertencentes a Z temos: 1. Reflexiva: a ≡ a (mod m); 2. Simétrica: Se a ≡ b (mod m), então b ≡ a (mod m); 3. Transitiva: Se a ≡ b (mod m) e b ≡ c (mod m), então a ≡ c (mod m); 4. Compatibilidade com a soma e diferença:{ a ≡ b (mod m) c ≡ d(mod n) ⇒ { a+ c ≡ b+ d (mod m) a− c ≡ b− d (mod m) Em particular, se a ≡ b (mod m), então ka ≡ kb (mod m) para todo k ∈ Z. 5. Compatibilidade com o produto: Podemos multiplicar “membro a membro”: { a ≡ b (mod m) c ≡ d (mod m) ⇒ ac ≡ bd (mod m) Em particular, se a ≡ b (mod m), então ak ≡ bk (mod m) para todo k ∈ Z. 6. Cancelamento: Se ac ≡ bc (mod m) e mdc(c,m) = d, então a ≡ b ( mod m d ) . Demonstração. Para a, b, c, d e m inteiros, temos: 1. m | 0⇒ m | (a− a)⇒ a ≡ a (mod m). 2. a ≡ b (mod m)⇒ m | (a− b)⇐⇒ m | −(a− b)⇒ m | (b− a)⇒ b ≡ a (mod m). Congruência Módulo m 30 3. a ≡ b (modm) e b ≡ c (modm)⇒ m | (a−b) em | (b−c)⇒ m | [(a−b)+(b−c)]⇒ m | (a− c)⇒ a ≡ c (mod m). 4. a ≡ b (mod m) e c ≡ d (mod m)⇒ m | (a− b) e m | (c− b)⇒ m | [(a− b) + (c− d)] ⇒ m | [(a + c) − (b + d)] ⇒ a + c ≡ b + d (mod m). A compatibilidade com a diferença segue de modo análogo. 5. Como a ≡ b (mod m) e c ≡ d (mod m), podemos concluir que existem inteiros s, t tais que a = b+sm e c = d+ tm, então ac = (b+sm).(d+ tm) = bd+ btm+dsm+ smtm = bd+(bt+ds+stm)m, que por definição de congruência, ac ≡ bd (mod m). 6. Se ac ≡ bc (mod m), então ac − bc = (a − b)c = km, com k ∈ Z. Ainda, se mdc(c,m) = d, existem inteiros r e s tais que c = dr e m = ds, onde r e s são primos entre si. Portanto: (a− b)dr = kds ou (a− b)r = ks, o que implica que, s | (a − b)r, com mdc(r, s) = 1. Logo, pelo Corolário 1.24, s | (a− b) e daí a ≡ b (mod s). Como s = m d segue que a ≡ b ( mod m d ) . Exemplo 1.42. Como 12 ≡ 22 (mod 5) e 8 ≡ 13 (mod 5) segue que 12 + 8 ≡ 22 + 13 (mod 5), ou seja, 20 ≡ 35 (mod 5) e 12 · 8 ≡ 22 · 13 (mod 5), ou seja, 96 ≡ 286 (mod 5). Exemplo 1.43. Vejamos que 31 | 2015 − 1. Para verificar a expressão acima é suficiente mostrar que 2015 ≡ 1 (mod 31). Para tal, observemos que 20 ≡ −11 (mod 31) (1.1) e com isso, 202 ≡ (−11)2 (mod 31) ⇔ 202 ≡ 121 (mod 31). Como 121 ≡ −3 (mod 31) temos 202 ≡ −3 (mod 31). (1.2) Multiplicando (1.1) e (1.2) membro a membro, obtemos 203 ≡ 33 (mod 31) e, como 33 ≡ 2 (mod 31), 203 ≡ 2 (mod 31). (1.3) Por fim, elevando (1.3) à potência 5, temos que (203)5 ≡ 25 (mod 31)⇒ 2015 ≡ 32 (mod 31) e como 32 ≡ 1 (mod 31), obtemos 2015 ≡ 1 (mod 31). Pequeno Teorema de Fermat 31 1.7 Pequeno Teorema de Fermat Os números primos possuem muitas propriedades. Uma delas foi encontrada por Pierre de Fermat, chamada de Pequeno Teorema de Fermat. Antes de enunciarmos e demonstrarmos este teorema, apresentamos primeiramente um lema, necessário para a sua demonstração. Lema 1.44. Sejam p um número primo e a e b inteiros. Então, (a+ b)p ≡ ap + bp (mod p). Demonstração. O lema é demonstrado utilizando a notação do binômio de Newton, no caso (a+ b)p ≡ ap + bp + p−1∑ i=1 ( p i ) ap−ibi. Para provar a veracidade do lema, basta mostrar que p−1∑ i=1 ( p i ) ap−ibi ≡ 0 (mod p). Ao expandirmos o número binomial, temos( p i ) = p(p− 1)(p− 2) · · · (p− i+ 1) i! . Como não sabemos se a e b são múltiplos de p, nos resta tentar concluir que ( p i ) o seja. Como ( p i ) é um inteiro positivo, pois é o coeficiente ai do polinômio a1X + · · ·+ ap−1X p−1, segue que todos os fatores de i! são cancelados com fatores do numerador da fração. Como 1 ≤ i ≤ p − 1 e p é primo, concluímos que nenhum dos fatores do denominador da fração cancela o fator p. Portanto, ( p i ) é múltiplo de p. Demonstrado o lema, podemos demonstrar o teorema por indução em n para os casos em que n é natural e depois estendermos para todos os inteiros. Teorema 1.45 (Pequeno Teorema de Fermat). Seja p um número primo e a um número inteiro, então ap ≡ a (mod p). Demonstração. Inicialmente suponha que np ≡ n (mod p). Para n = 1, temos 1p ≡ 1 (mod p), que é obviamente verdadeira. Função de Euler 32 Assumimos então que np ≡ n (mod p) é verdadeira, e utilizando o lema que acabamos de demonstrar, temos (n+ 1)p ≡ np + 1p ≡ n+ 1 (mod p). Caso tomemos n negativo, temos −n positivo, logo vale (−n)p ≡ −n (mod p). Aqui devemos considerar os dois casos possíveis de paridade de p. Ou p é par, especifi- camente o número 2, pois é o único primo par, ou p é ímpar. Quando tivermos p = 2, teremos (−n)2 ≡ −n (mod 2), ou seja, n2 ≡ −n (mod 2). Se estivermos tomando um n par, teremos n2 ≡ 0 (mod 2) e −n ≡ 0 (mod 2), logo n2 ≡ −n (mod 2). E caso tenhamos escolhido n ímpar, teremos n2 ≡ 1(mod 2) e −n ≡ 1 (mod 2), satisfazendo também n2 ≡ −n (mod 2). Já no caso em que p é ímpar, teremos (−n)p ≡ −np ≡ −n (mod p). Mas como estamos trabalhando com congruências, podemos multiplicar ambos os lados da nossa congruência por (−1), obtendo np ≡ n (mod p). O Pequeno Teorema de Fermat tem uma forma alternativa de ser enunciado, como pode- mos ver a seguir. Teorema 1.46. Seja p primo e a um inteiro não divisível por p. Então ap−1 ≡ 1 (mod p). Muitos algoritmos e testes de primalidade se basearam neste teorema para aumentar sua eficiência. 1.8 Função de Euler Também muito importante no processo de encriptação de mensagens da criptografia RSA, apresentamos a Função de Euler. Definição 1.47. Chamamos de função de Euler a função φ : Z+ → Z+, que associa a cada número n ao número positivo s tal que: (i) s 6 n; Equações Diofantinas 33 (ii) mdc(s, n) = 1. É razoável, pela Definição 1.47, dizer que 1 6 φ(n) 6 n. Teorema 1.48. Se p é primo e a um inteiro positivo, então φ(pa) = pa − pa−1. Demonstração. Pela definição de φ, segue que φ(pa) é o número de inteiros positivos não- superiores a pa e coprimo com pa. Mas, os únicos inteiros não coprimo com pa e menores ou iguais a pa são os divisíveis por p. Como os múltiplos de p não superiores a pa são pa−1, segue que φ(pa) = pa − pa−1. Proposição 1.49. Se mdc(p, q) = 1, então φ(pq) = φ(p)φ(q). Proposição 1.50. Um inteiro positivo p é primo se, e somente se, φ(p) = p− 1. Demonstração. (⇒) Se p é primo, segue imediato pelo Teorema 1.48 que φ(p) = p − 1. (⇐) Suponha que p não é primo. Então existe um elemento q ∈ Z, diferente de 1 e p tal que q | p. Pela definição da função de Euler temos que 0 < φ(p) 6 p − 1, mas nesse caso o valor de q deve ser excluído, pois não é coprimo com p. Logo, φ(p) 6= p − 1, o que é uma contradição. Portanto, p é primo. 1.9 Equações Diofantinas Estudaremos na Seção 3.5 do Capítulo 3, como encontrar um novo valor positivo para nosso componente da chave privada do sistema, caso o valor encontrado seja negativo. Para isso, utilizaremos o conceito e resultado apresentados a seguir. Definição 1.51. Uma equação nas variáveis inteiras x e y do tipo ax+ by = c, com a, b, c ∈ Z diz-se equação diofantina. Teorema 1.52. Sejam a e b inteiros positivos, c ∈ Z e mdc(a, b) = d. A equação ax+ by = c, com x, y ∈ Z tem solução se, e somente se, d divide c. Além disso, se x0, y0 são tais que ax0 + by0 = c, então a solução geral da equação ax+ by = c é dada por Equações Diofantinas 34 x = x0 + ( b d ) k, y = y0 − (a d ) k, onde k ∈ Z. Demonstração. Se a = 0 ou b = 0, então o resultado é imediato. Vejamos o caso em que a 6= 0 e b 6= 0. Nesse caso, a demonstração do teorema será dividida em duas partes, a primeira com relação a equação possuir solução se d divide c, e a segunda com relação a solução geral. Primeira parte do teorema: Supondo que a equação ax + by = c tenha solução em Z, e mdc(a, b) = d, então d|ax e d|by e, portanto, d|ax+ by o que implica d|c. Reciprocamente, supondo que d|c, então existe t ∈ Z tal que c = dt. Pelo Teorema 1.19 existem α, β ∈ Z tal que aα + bβ = d. Multiplicando essa última igualdade por t tem-se que a(tα) + b(tβ) = dt = c e, portanto x = αt e y = βt são soluções da equação ax+ by = c. Segunda parte do teorema: Sejam x0 e y0 tal que ax0 + by0 = c. Assim, se k ∈ Z, então a ( x0 + b d k ) + b ( y0 − a d k ) = ax0 + ab d k + by0 − ab d k = ax0 + by0 = c, o que mostra que x = x0 + ( b d ) k, y = y0− (a d ) k é uma solução da equação ax+ by = c. Vamos mostrar agora, que se x, y ∈ Z são tais que ax+ by = c, então x, y são da forma dada acima. Para isso, vamos supor que o par (x′, y′) seja outra solução da equação. Assim, ax′ + by′ = c = ax0 + by0, mas isto é equivalente a a(x′ − x0) = b(y0 − y′). Como mdc(a, b) = d, segue que d|a e d|b. Assim existem m e n inteiros tal que a = md e b = nd, com mdc(m,n) = 1. Desta forma, m(x′ − x0) = n(y0 − y′), e assim m|n(y0 − y′). Como mdc(m,n) = 1, segue que m deve dividir y0 − y′, isto é, y0 − y′ = mk, para algum k ∈ Z. Portanto, y′ = y0 −mk = y0 − a d k. Equações Diofantinas 35 Assim, m(x′ − x0) = n(y0 − y′) = nmk, e portanto, x′ − x0 = nk, ou equivalentemente, x′ = x0 + nk = x0 + b d k, o que prova o resultado. Exemplo 1.53. Resolvemos a equação 5x + 12y = 81, com soluções pertencentes ao con- junto dos números inteiros. Iniciaremos fazendo uso do algoritmo de Euclides, para encontrar mdc(12, 5). Sendo assim, 12 = 5 · (2) + 2 (1.4) 5 = 2 · (2) + 1 (1.5) 2 = 1 · (2) + 0. Logo, mdc(12, 5) = 1 e pelo Teorema (1.52), como mdc(12, 5) = 1 então a equação tem solução. Agora, isolamos os restos de (1.4) e (1.5), desconsiderando a última expressão, já que tem resto 0 e, portanto, não será substituída em nenhuma outra expressão. Logo, 2 = 12 + 5 · (−2) (1.6) 1 = 5 · (1) + 2 · (−2). (1.7) Substituindo (1.6) em (1.7), temos a expressão procurada: = 5 · (1) + (5 · (−2) + 12) · (−2) = 5 · (5) + 12 · (−2). (1.8) Multiplicando a Equação (1.8) por 81, segue que 81 = 5 · (405) + 12 · (−162). Portanto, uma solução da equação 5x + 12y = 81 é x0 = 405 e y0 = −162. Deste modo, temos que a solução geral no conjunto dos inteiros, será dada por: S = {(405 + 12k,−162− 5k), com k ∈ Z}. 2 Os Inteiros Gaussianos Neste capítulo estendemos para os inteiros gaussianos as clássicas propriedades de Z, que serão suporte para a nossa extensão do algoritmo RSA aos inteiros gaussianos, o qual será abordado no Capítulo 4. Muitas das propriedades apresentadas na Seção 2.1 são válidas para os inteiros gaussianos, pois neste caso nos restringimos aos números complexos com coeficientes em Z. Primeiramente discutimos propriedades resultantes da definição do con- junto dos números complexos C. As principais referências utilizadas neste capítulo foram [7, 8, 9, 10, 11, 12, 13]. 2.1 Números Complexos O conceito de número complexo se desenvolveu gradativamente, como ocorreu com os demais tipos de números. Algumas equações de grau 2, como x2 + 1 = 0, não haviam solução até o século XVI, pois para os matemáticos da época a raiz negativa não existia. Porém, não foi este o motivo pelo qual os números complexos surgiram. Ao passar dos anos, alguns matemáticos viram o mesmo problema para equações do 3º grau, onde perceberam que os números reais não eram suficientes para resolver este tipo de equação. Para solucionar este problema alguns matemáticos europeus, principalmente italianos, desenvolveram pesquisas. Houve algumas disputas também. Os números complexos começaram a ser desenvolvidos por Scipione dal Ferro. Ferro desenvolveu uma teoria para a solução das equações do tipo x3+px+q = 0, mas acabou não a publicando. Antônio Maria Fior conheceu a teoria de Ferro e ampliou-a para as equações do tipo x3+px2+q = 0. Fior acabou desafiando Niccolò Fontana, conhecido como Tartaglia. Tartaglia venceu todas as disputas com Fior. Neste momento, chega aos ouvidos de Girolamo Cardano que Tartaglia sabia resolver tais tipos de equações. Cardano implorou a “fórmula” para resolver essas equações. Com sua insistência e juramento de que não divulgaria o resultado, Tartaglia revelou a solução. Porém, Cardano não cumpriu com sua palavra, e em 1545 fez a publicação no livro Ars Magna. Ele somente fez uma menção de Tartaglia na sua obra e até hoje a fórmula é conhecida como 36 Números Complexos 37 “Fórmula de Cardano”3. Após esta “luta” surge um problema inquietante que Cardano trouxe, conhecido na época como números “sofisticados”, ou seja, as raízes quadradas de números negativos. Neste momento da história, se introduz a ideia de aceitar o imaginário, e não somente o real. Foi René Descartes que escreveu no seu livro Géométrie a seguinte frase: “Nem sempre as raízes verdadeiras (positivas) ou falsas (negativas) de uma equação são reais. Às vezes elas são imaginárias”. Com esta citação ficou definido que o número raiz quadrada de −1 seria chamado de número imaginário e que poderia ser manipulado de acordo com as regras da álgebra (GARBI, 1997, p. 75). Em seguida, Leonhard Euler em 1777 simbolizou à raiz quadrada de −1 por i. Segundo ele, os números complexos também possuem uma parte real. Logo, os caracterizou como sendo do tipo: z = a + bi, onde a e b são números reais e i2 = −1, mas esta ideia só foi mais aceita quando Carl Friedrich Gauss a introduziu, em 1832. Gauss além de introduzir a expressão do número complexo, realizou estudos relacionados a representação geométrica dos mesmos, que já tinha sido publicada e estudada também anteriormente por Jean Argand, em 1806. Para maiores detalhes sobre a origem dos números complexos a referência BOYER, Carl B. História da Matemática. Trad. Elza F. Gomide. SP: Editora Edgard Blücher Ltda, 1996, pode ser consultada. Definição 2.1. Os números z da forma a + bi são chamados de números complexos, onde a, b ∈ R e i = √ −1, esta última denominada unidade imaginária. Denotaremos por C o conjunto dos números complexos. Dados os números complexos z1 = a1 + b1i e z2 = a2 + b2i definimos sua soma por z1 + z2 = (a1 + b1i) + (a2 + b2i) = (a1 + a2) + (b1 + b2)i (2.1) e seu produto por z1.z2 = (a1 + b1i).(a2 + b2i) = (a1.a2 − b1.b2) + (a1.b2 + a2.b1)i (2.2) Exemplo 2.2. Consideremos os números complexos: z1 = 2 + 4i, z2 = 5 − i, z3 = 10 e z4 = −1 2 i. Pela definição de adição (2.1) e multiplicação (2.2) temos: 3Fórmula de Cardano Uma solução para equação x3 + px+ q, com p e q reais é: x = 3 √ −q 2 + √(q 2 )2 + (p 3 )3 + 3 √ −q 2 − √(q 2 )2 + (p 3 )3 Números Complexos 38 • z1 + z2 = (2 + 4i) + (5− i) = (2 + 5) + (4 + (−1))i = 7 + 3i; • z3 + z4 = (10) + ( −1 2 i ) = (10 + 0i) + ( 0− 1 2 i ) = (10 + 0) + ( 0 + ( −1 2 i )) = 10− 1 2 i; • z1.z2 = (2 + 4i).(5− i) = (2.5− 4.(−1)) + (2.(−1) + 4.5)i = 14 + 18i, • z2.z4 = (5− i). ( −1 2 i ) = (5− i). ( 0− 1 2 i ) = ( (5.0)− (−1). ( −1 2 )) + + ( 5. ( −1 2 ) + (−1).0 ) i = −1 2 − 5 2 i. As operações (2.1) e (2.2) satisfazem as seguintes propriedades: (C. 1) Comutatividade: Se z1 e z2 ∈ C então z1 + z2 = z2 + z1 e z1.z2 = z2.z1; (C. 2) Associatividade: Se z1, z2 e z3 ∈ C então (z1 + z2)+z3 = z1+(z2 + z3) e (z1.z2) .z3 = z1. (z2.z3); (C. 3) Distributividade: Se z1, z2 e z3 ∈ C então z1. (z2 + z3) = z1.z2 + z1.z3; (C. 4) Existência do zero: Existe um elemento 0 = 0 + 0i ∈ C tal que 0 + z = z para todo z ∈ C; (C. 5) Existência da unidade: Existe um elemento 1 = 1 + 0i ∈ C tal que 1.z = z para todo z ∈ C; (C. 6) Existência do inverso aditivo: Dado z = a + bi ∈ C existe um único w = (−a) + (−b) i ∈ C tal que z + w = 0. Notação: w = −z, (C. 7) Existência do inverso multiplicativo: Dado z = a + bi ∈ C, tal que a 6= 0 ou b 6= 0, existe w = a (a2 + b2) −1 − b (a2 + b2) −1 i tal que z.w = 1. Notação: w = z−1 = 1 z . Dizemos então que C é um corpo com as operações (2.1) e (2.2). Um fato que devemos ter em mente é que o corpo dos reais está naturalmente mergulhado em C e para isto basta identificarmos um número real x com o complexo x+ 0i. Tendo em vista esta identificação, diremos que R ⊂ C. Observe que se z = a + 0i ∈ R e w = b + 0i ∈ R então z + w e z.w estão em R. Portanto R é um subcorpo de C, isto é, as operações (2.1) e (2.2) estendem as operações de soma e produto de números reais. Podemos identificar o conjunto dos números complexos com o plano R2 = {(x, y) | x, y ∈ R} por meio do isomorfismo ϕ : R2 → C (x, y) 7→ x+ yi Números Complexos 39 Assim, podemos definir a soma e o produto de complexos z1 = (a1, b1) e z2 = (a2, b2), respectivamente: z1 + z2 = (a1, b1) + (a2, b2) = (a1 + a2, b1 + b2) (2.3) z1.z2 = (a1, b1).(a2, b2) = (a1.a2 − b1.b2, a1.b2 + a2.b1) (2.4) A representação dos números complexos por pontos do plano é muito útil e frequente. Por meio dela, o número complexo z = x+ yi é identificado como o ponto (x, y), ou com o vetor Oz de componentes x e y. Atualmente, o plano dos números complexos é conhecido como plano de Argand-Gauss. Dado z = x+ yi ∈ C, definimos Re(z) = x (parte real de z) Im(z) = y (parte imaginária de z). Logo, para todo z ∈ C temos z = Re(z) + Im(z)i. Na Figura 2.1 apresentamos a representação gráfica de z. Figura 2.1: Representação gráfica de z Definição 2.3. Definimos o módulo, ou valor absoluto ou norma de um número complexo z = x+ yi como sendo o número não negativo |z|= √ x2 + y2. Como se vê (Figura 2.2), |z| é a distância do ponto z à origem. Definição 2.4. O complexo conjugado de z = x + yi é definido como sendo z = x+ yi = x− yi. Em termos do módulo e do conjugado, temos: Números Complexos 40 zz = (x+ yi)(x− yi) = (x2 + y2) + (−xy + yx)i = x2 + y2, isto é, zz = |z|2. O quociente z = z1 z2 de dois números complexos z1 e z2, z2 6= 0, é definido pela condição z.z2 = z1. Para calcular o quociente basta multiplicar o numerador e o denominador pelo complexo conjugado do denominador, isto é, se z1 = x1 + y1i e z2 = x2 + y2i então z1 z2 = z1.z2 z2.z2 = z1.z2 |z2|2 = x1x2 + y1y2 + (y1x2 − x1y2)i x22 + y22 . (2.5) Exemplo 2.5. Considere os números complexos z1 = −3 + i e z2 = 1− 2i. Assim, z1 z2 = −3 + i 1− 2i = (−3 + i).(1 + 2i) (1− 2i).(1 + 2i) = ((−3).1− 1.2) + ((−3).2 + 1.1)i (1.1− (−2).2) + (1.2 + (−2).1)i = −5− 5i 5 = −1−i. Para todo z e w em C, tem-se as seguintes propriedades: 1. |z|= |z|, 2. (z + w) = z + w, 3. z.w = zw, 4. ( z w ) = z w , w 6= 0, 5. z−1 = z |z|2 , z ∈ C - {0}, 6. Re(z) = z + z 2 e Im(z) = z − z 2i , 7. |z + w|2= |z|2+|w|2+2Re (zw). Consideremos agora um número complexo não nulo z = x + iy. Se |z| é o segmento de reta que liga 0 a z e θ é o ângulo que |z| faz com o eixo dos x (0 ≤ θ ≤ 2π) podemos escrever cos θ = x√ x2 + y2 = x |z| e sen θ = y√ x2 + y2 = y |z| e, portanto, z = |z|cos θ + i|z|sen θ = |z|(cos θ + i sen θ). (2.6) A expressão (2.6) é chamada de representação polar do número complexo z. O número θ é chamado de argumento de z e denotaremos por arg(z). Na Figura 2.2 representamos geometricamente |z| e arg(z). Números Complexos 41 Figura 2.2: Representação gráfica da norma de z e seu argumento. Podemos determinar θ de maneira única exigindo, por exemplo, que 0 ≤ θ < 2π ou que −π < θ ≤ π. Exemplo 2.6. Seja z1 = 2−2i, então |z1|= 2 √ 2 e arg(z1) = −π 4 ±2nπ com n = 0, 1, 2, · · ·. Logo, uma forma polar desse número complexo é z1 = 2 √ 2 ( cos ( −π 4 ) + i sen ( −π 4 )) . Também podemos considerar algum ponto z0 que não seja a origem (0, 0). A represen- tação z − z0 = ρ(cosφ+ i senφ) (2.7) é a forma polar de z − z0, onde ρ = |z − z0| e φ é o ângulo de inclinação do vetor −−−→z − z0. Para os números complexos z1 = r1(cos θ1 + i sen θ1) e z2 = r2(cos θ2 + i sen θ2) segue a multiplicação e divisão, respectivamente: z1z2 = r1r2[cos(θ1 + θ2) + i sen(θ1 + θ2)] (2.8) z1 z2 = r1 r2 [cos(θ1 − θ2) + i sen(θ1 − θ2)] (2.9) Além disso, z1 = z2 ⇔ r1 = r2 e θ1 ≡ θ2(mod 2π). As igualdades seguem imediatamente considerando as relações conhecidas: • cos(θ1 + θ2) = cos θ1 cos θ2 − sen θ1 sen θ2 • sen(θ1 + θ2) = sen θ1 cos θ2 + cos θ1 sen θ2 • cos(θ1 − θ2) = cos θ1 cos θ2 + sen θ1 sen θ2 Números Complexos 42 • sen(θ1 − θ2) = sen θ1 cos θ2 − cos θ1 sen θ2 A fórmula de multiplicação acima estende-se para um número qualquer de fatores. Sendo zj = rj(cos θj + i sen θj), j = 1, 2, ..., n teremos z1z2...zn = r1r2...rn[cos(θ1 + θ2 + ...+ θn) + i sen(θ1 + θ2 + ...+ θn)]. A demonstração segue por indução. Em particular, quando todos os fatores são iguais e de módulo unitário, obtemos a chamada Fórmula de De Moivre: (cos θ + i sen θ)n = cosnθ + i sennθ. (2.10) Esta fórmula é válida também para expoentes negativos. De fato: (cos θ + i sen θ)−n = 1 (cos θ + i sen θ)n = 1 cosnθ + i sennθ = cosnθ − i sennθ, isto é, (cos θ + i sen θ)−n = cos(−nθ) + i sen(−nθ). (2.11) As seguintes propriedade se verificam de forma imediata: 1. |z|≥ 0 e |z|= 0 se, e somente se, z = 0; 2. |Re(z)|≤ |z| e |Im(z)|≤ |z|, 3. |z|= |−z|. Desenvolvendo |z1z2|2= (z1z2)(z1z2) = (z1z̄1)(z2z̄2) = |z1|2|z2|2 segue a propriedade 4: 4. |z1z2|= |z1||z2|. Mostremos agora um resultado importante bem conhecido: a desigualdade triangular, ou ainda a propriedade 5: 5. |z1 + z2|≤ |z1|+|z2|. Para a demonstração observemos que: Números Complexos 43 |z1 + z2|2 = (z1 + z2)(z̄1 + z̄2) = z1z̄1 + z2z̄2 + (z1z̄2 + z̄1z2) = |z1|2+|z2|2+z1z̄2 + z1z̄2 = |z1|2+|z2|2+2Re(z1z̄2) ≤ |z1|2+|z2|2+2|Re(z1z̄2)| ≤ |z1|2+|z2|2+2|z1z2| = |z1|2+|z2|2+2|z1||z2| = (|z1|+|z2|)2. Extraindo a raiz segue o resultado. Observamos ainda que |z1 − z2|= |z1 + (−z2)|≤ |z1|+|−z2|, e como |−z2|= |z2|, concluímos outra desigualdade: 6. |z1 − z2|≤ |z1|+|z2|. Uma terceira desigualdade conhecida é 7. |z1|−|z2|≤ |z1 + z2|. Para isto basta identificar |z1|= |(z1 + z2)− z2|≤ |z1 + z2|+|z2| (2.12) e então subtrair |z2| do primeiro e último membros. Por último, uma quarta desigualdade: 8. ||z1|−|z2||≤ |z1 + z2|. Para a verificação basta tomar |z1|−|z2|= a e mostrar que−|z1 + z2|≤ a ≤ |z1 + z2|. Do item (7) segue que a ≤ |z1 + z2| e −a ≤ |z1 + z2|, ou seja, |a|≤ |z1 + z2|, o que conclui o resultado. Os Inteiros Gaussianos 44 2.2 Os Inteiros Gaussianos O matemático alemão Gauss, investigava questões relacionadas à reciprocidade cúbica e biquadrática (x3 ≡ q(mod p) e x4 ≡ q(mod p), respectivamente,onde p e q são números primos), quando percebeu que essa investigação se tornava mais simples trabalhando sobre Z[i], o anel dos inteiros gaussianos, do que em Z, o conjunto dos números inteiros. Gauss estendeu a ideia de número inteiro quando definiu o conjunto Z[i], pois descobriu que muito da antiga Teoria de Euclides sobre fatoração de inteiros poderia ser transportada para esse novo conjunto com consequências importantes para a Teoria dos Números. Ele desenvolveu uma Teoria de Fatoração em Primos para esses números complexos e demons- trou que essa decomposição em primos é única, como acontece com o conjunto dos números inteiros. O uso que Gauss fez desse novo tipo de número foi de fundamental importância na demonstração do Último Teorema de Fermat. Definição 2.7. Seja Z[i] = {a+ bi | a, b ∈ Z, i2 = −1} .Os elementos de Z[i] são chamados de inteiros gaussianos. Os inteiros gaussianos são a extensão natural dos inteiros para o plano complexo. Como Z e Z[i] possuem estruturas parecidas, muitas propriedades que conhecemos de Z podem ser estendidas para Z[i]. Estudaremos algumas delas. Como Z[i] é um subconjunto de C, então eles compartilham das mesmas propriedades de adição e multiplicação, no entanto, Z[i] não é um corpo, pois veremos (Teorema 2.17) que os únicos elementos de Z[i] que são invertíveis são {1,−1, i,−i}. 2.2.1 Representação Gráfica dos Elementos de Z[i] Já dissemos que o conjunto dos números inteiros de Gauss está contido no conjunto dos números complexos e, por este motivo, é possível representar todos os elementos de Z[i] no plano cartesiano. Portanto, em geral, podemos representar graficamente cada inteiro gaussiano da forma a+ bi no ponto (a, b), de modo que tenhamos a correspondência (a, b) 7→ a+ bi, da mesma forma que fazemos com os números complexos. No exemplo a seguir veremos como representar graficamente um elemento z ∈ Z[i] e todos os seus múltiplos. Exemplo 2.8. Dado z = 3 + 2i ∈ Z[i] vamos representar graficamente todos os seus múlti- plos, isto é, os elementos da forma (3 + 2i)(x+ yi) = (3 + 2i)x+ (3 + 2i)yi = (3 + 2i)x+ (−2 + 3i)y, Os Inteiros Gaussianos 45 com x, y ∈ Z. Começamos colocando o elemento z = 3+2i no plano cartesiano, na posição Z = (3, 2), enquanto w = −2 + 3i é o ponto W = (−2, 3) (ver Figura 2.3). Todos os múltiplos de 3 + 2i são agora as combinações inteiras de w e z, conforme podemos ver na Figura 2.4, onde os múltiplos de 3 + 2i, o qual é um vértice de um dos quadrados, acabam por ser os vértices de todos os quadrados. Figura 2.3: Representação dos vetores z e w Figura 2.4: Múltiplos de 3 + 2i 2.2.2 Função Norma em Z[i] A função norma é muito importante para o estudo dos Inteiros Gaussianos e para nossa extensão do algoritmo RSA. Em Z, a distância de um número até a origem é medido pelo valor absoluto, já em Z[i], pela norma. Definição 2.9. A função N : Z[i] → Z+, tal que para todo α = a + bi ∈ Z[i], N(α) = αα = a2 + b2 é chamada norma. Os Inteiros Gaussianos 46 Há uma relação direta entre a norma do número complexo α e o valor absoluto do número α ∈ Z[i]. De fato, |α|= |a+ bi|= √ a2 + b2 e N(α) = a2 + b2 = |a+ bi|2. Exemplo 2.10. Interpretação geométrica da norma. Seja α = x + yi ∈ Z[i] e sua norma, N(α) = r, r ∈ Z, r > 0. Por definição de norma,N(α) = x2+y2, ou seja, sua representação no plano cartesiano se dá por uma equação da circunferência de raio √ r e centro (0, 0). Ver Figura2.5. Figura 2.5: Interpretação geométrica da norma Exemplo 2.11. N(3 + 8i) = 32 + 82 = 9 + 64 = 73. Teorema 2.12. Sejam α = a+ bi, β = c+ di ∈ Z[i]. Então N(αβ) = N(α)N(β). Demonstração. Para α = a+ bi, β = c+ di ∈ Z[i], temos: N(αβ) = N((a+ bi)(c+ di)) = N((ac− bd) + (ad+ bc)i) = (ac− bd)2 + (ad+ bc)2 = = (a2c2 + b2d2 + a2d2 + b2c2) = a2(c2 + d2) + b2(c2 + d2) = (a2 + b2)(c2 + d2) = = N(a+ bi)N(c+ di) = N(α)N(β). Exemplo 2.13. Vamos exemplificar o Teorema 2.12 para um caso particular. Tomando α = 3 + 5i e β = 2 + i temos que N(α) = N(3 + 5i) = 32 + 52 = 9 + 25 = 34 Os Inteiros Gaussianos 47 e N(β) = N(2 + i) = 22 + 12 = 4 + 1 = 5. Logo, N(α)N(β) = 34 · 5 = 170. Por outro lado, αβ = (3 + 5i)(2 + i) = 1 + 13i e calculando a norma de αβ, temos que N(αβ) = N(1 + 13i) = 12 + 132 = 1 + 169 = 170. Portanto, N(αβ) = N(α)N(β). Observação: A norma de cada inteiro gaussiano é um inteiro positivo, mas não é verdade que cada inteiro positivo é uma norma, pois normas são inteiros positivos da forma a2 + b2, e nem todo inteiro é possível escrever dessa maneira, que é o caso dos números 3, 7, 11, entre outros. 2.2.3 Unidades e Associados em Z[i] Veremos que as unidades e os elementos associados em Z[i] estão diretamente relaciona- dos com a função norma. Definição 2.14. Dizemos que α é invertível em Z[i], se existir β ∈ Z[i] tal que α · β = 1 A partir de agora, quando dizemos que α é invertível, significa α invertível em Z[i]. Pelo Teorema 2.12, podemos verificar a existência de inteiros gaussianos que possuem inverso multiplicativo, ou seja, α · β = 1. Teorema 2.15. Os únicos inteiros gaussianos que são invertíveis em Z[i] são ±1 e ±i. Demonstração. Tomemos α, β ∈ Z[i] tais que α·β = 1. Aplicando a função norma obtemos N(αβ) = N(1). Pelo Teorema 2.12 , N(α)N(β) = 1. Como N(α) e N(β) são inteiros positivos diferentes de 0, então N(α) = N(β) = 1. Tomando α = a+ bi, segue que N(α) = a2 + b2 = 1⇔ a = ±1 e b = 0 ou a = 0 e b = ±1. O mesmo acontece para β. Portanto, os únicos números possíveis para α e β são −1, 1, i e −i, ou seja, os únicos inteiros gaussianos invertíveis em Z[i] são ±1 e ±i. Fica claro observar o resultado do Teorema 2.15 com a representação geométrica dos inteiros gaussianos α e β com normas iguais a 1. Nesse caso a norma é representada geome- tricamente por uma circunferência de raio 1 e centro (0, 0), Figura 2.6. Note que os únicos inteiros de Gauss pertencentes a circunferência são ±1 e ±i. Definição 2.16. Chamamos os elementos invertíveis de Z[i] de unidades. Os Inteiros Gaussianos 48 Figura 2.6: Interpretação geométrica do Teorema 2.15 Teorema 2.17. O elemento α = a+ bi é uma unidade em Z[i] se, e somente se, N(α) = 1. Demonstração. (⇒) Primeiro suponhamos que α = a + bi ∈ Z[i] é uma unidade. Então existe β = c+ di ∈ Z[i] tal que α · β = 1. Aplicando a função norma na equação temos que N(αβ) = N(1) e, pelo Teorema 2.12, N(α)N(β) = N(1). Logo, (a2 + b2)(c2 + d2) = 1. Como a2 + b2, c2 + d2 ∈ Z+, segue que ambos os fatores devem ser iguais a 1. Portanto, 1 = a2 + b2 = N(a+ bi) = N(α). (⇐) Agora, suponhamos para algum α = a+bi ∈ Z[i] queN(α) = 1. Então a2+b2 = 1, o que implica que, a2 = 1− b2. Como a2 ≥ 0, temos que analisar quando 1− b2 ≥ 0 e para isso consideremos dois casos: i) Se b2 = 0 então b = 0 e a2 = 1 − 0 = 1. Logo, a = 1 ou a = −1. Se a = 1, então α = 1 + 0i. Como N(1 + 0i) = 1, segue que α = 1 + 0i é uma unidade em Z[i]. Se a = −1, então α = −1 + 0i. Como N(−1 + 0i) = 1, segue que α = −1 + 0i é uma unidade em Z[i]. ii) Se b2 = 1 então a2 = 1 − 1 = 0. Logo, a = 0 e b = 1 ou b = −1. Se b = 1, então α = 0 + i. Como N(0 + i) = 1, segue que α = 0 + i é uma unidade em Z[i]. Se b = −1, então α = 0− i. Como N(0− 0i) = 1, segue que α = 0− i é uma unidade em Z[i]. Definição 2.18. Dizemos que α, β ∈ Z[i] são associados se α = u ·β e N(α) = N(β), onde u ∈ {−1, 1, i,−i}. Exemplo 2.19. 3 + 5i é associado a 5− 3i, pois 3 + 5i = i · (5− 3i). Os Inteiros Gaussianos 49 2.2.4 Divisibilidade em Z[i] Assim como em Z, falaremos de divisibilidade em Z[i]. Definição 2.20. Dados dois inteiros gaussianos α e β, com α 6= 0. Diremos que α divide β, escrevendo α | β, quando existir ω ∈ Z[i] tal que β = α · ω. Exemplo 2.21. Como −4 + 7i = (1 + 2i)(2 + 3i), segue que (1 + 2i) divide −4 + 7i. Exemplo 2.22. 1 + 2i - 4 + 7i pois, ao fazermos esta divisão e racionalizar o denominador obtemos: 4 + 7i 1 + 2i = (4 + 7i)(1− 2i) (1 + 2i)(1− 2i) = 18− i 5 = 18 5 − 1 5 i /∈ Z[i], pois as partes real e a imaginária não são números inteiros. Portanto, 1 + 2i - 4 + 7i em Z[i]. Veremos sob quais condições β α ∈ Z[i]. Teorema 2.23. Dado α = a + bi ∈ Z[i] e c ∈ Z. Então c | α se, e somente se, c | a e c | b em Z. Demonstração. Se c | (a+ bi), então existe β = m+ ni ∈ Z[i] tal que a+ bi = c(m+ ni). Fazendo a distributiva e comparando as partes reais e imaginárias do inteiro gaussiano, temos que a = cm e b = cn, ou seja c | a e c | b. Reciprocamente, se c | a e c | b então a = cm e b = cn, para algum m, n ∈ Z. Como α = a + bi, substituindo temos α = (cm) + (cn)i = c(m + ni), para algum c ∈ Z e β = m+ ni ∈ Z[i]. Portanto, c | α. Proposição 2.24. Se α, β e γ são inteiros gaussianos, γ | α e γ | β, então existem δ, η ∈ Z[i] tal que γ | αδ + βη. Demonstração. Se γ | α e γ | β, então α = γζ1 e β = γζ2. Multiplicando as equações por δ e η, respectivamente, obtemos αδ = γζ1δ e βη = γζ2η. Somando as equações temos que αδ + βη = γ(ζ1δ + ζ2η). Portanto, γ | αδ + βη. Teorema 2.25. Para α, β ∈ Z[i], se α | β em Z[i], então N(α) | N(β) em Z. Demonstração. Como α | β, então existe γ ∈ Z[i], tal que β = αγ. Aplicando a norma nesta equação temos, N(β) = N(αγ). Pelo Teorema 2.12, N(β) = N(α)N(γ) e portanto N(α) | N(β), já que a norma é uma função em Z. Os Inteiros Gaussianos 50 Exemplo 2.26. Vamos encontrar todos os divisores de 1− 3i em Z[i]. Para isso, temos que encontrar os inteiros gaussianos α = a + bi, tal que α | 1 − 3i. Se 1− 3i = αγ, γ ∈ Z[i], então aplicando a função norma teremos N(1− 3i) = N(αγ) 10 = N(α)N(γ). Pelo Teorema 2.25, se α | 1 − 3i então N(α) | 10, logo N(α) ∈ {1, 2, 5, 10}. Fazendo α = a+ bi, temos: • se N(α) = a2 + b2 = 1, então α ∈ {±1,±i}; • se N(α) = a2 + b2 = 2, então α ∈ {±(1 + i),±(1− i)}; • se N(α) = a2 + b2 = 5, então α ∈ {±(1 + 2i),±(1− 2i),±(2 + i),±(2− i)} e • se N(α) = a2 + b2 = 10, então α ∈ {±(1 + 3i),±(1− 3i),±(3 + i),±(3− i)}. Portanto, encontramos 24 possíveis divisores de 1 − 3i. Ao fazermos a verificação, os divisores de 1− 3i são: {±1,±i,±(1 + i),±(1− i),±(1 + 2i),±(2− i),±(1− 3i),±(3 + i)} . Podemos observar na Figura 2.7 a representação de N(α) ∈ {1, 2, 5, 10} nas circunfe- rências C1, C2, C3 e C4, respectivamente. Os pontos marcados são os inteiros de Gauss α que pertencem as circunferências. Figura 2.7: Representação gráfica do Exemplo 2.26 Os Inteiros Gaussianos 51 Corolário 2.27. Um inteiro gaussiano tem norma par se, e somente se, é um múltiplo de 1 + i. Demonstração. (⇐) Como N(1 + i) = 2, segue que qualquer múltiplo de 1 + i tem norma par. (⇒) Por outro lado, seja α = a + bi ∈ Z[i] com norma par, ou seja, a2 + b2 = 2t, t ∈ Z. Para a2 + b2 ser par, a e b devem ser ambos pares ou ambos ímpares. Tomando a + bi = (1 + i)(r+ si) para alguns r, s ∈ Z, temos que a+ bi = (r− s) + (r+ s)i, que tem solução r = a+b 2 e s = b−a 2 . Como a e b tem a mesma paridade, r e s são números inteiros. Portanto α é um múltiplo de 1 + i. Exemplo 2.28. Seja α = 5 + 3i. Temos que N(α) = 52 + 32 = 34 e pelo Corolário 2.27, 5 + 3i é múltiplo de 1 + i. Ainda, de acordo com a demonstração do Corolário 2.27, γ ∈ Z[i] é dado por γ = ( 5 + 3 2 ) + ( 5− 3 2 ) = 4 + i. Portanto, 5 + 3i = (1 + i)(4 + i). Lema 2.29. Se β | α e N(β) = 1 ou N(β) = N(α), então ou β é uma unidade ou é um associado de α. Demonstração. Se N(β) = 1, então β é uma unidade, pelo Teorema 2.17. Se N(β) = N(α), com β | α, então α = βγ para algum γ ∈ Z[i]. Aplicando a função norma, temos N(α) = N(β)N(γ). Substituindo, temos N(α) = N(α)N(γ) N(α)−N(α)N(γ) = 0 N(α)(1−N(γ)) = 0. Como a norma de um inteiro gaussiano não nulo é um número inteiro positivo, concluí- mos que N(γ) = 1. Portanto, β é um associado de α. É importante observar que o Lema 2.29 não afirma que existem apenas ±α ou ±αi cuja a norma é igual a N(α). Os números 18i e −4 + 7i possuem normal igual a 65 e ambos não são associados. Na verdade, o Lema 2.29 indica que ±α ou ±αi são os únicos inteiros de Gauss que dividem α e tem normal igual a N(α). 2.2.5 Teorema da Divisão em Z[i] Uma razão pela qual somos capazes de transferir muitas propriedades de Z para Z[i] é devido ao próximo teorema. Os Inteiros Gaussianos 52 Teorema 2.30. (Teorema da Divisão) Para α, β ∈ Z[i], com β 6= 0, existem γ, δ ∈ Z[i] de tal forma que α = βγ + δ e δ = 0 ou N(δ) < N(β). Demonstração. Ao fazermos a divisão de α por β, obtemos α β = x+ yi, onde x e y podem ser inteiros ou racionais. Se x e y forem inteiros então γ = x + yi e δ = 0. Se x e y forem racionais então devemos procurarm e n, os inteiros mais próximos de x e y, respectivamente, ou seja, | x−m |≤ 1 2 e | y − n |≤ 1 2 . Tomando γ = m+ ni e δ = α− βγ, temos que N ( α β − γ ) = N((x+ yi)− (m+ ni)) = N((x−m) + (y− n)i) = (x−m)2 + (y− n)2. Como | x−m |≤ 1 2 e | y − n |≤ 1 2 , segue que (x−m)2 ≤ 1 4 e (y − n)2 ≤ 1 4 . Assim N ( α β − γ ) = (x−m)2 + (y − n)2 ≤ 1 4 + 1 4 = 1 2 . Como N ( α β − γ ) ≤ 1 2 e 1 2 < 1, segue que N( α β − γ) < 1. Multiplicando por N(β) esta desigualdade, obtemos N ( α β − γ ) N(β) < N(β) N (( α β − γ ) β ) < N(β) N(α− βγ) < N(β) N(δ) < N(β). Exemplo 2.31. Considere α = 1 + 4i e β = 2− 6i. Vamos realizar a divisão para encontrar α = βγ + δ. Como N(β) = 40, pelo Teorema 2.30 devemos ter N(δ) < 40. Note que 1 + 4i 2− 6i = (1 + 4i)(2 + 6i) (2− 6i)(2 + 6i) = −22 + 14i 40 = −11 20 + 7 20 i. Como −11 20 = −0, 55 e 7 20 = 0, 35, temos que considerar o maior inteiro mais próximo deles. Logo, γ = −1 + 0i e assim segue que 1 + 4i = (2− 6i)(−1 + 0i) + (3− 2i), já que δ = 3− 2i e N(3− 2i) = 13, N(δ) < 40. Existe uma diferença interessante entre o teorema da divisão em Z[i] e o teorema da divisão em Z : o quociente e o resto não são únicos em Z[i]. Os Inteiros Gaussianos 53 Exemplo 2.32. Seja α = 37 + 2i e β = 11 + 2i. Temos que N(β) = 125. Se realizarmos o algoritmo da divisão em Z[i] (Teorema 2.30), encontraremos que α = 3β + (4− 4i). Entretanto, também é verdade que α = β(3− i) + (2 + 7i). O resto em ambos os casos tem norma menor do que 125 (na verdade, menor do que 125 2 ). 2.2.6 O Algoritmo de Euclides em Z[i] Começamos definindo o máximo divisor comum em Z[i]. Definição 2.33. Sejam α, β e γ inteiros gaussianos não nulos. Diremos que γ será o máximo divisor comum de α e β, quando: i) γ | α e γ | β; ii) Se existe δ ∈ Z[i] tal que δ | α e δ | β, então N(δ) ≤ N(γ). Em outras palavras, o mdc entre dois ou mais inteiros gaussianos será o divisor comum com a maior norma. Indicamos o máximo divisor comum de α e β por γ = mdc(α, β). Mesmo sendo análogo o conceito de máximo divisor comum em relação a Z, não existe um valor fixo para mdc(α, β). Se γ é um máximo divisor comum de α e β, neste caso, também são (pelo menos) seus múltiplos da unidade: −γ, iγ e −iγ. Devido a isso, há a possibilidade de existir maiores divisores. Assim, podemos falar apenas na existência de um máximo divisor comum, porém não sobre o maior divisor comum. Teorema 2.34. Se α, β ∈ Z[i] e α = βγ + δ, onde γ e δ são inteiros gaussianos, então mdc(α, β) = mdc(β, δ). Demonstração. Da relação α = βγ + δ podemos concluir que todo divisor de β e γ é um divisor de α, pela Proposição 2.24. Esta mesma relação, escrita da seguinte forma δ = α−βγ nos diz que todo divisor de α e β é um divisor de δ. Logo o conjunto de divisores comuns de α e β é igual ao conjunto de divisores de β e δ, o que nos garante que mdc(α, β) = mdc(β, δ). Teorema 2.35. (Algoritmo de Euclides) Sejam α, β ∈ Z[i] e diferentes de zero. Aplicando repetidamente o Teorema 2.30 (Teorema da Divisão), onde o resto é diferente de zero, tere- mos: Os Inteiros Gaussianos 54 α = βγ1 + δ1, com N(δ1) < N(β) β = δ1γ2 + δ2, com N(δ2) < N(δ1) δ1 = δ2γ3 + δ3, com N(δ3) < N(δ2) ... O último resto diferente de zero é divisível por todos os divisores comuns de α e β e será divisor comum, por isso é um máximo divisor comum de α e β. Demonstração. Pela divisão euclidiana, temos α = βγ1 + δ1, com N(δ1) < N(β). Pelo Teorema 2.34, mdc(α, β) = mdc(β, δ1), desta forma temos duas situações: 1. N(δ1) = 0, neste caso mdc(β, δ1) = β. 2. N(δ1) 6= 0, neste caso fazemos a divisão euclidiana de β por δ1, obtendo β = δ1γ2 + δ2, com N(δ2) < N(δ1). Segue que mdc(β, δ1) = mdc(δ1, δ2). Novamente pode ocorrer duas situações: 1. N(δ2) = 0, neste caso mdc(δ1, δ2) = δ1. 2. N(δ2) 6= 0, neste caso fazemos a divisão euclidiana de δ1 por δ2, obtendo δ1 = δ2γ3 + δ3, com N(δ3) < N(δ2). Segue que mdc(α, β) = mdc(β, δ1) = mdc(δ1, δ2) = mdc(δ2, β3), e assim sucessivamente. Definindo δ0 = β, existe um valor n natural que δn+1 = 0 e δn 6= 0. De fato se tivéssemos para todo n, δn 6= 0, teríamos uma sequência infinita em N, N(δ0) > N(δ1) > N(δ2) > ... > 0, o que é um absurdo. Logo, mdc(α, β) = mdc(β, δ1) = mdc(δ1, δ2) = ... = mdc(δn, δn+1) = mdc(δn, 0) = δn. Portanto, o último resto não nulo δn deste processo fornece o valor de mdc(α, β). Os Inteiros Gaussianos 55 Exemplo 2.36. Vamos encontrar mdc(32 + 9i, 4 + 11i). Aplicando o teorema da divisão (Teorema 2.30) e o Algoritmo de Euclides (Teorema 2.35), encontramos 32 + 9i = (4 + 11i)(2− 2i) + (2− 5i) 4 + 11i = (2− 5i)(−2 + i) + (3− i) 2− 5i = (3− i)(1− i) + (−i) 3− i = (−i)(1 + 3i) + 0. Portanto, mdc(32 + 9i, 4 + 11i) = −i. Definição 2.37. Dizemos que α, β ∈ Z[i] são primos entre si ou coprimos, quando têm as unidades como máximo divisor comum. Exemplo 2.38. No Exemplo 2.36, 32 + 9i e 4 + 11i são primos entre si. Exemplo 2.39. Para calcularmdc(27+4i, 5−2i) basta aplicar o teorema da divisão (Teorema 2.30) e em seguida o Algoritmo de Euclides (Teorema 2.35). Logo, encontramos, 27 + 4i = (5− 2i)(4 + 3i) + (1− 3i) (5− 2i) = (1− 3i)(1 + i) + 1 (1− 3i) = 1(1− 3i) + 0. O último resto diferente de zero é 1, então mdc(27 + 4i, 5 − 2i) = 1 e portanto, 27 + 4i e 5− 2i são primos entre si. Nos exemplos apresentados o máximo divisor comum entre dois inteiros gaussianos é uma unidade, mas veremos no resultado que segue que isso nem sempre acontece. Proposição 2.40. Dados α, β ∈ Z[i] e γ = mdc(α, β) obtido pelo algoritmo de Euclides. Qualquer máximo divisor comum é associado a γ. Demonstração. Suponha que γ̃ = mdc(α, β). Como γ | α e γ | β, segue que γ | γ̃ ⇒ N(γ) ≤ N(γ̃). (2.13) Por outro lado, como γ = (α, β) e γ̃ | α e γ̃ | β então γ̃ | γ ⇒ N(γ̃) ≤ N(γ). (2.14) De (2.13) e (2.14), temos que N(γ) = N(γ̃), assim, γ e γ̃ são associados, segundo o Lema 2.29 . Os Inteiros Gaussianos 56 Exemplo 2.41. Suponha α = 11 + 3i e β = 1 + 8i. Pelo teorema de Euclides (Teorema 2.35), temos que 11 + 3i = (1 + 8i)(1− i) + (2− 4i) 1 + 8i = (2− 4i)(−1 + i) + (−1 + 2i) 2− 4i = (−1 + 2i)(−2) + 0. Neste caso mdc(α, β) = −1 + 2i. Agora, vamos utilizar uma outra possibilidade na segunda equação. 11 + 3i = (1 + 8i)(1− i) + (2− 4i) 1 + 8i = (2− 4i)(−2 + i) + (−1− 2i) 2− 4i = (1− 2i)(2) + 0. Neste caso mdc(α, β) = 1− 2i. Note que obtemos dois máximos divisor comum para α e β e segundo a Proposição 2.40, eles são associados. De fato, −1 + 2i = (−1)(1− 2i). 2.2.7 O Teorema de Bézout em Z[i] Vimos no Capítulo 1 que em Z o teorema de Bézout diz que para todo inteiro não nulo a e b em Z tem-se que mdc(a, b) = ax+ by, para algum x, y ∈ Z que são encontrados usando o algoritmo euclidiano. A mesma ideia vale para Z[i], conforme veremos aqui. Teorema 2.42. (Teorema de Bézout) Sejam α, β ∈ Z[i] diferentes de zero e mdc(α, β) = γ. Então γ = αx+ βy, para algum x, y ∈ Z[i]. Demonstração. Considere o conjunto C sendo todas as combinações lineares de α e β e n = αx0 +βy0, onde n é o elemento de menor norma de C. Suponha por absurdo que n - α. Então α = nq + r, com N(r) < N(n). Temos que r = α− nq = α− (αx0 + βy0)q = α− αx0q − βy0q = α(1− x0q) + β(−y0q). Então r ∈ C, N(r) < N(n), mas n é o elemento de menor norma em C, portanto, n | α. Os Inteiros Gaussianos 57 Analogamente, n | β. Assim, n é o divisor comum de α e β. Vamos mostrar que n = γ. De fato, como mdc(α, β) = γ, então γ | α e γβ. Logo existem q1 e q2 ∈ Z[i] tais que α = γq1 e β = γq2. Como n = αx0 + βy0, segue que n = (γq1)x0 + (γq2)y0 n = γ(q1x0 + q2y0). Se γ | n então N(γ) | N(n). Como n é o menor elemento de C, N(γ) = N(n). Se γ | n e N(γ) = N(n) então γ e n são associados. Isso implica que, γ = n · u⇒ γ = αx0u+ βy0u⇒ γ = αx+ βy, para algum x, y ∈ Z[i]. Corolário 2.43. Sejam α e β inteiros gaussianos primos entre si. Então existem x, y ∈ Z[i] tais que αx+ βy = 1. Demonstração. Como α e β são primos entre si, entãomdc(α, β) = m, ondem ∈ {−1, 1,−i, i}. Pelo Teorema 2.42, existem x, y ∈ Z[i] tais que αx+ βy = m. Temos quatro casos: 1. Para m = 1, então αx+ βy = 1; 2. Para m = −1, então αx + βy = −1, multiplicando a equação por −1, temos que α(−x) + β(−yi) = 1. 3. Para m = i, então αx+βy = i, multiplicando a equação por−i, temos que α(−xi) + β(−yi) = 1. 4. Para m = −i, então αx+βy = −i, multiplicando a equação por i, temos que α(xi) + β(yi) = 1. Portanto, em todos os casos conseguimos escrever αx+ βy = 1. Exemplo 2.44. Temos que 27+4i e 5−2i são primos entre si, poismdc(27+4i, 5−2i) = 1. Agora, escrevendo 1 como uma combinação linear de 27 + 4i e 5− 2i, conforme o teorema de Bézout (Teorema 2.42) obtemos: 1 = 5− 2i− (1− 3i)(1 + i) 1 = 5− 2i− [(27 + 4i)− (5− 2i)(4 + 3i)](1 + i) 1 = 5− 2i− (27 + 4i)(1 + i) + (5− 2i)(4 + 3i)(1 + i) 1 = (5− 2i)[1 + (4 + 3i)(1 + i)]− (27 + 4i)(1 + i) 1 = (5− 2i)[1 + 1 + 7i] + (27 + 4i)(−1− i) 1 = (5 + 2i)(2 + 7i) + (27 + 4i)(−1− i). Os Inteiros Gaussianos 58 Logo, (27 + 4i)(−1− i) + (5− 2i)(2 + 7i) = 1, com x = −1− i e y = 2 + 7i. Corolário 2.45. Se α | βγ e α e β são primos entre si, então α | γ. Demonstração. Como α | βγ segue que βγ = αn, para algum n ∈ Z[i]. Sendo α e β primos entre si, pelo Corolário 2.43 temos que existem x, y ∈ Z[i], tais que αx+ βy = 1. (2.15) Multiplicando a Equação 2.15 por γ e sabendo que βγ = αn, temos que γ = α(γx + ny), ou seja, α | γ. Teorema 2.46. Sejam α, β, γ ∈ Z[i] tais que mdc(α, β) = 1 e γ = αβ. Então para todo δ ∈ Z[i], mdc(γ, δ) = 1 se, e somente se, mdc(α, δ) = 1 e mdc(β, δ) = 1. Demonstração. (⇒) Sejam α, β, γ em Z[i] tal que α e β são primos entre si e γ = αβ. Suponhamos que mdc(α, δ) 6= 1 ou mdc(β, δ) 6= 1. Sem perda de generalidade, tomamos mdc(α, δ) = µ para algum µ ∈ Z[i], não unidade. Então µ | α e µ | δ e além disso, já que α | γ, temos que µ | γ. Como µ | γ e µ | δ, segue que µ é um divisor comum, diferente da unidade, de γ e δ. Assim, γ e δ não são primos entre si, pois 2 ≤ N(µ) ≤ N(γ). (⇐) Agora, suponhamos que mdc(α, δ) = 1 e mdc(β, δ) = 1. Então, αk1 + δk2 = 1 e βk3 + δk4 = 1 para algum k1, k2, k3 e k4 ∈ Z[i]. Multiplicando as equações membro a membro, temos (αk1 + δk2)(βk3 + δk4) = 1 αk1βk3 + αk1δk4 + δk2βk3 + δk2δk4 = 1. Como γ = αβ, γ(k1k3) + δ(αk1k4 + k2βk3 + k2δk4) = 1. Portanto, mdc(γ, δ) = 1. 2.2.8 Primos em Z[i] e Fatoração Única Nesta seção responderemos a seguinte pergunta: como são caracterizados os primos em Z[i]? Definição 2.47. Seja α ∈ Z[i]. Dizemos que α é composto se existirem β, γ ∈ Z[i] tais que α = βγ e N(β) > 1 e N(γ) > 1. Se α tem somente fatores triviais, dizemos que α é um número primo. Os Inteiros Gaussianos 59 Ao pensar em números primos é natural perguntar: todo primo em Z é primo em Z[i]? Nem sempre, vejamos os exemplos que seguem. Exemplo 2.48. 13 é primo em Z mas não é primo em Z[i] pois, 13 = (3 + 2i)(3− 2i). Exemplo 2.49. 7 é primo em Z e é primo em Z[i]. De fato, suponhamos que 7 é composto, então podemos escrever 7 = αβ com N(α)> 1 e N(β) > 1. Tomando a norma em ambos os membros temos que N(α)N(β) = 49. Logo, como N(α)> 1 e N(β) > 1 segue que N(α) = 7. Se α = a+ bi então N(α) = a2 + b2 = 7, que não tem solução inteira. Portanto, 7 é primo em Z[i]. Teorema 2.50. Se a norma de um inteiro Gaussiano α é um número primo em Z, então α será um número primo em Z[i]. Demonstração. Suponha N(α) = p, p é primo em Z. Considere qualquer fatoração de α, sendo como α = βγ para β, γ ∈ Z[i]. Aplicando a função Norma, temos que N(α) = N(β)N(γ), entãoN(β)N(γ) = p. Como p é primo temos duas possibilidades: ouN(β) = 1 e N(γ) = p ou N(β) = p e N(γ) = 1. Podemos observar que β é uma unidade e γ é um associado de α ou β é um associado de α e γ é uma unidade e, portanto, α possui apenas divisores triviais, ou seja, α é primo. Exemplo 2.51. 5 + 2i é primo em Z[i], pois N(5 + 2i) = 52 + 22 = 25 + 4 = 29 e 29 é primo em Z. Lema 2.52. Seja π um primo em Z[i] e αβ ∈ Z[i]. Se π | αβ, então π | α ou π | β. Demonstração. Suponha que π - α. Então mdc(α, π) é uma unidade, isso significa que α e π são primos entre si. Sendo assim, podemos escrevê-los como uma combinação linear, αx+πu = 1. Multiplicando por β, temos que βαx+βπy = β. Como π | αβ e π | π, temos que π | (βαx+ βπy) e, portanto, π | β. Lema 2.53. α é primo em Z[i] se, e somente se, seu conjugado α é primo em Z[i]. Demonstração. Suponha que α não é primo em Z[i]. Então α = γβ, onde γ, β ∈ Z[i] são divisores não triviais de α. Por conjugação, temos α = γβ = γβ e portanto α tem uma fatoração de números não triviais, ou seja, α não é primo em Z[i]. Reciprocamente, suponha que α não é primo em Z[i]. Então α = γβ, onde γ e β são divisores não triviais de α. Aplicando a conjugação complexa na igualdade anterior temos: α = γβ α = γβ α = γβ, com γ, β ∈ Z[i] divisores não triviais de α. Portanto α não é primo em Z[i]. Os Inteiros Gaussianos 60 Lema 2.54. Se α = a+ bi com a · b 6= 0 é primo em Z[i], então N(α) = a2 + b2 é primo em Z. Demonstração. Note que N(α) = a2 + b2 = (a+ bi)(a− bi) é um múltiplo de α. Suponha que N(α) = a2 + b2 não é primo em Z, ou seja, N(α) = (a+ bi)(a− bi) = a2 + b2 = m · n, com m,n ≥ 2. Por hipótese, α = a + bi é primo em Z[i] e como α | m · n, segue do Lema 2.52 que α | m ou α | n. Se α | m então m = γ · α, para algum γ ∈ Z[i], ou seja, m não pode ser associado a α. Logo, multiplicando por n temos m · n = γ · α · n = (a+ bi)(a− bi) γ · n = (a− bi). Como n não é uma unidade, então a− bi não é primo em Z[i], o que é um absurdo. Exemplo 2.55. 2 + i é primo em Z[i] e N(2 + i) = 22 + 12 = 4 + 1 = 5 é primo em Z. Lema 2.56. Seja α = a + bi ∈ Z[i] com a · b 6= 0. Então α = a + bi é primo em Z[i] se, e somente se, a2 + b2 = p é um número primo em Z com p ≡ 1(mod 4) ou p = 2. Demonstração. (⇒) Suponha que α = a+ bi é primo em Z[i]. Usando a aritmética módulo 4 vamos calcular a soma de a2 + b2 módulo 4: 02 ≡ 0( mod 4), 12 ≡ 1( mod 4), 22 ≡ 0( mod 4) e 32 ≡ 1( mod 4). Logo, um quadrado módulo 4 é igual a 0 ou 1, e sua soma módulo 4 é 0, 1 ou 2, ou seja, p ≡ 0( mod 4), p ≡ 1( mod 4) ou p ≡ 2( mod 4). Se p ≡ 0( mod 4), então 4 | p, logo p não é primo. Pelo Lema 2.54, p = a2 + b2 ≡ 1( mod 4) ou p = a2 + b2 ≡ 2( mod 4) e o único primo p, p ≡ 2( mod 4) é p = 2. (⇐) Suponha que a2 + b2 = p é um número primo e que α = a + bi não é primo, ou seja, a+ bi = γ · β, para algum γ, β ∈ Z[i]. Então, N(a+ bi) = N(γ · β) a2 + b2 = N(γ)N(β) p = N(γ)N(β). Como p é primo, então N(γ) = 1 ou N(β) = 1. Logo γ ou β é uma unidade, o que é um absurdo. Portanto α = a+ bi é primo. Exemplo 2.57. 2+5i é primo em Z[i], poisN(2+5i) = 22+52 = 4+25 = 29 e 29 ≡ 1(mod 4). Os Inteiros Gaussianos 61 Observação 2.58. 1. Qualquer número que é ≡ 3 (mod 4) não é a soma de dois quadra- dos em Z. De fato, os quadrados módulo 4 são 0 e 1. Fazendo a soma entre eles e a congruência módulo 4 temos: 0 + 0 = 0 ≡ 0 (mod 4), 1 + 0 = 0 + 1 = 1 ≡ (mod 4) e 1 + 1 = 2 ≡ 2 (mod 4). 2. Se a + bi é um primo em Z[i] com a2 + b2 = p = 2, então a + bi é um dos quatro elementos: • Se a = 1 e b = 1, então α = 1 + i; • Se a = 1 e b = −1, então α = 1− i; • Se a = −1 e b = 1, então α = −1 + i; • Se a = −1 e b = −1, então α = −1− i; 3. Considerando elementos da forma a ou bi em Z[i], podemos ver bi como um associado de b, pois b = −i(bi). Agora os elementos da forma a + 0i estão em Z[i]. Note que, se n é um inteiro composto em Z, então n é um inteiro composto em Z[i], pois para n = r · s como r, s > 1 em Z, temos n = r · s = (r + 0i)(s+ 0i) ∈ Z[i]. Lema 2.59. Se p é primo em Z com p ≡ 3(mod 4), então p também é primo em Z[i]. Demonstração. Suponha que p não é primo em Z[i]. Então p = αβ, onde nem α e nem β são unidades em Z[i]. Logo, N(p) = N(αβ) = N(α)N(β) p2 = N(α)N(β). Como N(α) > 1 e N(β) > 1, temos que N(α) = N(β) = p. Mas, N(α) = N(β) é a soma de dois quadrados e a soma de dois quadrados nunca pode ser congruente a 3 módulo 4 (Observação 2.58, item 1)). Portanto, a hipótese de p não ser primo em Z[i] é falsa, logo p é primo em Z[i]. Exemplo 2.60. 5 não é primo em Z[i] já que não é congruente a 3 módulo 4. Mas 7 é primo em Z[i], pois 7 ≡ 3(mod 4). Lema 2.61. Seja p um primo em Z. Se p ≡ 1(mod 4), então a congruência x2 ≡ −1(mod p) tem solução. Demonstração. Considere p 6= 2 e o polinômio T p−1 − 1 = (T p−1 2 − 1)(T p−1 2 + 1) módulo p. Os Inteiros Gaussianos 62 Vamos contar as raízes desses polinômios módulo p. Sabemos que um polinômio de grau d não tem mais que d raízes módulo p. Assim, • T p−1 − 1, tem p− 1 raízes diferentes módulo p • T p−1 2 − 1, tem p−1 2 raízes diferentes módulo p. Portanto, T p−1 2 + 1 tem que ter raízes módulo p, ou seja, deve existir algum inteiro C tal que C p−1 2 + 1 ≡ 0(mod p), isto é, C p−1 2 ≡ −1(mod p). Como p ≡ 1(mod 4), então p− 1 2 = 2k é par. Portanto, (Ck)2 ≡ −1(mod p), ou seja, x2 ≡ −1(mod p) tem solução. Lema 2.62. Se p é um primo em Z com p ≡ 1(mod 4), então p não é primo em Z[i], mas tem uma fatoração em primos da forma p = (a+ bi)(a− bi). Demonstração. Suponha que p é primo em Z[i]. Pelo Lema 2.61, existe ` ∈ Z tal que p | `2 + 1. Agora, considere esta divisibilidade em Z[i]. Note que `2 + 1 = (` + i)(` − i), assim p | `2 + 1 = (`+ i)(`− i) e temos, pelo Lema 2.61, que p | `+ i ou p | `− i. Portanto, algum m+ni ∈ Z[i] satisfaz `± i = p(m+ni). Olhando para a parte imaginária temos que pn = ±1, o que é um absurdo pois p é primo em Z. Portanto, p não é primo em Z[i]. Assim, existem fatores não triviais α, β ∈ Z[i] tais que p = αβ. Aplicando a norma em ambos os membros dessas equação, temos N(p) = N(α)N(β) ⇒ p2 = N(α)N(β). Portanto, N(α) = N(β) = p. Escrevendo α = a+ bi temos que p = a2 + b2 = (a+ bi)(a− bi). Exemplo 2.63. 5 é primo em Z e 5 ≡ 1 (mod 4), então 5 = (2 + i)(2− i). Exemplo 2.64. 17 é primo em Z e 17 ≡ 1(mod 4), então 17 = (4 + i)(4− i). O resultados dos lemas anteriores fornecem a demonstração do seguinte teorema: Teorema 2.65. Os elementos primos em Z[i] são os seguintes: 1. associados dos inteiros da forma p+ 0i, onde p é primo com p ≡ 3(mod 4); 2. associados de 1 + i e 1− i; e 3. elementos a+ bi tais que N(a+ bi) = a2 + b2 = p um número primo com p ≡ 1(mod 4). Demonstração. 1. Segue do Lema 2.59; Os Inteiros Gaussianos 63 2. Segue da Observação 2.58(2); e 3. Segue dos Lemas 2.54, 2.56, 2.61 e 2.62. Lema 2.66. Seja π ∈ Z[i]. Se α1, α2, · · · , αr ∈ Z[i], com π | α1α2 · · ·αr, então π | αj, com 1 ≤ j ≤ r e r ∈ N. Demonstração. Faremos a verificação para r = 2, visto que para r > 2 é um processo simples de indução. Suponha que π | α1α2, mas π - α1. Logo, π e α1 são primos entre si. Pelo Corolário 2.45, segue que π | α2. Teorema 2.67. (Fatoração Única) Qualquer α ∈ Z[i], com N(α) > 1, tem uma fatoração de primos. Essa fatoração é única a menos da ordem dos fatores e associados. Demonstração. A primeira parte da demonstração será feita por indução emN(α). Suponha que N(α) = 2, então α é um primo em Z[i], pelo Teorema 2.50. Agora, vamos supor que n ≥ 2 e que se β ∈ Z[i] tal que 1 < N(β) < n então β é um produto de números primos em Z[i]. Vamos supor que há inteiros gaussianos com norma n. Se temos um número inteiro de Gauss α com norma n, que é composto, então podemos escrever α = βγ. Aplicando a norma, temos N(α) = N(β)N(γ), onde N(β) < N(α) = n. Por hipótese indutiva, β e γ são produtos de primos em Z[i]. Portanto, α também é um produto de primos em Z[i]. Para provar a unicidade também vamos usar indução sobre n. ParaN(α) = 2 basta tomar α = ±1 ± i que são primos em Z[i]. Agora, suponha que n ≥ 3 e que 1 < N(α) < n com α tendo uma fatoração única. Podemos supor que há inteiros gaussianos com a norma n. Considere duas fatorações de primos de α: α = π1π2 · · · πr = π ′ 1π ′ 2 · · · π ′ s. Como π1 | α, podemos escrever π1 | π ′ 1π ′ 2 · · · π ′ s. Pelo Lema 2.66, segue que π1 | π ′ j , para algum j = 1, · · · s. Podemos supor que j = 1, ou seja, π1 | π ′ 1. Logo, π′1 = π1 ·w, para algum w ∈ Z[i]. Consequentemente, π1 = uπ ′ 1 para alguma unidade u ∈ {±1,±i}. Substituindo a última igualdade na fatoração de α temos: α = uπ ′ 1π2 · · · πr = π ′ 1π ′ 2 · · · π ′ s. (2.16) Cancelando π′1 em ambos os lados, temos: uπ2 · · · πr = π ′ 2 · · · π ′ s. Os Inteiros Gaussianos 64 Considerando β = π ′ 2 · · · π ′ s, então N(β) = N(α) N(π ′ 1) < N(α). Embora u seja uma unidade, o produto uπ2 no lado esquerdo de (2.16) é um primo, e portanto (2.16) têm duas fatorações de primos de β, com (r − 1) primos do lado esquerdo e (s − 1) primos do lado direito. Como N(β) < n, a hipótese de indução diz que β tem uma fatoração única, então (r − 1) = (s − 1), o que implica r = s. Após nova rotulagem apropriada, temos que uπ2 e π′2 são múltiplos unitários e πi, π ′ i são múltiplos unitários para i > 2. Como uπ2 e π′2 são múltiplos unitários, segue que π2 e π′2 são múltiplos unitários. Assim, vemos todo πi como um múltiplo unitário de π′i, o que conclui a demonstração. Exemplo 2.68. Vamos fatorar 3 − 4i. Sabemos que N(3 − 4i) = 25 = 5 · 5. Já que 5 é a norma de um fator não trivial de 3− 4i, podemos escrever 5 = (2 + i)(2− i). Considerando α = 2 + i e β = 2− i, temos as seguintes possibilidades: 1. α · α = (2 + i)(2 + i) = 3 + 4i; 2. α · β = (2 + i)(2− i) = 5; 3. β · β = (2− i)(2− i) = 3− 4i. Portanto, a fatoração de 3− 4i é (2− i)2. Exemplo 2.69. Verifiquemos se 1− 3i é primo. Podemos verificar calculando N(1− 3i) = 10. Como a norma de 1− 3i é par, nos indica que um dos fatores de 1 − 3i é 1 + i (Corolário 2.27). Ao fatorarmos N(1 − 3i) = 2 · 5, temos que N(1 + i) = 2. Para que N(α) = 5, α = ±1 ± 2i ou α = ±2 ± i. Fazendo as possíveis combinações de 1 + i e α, encontramos: • (1 + i)(1 + 2i) = −1 + 3i; • (1 + i)(1− 2i) = 3− i; • (1 + i)(−1 + 2i) = −3 + i; • (1 + i)(−1− 2i) = 1− 3i; • (1 + i)(2 + i) = 1 + 3i; • (1 + i)(2− i) = 3 + i; • (1 + i)(−2 + i) = −3− i; • (1 + i)(−2− i) = −1− 3i. Portanto, 1− 3i não é primo e sua fatoração é (1 + i)(−1− 2i). Os Inteiros Gaussianos 65 Exemplo 2.70. Vamos determinar a fatoração de 3 + 5i. Sua norma é 34, cuja fatoração em Z é 2 · 17. Já sabemos pelo Corolário 2.27 que um dos fatores de 3 + 5i é 1 + i. Vamos observar os inteiros gaussianos com norma 17, em seguida iremos multiplicá-los por 1 + i para obtermos 3 + 5i. Representando 17 como a soma de dois quadrados, temos: 17 = 42 + 12 = 12 + 42. Logo, podemos fatorar em primos gaussianos: 17 = (4 + i)(4− i) ou 17 = (1 + 4i)(1− 4i). Os inteiros gaussianos são primos, pois suas normas são primos em Z. Então temos as seguintes combinações: • (1 + i)(4 + i) = 3 + 5i; • (1 + i)(4− i) = 5 + 3i; • (1 + i)(1 + 4i) = −3 + 5i; • (1 + i)(1− 4i) = 5− 3i. Portanto, a fatoração de 3 + 5i é (1 + i)(4 + i). 2.2.9 Aritmética Modular em Z[i] Similar ao que acontece em Z, abordaremos aqui a aritmética modular em Z[i] e suas propriedades. Definição 2.71. Sejam α, β e γ inteiros gaussianos. Dizemos que α é congruente a β módulo γ, indicado por α ≡ β (mod γ), quando γ | (α − β). ou seja, α − β = γδ, para algum δ ∈ Z[i]. Exemplo 2.72. Vamos verificar que (16 + 8i) ≡ (3− i) mod (7 + i). Pela definição de congruência temos que (7 + i) | (16 + 8i)− (3− i) se existe δ ∈ Z[i] tal que (16 + 8i)− (3− i) = (7 + i)δ. De fato, (16 + 8i)− (3− i) (7 + i) = δ (13 + 9i) (7 + i) · (7− i) (7− i) = δ 100 + 50i 50 = δ 2 + i = δ. Como 2 + i ∈ Z[i], segue que (16 + 8i) ≡ (3− i) mod (7 + i). Os Inteiros Gaussianos 66 Assim como nos inteiros, as propriedades da soma e da multiplicação são válidas na congruência para inteiros gaussianos. Proposição 2.73. Sejam α, α ′ , β e β ′ em Z[i]. Se α ≡ α ′ (mod γ) e β ≡ β ′ (mod γ), então: 1. α + β = α ′ + β ′ (mod γ) 2. αβ = α ′ β ′ (mod γ) Demonstração. i) Pela definição de congruência, existem δ1 e δ2 em Z[i] tais que α − α′ = δ1γ e β − β ′ = δ2γ. Somando as equações membro a membro, temos: α− α′ + β − β ′ = δ1γ + δ2γ (α + β)− (α ′ + β ′ ) = γ(δ1 + δ2), o que implica que γ | (α + β)− (α ′ + β ′ ) e portanto α + β = α ′ + β ′ (mod γ). ii) Multiplicando a primeira equação do item (i) por β e a segunda do item (i) por α′ , obtemos: β(α− α′) = β(δ1γ) e α′(β − β ′) = α ′ (δ2γ). Em seguida, somando membro a membro, temos: β(α− α′) + α ′ (β − β ′) = β(δ1γ) + α ′ (δ2γ) βα− βα′ + α ′ β − α′β ′ = βδ1γ + α ′ δ2γ αβ − α′β ′ = γ(βδ1 + α ′ δ2) e portanto, γ | αβ−α′β ′ , o que implica pela definição de congruência que αβ = α ′ β ′ (mod γ). Vejamos um exemplo aplicando o item 1. da Proposição 2.73. Exemplo 2.74. Sejam (6+16i) ≡ (−10+8i)mod (3−i) e (−1+12i) ≡ (−2−i)mod (3−i). Somando as congruências, obtemos (5 + 28i) ≡ (−12 + 7i) mod (3− i). O que é verdade, pois: (5 + 28i)− (−12 + 7i) (3− i) = (17 + 21i) (3− i) ·(3 + i) (3 + i) = 51 + 17i+ 63i− 21 10 = 30 + 80i 10 = 3+8i e 3 + 8i ∈ Z[i]. Proposição 2.75. Sejam α, β, γ e δ ∈ Z[i]. Então, 1. Reflexiva: α ≡ α (mod γ); Os Inteiros Gaussianos 67 2. Simétrica: se α ≡ β (mod γ), então β ≡ α (mod γ); 3. Transitiva: se α ≡ β (mod γ) e β ≡ δ (mod γ), então α ≡ δ (mod γ). Demonstração. i) Temos que α − α = 0 e 0 é divisível por γ, ou seja, γ | 0, o que implica que γ | α− α. Logo pela definição de congruência, α ≡ α (mod γ). ii) Como γ | (α − β) por hipótese, segue que existe k em Z[i] tal que α − β = γk. Multiplicando a equação por −1 encontramos β − α = γ(−k), logo γ | (β − α) e pela definição de congruência, β ≡ α (mod γ). iii) Por hipótese γ | (α − β) e γ | (β − δ). Logo existem k1 e k2 em Z[i] tais que α− β = γk1 e β − δ = γk2. Somando membro a membro as equações temos que α− β + β − δ = γk1 + γk2 α− δ = γ(k1 + k2), ou seja, γ | α− δ e pela definição de congruência, α ≡ δ (mod γ). Assim, a congruência modular em Z[i] é uma relação de equivalência. Teorema 2.76. Sejam a, b e n em Z. Então a ≡ b (mod n) em Z, se e somente se, a ≡ b (mod n) em Z[i]. Demonstração. Pela definição de congruência, a ≡ b (mod n) equivale a n | (a−b) em Z, o que implica que n | (a−b) em Z[i]. Por outro lado, pelo Teorema 2.23, se n | (a−b) em Z[i] implica que n | (a− b) em Z, pois a divisibilidade dos inteiros não muda quando se trabalha em Z[i]. Portanto, a ≡ b (mod n) em Z se e somente se, a ≡ b (mod n) em Z[i]. Para permitir que a extensão do algoritmo RSA funcione, precisamos do valor da função de Euler φ de um número n em Z[i], composto pelo produto de dois primos p e q em Z[i]. O teorema a seguir fornece tal valor, no entanto, sua demonstração requer vários resultados sobre classes residuais e que não abordamos aqui, tendo em vista que o foco deste trabalho não é fazer um estudo detalhado dos inteiros gaussianos. Para detalhes desta teoria o leitor pode consultar as referências [10, 11]. Teorema 2.77. Sejam p e q em Z[i] primos. Então a função φ de Euler de n = pq é: φ(n) = φ(p)φ(q) = (N(p)− 1)(N(q)− 1). 3 Criptografia RSA O algoritmo RSA foi inventado em 1977 por Rivest, Samir e Adleman. É um dos mais conhecidos e usados sistema de criptografia de chave pública, que fornece segurança em toda rede. Foi criado a partir de funções matemáticas em Z. Seu sistema baseia-se não somente na segurança de sua chave privada, mas também na sua difícil fatoração. Recentemente alguns estudos, como o de Stillwell (2003), com o objetivo de encontrar um sistema mais seguro e eficiente, provaram que é possível a extensão desse algoritmo para o domínio de números inteiros gaussianos Z[i], a qual será apresentada no Capítulo 4. RSA é um algoritmo de criptografia de dados do tipo assimétrico, ou seja, possui uma chave pública em que todos os envolvidos tem acesso e uma chave privada. A primeira é a responsável pela codificação dos dados e deve possuir funções de difícil inversão, uma vez que é isso que garante o sigilo das informações. Para entendermos o método, precisamos analisar cada item, desde a pré-codificação até a decriptação e segurança do método. Come- çamos a seguir contando um pouco sobre sua história. As principais referências utilizadas para o desenvolvimento deste capítulo foram [1, 5]. 3.1 Um Pouco sobre a História A palavra criptografia vem do grego “kriptos” e significa oculto. Enviar e receber men- sagens ocultas sem que elas fossem interceptadas por terceiros são desejos e anseios que datam desde a muito tempo, tendo registros desde 1900 a.C. no Egito. O primeiro exemplo de um código secreto de que se tem notícia foi usado por César para comunicar-se com as le- giões em combate pela Europa. Sistemas de criptografia sempre foram utilizados no campo militar. Durante os períodos de guerra a criptografia foi muito utilizada e se desenvolveu, segundo registros históricos. Enigma, a máquina desenvolvida pelos nazistas durante a Se- gunda Guerra Mundial é um dos melhores códigos já conhecido. A detecção da chave e a quebra do código pelos aliados foi um dos pontos cruciais que marcaram o fim da guerra e a vitória das forças aliadas. Atualmente, com a chegada da Internet e de todas as suas tecnologias de suporte que 68 Pré-Codificação 69 utilizam redes, a codificação de mensagens se tornou essencial. Manter o sigilo no envio de e-mails, conversas on-line, transações bancárias, entre outros, é fundamental no nosso mundo digital. Com o surgimento da criptografia nasce também a criptoanálise, que tem como objetivo decriptar