31
Números Inteiros e Criptografia RSA S. C. Coutinho Universidade Federal do Rio de Janeiro i

Equação de Pell

Embed Size (px)

DESCRIPTION

equação de pell

Citation preview

  • Nmeros Inteiros e Criptografia RSA

    S. C. CoutinhoUniversidade Federal do Rio de Janeiro

    i

  • ii

    c by S. C. Coutinho 2014

  • Sumrio

    Agradecimentos v

    Captulo 1. Equao de Pell 11. Compondo solues 12. Grupos 63. Achando solues 114. Anlise do algoritmo de Brouncker 165. Estrutura do grupo P(d) 21Exerccios 21

    Referncias Bibliogrficas 25

    iii

  • Agradecimentos

    Muito obrigado a Gabriel da Silva Alves, Flvio Rangel, Leonardo Barrozo pelas cor-rees e sugestes.

    v

  • CAPTULO 1

    Equao de Pell

    Neste captulo estudaremos a equao de Pell. Como vimos na seo ?? da introduo,esta equao diofantina vem sendo investigada desde a antiguidade e existe uma teoriabastante desenvolvida acerca das suas solues. Comearemos considerando o mtodoutilizado pelos matemticos indianos para gerar novas solues, a partir de outras duasj conhecidas. Na seo seguinte, veremos que este mtodo pode ser interpretado comouma operao no conjunto das solues da equao de Pell, o que nos levar definio degrupo abeliano e ao estudo de algumas de suas propriedades mais elementares. Finalmente,nas duas ltimas sees, descrevemos um algoritmo capaz de achar uma soluo de umaequao de Pell e provamos que sempre para e que funciona corretamente.

    1. Compondo solues

    Como vimos na introduo, a equao de Pell a equao diofantina

    x2 dy2 = 1em que d um nmero inteiro. Se x0 e y0 so nmeros inteiros tais que

    x20 dy20 = 1;dizemos que o par (x0; y0) uma soluo de x2 dy2 = 1. Como as variveis x e yaparecem ambas ao quadrado na equao, sempre que o par (x0; y0) uma soluo dex2 dy2 = 1, o mesmo vale para(1) (x0; y0); (x0;y0); e (x0;y0):Observe, tambm, que, no importa qual seja o valor de d, a equao de Pell sempre temos pares (1; 0) como solues. Estas so as chamadas solues triviais e so as nicassolues possveis quando d um inteiro negativo menor que 1. J no caso em qued = 1, a equao tem outras duas solues, a saber (0;1). Uma verso devidamentedecupada da demonstrao destes fatos pode ser encontrada nos exerccios 3 e 4.

    Um caso mais interessante aquele em que d um quadrado perfeito. Digamos qued = r2, para algum inteiro positivo r. Ento,

    1 = x2 dy2 = x2 r2y2 = x2 (ry)2 = (x ry)(x+ ry):1

  • 2 1. EQUAO DE PELL

    Mas o produto dos nmero inteiros xry e x+ry s pode ser igual a 1 se ambos os termosforem iguais a 1, ou ambos forem iguais a 1. Obtemos, assim, os sistemas lineares

    x ry = 1 x ry = 1x+ ry = 1 x+ ry = 1;

    cujas solues so, respectivamente, (1; 0) e (1; 0). Portanto, tambm neste caso a equa-o tem apenas as solues triviais. Mais detalhes podem ser encontrados no exerccio5.

    Levando em conta as consideraes dos dois ltimos pargrafos, h apenas um caso emque ainda no sabemos resolver a equao de Pell: aquele em que d um inteiro positivo,mas no um quadrado perfeito. Mesmo neste caso, no difcil advinhar solues paraa equao quando d pequeno. Por exemplo, o par (2; 1) claramente uma soluo parax2 3y2 = 1. Uma soluo no trivial para x2 2y2 = 1 no to bvia mas, depoisde algumas tentativas, verificamos que o par (3; 2) uma tal soluo. Com um pouco depacincia, os casos em que d = 5, 6, 7, 8 e 11 podem ser resolvidos da mesma maneira. Jd = 13 bem mais complicado, porque a soluo cujas entradas so as menores possveis,em valor absoluto, (649; 180).

    Como os matemticos indianos do sculo VII j sabiam, possvel obter infinitas solu-es de uma dada equao de Pell a partir de qualquer soluo no trivial. Para isto usavama frmula de Brahmagupta

    (2) (xu+ dyv)2 d(xv + yu)2 = (x2 dy2)(u2 dv2);que j consideramos na introduo. Se x1, y1, x2 e y2 forem inteiros que satisfazem

    x21 dy21 = x22 dy22 = 1;ento, por (2),

    (x1x2 + dy1y2)2 d(x1y2 + y1x2)2 = 1:

    Em outras palavras, se (x1; y1) e (x2; y2) so solues da equao de Pell x2 dy2 = 1,ento

    (3) (x1x2 + dy1y2; x1y2 + y1x2)

    tambm soluo da mesma equao.

    Por exemplo, como os pares (2; 1) e (1; 0) so solues de x2 3y2 = 1, entopodemos combin-los usando a frmula (3), obtendo assim que o par (2;1) tambm soluo da mesma equao. Mas isto, convenhamos, no muito interessante porquej sabamos que (2;1) so todas elas solues de x2 3y2 = 1. Combinar (2; 1) e(1; 0) ainda menos interessante, porque o resultado o prprio par (2; 1). Antes quevoc comece a pensar que a frmula (3) no , afinal, to til, convm lembrar que h umapossibilidade que ainda no exploramos: aquela que consiste em combinar (2; 1) com elemesmo. Fazendo isto, obtemos o par (7; 4), que uma soluo genuinamente diferente

  • 1. COMPONDO SOLUES 3

    de todas as anteriores. Isto sugere duas novas possibilidades. A primeira consiste emcombinar (7; 4) com ele mesmo, donde resulta o par (97; 56); j na segunda, combinamos(2; 1) com (7; 4), obtendo (26; 15).

    Como voc deve ter notado, seria mais conveniente se tivssemos uma maneira maiscompacta de expressar as aplicaes da frmula (3) do que a utilizada no pargrafo ante-rior. O ideal seria uma notao que nos informasse, de maneira clara e direta, quais so ospares que esto sendo combinados e qual o par resultante da aplicao da frmula. Natu-ralmente, h vrias maneiras possveis de fazer isto. A que utilizaremos ter consequnciassignificativas em nosso estudo da equao de Pell.

    Para comear, dado um inteiro d, definimos o conjunto soluo da equao de Pellx2 dy2 = 1 como sendo o conjunto de todos os pares de inteiros (x; y) que satisfazemaquela equao. Denotando este conjunto por P(d), podemos escrever

    P(d) = f(x; y) 2 Z Z j x2 dy2 = 1g:Lembre-se que os elementos do produto cartesiano A B entre dois conjuntos A e B soos pares (a; b) em que a 2 A e b 2 B. No caso acima, estamos listando apenas os paresque satisfazem a condio imposta pela equao de Pell. A propsito, j sabemos que P(d)nunca vazio, porque (1; 0) 2 P(d), qualquer que seja o inteiro d.

    Tendo introduzido P(d), podemos interpretar a identidade (2) como uma maneira decombinar dois elementos de P(d) de modo a obter um novo elemento de P(d). Usandoa terminologia usual, o que fizemos foi definir uma operao no conjunto P(d), para aqual usaremos a notao . Assim, dadas duas solues 1 = (x1; y1) e 2 = (x2; y2) daequao de Pell x2 dy2 = 1, definimos(4) 1 2 = (x1x2 + dy1y2; x1y2 + y1x2):A identidade (2) nos garante que, como 1; 2 2 P(n) ento 1 2 2 P(d). Usandoesta notao, os clculos com solues de x2 3y2 = 1 que fizemos no incio desta seopodem ser resumidos da seguinte forma:

    (2; 1) (1; 0) = (2;1) (7; 4) (7; 4) = (97; 56)(2; 1) (2; 1) = (7; 4) (2; 1) (7; 4) = (26; 15):

    Para falar a verdade, tambm vimos que

    (2; 1) (1; 0) = (2; 1)e as equaes acima sugerem outras combinaes que podemos tentar, como (1; 0)

    (2; 1) e (7; 4) (2; 1). Entretanto, se voc efetuar os clculos correspondentes, ver que atroca nas posies dos pares no afeta em nada o resultado.

    Estes ltimos comentrios escondem propriedades gerais da operao , que convmexplicitar para que possamos us-las livremente em nosso estudo das equaes de Pell. Aspropriedades so as seguintes. Em primeiro lugar, uma aplicao direta de (4) nos d

  • 4 1. EQUAO DE PELL

    se e = (1; 0) e um elementos qualquer de P(d), ento e = ;isto , o par (1; 0), que denotaremos a partir de agora por e, funciona como elementoneutro para a operao . Por outro lado, a comutatividade da soma e da multiplicao denmeros inteiros implica que

    quaisquer que sejam 1; 2 2 P(d) teremos 1 2 = 2 1;de modo que tambm comutativa. Uma outra propriedade, que no encontramosanteriormente, a seguinte: se = (x0; y0) 2 P(d), ento = (x0;y0) satisfaz(5) = (x0; y0) (x0;y0) = (1; 0);de modo que , que tambm pertence a P(d), funciona como uma espcie de inverso de .

    Apesar das propriedades que j identificamos simplificarem em muito nossos clculoscom solues de uma equao de Pell, ainda deixam problemas bastante simples sem so-luo. Por exemplo, dado 2 P(d), podemos definir seu quadrado 2 como sendo e seu cubo 3 como sendo

    2 ou 2 ;j que so iguais pela propriedade comutativa. Mas como definir 4? A primeira impresso que a resposta bvia; basta tomar

    3 = 3 :Entretanto, neste caso, tambm poderamos definir 4 como 2 2, que no sabemos se ou no igual a 3. Verificamos, assim, que, embora a comutatividade de bastapara podermos definir o cubo de uma soluo sem ambiguidade, o mesmo no se d coma quarta potncia. Para podermos lidar com ela, precisamos mostrar que

    1 (23) = (12)3, quaisquer que sejam 1; 2; 3 2 P(d).Esta propriedade, conhecida como associativa, nos d a garantia de que, no importa comoagrupemos os termos de um produto em uma multiplicao, o resultado sempre ser omesmo. De todas as propriedades bsicas da operao que definimos em P(d) esta amais complicada de provar, porque os clculos so longos e requerem ateno; mas no sodifceis, razo por que vamos deix-los por sua conta. Para confirmar que a associatividadeera o ingrediente que faltava para eliminar a ambiguidade na definio da quarta potncia,verificaremos que se 2 P(d) ento

    3 = 2 2:Comeamos observando que

    3 = ( 2);pois 3 = 2. Mas, pela associatividade,

    ( 2) = ( ) 2;

  • 1. COMPONDO SOLUES 5

    que igual a 2 2, como desejvamos mostrar.No podemos encerrar esta questo sem mostrar que a operao de multiplicao de

    solues de uma equao de Pell admite uma linda interpretao geomtrica. Em primeirolugar, o conjunto de todos os pontos com coordenadas reais que satisfazem a equaox2 dy2 = 1 uma hiprbole. Por exemplo, quando d = 2 a hiprbole correspondente ilustrada na figura 1.

    FIGURA 1. A hiprbole x2 2y2 = 1

    Para multiplicar duas solues P1 e P2 da equao de Pell x2 dy2 = 1 de maneirapuramente geomtrica comeamos determinando a reta r, paralela ao segmento que uneP1 a P2, e que passa pelo ponto e = (1; 0). Como a equao de Pell tem grau dois, estareta ter que intersectar a hiprbole em um segundo ponto, que ser o produto desejado;veja Exerccio 14. Queremos mostrar que esta construo produz o ponto P1 P2. Paraisto, suporemos que P1 = (x1; y1) e que P2 = (x2; y2). A reta que passa por P1 e P2 temcoeficiente angular

    (6) =y2 y1x2 x1 :

    Por outro lado, temos de (4) que a reta por e = (1; 0) e P1 P2 tem coeficiente angular

    =x1y2 + x2y1

    x1x2 + dy1y2 1 :

    Para que estas duas retas sejam paralelas, necessrio que = , que equivale a dizer que

    (x1y2 + x2y1)(x2 x1) = (x1x2 + dy1y2 1)(y2 y1):Contudo, um clculo simples mostra que

    (x1y2+x2y1)(x2x1)(x1x2+dy1y21)(y2y1) = dy1y22+dy21y2x21y2+y2+x22y1y1;que podemos reescrever na forma

    (7) y1(dy22 + x22 1) + y2(x21 + dy21 + 1):

  • 6 1. EQUAO DE PELL

    A

    FIGURA 2. A tangente no ponto A (linha cheia) como limite das secantes

    Entretanto, como P1 e P2 so, por hiptese, solues da equao de Pell x2 dy2 = 1,teremos que

    x21 dy21 = 1 e que x22 dy22 = 1donde segue, imediatamente, que a expresso (7) nula, confirmando, assim, que = ,como queramos mostrar.

    A despeito do que acabamos de provar, se tentarmos esboar a figura correspondenteao clculo do quadrado do ponto (2; 1) 2 P(3) vamos ter uma amarga surpresa. Afinal,para isso, teramos que aplicar a construo geomtrica com P1 = P2. Contudo, nestecaso, a frmula para o coeficiente angular dada em (6) no faz sentido. Por sorte podemoscontornar isto de maneira bastante simples, porque medida que o ponto P2 se aproximado ponto P1, a secante vai se aproximando cada vez mais da tangente, como ilustra a figura2. Isto sugere que a soluo do problema est em substituir, na construo geomtrica, asecante atravs de P1 e P2, pela tangente em P1. Entretanto, isto requer que determinemosa inclinaom, em um dado ponto P , da tangente hiprbole x2 dy2 = 1. Se voc sabeum pouco de clculo diferencial, no ter dificuldade em verificar que se y0 6= 0, entom = x0=dy0; se no sabe, encontrar um roteiro de como provar isto no exerccio 14. Afigura 3 ilustra a representao geomtrica do clculo do quadrado de (2; 1) em P(3).

    2. Grupos

    Vimos na seo anterior que, dada uma equao de Pell, possvel definir uma opera-o no conjunto das suas solues. Alm disso, esta operao satisfaz vrias das propri-edades que estamos acostumados a associar soma e multiplicao de nmeros, sejameles inteiros, reais ou complexos. A frequncia com que uma operao definida em umdado conjunto satisfaz estas propriedades tanta que os matemticos usam o termo grupopara indicar sua presena.

    Um grupo constitudo de dois ingredientes bsicos: um conjunto e uma operaodefinida neste conjunto. Vamos chamar o conjunto de G e a operao de ?. Por operao

  • 2. GRUPOS 7

    eBC

    FIGURA 3. C = (7; 4) o quadrado do ponto B = (2; 1)

    estamos entendendo uma regra que a cada dois elementos a; b 2 G associa um terceiroelemento a ? b que tambm est em G. As operaes mais conhecidas so, certamente, asoma, a subtrao e a multiplicao definidas nos conjuntos de nmeros inteiros, racionaise reais. Outros exemplos de operaes com os quais voc j deve ter se deparado so a somae o produto de matrizes e a soma de vetores do plano. Observe, contudo, que nem tudoque, em matemtica, chamamos de operao coberto pela definio acima. Por exemplo,o produto escalar de dois vetores do plano associa a um par de vetores um nmero, no umvetor; ao passo que, segundo nossa definio, a cada par de elementos de um conjunto, aoperao deve associar um elemento do mesmo conjunto. Para chamar a ateno para estefato, diremos que a operao de um grupo tem que ser fechada no sentido de que combinaelementos de um conjunto e retorna um outro elemento do mesmo conjunto. Com istoestamos prontos para a definio oficial de grupo.

    Um conjunto G no qual est definida uma operao ? um grupo se, quaisquer queforem os elementos a; b; c 2 G, a operao satisfaz as seguintes propriedades:

    fechamento: a ? b 2 G;associatividade: a ? (b ? c) = (a ? b) ? c;

    comutatividade: a ? b = b ? a;

    elemento neutro: existe e 2 G tal que a ? e = a;elemento inverso: dado a 2 G, existe a1 2 G tal que a ? a1 = e.

  • 8 1. EQUAO DE PELL

    Para ser honesto, a definio usual de grupo no inclui a comutatividade da operao. Umgrupo cuja operao comutativa, como ser o caso de todos os exemplos neste livro, conhecido como grupo abeliano. Contudo, dado que s estamos interessados em gruposabelianos, podemos omitir o adjetivo sem incorrer em nenhuma confuso, o que simplificanossa terminologia. Outra coisa: precisamos de um verbo que faa o papel da expressocombinar dois elementos do conjunto G pela operao ?. Como estrelar soa muitoestranho, usaremos multiplicar, a no ser quando a operao for a soma ou a subtrao,para as quais j existem os verbos somar e subtrair.

    Uma boa maneira de nos certificarmos de que entendemos um novo conceito bus-cando objetos matemticos que exemplifiquem este conceito, assim como objetos para osquais alguma das propriedades requeridas no satisfeita. Por exemplo, os nmeros intei-ros, racionais, reais e complexos so grupos relativamente operao de soma e o mesmovale para os vetores do plano e as matrizes 2 2. Por outro lado, os inteiros no cons-tituem um grupo relativamente subtrao, porque esta operao no associativa, nemcomutativa, nem tem elemento neutro; veja exerccio 15. Quando a operao a multipli-cao, nenhum dos conjuntos de nmeros mencionados acima um grupo, porque 0 notem inverso multiplicativo; isto , no existe nenhum nmero que multiplicado por 0 dcomo resultado 1. Embora, os nmeros racionais, reais e complexos no nulos formemum grupo para a multiplicao usual, o mesmo no se d com os inteiros, j que os nicosinteiros que admitem inversos multiplicativos so 1 e 1.

    A menos dos exemplos mencionados acima, e que voc j conhecia, mesmo sem saberque eram grupos, o nico outro grupo com o qual trabalharemos neste captulo o queintroduzimos na seo anterior; isto , o conjunto P(d) das solues inteiras da equaode Pell x2 dy2 = 1, com a operao definida pela frmula (4). Contudo, mais exemplospodem ser encontrados exerccios 16 e 17. Embora um grupo devesse sempre ser designadopelo par formado pelo conjunto e a operao, seguiremos a tradio de no mencionar aoperao quando ela estiver implcita no contexto. Por exemplo, como definimos apenasuma operao no conjunto das solues da equao de Pell x2dy2 = 1, vamos nos referira este grupo apenas como P(d), e no como (P(d);).

    Uma coisa que as propriedades das operaes de um grupo nos permitem fazer re-solver equaes simples. Por exemplo, se (G; ?) um grupo e a; b 2 G, podemos nosperguntar se existe um elemento x 2 G que satisfaa a equao(8) a ? x = b:

    Como todo elemento de um grupo tem inverso, tem que existir um elemento a1 2 G talque a1 ? a = e. Multiplicando a equao (8) por a1, obtemos

    a1 ? (a ? x) = a1 ? b:

    Levando em conta que ? associativa, a equao acima equivale a

    (a1 ? a) ? x = a1 ? b:

  • 2. GRUPOS 9

    Mas(a1 ? a) ? x = e ? x = x;

    de modo quex = a1 ? b:

    Mostramos, assim, que em qualquer grupo, toda equao da forma a ? x = b tem soluo,e que esta soluo sempre igual a a1 ? b. Por exemplo, para achar o elemento S 2 P(3)que satisfaz

    S (7; 4) = (2; 1);multiplicamos os dois lados da equao pelo inverso de (7; 4) que, pela equao (5) (7;4), obtendo

    S (7; 4) (7;4) = (2; 1) (7;4);de modo que

    S = (2; 1) (7;4) = (26; 15):

    H um outro tipo de problema que podemos resolver em um grupo e que especial-mente importante do ponto de vista da criptografia mas, antes de enunci-lo, precisamosdefinir potncias de um elemento em um grupo. Como vimos na seo anterior, a associati-vidade de uma operao garante que o resultado de um produto de elementos independenteda maneira como escolhemos agrup-los quando efetuamos o clculo. Isto nos permite de-finir a potncia de um dado elemento a, de um grupo (G; ?), por um expoente inteiropositivo k como

    ak = a ? ? a| {z }k vezes

    :

    Por exemplo, nossos clculos anteriores mostram que no grupo P(3),

    (2; 1)2 = (7; 4); (2; 1)3 = (26; 15) e (2; 1)4 = (97; 56):

    Segue diretamente desta definio e da associatividade da operao ? que, se k e ` sointeiros positivos, ento

    (9) ak ? a` = ak+` e (ak)` = ak`:

    Estas frmulas, por sua vez, sugerem que deveramos definir a0 como sendo o elementoneutro de G, que denotaremos por e. Para entender porqu, observe que tomando ` = 0 naprimeira das frmulas em (9), obtemos

    ak ? a0 = ak+0 = ak:

    Mas, multiplicando a equao acima pelo inverso de ak, conclumos que

    e ? a0 = e:

    Como e ? a0 = a0 pela definio do elemento neutro, temos que a0 = e, como havamosafirmado. Com isto estamos prontos para enunciar o problema mencionado no incio destepargrafo.

  • 10 1. EQUAO DE PELL

    PROBLEMA DO LOGARITMO DISCRETO. Dados a e b em um grupo G, existe alguminteiro k tal que bk = a?

    Talvez voc se surpreenda pelo uso da palavra logaritmo neste problema, mas a escolha bastante adequada. Afinal de contas, se a e b fossem nmeros reais, o nmero real k quesatisfaz bk = a seria o logaritmo de a na base b. Ao contrrio das equaes lineares, quesempre tm soluo qualquer que seja o grupo e os elementos a e b que escolhermos, oproblema do logaritmo discreto nem sempre tem soluo. Alm disso, e esta a parteimportante em criptografia, ainda que o problema tenha soluo, pode ser extremamentedifcil obt-la. A segurana do algoritmo de criptografia conhecido como El Gamal, porexemplo, baseia-se na dificuldade de resolver o problema do logaritmo discreto em certosgrupos; veja Exerccio ??? do captulo ???.

    A noo de potncia nos permite mostrar que P(3) um conjunto infinito. Para provaristo, analisaremos o que acontece quando comparamos as coordenadas de um dado parP = (a; b) com as do seu quadrado. Usando a frmula (4), verificamos que

    P 2 = (a2 + 3b2; 2ab):

    Mas, se a e b so ambos positivos, ento

    a < a2 + 3b2 e b < 2ab:

    Em outras palavras, as coordenadas de P 2 so ambas maiores que as respectivas coorde-nadas de P . Denotaremos isto escrevendo

    P < P 2:

    Note que esta desigualdade implica que as coordenadas de P 2 tambm tm que ser positi-vas, de forma que o mesmo argumento aplicado a P 2 garante que

    P 2 < P 4;

    e assim por diante. Em outras palavras, temos que se as coordenadas de P so positivas,ento a sequncia

    P < P 2 < P 4 < P 8 < < P 2k < tem que ser infinita, porque as coordenadas de qualquer um dos seus pares tm que sermaiores que as do seu antecessor. Logo, escolhendo P = (2; 1), obtemos uma sequnciainfinita de pares distintos em P(3), provando o que desejvamos. Se voc est familiari-zado com o princpio de induo finita, vai identificar esta demonstrao como uma apli-cao mal disfarada deste mtodo; caso contrrio, talvez voc queira reler este argumentodepois de estudar o captulo ??.

    Para completar nossa anlise da equao de Pell falta, apenas, descobrir como acharuma soluo de x2 dy2 = 1 no caso em que o inteiro positivo d no um quadrado per-feito. claro que podemos fazer isto na base da fora bruta. Por exemplo, incrementamosy de um em um, calculando o valor de

    p1 + dy2 correspondente. Teremos achado uma

  • 3. ACHANDO SOLUES 11

    soluo da equao quando encontrarmos um y para o qual x =p

    1 + dy2 nmero in-teiro. O problema deste algoritmo que s temos certeza de que funciona se j soubermosque toda equao de Pell para a qual d no quadrado perfeito sempre tem soluo comentradas positivas. Na prxima seo descreveremos um outro algoritmo, muito menosingnuo que a busca proposta acima, e que seremos capazes de provar que sempre para,retornando uma soluo da equao de Pell que lhe foi dada como entrada.

    3. Achando solues

    Nesta seo completamos nossa anlise da equao de Pell, descrevendo um algoritmoque, tendo como entrada um inteiro positivo d, que no um quadrado perfeito, retornauma soluo da equao de Pell x2 dy2 = 1. Na forma em que vamos apresent-loeste algoritmo foi descrito em uma carta de John Wallis, em que ele explica a soluode um problema proposto por Fermat. Segundo Wallis, o algoritmo teria sido descobertopor William Brouncker. Na verdade, uma verso do mesmo algoritmo, conhecido comomtodo cclico, era conhecida dos matemticos indianos desde o sculo XII, embora os ma-temticos europeus que estudaram a equao no tivessem conhecimento disto. Seguindoos passos de Wallis, vamos descrever nesta seo o mtodo cclico como idealizado porBrouncker e executar um exemplo passo a passo. No final da seo enunciamos o mtodona forma de um algoritmo, cuja demonstrao detalhada ser feita na prxima seo. Estealgoritmo ilustra um fato surpreendente, mas comum em matemtica: um problema maisgeral pode ser mais fcil de resolver que um de seus casos especiais.

    Digamos que d > 0 um inteiro positivo que no um quadrado perfeito e seja

    (10) x2 dy2 = 1a equao de Pell que queremos resolver. Diremos que uma soluo de (10) positiva sesuas coordenadas so inteiros maiores que zero. Se (u0; v0) uma soluo positiva destaequao, ento

    u20 = dv20 + 1 > v

    20;

    de modo que u0 > v0. Portanto, ao dividir u0 por v0, obteremos

    u0 = v0q + r em que r > 0:

    Substituindo esta expresso para u0 na equao (10) e expandindo o produto notvel, po-demos concluir que (v0; r) soluo da equao diofantina

    (q2 d)x2 + 2qxy + y2 = 1:Como v0, q e r so inteiros positivos, (v0; r) s pode ser soluo desta equao se d > q2.Por isso, vamos reescrev-la na forma

    (11) (d q2)x2 2qxy y2 = 1;

  • 12 1. EQUAO DE PELL

    j que isto faz com que o coeficiente do termo quadrtico em (11) seja positivo quandod > q2. O ponto crucial deste argumento que 0 r < v0 porque, se pudermos iteraro procedimento acima, obteremos equaes com solues em inteiros cada vez menores,reduzindo assim o problema a equaes cada vez mais fceis de resolver. Infelizmente,h um obstculo bvio implementao desta ideia: a substituio que usamos no trans-forma uma soluo da equao de Pell em uma outra soluo, com ordenada menor, damesma equao. Na verdade, (11) no nem mesmo uma equao de Pell. A sada con-siste em ampliar o escopo das equaes que estamos tentando resolver, de modo a incluirtanto (10), quanto (11).

    Seguindo nos passos de Brouncker, devemos considerar equaes da forma

    (12) Ax2 2Bxy Cy2 = 1;em que A, B e C so inteiros positivos. Se (u0; v0) for uma soluo desta equao e q er forem inteiros positivos tais que u0 = v0q + r ento, substituindo esta ltima expressoem (12), obtemos

    (13) (Aq2 2Bq C)y2 + 2(Aq B)ry + Ar2 = 1:Note que precisamos que q seja positivo, pois se q = 0, ento r = u0 e a substituio emnada alteraria a equao dada. Brouncker props escolher q como o maior inteiro para oqualAq22BqC < 0. Com isso o coeficiente de y2 em (13) necessariamente negativo.Assim, multiplicando (13) por 1 e tomando

    A1 = (Aq2 2Bq C); B1 = Aq B e C1 = Aobtemos a equao

    A1y2 2B1yr C1r2 = 1:

    Note a inverso do sinal do lado direito da equao. Como C1 = A > 0 por hiptese eA1 > 0 pela escolha de q, esta ltima equao ser da forma (12) desde que B1 tambmseja positivo. Como veremos a seguir, o mtodo de Brouncker consiste em iterar estaconstruo at obter uma equao para a qual seja fcil obter uma soluo. No melhorestilo da poca, nem Brouncker, nem Wallis, tentaram provar que este mtodo semprefunciona corretamente. Parecem ter ficado satisfeitos em verificar que tudo corria comoprevisto nos exemplos aos quais aplicaram o mtodo.

    Para podermos sistematizar o mtodo de Brouncker vamos introduzir a seguinte termi-nologia. Se F (x; y) = Ax2 2Bxy Cy2 e q o maior inteiro positivo tal que

    F (q; 1) = Aq2 2Bq C < 0;ento, chamaremos de transformada de F a forma

    F t(x; y) = A1x2 2B1xy C1y2;

    em que,

    (14) A1 = (Aq2 2Bq C); B1 = Aq B e C1 = A:

  • 3. ACHANDO SOLUES 13

    Os clculos acima tambm mostram que

    F (u0; v0) = F (qv0 + r; v0) = F t(v0; r) = F t(v0; u0 qv0):Portanto, se (u0; v0) for uma soluo de F (x; y) = 1, ento (v0; u0 qv0) uma soluode F t(x; y) = 1, em que, mais uma vez, temos a inverso do sinal no lado direito daequao.

    Para podermos esclarecer, de maneira mais precisa, o funcionamento do algoritmo deBrouncker, digamos que F0 = x2 dy2, de modo que a equao de Pell a ser resolvida F0 = 1. Denotaremos por Fi(x; y) a i-sima transformada de F0. Em outras palavras,

    F1 = (F0)t; F2 = (F1)

    t; F3 = (F2)t;

    e assim por diante. Como ser necessrio fazer substituies de variveis a cada passoexecutado pelo algoritmo, denotaremos por xi e yi as variveis da i-sima transformada.Em outras palavras,

    Fi = Fi(xi; yi) = Aix2i 2Bixiyi Cy2i ;

    em que estamos supondo, tacitamente, que Ai, Bi e Ci so inteiros positivos. Se qi for omaior inteiro positivo para o qual Fi(qi; 1) < 0 ento, fazendo a substituio

    (15) xi = qixi+1 + yi+1 e yi = xi+1;

    em Fi(xi; yi), obtemos a forma

    Fi(qixi+1 + yi+1; xi+1) = Fi+1(xi+1; xi+1):Esta troca de sinal, que ocorre cada vez que este passo executado, transforma a equaoF0(x0; y0) = 1 em

    Fi(xi; yi) = (1)i;ao final do i-simo passo. Portanto, se, em algum momento, obtivermos uma equaoFk(xk; yk) = (1)k que seja fcil de resolver, podemos usar as transformaes (15) vriasvezes para obter, a partir dela, uma soluo de F0(x0; y0) = 1.

    Na prtica h uma maneira bem mais eficiente de determinar (u0; v0), do que esperarque (uk; vk) tenha sido encontrado, e s ento usar (15) para achar (u0; v0). A ideia utilizar estas equaes para escrever P = (x0; y0) como funo de (xi; yi). Assim, ao caboda primeira iterao, teremos que

    P = (x0; y0) = (q1x1 + y1; x1):

    Substituindo, ento, os valores de x1 e y1 pelas expresses obtidas substituindo i = 1 em(15), obtemos

    P = (q1x1+y1; x1) = (q1(q2x2+y2)+x2; q2x2+y2) = ((q1q2+1)x2+ q1y2; q2x2+y2):

    Tomando i = 2 e procedendo da mesma maneira, obtemos

    P = (((q1q2 + 1)q3 + q1)x3 + (q1q2 + 1)y3; (q2q3 + 1)x3 + q2y3);

  • 14 1. EQUAO DE PELL

    ao final da terceira iterao. Continuando a efetuar as substituies adequadas, obteremos,na k-sima iterao,

    P = ((xk; yk); (xk; yk));

    em que e so funes lineares de xk e yk. Com isto, se (uk; vk) for uma soluo deFk(xk; yk) = (1)k, ento

    ((uk; vk); (uk; vk));

    ser uma soluo de F0(x0; y0) = 1.

    Para melhor esclarecer o funcionamento deste procedimento, faremos o exemplo resol-vido por Wallis em sua carta a Brouncker datada de 17 de dezembro de 1657; ver [13, p.479-480]. A equao de que trata o exemplo

    x2 13y2 = 1:Usando a notao introduzida acima, escreveremos esta equao na forma F0(x0; y0) = 1,em que

    F0(x0; y0) = x2 13y2:

    Como a maior raiz de F0(t; 1) = 0 t = 3:59375:::, o maior inteiro q0 para o qualF0(q0; 1) < 0 q0 = 3. Fazendo a substituio

    x0 = y1 + 3x1 e y0 = x1em F0(x0; y0) e no ponto P = (x0; y0), obtemos

    F1(x1; y1) = 4x21 6x1y1 y2 e P = (y1 + 3x1; x1);

    de modo que de F0(x0; y0) = 1 obtivemos F1(x1; y1) = 1. Repetindo este procedimentocom F1(x1; y1) = 0, verificamos que F1(1; t) = 0 tem uma nica raiz positiva em t =1:65625:::, de modo que q1 = 1. Aplicando a substituio

    x1 = y2 + x2 e y1 = x2a F1(x1; y1) e a P , temos que

    F2(x2; y2) = 3x22 2x2y2 4y22 e P = (4x2 + 3y2; y2 + x2);

    com F1(x1; y1) = 1 tendo sido convertido em F2(x2; y2) = 1. Para chegar at resultadodesejado, o algoritmo executa mais oito etapas, que resumimos, juntamente com as duasque j calculamos, na tabela 1, na qual a forma Fi est abreviada como a trinca [Ai; Bi; Ci].

    De acordo com a tabela 1, obtemos, aps dez passos, a forma

    F10(x10; y10) = x210 6x10y10 4y210

    que tem como soluo x10 = 1 e y10 = 0. Substituindo estes valores em

    P = (649x10 + 393y10; 180x10 + 109y10)

    obtemosP = (649; 180)

  • 3. ACHANDO SOLUES 15

    Passo q Substituies Fi(xi; yi) P1 3 x0 = y1 + 3x1 e y0 = x1 [4; 3; 1] (3x1 + y1; x1)2 1 x1 = y2 + x2 e y1 = x2 [3; 1; 4] (4x2 + 3y2; y2 + x2)3 1 x2 = y3 + x3 e y2 = x3 [3; 2; 3] (7x3 + 4y3; 2x3 + y3)4 1 x3 = y4 + x4 e y3 = x4 [4; 1; 3] (11x4 + 7y4; 3x4 + 2y45 1 x4 = y5 + x5 e y4 = x5 [1; 3; 4] (18x5 + 11y5; 5x5 + 3y5)6 6 x5 = y6 + 6x6 e y5 = x6 [4; 3; 1] (119x6 + 18y6; 33x6 + 5y6)7 1 x6 = y7 + x7 e y6 = x7 [3; 1; 4] (137x7 + 119y7; 38x7 + 33y7)8 1 x7 = y8 + x8 e y7 = x8 [3; 2; 3] (256x8 + 137y8; 71x8 + 38y8)9 1 x8 = y9 + x9 e y8 = x9 [4; 1; 3] (393x9 + 256y9; 109x9 + 71y910 1 x9 = y10 + x10 e y9 = x10 [1; 3; 4] (649x10 + 393y10; 180x10 + 109y10)

    TABELA 1. Aplicao do mtodo de Brouncker equao x2 13y2 = 1

    que a soluo desejada de x2 13y2 = 1. Brouncker e Wallis descobriram que, longede ser atpico, o comportamento do mtodo quando quando d = 13 se repetia em todos osexemplos. Mais precisamente, era sempre possvel encontrar um nmero inteiro positivopar k de modo que o coeficiente de x2k em Fk(xk; yk) fosse igual a 1, garantindo assim queFk(1; 0) = 1, o que permitia resolver F0(x0; y0) = 1 com bastante facilidade. levando istoem conta, podemos enunciar o mtodo de Brouncker e Wallis da seguinte forma.

    ALGORITMO 3.1 (Mtodo cclico). Dado um inteiro positivo d, que no um quadradoperfeito, o algoritmo retorna uma soluo no trivial da equao de Pell x2 dy2 = 1.

    Calcule a parte inteira q da raiz quadrada de d.Inicialize A com (q2 d), B com q e C com 1.Inicialize um contador k := 1 e P := [x; y].Enquanto A 6= 1 ou k for mpar repita:

    Determine o maior inteiro q menor que a raiz positiva deAt22BtC = 0.Substitua A por (Aq2 2Bq C), B por Aq B e C por A.Substitua x por qx+ y e y por x em P .Incremente k de uma unidade.

    Substitua x por 1 e y por 0.Retorne P .

    Embora nossa descrio do algoritmo de Brouncker esteja completa, no fcil en-tender porque a execuo deste conjunto de instrues deveria parar. Uma anlise mais

  • 16 1. EQUAO DE PELL

    detalhada do que fizemos revela que h muito mais a ser verificado. A lista de pendncias a seguinte:

    (a) determinar condies sobre F , sob as quais F t existe e tem coeficientes positivos;

    (b) assegurar que as condies em (1) se propagam transformada, permitindo que oalgoritmo possa ser iterado;

    (c) mostrar que as condies que fazem o algoritmo parar sempre so realizadas apsuma quantidade finita de etapas.

    A ressalva sob a existncia de F t em (a) necessria porque a transformada s existe sehouver um inteiro positivo q para o qual F (q; 1) < 0. Note que h uma grande diferenaentre, de um lado (a) e (b), e do outro (c). De fato, para resolvermos (a) e (b) basta conside-rarmos o que ocorre na passagem de uma dada forma sua transformada; j (c) requer queconsideremos o efeito do algoritmo sobre tantos passos quantos forem necessrios paraatingirmos as condies que fazem o algoritmo parar. Por isso vamos nos referir a (a) e (b)como parte da anlise local do algoritmo e a (c) como resultando de sua anlise global. Aprxima seo dedicada a uma demonstrao detalhada de (a), (b) e (c).

    4. Anlise do algoritmo de Brouncker

    Comeamos a seo com a anlise local do algoritmo de Brouncker, que trata da pas-sagem de uma forma sua transformada. Ao longo de toda a anlise local, denotaremospor F a forma

    F (x; y) = Ax2 2Bxy Cy2;em que A > 0, B 0 e C > 0 so inteiros. Se F (t; 1) = 0 tiver uma raiz positivamaior que 1, determinamos o maior inteiro positivo q para o qual F (q; 1) > 0 e definimosa transformada F t de F por

    F t(x0; y0) = F (y + qx; x):Escrevendo

    F t(x0; y0) = A0(x0)2 2B0x0y0 C 0(y0)2;vimos que

    (16) A0 = (Aq2 2Bq C); B0 = (Aq B) e C 0 = A:Portanto, para que F t possa ser calculada e tenha as mesmas propriedades que F , precisa-mos identificar condies que garantam que:

    (1) F (t; 1) = 0 tenha uma raiz maior que 1;

    (2) A0 > 0, B0 0 e C 0 > 0;(3) as condies que garantem (1) e (2) tambm valham para F t.

  • 4. ANLISE DO ALGORITMO DE BROUNCKER 17

    11q + 1q

    FIGURA 4. A parbola y = F (x; 1).

    As condies desejadas decorrem da anlise da parbola u = F (t; 1), ilustrada nafigura 4. Para comear, o discriminante 4(B2 + AC) de F (t; 1) = 0 positivo, de modoque a equao F (t; 1) = 0 tem duas razes reais distintas < . Como

    = CA

    e A e C so positivos, uma dessas razes ser positiva e a outra negativa; isto < 0 < .At aqui usamos apenas que A e C so positivos e que B 0. Contudo, nem toda escolhade inteiros satisfazendo estas condies garante que a forma F correspondente satisfaa(1). Isto porque (1) equivale a dizer que > 1 e as hipteses que temos s garantem que > 0. Entretanto, a parbola u = F (t; 1) tem concavidade para cima, pois A > 0. Logo,para que 1 esteja entre as razes de F (t; 1) = 0 devemos ter que

    F (1; 1) = A 2B C < 0:Portanto, s hipteses A > 0, B 0 e C > 0 devemos acrescentar que A 2B C < 0para que exista um inteiro q > 0 para o qual F (q; 1) < 0.

    Passando, agora, a (2), sabemos que a escolha feita para q garante que

    A0 = (Aq2 2Bq C) = F (q; 1) > 0;

  • 18 1. EQUAO DE PELL

    ao passo queC 0 = A > 0;

    consequncia direta das hipteses originais impostas a F . Resta-nos, apenas, verificar seB0 = Aq B no negativo. Mas isto ocorre quando q B=A. Contudo, escolhendoq 1 como o maior inteiro menor que a raiz positiva de F (t; 1) = 0, teremos que

    < q + 1 2q:Por outro lado,

    + =2B

    Adonde

    B

    A=

    +

    2 0 sob as mesmas hipteses quegarantem que A0 > 0 e C 0 > 0, o que uma tima notcia.

    Resta-nos, apenas, mostrar que estas condies so herdadas por F t, permitindo que oprocedimento seja iterado. Como j sabemos que, sob as novas hipteses, A0, B0 e C 0 sopositivos, basta verificar que elas tambm garantem que F t(1; 1) < 0. Mas

    (17) F t(1; 1) = A0 2B0 C 0 = F (q 1; 1):Como < q + 1 e a parbola y = F (x; 1) tem concavidade para cima, temos de (17) que

    F t(1; 1) = F (q + 1; 1) < 0:Portanto, se A > 0, B 0, C > 0 e A C < 2B, ento estas mesmas propriedadesvalem para os coeficientes da transformada F t.

    Antes de passar anlise global, precisamos investigar uma outra propriedade quepertence anlise local e que ser necessria mais adiante. Para isso, dada F introduzimossua simtrica SF como sendo a forma obtida trocando-se o coeficiente de x2 com o de y2;isto

    SF (x; y) = Cx2 2Bxy Ay2:

    Em particular, a simtrica de F t

    SF t = C0x2 2B0xy A0y2:

    Vejamos o que acontece se calcularmos a transformada de S = SF t . Em primeiro lugar,para que isto seja possvel, preciso que S(1; 1) < 0; isto , que

    C 0 2B0 A0 < 0:

  • 4. ANLISE DO ALGORITMO DE BROUNCKER 19

    Substituindo as frmulas para A0, B0 e C 0 de (16) e reagrupando os termos, temos que

    C 0 2B0 A0 = A(q 1)2 2B(q 1) C:Mas q > 1 implica que 0 < q1 < q, de modo que q1 est entre as razes de F (t; 1) = 0.Logo,

    (18) A(q 1)2 2B(q 1) C = F (q 1; 1) < 0:Portanto, S 0 satisfaz as condies requeridas para que o clculo da transformada possa serefetuado. O prximo passo consiste em determinar o maior inteirom > 0 tal que

    S 0(m; 1) = C 0m2 2B0m A0 < 0:Substituindo as frmulas de (16) e reagrupando os termos, como acima, obtemos

    S 0(m; 1) = A(q m)2 2B(q m) C = F (q m; 1):Desta ltima equao, segue-se que

    (19) S 0(q; 1) = C < 0;pois C > 0 por hiptese. Por outro lado,

    C 0(q + 1)2 2B0(q + 1) A0 = A+ 2B C:Logo, se

    A+ 2B C > 0entom = q e os coeficientes da transformada de S 0 sero

    C 0q2 2B0q A0 = A; A0q B0 = B e C 0 = A:Em outras palavras, adicionando A + 2B C > 0 s hipteses vigentes, teremos que atransformada de SF t SF . Contudo, antes de acrescentar A + 2B C > 0 s demaiscondies, precisamos nos certificar de que herdada pela transformada, do contrrio nopoderamos iterar o clculo das transformadas das formas simtricas, requerido na anliseglobal. Entretanto,

    A0 + 2B0 C 0 = (A(q 1)2 2B(q 1) C) = F (q 1; 1);que positivo por (18), de forma que tambm esta condio preservada pelo processo dederivao de formas.

    Para simplificar o enunciado final que resulta de nossa anlise da passagem de umaforma sua transformada, diremos que uma forma F = Ax2 2BxyCy2 reduzida seA > 0, B 0, C > 0 e jA Cj < 2B e que seu discriminante o nmero B2 + AC.Com isto, o que provamos acima pode ser resumido nas seguintes concluses:

    Concluso 1: a transformada de uma forma reduzida tambm reduzida;

    Concluso 2: a transformada da simtrica de uma forma reduzida a forma origi-nal;

  • 20 1. EQUAO DE PELL

    Precisamos, tambm, do seguinte resultado, que pode ser obtido por um clculo simples apartir das frmulas (16):

    Concluso 3: uma forma e sua reduzida tm o mesmo discriminante.

    Com isto estamos prontos para passar anlise global. Usando a notao que introdu-zimos na seo anterior, denotaremos por

    Fi(x; y) = Aix2 2Bixy Ci

    a i-sima transformada da forma

    F0(x; y) = x2 dy2:

    Como, pela concluso 3, o discriminante de uma forma e de sua transformada coincidem,temos que

    B2i + AiCi = d;

    pois o discriminante de F0 d. Contudo, a quantidade de inteiros no negativos , e que satisfazem a relao

    2 + = d

    finita. Isto significa que, aps uma certa quantidade r de passos, teremos, necessaria-mente, que

    Fr(x; y) = Fq(x; y)

    para algum inteiro q < r. Portanto, se Si for a forma simtrica de Fi, teremos que

    Sr(x; y) = Sq(x; y):

    Calculando a q-sima transformada destas duas formas, obtemos

    Srq(x; y) = S0(x; y);

    que, pela concluso 2 equivale a

    Frq(x; y) = F0(x; y):

    Como r > q, podemos concluir que, depois de executar uma quantidade k = r q > 0 depassos, o algoritmo 3.1 retorna forma original F0. Levando em conta a alternncia dossinais na passagem de um passo ao outro do algoritmo, obtivemos, ao final de k etapas aequao diofantina

    Fk = F0 = (1)k:Se k for par, esta equao tem (1; 0) como soluo e o algoritmo para, retornando umasoluo de F0(x; y) = 1. Se k for mpar, continuamos a executar o algoritmo por mais kpassos, o que nos d

    F2k = Fk = F0 = (1)2k = 1;

  • EXERCCIOS 21

    que tem (1; 0) como soluo. Portanto, o algoritmo funciona corretamente em qualquer dosdois casos, retornando a resposta desejada. A demonstrao de que o algoritmo 3.1 funci-ona tambm explica porque os indianos, que foram os primeiros a invent-lo, chamavam-no de mtodo cclico: medida que o valor de i aumenta, a sequncia de transformadaspercorre o ciclo

    F0; F1; : : : ; Fk = F0

    se k for par, ouF0; F1; : : : ; F2k = F0

    se k for mpar.

    5. Estrutura do grupo P(d)

    Nesta seo pretendo responder pergunta, feita em aula por alguns alunos, que que-riam saber se todos os elementos de P(d) so potncias do elemento encontrado pelo m-todo cclico. A resposta sim. Mais precisamente, se G um grupo e todos os seuselementos so potncias de um nico dentre eles, ento o grupo chamado de cclico eeste elemento um gerador do grupo. O resultado desejado pode ento ser enunciado daseguinte forma.

    TEOREMA 5.1. O grupo P(d) cclico e gerado pelo elemento obtido aplicando-seo algoritmo 3.1 equao x2 dy2 = 1.

    A demonstrao deste resultado um pouco trabalhosa e vou deix-la para outra oca-sio.

    Exerccios

    1. Prove que se, para um dado d, a equao de Pell x2 dy2 = 1 tem uma soluono trivial, ento ela tambm admite uma soluo no trivial cujas duas entradas sopositivas.

    2. Determine, por tentativa, pelo menos uma soluo cujas entradas so positivas, para asseguintes equaes de Pell:(a) x2 3y2 = 1;(b) x2 6y2 = 1;(c) x2 15y2 = 1.

    3. O objetivo deste exerccio calcular todas as solues da equao de Pell x2ny2 = 1quando n < 2:(a) Mostre que se n < 2 ento x2 ny2 > 2 quaisquer que sejam os inteiros x e y.

  • 22 1. EQUAO DE PELL

    (b) Use (a) para mostrar que se x e y so solues da equao de Pell com n < 2,ento y = 0.

    (c) Use (b) para provar que, quando n < 2, as nicas solues da equao de Pellso as triviais.

    4. Resolva a equao de Pell x2 + y2 = 1 seguindo os seguintes passos:(a) se x 1 e y 1 so inteiros ento x2 + y2 > 1;(b) conclua de (a) que se x2 + y2 = 1 ento x = 0 ou y = 0;(c) use (b) para achar todas as Solues de x2 + y2 = 1.

    5. Resolva a equao de Pell x2 dy2 = 1 quando d = r2 para algum nmero inteiro nopositivo r. Siga os seguintes passos:(a) fatore x2 dy2 = x2 r2y2;(b) lembrando que x e y so inteiros, e comparando a fatorao obtida em (a) com o

    lado direito da equao, determine os possveis valores destes fatores;(c) considerando todos os possveis valores dos fatores, voc obter dois sistemas li-

    neares, cujas solues inteiras lhe daro todas as solues desta equao de Pell.

    6. Seja (x0; y0) uma soluo da equao de Pell x2 dy2 = 1. Calcule(x0; y0) (1; 0):

    7. Seja 0 = (1; 0) soluo de x2 ny2 = 1. Determine k0 para cada inteiro k > 0.

    8. Ache uma soluo da equao de Pell x2 5y2 = 1 e calcule seu quadrado e seu cubo.

    9. Seja 0 = (8; 3) soluo de x2 7y2 = 1. Determine 20 , 30 e 40 .

    10. Seja P = (x0; y0) uma soluo de x2 2y2 = 1. Mostre como obter uma soluo dex2 8y2 = 1 a partir de P 2.

    11. Calcule P 2 P(7) tal que (2024; 765) P = (514088; 194307).

    12. Sejam 0 e 1 duas solues da equao de Pell x2 dy2 = 1 cujas entradas so todaspositivas. Prove que:(a) todas as entradas de 0 1 so positivas;(b) a primeira entrada de 0 1 maior que o mximo das primeiras entradas de 0

    e 1.(c) Use (b) para provar que 0 1 no pode ser igual a 0 nem a 1.

    13. Use o exerccio 12 para provar que se a equao x2dy2 = 1 tem alguma soluo notrivial, ento ela tem infinitas solues.

  • EXERCCIOS 23

    14. Neste exerccio apresentamos um roteiro para a demonstrao de que inclinao dareta tangente hiprbole x2 dy2 = 1 no ponto P = (x0; y0) igual a x0=dy0.Usaremos a mesma definio de tangente adotada no estudo da circunferncia noscursos elementares de geometria. Isto , diremos que uma reta tangente hiprbolese ela toca a curva em um nico ponto.(a) Determine a equao quadrtica em x que as abscissas dos pontos de interseo da

    reta de equao y = m(x x0) + y0 com a hiprbole satisfazem.(b) Mostre que o discriminante da equao quadrtica obtida em (a) igual a (mdy0

    x0)2.

    (c) Use (b) para chegar concluso desejada.DICAS: para (a) substitua a equao da reta na equao da hiprbole; para (b) use quex20 dy20 = 1.

    15. Este exerccio tem como objetivo provar que a subtrao de inteiros no associativa,nem comutativa, nem admite elemento neutro. Sejam a, b e c nmeros inteiros:(a) Para quais valores de c vale a igualdade a (b c) = (a b) c?(b) Que relao a e b devem satisfazer para que a b = b a?(c) Mostre que no pode existir um inteiro z de modo que az = za = a, qualquer

    que seja o inteiro a.

    16. Seja P o conjunto cujos elementos so os subconjuntos de f1; 2; : : : ; ng. Para quaisdas operaes abaixo este conjunto constitui um grupo?(a) unio;(b) complementar;(c) diferena simtrica.Para caso de voc no lembrar, a diferena simtrica entre dois conjuntos A e B definida por (A nB) [ (B n A).

    17. Dados dois nmeros reais u e v, definimos

    u v = u+ v1 + uv

    c2

    :

    Determine se o intervalo (c; c) com a operao ou no um grupo. Esta operaocorresponde soma de velocidades na teoria da relatividade restrita, em que c avelocidade da luz.

    18. Seja (G; ?) um grupo e a um elemento de G. Usando as frmulas

    a0 = e e ak+` = ak ? a`;

    para inteiros no negativos k e `, determine como deveramos definir potncias negati-vas de a em G.

    19. Seja (G; ?) um grupo.(a) Mostre que um grupo no pode ter mais de um elemento neutro.

  • 24 1. EQUAO DE PELL

    (b) Mostre que cada elemento de um grupo s pode um inverso.

    20. Seja (G; ?) um grupo. Um subconjunto S de G fechado relativamente operao ?se para quaisquer elementos a; b 2 S temos sempre que a ? b 2 S. Quais dos seguintessubconjuntos so fechados relativamente operao de adio de inteiros:(a) os nmeros pares;(b) os nmeros mpares;(c) os mltiplos de 3;(d) os nmeros positivos.

    21. Todo grupo tem, pelo menos dois subconjuntos distintos que so fechados relativa-mente sua operao: quais so estes subconjuntos?

    22. Seja (G; ?) um grupo e a um elemento de G. Defina hai como sendo o conjunto daspotncias de a com expoentes no negativos; isto

    hai = fak j k 0 inteiro g:Mostre que hai um conjunto fechado relativamente operao ?.

    23. Mostre que se a equao de Pell x2 dy2 = 1 tem soluo diferente de (1; 0), entoo grupo P(d) infinito.

    24. Seja d > 0 um nmero inteiro. Qual a maior quantidade de inteiros no negativos , e que satisfazem 2 + = d?

    25. Use o algoritmo de Brouncker para achar solues para as seguintes equaes de Pell(a) x2 10y2 = 1;(b) x2 12y2 = 1;(c) x2 20y2 = 1.

    26. Suponha que x0 e y0 so dois inteiros tais que x20 ny20 = 2.(a) Obtenha solues para a equao x2 ny2 = 4 em termos de x0 e y0.(b) Usando ny20 = x

    20 2 e (a) obtenha u; v 2 Z tais que (2u)2 n(2v)2 = 4.

    (c) Usando (b) ache solues da equao de Pell x2 ny2 = 1 em termos de x0 e y0.(d) Usando (c) obtenha uma soluo da equao de Pell x2 7y2 = 1 a partir da

    soluo (3; 1) de x2 7y2 = 2.

  • Referncias Bibliogrficas

    [1] W. R.Alford, A. Granville e C. Pomerance, There are infinitely many Carmichael numbers, Ann. of Math.140 (1994), 703722.

    [2] F. Arnault, Constructing Carmichael numbers which are strong pseudoprimes to several bases, J. Sym-bolic Computation, 20 (1995), 151161.

    [3] M. Artin, Algebra, Prentice-Hall, Englewood Cliffs, (1991).

    [4] C. B. Boyer, Histria da Matemtica, traduzido por E.F. Gomide, Editora Edgar-Blcher, So Paulo,(1994).

    [5] D. M. Bressoud, Factorization and primality testing, Undergraduate Texts in Mathematics, Springer-Verlag, New York (1999).

    [6] R. D. Carmichael On composite numbers P which satisfy the Fermat congruence aP1 1 (mod P ),Amer. Math. Monthly 19 (1912), 2227.

    [7] D. Cox, J. Little, e D. OShea, Ideals, varieties and algorithms: an introduction to computation algebraicgeometry and commutative algebra, Undergraduate Texts in Mathematics, Springer-Verlag, New York(1992).

    [8] J. H. Davenport, Y. Siret e E. Tournier, Computer Algebra: systems and algorithms for algebraic com-putation, translated by A. Davenport and J.H. Davenport, Academic Press, London (1998).

    [9] M. Davis, What is computation?, in Mathematics Today, editado por L. A. Steen, Vintage Books, NewYork (1980), 241267.

    [10] L. E. Dickson, A history of the theory of numbers, Chelsea Publishing Company, New York, (1952).

    [11] H. M. Edwards, Fermats last theorem, Graduate Texts in Mathematics 50, Springer-Verlag, New York(1977).

    [12] H. M. Edwards, Galois theory, Graduate Texts in Mathematics 101, Springer-Verlag, New York (1984).

    [13] Pierre de Fermat, Oeuvres de Fermat, editada por Paul Tannery e Charles Henry, volume III, Gauthier-Villars (1896).

    [14] R. P. Feynman, QED: the strange theory of light and matter, Princeton University Press, Princeton(1985).

    [15] C. F. Gauss, Disquitiones Arithmetic, translated by A.A. Clarke, revised by W.C. Waterhouse with thehelp of C. Greither e A.W. Grotendorst, Springer-Verlag, New York (1986).

    25

  • 26 REFERNCIAS BIBLIOGRFICAS

    [16] P. Giblin, Primes and programming, Cambridge University Press, Cambridge (1993).

    [17] A. Gonalves, Introduo lgebra, Projeto Euclides, IMPA, Rio de Janeiro (1979).

    [18] G. B. Gostin, New factors of Fermat numbers, Math. of Comp. 64 (1995), 393395.

    [19] G. H. Hardy, e E.M. Wright, An introduction to the theory of numbers, quinta edio, Oxford SciencePublications, Oxford University Press, Oxford (1994).

    [20] A. Hefez, Curso de lgebra, vol. 1, Coleo Matemtica Universitria, IMPA, Rio de Janeiro (1993).

    [21] A. E. Ingham, The distribution of primes, Cambridge University Press, Cambridge (1932).

    [22] D. E. Knuth, The Art of computer programming, vol. 2, Seminumerical algorithms, segunda edio,Addison-Wesley Publishing Company, Reading (1981).

    [23] N. Koblitz, A course in number theory and cryptography, Graduate Texts in Mathematics 97, Springer-Verlag, New York (1987).

    [24] E. Kranakis, Primality and criptography, Wiley-Teubner series in Computer Science, B.G. Teubner eJ. Wiley & Sons (1986).

    [25] M. Lemos, Criptografia, nmeros primos e algoritmos, 17 Colquio Brasileiro de Matemtica,IMPA/CNPq (1989).

    [26] A. K. Lenstra, H. W. Lenstra jr, M. S. Manasse e J. M. Pollard, The factorization of the ninth Fermatnumber, Math. of Comp., 61 (1993), 319349.

    [27] C. Pomerance, A tale of two sieves, Notices of the Amer. Math. Soc., 43(12) (1996), 14731485.

    [28] S. Ramanujan, Collected papers of Srinivasa Ramanujan, editado por G. H. Hardy, P. V. Seshu Aiyare B. M. Wilson, Cambridge University Press, Cambridge (1927).

    [29] H. Riesel, Prime numbers and computer methods of factorization, second edition, Progress in Mathe-matics 126, Birkhuser, Boston (1994).

    [30] R. L. Rivest, A. Shamir e L. Adleman, A method for obtaining digital signatures and public-key cryp-tosystems, Comm. ACM, 21 (1978), 120126.

    [31] P.W. Shor, Algorithms for quantum computation: discrete logarithms and factoring, in Proceedings of35th Annual Symposium on Foundations of Computer Science, IEEE Computer Science Press (1994),124134.

    [32] J. H. Silverman e J. Tate, Rational points on elliptic curves, Undergraduate Texts in Mathematics,Springer-Verlag, New York (1992) .

    [33] B. L. van der Waerden, A history of algebra, Springer-Verlag, Berlin-Heidelberg (1985).

    [34] J. F. Voloch, A distribuio dos nmeros primos, Matemtica Universitria, nmero 06 (1987), 7182.

    [35] A. Weil, Number theory: an approach through history, Birkhuser, Boston (1987) .

    [36] H. Weyl, Symmetry, Princeton University Press, Princeton (1982) .