UNIVERSIDADE ESTADUAL DO SUDOESTE DA BAHIA - UESB Documentos DEPARTAMENTO DE CIÊNCIAS EXATAS E TECNOLÓGICAS– DCET CURSO DE LICENCIATURA EM MATEMÁTICA DINGUISTON DOS SANTOS BISPO EQUAÇÕES DIOFANTINAS LINEARES E SUAS APLICAÇÕES Vitória da Conquista - BA 2013 DINGUISTON DOS SANTOS BISPO EQUAÇÕES DIOFANTINAS LINEARES E SUAS APLICAÇÕES Monografia apresentada ao curso de Licenciatura em Matemática da Universidade Estadual do Sudoeste da Bahia – UESB / Campus de Vitória da Conquista - BA, para obtenção do título de Licenciado em Matemática, sob orientação da Prof.Antônio Augusto Oliveira Lima. Orientador: Prof.Antônio Augusto Oliveira Lima. Vitória da Conquista - BA 2013 FOLHA DE APROVAÇÃO DINGUISTON DOS SANTOS BISPO EQUAÇÕES DIOFANTINAS LINEARES E SUAS APLICAÇÕES Monografia apresentada como requisito para obtenção do título de Licenciado em Matemática no curso de Licenciatura em Matemática da Universidade Estadual do Sudoeste da Bahia – UESB. Aprovada em _____de _______________de_______ Componentes da banca examinadora: ______________________________________________________ Prof. Antônio Augusto Oliveira Lima. Orientador ______________________________________________________ Prof.º Ms. Wallace Juan Teixeira Cunha ______________________________________________________ Prof.ª Ms. Clênia Andrade Oliveira de Melo AGRADECIMENTOS Quero expressar aqui a minha gratidão a todos que, direta ou indiretamente contribuíram para minha formação acadêmica e a realização desse trabalho. A Deus por me fortalecer e iluminar nos momentos mais difíceis da vida universitária e ainda por me ter dado saúde física e mental para enfrentar os desafios que a vida nos oferece. A meus pais por sempre me apoiarem nas minhas decisões. A minha amada esposa que amavelmente me acompanhou em todos os momentos decisivos na minha vida. A UESB por oferecer uma excelente formação acadêmica que nos prepara para a vida. A todos os professores do curso de Licenciatura em Matemática e em especial ao meu orientador Antônio Augusto Oliveira Lima que gentilmente disponibilizou tempo, dedicação, flexibilidade, carisma, atenção e proporcionou uma grande evolução pessoal e profissional. Aos meus caríssimos colegas, pela troca de experiências e discussões enriquecedoras nos grupos de estudos que sempre fazíamos. Em fim, a todos vocês o meu muito obrigado. Um bom ensino da Matemática forma melhores hábitos de pensamento e habilita o indivíduo a usar melhor a sua inteligência. Irene de Albuquerque Sumário INTRODUÇÃO ......................................................................................................................... 7 1. REFERENCIAL HISTÓRICO ......................................................................................... 8 2. REFERENCIAL TEÓRICO ........................................................................................... 13 2.1. Divisibilidade em Z ..................................................................................................... 13 2.2.Máximo Divisor Comum ............................................................................................. 15 2.3.Algoritmo da Divisão de Euclides ............................................................................. 16 2.4 Teoria da Congruência ............................................................................................... 25 2.5 Congruência Linear ..................................................................................................... 35 3.EQUAÇÕES DIOFANTINAS LINEARES ....................................................................... 42 3.1. Condição de Existência de Solução ....................................................................... 44 3.2.Soluções da equação a.x + b.y c........................................................................... 45 3.3. Usar a congruência linear para resolver equações diofantinas ......................... 52 3.4.Equações Diofantinas Linear com 3 variáveis ....................................................... 53 4. APLICAÇÕES DAS EQUAÇÕES DIOFANTINAS LINEARES .................................. 58 4.1 Problemas Envolvendo Equações Diofantinas Lineares ...................................... 58 4.2.Utilizando o Winplot .................................................................................................... 68 CONSIDERAÇÕES FINAIS ................................................................................................. 74 REFERÊNCIA BIBLIOGRAFIA ........................................................................................... 75 INTRODUÇÃO Este trabalho tem como finalidade auxiliar estudantes na resolução e compreensão de problemas envolvendo Equações Diofantinas Lineares com Duas e até Três incógnitas através dos conceitos da teoria dos números. Pretende-se no desenvolvimento desse estudo promover uma integração entre Aritmética com a Álgebra e também a Geometria ao utilizar o programa computacional Winplot como suporte para a visualização gráfica de soluções inteiras das Equações Diofantinas. Inicialmente fazemos um breve estudo da história da álgebra ilustrando os principais fatos que contribuíram para o desenvolvimento da álgebra e acerca da vida de Diofanto. A quem se deve o surgimento deste conteúdo, viveu presumivelmente no século III em Alexandria - Egito, já sob o domínio de Roma. Foi o único matemático da Grécia antiga que se dedicou à teoria dos números. Fazia uso de métodos geométricos para deduzir e provar suas afirmações. Nos próximos capítulos vamos conhecer melhor a essência da Teoria Elementar dos Números, pois apresentaremos e demonstraremos as ferramentas matemáticas que serão utilizadas na resolução das Equações Diofantinas Lineares, algumas delas já conhecidas, que é o caso do máximo divisor comum (m.d.c) e a poderosa ferramenta para calculá-lo, algoritmo de Euclides. Destaca-se também o papel da Congruência Linear na resolução desses problemas. Ao estudar Equações Diofantinas Lineares da forma a.x + b.y c, com a, b e c inteiros é conveniente perguntar: Sob quais condições a equação admite soluções inteiras? E se existem essas soluções, como determiná-las? Em seguida serão introduzidas as equações diofantinas e os métodos de determinação de soluções da mesma para aplicação em resolução de problemas do cotidiano. No quarto capitulo apresentamos algumas situações-problemas, a fim de aplicar os métodos acima referidos para resolução de problemas aritméticos. Por fim esta monografia deseja mostrar o desenvolvimento a importância da interpretação algébrica e geométrica das Equações Diofantinas Lineares, e que o contato com problemas desta área contribui para que o aluno desenvolva, de forma criativa suas habilidades de raciocínio. 1. REFERENCIAL HISTÓRICO Para podermos compreender as primeiras manifestações ditas algébricas fazemos menção de uma pequena divisão histórica acerca da álgebra, sugerida por Sr.G.H.FNesselmenn (1842) que destaca-se em três momentos distintos: -O Retórico ou Verbal conhecido também pelo desenvolvimento da álgebra pré-diofantina em que os argumentos da resolução de um problema são escritos em prosa pura, sem abreviações ou símbolos específicos. -Sincopado, aqui se adotavam algumas abreviações para das quantidades e operações que se repetem mais frequentemente. -Simbólico, nesse momento as resoluções se expressam numa espécie de taquigrafia matemática formada por símbolos que aparentemente nada têm a ver com os entes que representam. (Ives, p.206). Notemos que não há possibilidades de definir uma linha de demarcação exata acerca do desenvolvimento da álgebra na historia da matemática. Visto que foram inúmeras influencias em diferentes tempos que contribuíram para a formação da álgebra que estudamos. Desta forma, mostraremos alguns fatos históricos que evidenciaram o papel da álgebra no pensamento matemático. Desde os primórdios que são notáveis a ênfase dada aos procedimentos e resolução de técnicas nos problemas de equações. Por volta de 2000 a.C a aritmética babilônica parecia ter evoluído para uma álgebra retórica desenvolvida. Eles resolviam equações lineares e quadráticas com duas incógnitas, tanto pelo método equivalente ao de substituição numa fórmula geral, como pelo método de completar quadrados. A álgebra naquela época era utilizada para resolver problemas por meio de equações que ainda, nos dias de hoje, requerem uma considerável habilidade numérica, e nota-se ainda que os babilônicos eram infatigáveis construtores de tábuas de cálculos, calculistas extremamente hábeis e certamente mais fortes em álgebra do que em geometria. (Eves, 2004, p.63) Devido a sua importância histórica faz-se necessário destacar a civilização egípcia. Os mais conhecidos documentos antigos da historia da matemática são os papiros egípcios. Os papiros de Rhind e de Moscou juntos contém 110 problemas de origem práticas com questões sobre pão, cerveja, o balanceamento de rações para o gado e aves. As resoluções de boa parte dos problemas eram feitas por uma equação linear com uma incógnita, utilizando a regra da falsa posição que mais tarde foi desenvolvido na Europa. Percebe-se que nesse período a busca por soluções das equações algébricas eram feitas de modo especifico, não se se preocupava com a generalização do conhecimento matemático. Os Gregos Na era grega nota-se o surgimento de um número significativo de matemáticos que se preocupavam em buscar soluções para problemas matemáticos não de ordem prática, mas que representava um pensamento mais generalizado das questões matemáticas de forma dedutiva com manipulações geométricas. A característica principal desse período é a passagem da álgebra aritmética para a álgebra geométrica, destacando-se a resolução de equações lineares e quadráticas através do método das proporções e aplicações de áreas, tais métodos parecem ter origens nos pitagóricos. Uma das melhores fontes de problemas algébricos gregos antigos é a coleção conhecida como Palatine ou Antologia Grega. Trata-se de uma coleção de quarenta e seis problemas numéricos, em forma epigramática, reunida por volta de 500 D.C. pelo gramático Metrôdoro. -Euclides (c. 300 a.c.): Em os Elementos, apresentava-se a resolução das identidades algébricas por meio da terminologia geométrica. Demonstrou com clareza a seguinte preposição: (a + b)2 = a2 + 2ab + b2. -Herão de Alexandria (150 a.C. a 250 d.C.?): Supõe-se que era um egípcio com formação grega. A sua mais importante obra A Métrica composta por três livros sendo descoberta só em 1896 em Constantinopla por R. Schone Trata-se de problemas de mensuração e do seu principal método de aproximar a raiz quadrada de um inteiro que não é quadrado perfeito. Tal método é hoje frequentemente usado nos computadores. -Diofanto: Matemático grego, pouco se sabe, presumindo-se que nasceu em cerca de 200 d.C. em Alexandria, no Egito, uma colônia grega e morreu em cerca de 284 d.C., também em Alexandria. A única evidência para essa data é que Antólios Bispo de Laodiceia sendo um matemático de talento, que começou seu episcopado em 270 d.C, dedicou um livro à seu amigo Diofantos. Devido a uns versos encontrados no seu túmulo, em forma de um enigmático problema, deduz-se que viveu 84 anos. “Deus lhe concedeu ser menino pela sexta parte de sua vida, e somando sua duodécima parte aisso, cobriu-lhe as faces de penugem. Ele lhe acendeu a lâmpada nupcial após uma sétima parte, e cinco anos após seu casamento concedeu-lhe um filho. Ai! Infeliz criança; depois de viver a metade da vida de seu pai, o Destino frio o levou. Depois de se consolar de sua dor durante quatro anos com a ciência dos números, ele terminou sua vida”. (BOYER, [3]). Diofanto escreveu três trabalhos: Aritmética, o mais importante, do qual remanesceram seis dos treze livros; Sobre Números Poligonais do qual restou apenas um fragmento; e Porismas, que se perdeu. Foi um gênio que se diferenciou dos demais de sua época pela originalidade, pelo seu alto grau dehabilidade matemática e profundidade de suas obras. Através de sua obra Aritmética fez uma abordagem analítica da teoria algébrica dos números. (Ives, p. 205 a 207). Segundo estudiosos, em sua obra “Aritmética”, Diofanto só se interessava por soluções racionais positivas, não aceitando as negativas ou as irracionais. Este livro é considerado o primeiro manual de álgebra que usa símbolos para indicar incógnitas e potências, e apresenta a resolução exata de equações indeterminadas. As outras obras tratam de um trabalho sobre frações, introduzindo o emprego de números fracionários. Os problemas estudados por Diofante são problemas indeterminados que exigem soluções inteiras (ou racionais) positivas e envolvem, em geral, equações de grau superior ao primeiro. Mesmo assim, hoje em dia, equações indeterminadas do primeiro grau, com coeficientes inteiros, são chamadas equações diofantinas em homenagem ao pioneirismo de Diofante nessa área, das quais, veremos mais adiante as suas aplicações. Árabes e Hindus Al-khwarizmi um dos principais nomes da época escreveu umas das mais importantes obras do estudo das equações llmal-JabrWa al Muqabalah, que pode ser entendida como “restauração por transposição de termos de um lado da equação para o outro”. Nesse livro aparecem pela primeira vez regras para a resolução de equações do 1º e 2º graus com coeficientes numéricos. A matemática hindu era desenvolvida de forma intuitiva, dois matemáticos que contribuíram significativamente para historia da álgebra foi Brahmagupta e Bháskara. Segundo Bashmakova e Smirnova (2000), Brahmagupta matemático hindu que viveu em 628 na Índia central, encontrou soluções gerais das equações quadráticas, determinando duas raízes, inclusive uma delas negativa. Pode observar a influencia da matemática grega em Brahmagupta. Ele foi o primeiro a encontrar todas as soluções inteiras possíveis para a equação linear diofantinaa.x + b.y c onde a, b e c são inteiros, enquanto Diofanto, em sua época, procurava uma solução racional qualquer. No século XII com sua obra Lilavati, Bháskara veio unificar a solução geral das equações quadráticas pelo método do complemento de quadrados (método hindu) que ficou conhecida até os dias atuais como Formula de Bháskara. Europeus A principal obra álgebra da Europa foi publicada na Itália e escrita por um frade chamado de Luca Pacioli: “A Summa de arithmetica, geométrica, proportioni et proportionalita” Sendo concluída em 1487 destacando a resolução usual de equações lineares e quadráticas. Outro feito matemático extraordinário foi à descoberta de soluções algébrica das equações cúbicas e quárticas pelos italianos. Nicolo Fontana, mais conhecido por Tartaglia nasceu em 1499 e desenvolveu a solução algébrica para a equação cúbica Retratando assim a melhor álgebra do século XVI. François Viéte nasceu na França em 1540 e é considerado por muitos como precursor da Álgebra simbólica. Foi o primeiro algebrista a demonstrar as vantagens no uso de letras para designar quantidades desconhecidas ou incógnitas. Em 1591, publicou a obra In ArtemAnalyticamIsagoge – Introdução a Arte Analítica. Nessa obra ele destaca o simbolismo algébrico introduzindo uma convenção extremamente importante para escrita das equações na forma geral, para representar uma quantidade desconhecida usava uma vogal e para representar uma grandeza ou números usava uma consoante. Outro matemático que contribuiu significativamente para o desenvolvimento da linguagem algébrica foi René Descartes, nascido em 1596 na França. Descartes consolidou a álgebra simbólica introduzindo as seguintes inovações para aperfeiçoar a álgebra de Viète: criando o símbolo (.) para a operação de multiplicação; a notação que usamos hoje para os expoentes de uma potenciação: e ainda passou a usar as primeiras letras do alfabeto para os coeficientes da incógnita e os termos independentes (se literais) e as últimas letras para representar as incógnitas. Formulou o método geral para a aplicação da álgebra a problemas geométricos determinados. Em sua obra La Geométrie apresenta a teoria elementar das equações; regra de sinais; como achar a solução algébrica de equações cúbicas e quárticas (Boyer: p. 248 a 253). E sem dúvida estabeleceu um elo forte entre a álgebra e a geométrica implantando o plano cartesiano. Pierre de Fermat (1601 - 1655), funcionário público francês foi ultimo dos grandes matemáticos amadores que cultivou o estudo da Ciência dos Números. Fez importantíssimas contribuições à matemática. Ao traduzir a Arithmetica de Diofanto transcreveu uma das declarações mais conhecidas da Álgebra que muitos matemáticos ao longo de séculos tentaram demonstrar, conhecida como “último teorema de Fermat”. É impossível escrever um cubo como soma de dois cubos, uma quarta potência como soma de duas quartas potências, e, em geral, qualquer potência maior que a segunda como soma de duas potências similares. Para isso eu descobri uma prova verdadeiramente maravilhosa, mas esta margem é muito pequena para contê-la. Pierre de Fermat, em torno de 1637. Explicitamente, afirma - se que para a equação não possui soluções inteiras. Grande parte dos teoremas anunciados por Fermat foram posteriormente provados pelo matemático suíço Leonhard Euler (1707 - 1783). 2. REFERENCIAL TEÓRICO Hoje em dia Teoria dos Números é uma área de conhecimento mais ampla do que na antiguidade. O domínio de suas aplicações está se multiplicando, nos diferentes ramos da Ciência. E esse crescimento se deve ao belo elo entre o passado da historia da matemática com o seu futuro. É bem verdade que na matemática não há como negar um resultado demonstrado, pois estamos lidando com verdadeiro ou falso não existindo um terceiro caso. Contudo, isso é feito baseando-se em suposições, definições, axiomas, postulados e princípios. Portanto, nessa mesma perspectiva iremos apresentar neste capítulo para que o nosso objetivo seja atingindo alguns conceitos básicos de teoria dos números aos quais faremos uma breve apresentação das definições, proposições e teoremas, exemplificando-os quando necessário e a partir delas deduzir a fórmula geral que fornece o número total de soluções inteiras de uma equação diofantina linear. Algumas vezes o leitor irá encontrar o símbolo “ ” que indica o fim de uma demonstração. 2.1. Divisibilidade em Z Definição 1: Dados a, b Z e b 0 dizemos que b divide a, ou que a é um múltiplo de b, ou ainda que b é um divisor de a se e somente se existe c Z tal que a b.c. Note que o c da definição é uma solução da equação b.x a. Esta equação pode não ter solução em N, por exemplo, 2.x 7 não tem solução em Z, mas sempre tem solução em Q. Logo a definição de divisibilidade não faria sentido em Q. Por esse motivo, só estudaremos divisibilidade em Z. Destacamos quatro consequências imediatas dessa relação. i. Para todo a Z, 1 divide a; já que a 1.a ii. Para todo a Z, a divide a; já que a a.1 iii. Para todo a Z, a divide 0; já que 0 a.0 iv. Para todo a, d Z, d divide a implica que |d| |a|. A partir de agora usaremos a notação a|b para indicar que a divide b. Note que b|a a b.c, c Z. Se b 0, o inteiro c nas condições da definição é único. Pois se existisse outro c’ Z tal que a b.c’, teríamos b.c’ b.c, daí obtemos que c c’. Esse c assim definido é chamado de quociente de a por b. Por outro lado, veja que 0|a se e somente se a 0. Neste caso o quociente não é único, pois 0.c 0, para todo c Z. Por isso excluímos o caso em que o divisor é nulo. De acordo com a definição de divisibilidade apresentamos as seguintes proposições. Proposição 1: Se a|1, então a 1. Demonstração:De fato, se a divide 1, existe q Z tal que 1 q.a. O que implica a 1 e q 1 ou a - 1 e q -1, ou seja a 1. Proposição 2: Se a, b, c e d são inteiros com a 0 e b 0, tais que a|b e c|d então ac|bd. Demonstração: Existe u, v Z tais que se a|b então b u.a e se c|d então d v.c. Multiplicando-se as equações membro a membro temos que b.d (u.v).ac daí ac|bd. Proposição 3: Se a, b e c são inteiros com a 0 e b 0, tais que a|b e b|c então a|c. Demonstração: Existe u, v Z tais que se a|b então b a.u e se b|c então c b.v. Logo, c a.(u.v) e assim a|c. Proposição 4: Sejam a e b inteiros e diferentes de zero, se a|b e b|a então a b. Demonstração: Existe u, v Z tais que se a|b então b a.u e se também b|a então a b.v. Logo a a.(u.v) que implica u.v 1, assim u|1 e daí temos que u 1 e que a b. Proposição 5: Sejam a e b inteiros e diferentes de zero, se a|b então |a| |b|. Demonstração: Existe u Z com u 0 tal que se a|b então b a.u, ou seja |b| |a|.|u|. Como u 0,temos que |u| 1, desse modo segue que |b| |a|. Proposição 6: Se a, b, c, x e y são inteiros com a 0, tais que se a|b e se a|c então a|(b.x + c.y). Demonstração: Existe u, v Z tais que se a|b então b a.u e se a|c então c a.v. Logo, quaisquer que sejam os inteiros x e y temos que b.x + c.y (a.u).x + (a.v).y a.(u.x) + a.(v.y) a.(u.x + v.y), o que implicaque a|(b.x + c.y). 2.2.Máximo Divisor Comum O conceito de Máximo Divisor Comum é extremamente usado nas mais variadas áreas do conhecimento. Desde analisar o ciclo de vida de alguns seres vivos até avaliar o desperdício em construções civis.As noções fundamentais de Máximo Divisor Comum são de suma importância para o seu estudo do nosso trabalho, pois compõem uma parcela significativa da Teoria Elementar dos Números, com isso pretendemos mostrar esta relevância através da seguinte abordagem de teórica. Definição 2: Diz-se que c é um divisor comum de a e b se c|a e c|b. O conjunto D(a, b) de todos os divisores comuns de a e b é limitado superiormente, pois se a 0 para todo elemento c D(a, b) temos que c |a|. Logo D(a, b) tem máximo. Chama-se máximo divisor comum de a e b o maior de seus divisores comuns. mdc (a, b) max D(a,b) Dados a, b Z diz-se que um inteiro d é MÁXIMO DIVISOR COMUM entre a e b se, e somente se, são válidas as seguintes condições; i. d 0 ii. d|a e d|b iii. Para todo número inteiro d’, se d’|a e d’|b então d’|d. Exemplificando: Sejam a 12 e b 4. Determine o mdc (12, 4). Solução: Sabemos que o divisor de um número inteiro é todo o número inteiro que ao dividir tal número, resultará em uma divisão exata. Com essa informação vamos determinar o conjunto dos divisores de a 12 e de b 4, sendo denotados por D12 e D4. Assim, D12 { 1, 2, 4, 6, 12} e D4 { 1, 2, 4}. Como o mdc (12, 4) é o maior inteiro que divide 12 e 4, para encontrar o máximo divisor comum entre esses números, basta determinar a intersecção D12 D4 e tomar o maior número em módulo desse conjunto. Logo, D12 D4 { 1, 2, 4} e máx (D12 D4) 4. Portanto mdc (12, 4) 4. 2.3.Algoritmo da Divisão de Euclides Não é muito que se sabe sobre a vida de Euclides, é provável que sua formação matemática tenha sido dada na escola platônica de Atenas e logo depois lecionou em Alexandria. Uma das obras mais importantes do mundo ocidental o tratado matemático de Euclides “Os elementos” composto por trezes livros sendo que o sétimo trata de um processo algébrico para achar o máximodivisor comum de dois ou mais números inteiros e ainda usa para verificar se dois inteiros são primos entre si, conhecido como algoritmo euclidiano. Teorema 1:(Algoritmo da Divisão de Euclides) Para quaisquer a, b Z, com b 0, existe um único par de inteiros q e r, de modo que a b.q + r, onde 0 r b. Demonstração: Será divida em duas partes. (1º) Prova da existência: Seja b um número inteiro positivo não nulo. Se a Z, então a é múltiplo de b ou está compreendido entre dois múltiplos consecutivos de b, isto é, b.q a b.(q + 1). Se b.q a, então a b.q + r, onde r Z e r 0. Se a b.(q + 1), temos que b.q + r b.q + b e daí r b. Logo, podemos afirmar que a b.q + r, com 0 r < b. 2ª) Prova da unicidade: Suponhamos que existam inteiros q1, q2, r1, r2, onde q1 q2 e r1 r2, com r1 r2 e que satisfaçam às igualdades: a b.q1 + r1, com 0 r1 b e a b.q2 + r2, com 0 r2 b. Se b r1 e b r2, então b r1 - r2 e temos que a b.q1 + r1 b.q2 + r2 o que implica que b.(q2 - q1) r1 - r2. Fazendo k (q2 - q1), temos que r1 - r2 b.k, com k Z, mostrando que b|(r1 - r2). Portanto b (r1 - r2) é absurdo, pois contradiz a hipótese. Logo, r1 r2 e concluímos também que b.(q2 - q1) 0. Se b 0, temos (q2 - q1) 0, mostrando que q2 q1. Proposição 7: Quaisquer que sejam a, b Z, existem d Z que é o máximo divisor comum de a e b. Demonstração: O caso em que a 0 e b 0. Seja K {a.x + b.y; x, y Z}. Tomando os elementos estritamente positivos de K. Seja d o menor desses elementos. Vamos mostrar que d é o máximo divisor comum entre a e b. i. Como d K+ então d 0 ii. Como d K, então existem x0 e y0 Z tais que; d a.x0 + b.y0 Aplicando o algoritmo da divisão aos elementos a e d; a d.q + r, com 0 r d Das duas últimas igualdades teremos; a (a.x0 + b.y0).q + r a a.x0 .q + b.y0. q + r r a.(1 – x0. q) + b.(-y0). q Dessa forma r K, r 0. Como r d e d é o menor elemento de K, temos: r d 0; Onde tiramos a d.q d|a Aplicando o algoritmo da divisão aos elementos b e d. b d.q’ + r’, com 0 r’ d b (a.x0 + b.y0). q’ + r’ r’ b – b.y0. q’ –a.x0. q’ r’ b.(1 – q’. y0) + a.(-x0). q’ Logo r’ 0 b d.q’ d|b iii. Se d’|a e d’|b temos; a d’. k b d’. q a. x0 d’.k. x0 e b.y0 d’.q.y0 a.x0 + b.y0 d’.(k.x0 + q.y0) d d’. (k.x0 + q.y0) Portanto d’|d o que implica d mdc (a, b). Lema 1. Sejam a e b dois inteiros positivos e a b.q + r, com 0 r b. Então mdc(a, b) mdc(b, r). Demonstração: Com efeito, se a b.q + r, então r a – b.q. Seja k um divisor comum de a e de b então k|a e k|b. Assim, k|r, ou seja, k é um divisor comum de b e de r. Reciprocamente, como a b.q + r, vemimediatamente que todo divisor comum de b e de r é divisor comum de b e de a. Assim, o conjunto dos divisorescomuns de a e de b é igual ao conjunto dos divisores comuns de b e de r. Logo, mdc(a, b) mdc(b, r). Demonstrado esse resultado, podemos enunciar e provar o algoritmo de Euclides: Teorema 2. Sejam a e b inteiros positivos, com a b. Usando sucessivamente o algoritmo da divisão, segue do lema 1 que o problema de achar o mdc(a, b) reduz-se a achar o mdc(b, r). Demonstração: Naturalmente, repetindo esse processo e fazendo divisões sucessivas, teremos: a b.q1 + r1, com 0 r1 b b r1.q2 + r2, com 0 r2 r1 r1 r2.q3 + r3, com 0 r3 r2 ................................ ................................. rn -2 rn -1.qn + rn, com 0 rn rn -1 rn -1 rn.qn+1 + rn+1, com rn+1 0 Como o resto diminui a cada passo, o processo não pode continuar indefinidamente, e alguma das divisões deve ser exata. Suponhamos então que rn+1 seja o primeiro resto nulo, como está indicado antes. Do lema 1,temos que: mdc(a, b) mdc(b, r1) mdc(r1, r2) ........... mdc(rn -1,rn) Demonstramos que, nesse processo o máximo divisor comum de a e b é o último resto diferente de zero. É usual o seguinte dispositivo de cálculo no emprego do algoritmo de Euclides para encontrar o mdc(a, b) de acordo com o Teorema 2: Geralmente, para dividir a por b utilizamos o seguinte esquema: a b r q Mudando o esquema temos; q a b r Aplicando o dispositivo prático do cálculo do mdc(a, b) dispomos os números; q1 q2 q3 ... ... qn qn+1 a b r1 r2 rn-2 rn-1 rn r1 r2 r3 rn 0 O procedimento exposto se traduz na seguinte REGRA: Para se “achar” o mdc de dois inteiros a e b positivos, divide-se o maior pelo menor, este pelo primeiro resto obtido, o segundo resto pelo primeiro, e assim sucessivamente até encontrar um resto nulo. O último resto não nulo é o máximo divisor comum procurado. Teorema 3: (Bézout) Sejam a e b dois números inteiros não nulos simultaneamente e seja d mdc (a, b); nestas condições, existem inteiros r e s tais que; d r.a + s.b Demonstração: Consideremos o conjunto A {(m.a + n.b) 0; m, n Z}. Note que A , logo pelo PBO existe d1 min A 0. Como d1 A, então existem r, s Z, tais que; d1 r.a + s.b E observando que d|a e d|b resultam que d|d1, daí temos d d1. Com essas afirmações, obtemos d1|a e d1|b. Suponha que d1 não divide nem a e nem b. Assim existiriam números inteiros q, q’ e t, t’ tais que; a q.d1 + t, com 0 t d b q’.d1 + t’, com 0 t’ d Segue-se; t a – q.d1 a – q.(r.a + s.b) a – q.r.a – q.s.b (1 – q.r).a + (- q.s).b e t’ b – q’. d1 b – q’.(r.a + s.b) b – q’. r.a – q’.s.b (- q’.r).a + (1 – q’.s) Como 0 t, t’ d1 temos que t, t’ A.(absurdo), pois 0 t d1 min A. Portanto, d1 é divisor comum positivo de a e b, logo d1 d e então d1 d. Além de servir de ferramenta computacional para o cálculo do mdc, a divisão euclidiana tem consequências teóricas importantes. O algoritmo de Euclides também pode ser usado para achar a expressão do mdc(a, b) rn como combinação linear de a e de b. Para isso basta eliminar sucessivamente os restos rn -1; rn - 2;...; r3; r2; r1 entre as n primeiras igualdades do Teorema 2. Exemplo 1: Achar o mdc(963, 657) pelo algoritmo de Euclides e sua expressão como combinação linear de 963 e 657. Aplicando as divisões sucessivas, temos: 1 2 6 1 4 963 657 306 45 36 9 306 45 36 9 0 963 657.1 + 306, então 306 963 – 657.1 657 306.2 + 45, então 45 657 – 306.2 306 45.6 + 36, então 36 306 - 45 .6 45 36.1 + 9, então 9 45 - 36 .1 36 9.4 + 0 Portanto, o mdc(963, 657) 9 e a sua expressão como combinação linear de 963 e 657 se obtém eliminando - se os restos 36, 45 e 306 entre as quatro primeiras igualdades anteriores do seguinte modo: 9 45 - 36 45 -(306 – 45 6) - 306 + 7.45 - 306 + 7.(657 – 306.2) 7.657 – 15.306 7.657 – 15.(963 - 657) 963.(-15) + 657.2. Assim, a expressão do mdc(963, 657) 9 como combinação linear é: 963.x + 657.y 9, onde x0 -15 e y0 2. Teorema 4: Os números inteiros a e b são primos entre si se, e somente se, existem r, s Z tais que: r.a + s.b 1 Demonstração: Como a, b Z são primos entre si por definição temos que mdc (a, b) 1. Fazendo uso do teorema de Bézout existem r, s Z tais que: r.a + s.b 1 Suponhamos que d mdc (a, b) e ainda temos que existem r, s Z tais que r.a + s.b 1. Como d|a e d|b isso implica d|(r.a + s.b) daí d|1 o que resulta d 1, assim o mdc (a, b) 1. Portanto a e b são primos entre si. Definição 3: Diz - se que dois números inteiros a e b são primos entre si se, e somente se, mdc (a, b) 1. Teorema 5: (Euclides) Sejam a, b, c Z tais que a|(b.c). Se mdc (a. b) 1 então a|c. Demonstração: Como a|(b.c) temos que existe k Z tal que b.c a.k. De mdc (a. b) 1 temos que existem r, s Z tais que r.a + s.b 1. Multiplicando por c e substituindo (b.c) nesta última igualdade obtemos: c r.a.c + s.b.c c r.a.c + s.a.k c (r.c + s.k). a c (x.a); x Z Logo a divide c. Corolário 1: Se a, b Z e mdc(a, b) d, então o mdc (a, b) d, então mdc ( , ) 1. Demonstração: Inicialmente nota-se que e são inteiros, pois d é um divisor comum de a e b. Agora como mdc(a, b) d, então existem inteiros x0 e y0 tais que a.x0 + b.y0 d. Dividindo-se ambos os membros desta igualdade por d, temos que: ( ).x0 + ( ).y0 1. Pelo Teorema 4, os inteiros e são primos entre si assim, o mdc ( , ) 1. Exemplificando: Seja os números 12 e 30, cujo mdc (12, 30) 6 daí pelo corolário acima temos que mdc ( , ) mdc (2, 5) 1. Teorema Fundamental da Aritmética Um número natural é um número primo quando ele tem exatamente dois divisores naturais distintos: o número 1 e ele mesmo. Já nos inteiros um número p Z é primo se ele tem exatamente quatro divisores distintos: 1 e p. Se um número inteiro tem módulo maior que um e não é primo, diz-se que é composto. Por convenção, os números 0, 1 e -1 não sãoconsiderados primos nem compostos. O Teorema Fundamental da Aritmética coloca em evidência o papel dos números primos na estrutura dos inteiros. Ele nos assegura que um número pode ser expresso como um produto de números primos de modo único, a menos da ordem desses fatores primos. O matemático que primeiro construiu uma tabela de primos foi Eratóstenes, que foi diretor da biblioteca de Alexandria no século III a. C. Criou uma técnica para achar todos os primos menores do que ou iguais a um numero inteiro dado n, que ficou conhecida como crivo de Eratóstenes. Teorema 6: Todo número inteiro maior do que 1 se escreve como o produto único de números primos, amenos da ordem desses fatores primos. Demonstração: Vamos supor que o teorema seja falso. Seja n o menor inteiro maior do que 1 que não pode ser escrito como produto de primos. Note que n não pode ser primo, pois se fosse seria a sua própria decomposição em fatores primos. Assim n seria composto podendo ser escrito como n a.b, com 0 a n e 0 b n. Nesse caso, a e b podem ser decomposto em produtos primos, pois ambos são menores que n já que pela hipótese o menor número que não pode ser decomposto em fatores primos é o n. Logo teríamos; a p1.p2.p3.p4...pn onde p1, p2, p3, p4,..., pn São números primos não necessariamente distintos e. b q1.q2.q3.q4...qn onde q1, q2, q3, q4,...,qn São números primos não necessariamente distintos. Daí tem; n a.b p1.p2.p3.p4...pn...q1.q2.q3.q4...qn Dessa forma teríamos n escrito como produto de primos, o que contraria a escolha do n. Logo todo inteiro maior do que 1 se escreve como produto de números primos. 2.4 Teoria da Congruência A teoria da congruência é fundamental no estudo dos números inteiros. E o seu desenvolvimento está intimamente relacionado ao nome do grande matemático alemão Carl Friedrich Gauss (1777 – 1855). Sua contribuição à teoria dos números foi essencial e seu trabalho mais importante sobre o assunto é o livro Disquisitionesarithmeticae, (investigações na aritmética) publicado em 1801. Com ele, essa teoria se tornou mais explicita com sua definição mais precisa e o simbolismo que usamos até hoje. Para nos dar uma ideia ilustrativa da noção de congruência vamos considerar a seguinte questão. Se hoje é sexta-feira, que dia da semana será daqui a 1520 dias? Para organizar o raciocínio vamos indicar o zero (0) para o dia de hoje (sexta) e o 1 para o dia de amanhã (sábado) e assim por diante. Veja a tabela: Sexta Sábado Domingo Segunda Terça Quarta Quinta 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ... ... ... ... ... ... ... Agora a nossa questão se resume em apenas encontrar a coluna em que está o numero 1520. Observe que dois números na sequência 0, 1, 2,..., estão na mesma coluna se, e somente se, sua diferença é divisível por 7. Assim vamos supor que o numero 1520 está na coluna encabeçada pelo numero 0 a 6. Fazendo uso da divisão euclidiana temos que para algum q Z, 1520 7.q + a, com 0 a 6. E ainda pela unicidade do resto na divisão euclidiana segue-se 1520 7.217 + 1. Logo se tem que após 1520 dias será um sábado. Definição 4: Seja m 0 um inteiro fixo. Dois inteiros a e b dizem-se congruentes módulos m se m divide a diferença a – b. Notação: a b (mod m) m|(a – b) Em outros termos a é congruente a b módulo m se, e somente se, existe um inteiro k tal que a b + k.m. Se m não divide a diferença de a e b então dizemos que a é incongruente módulo m e denotamos por a b (mod m). Demonstração: Queremos mostrar que a e b deixam o mesmo resto quando divididos por m se e somente se m|(a – b). Se a e b deixam o mesmo resto quando divididos por m, temos; a q.m + r b p.m + r com 0 r |m| Isso acontece para certos p e q inteiros. a – b q.m – p.m a – b (q – p).m m|(a – b) Se m|(a – b) então existe k Z tal que; a – b k.m a k.m + b Por outro lado, a divisão euclidiana garante que existem q e r pertencentes a Z tais que; a q.m + r com 0 r |m| Assim temos; k.m + b q.m + r b (k – q). m + r com 0 r |m| Note que a unicidade do resto da divisão euclidiana garante que a e b deixam o mesmo resto quando divididos por m. Exemplo: 3 24 mod 7, pois 7|(3 – 24) donde que – 21 7. (- 3). Proposição 8: Seja m 0 um inteiro e a, b, c Z. Então a congruência módulo m satisfaz; i. Reflexiva: a b (mod m) Demonstração: Como m|0, pois existe c Z tal que 0 m.c (0 m.0). Assim m|(a – a) a a (mod m). ii. Simétrica: Se a b (mod m) então b a (mod m). Demonstração: Se a b (mod m) então para algum k1 Z temos a b + k1.m. Daí; b a – k1. M b a + (- k1). M Assim existe um inteiro x - k1 tal que b a + x.m Logo por definição b a (mod m). iii. Transitiva: Se a b (mod m) e b c (mod m) então a c (mod m). Demonstração: Como a b (mod m) e b c (mod m) então existem k1 e k2 inteiros tais que; a – b k1.m b – c k2.m Somando membro a membro das duas últimas equações obtemos; a - c (k1 + k2).m Portanto a c (mod m). A relação de congruência módulo m é uma relação de equivalência, pois acabamos de mostrar que ela é reflexiva, simétrica e transitiva. Observações:  Dois inteiros quaisquer são congruentes módulo 1.  Dois inteiros são congruentes módulo 2, se ambos são pares ou ambos ímpares.  a 0 (mod m) se, e somente se, m|a. Mostrar que se a 7 (mod 12) então, a 3 (mod 4) para todo a Z. Note que 12|(a – 7) o que implica a – 7 12.k, k Z. Pelas propriedades operatórias fazemos; a – 3 – 4 12.k a – 3 4 + 12.k a – 3 4.(1 + 3.k) Assim, a – 3 4.x, tal que x Z Temos que 4|(a – 3), por definição de congruência obtemos a b (mod 4). Teorema 7: Se a,b,c, m são inteiros tais que a b (mod m) então; 1. (a + c) (b + c) (mod m). Demonstração: Como a b (mod m) então para algum k Z, temos a – b k.m; Note que a – b (a + c) – (b + c), assim escrevemos (a + c) – (b + c) k.m e isso implica (a + c) (b + c) (mod m). 2. (a – c) (b – c) (mod m). Demonstração: Note que (a – c) – (b – c) a – b e ainda a – b k.m; Fazendo; (a – c) – (b – c) k.m (a – c) (b – c) (mod m). 3. a.c b.c (mod m). Demonstração: Por hipótese temos a – b k.m, para algum k Z. Como c Z, podemos escrever a.c – b.c (c.k).m; O que implica a.c b.c (mod m). Teorema 8: Se a, b, c, d, m inteiros tais que a b (mod m) e c d (mod m) então; 1) (a + c) (b + d) (mod m) Demonstração: Como a b (mod m) e c d (mod m) segue-se; a – b k1.m c – d k2.m Somando membro a membro obtemos; (a + c) – (b + d) (k1 + k2).m Portanto (a + c) (b + d) (mod m). 2) (a – c) (b – d) (mod m) Demonstração: Por hipótese temos; a – b k1.m c – d k2.m Subtraindo membro a membro obtemos; (a – c) – (b – d) (k1 – k2).m Portanto (a – c) (b – d) (mod m). Proposição 9: Seja m um inteiro fixo e sejam a, b, c inteiros arbitrários. Se mdc (c, m) 1, então a.c b.c (mod m) implica a b (mod m). Demonstração: Se a.c b.c (mod m), temos que m|(a – b).c: Como o mdc (c, m) 1 pelo Teorema de Euclides vem que m|(a – b), donde vem a b (mod m). Proposição 10: Se a, b, k, m são inteiros com k 0 e a b (mod m) então ak bk (mod m). Demonstração: Fazendo uso da seguinte identidade: ak – bk (a – b).(ak – 1 + ak – 2.b + ak – 3.b2 +…+a.bk – 2 + bk– 1 ) Como a b (mod m) então m|(a – b) e ainda para algum q Z, temos; a – b m.q Das duas ultimas igualdade concluímos que: ak – bk m.x tal que x Z Portanto m|(ak – bk) ak bk (mod m). Teorema 11: Se a, b, c, m são inteiros e a.c b.c (mod m) então a b (mod ), com mdc (m, c) d. Demonstração: De a.c b.c (mod m) temos que a.c – b.c c.(a – b) k.m; Dividindo-se membro a membro por d, obtemos; .(a – b) k. Assim | .(a – b), note ainda que mdc ( , ) 1. Fazendo uso do Teorema de (Euclides) implica que: |(a – b) a b (mod ) Definição 5: Se h, k são dois inteiros com h k (mod m) dizemos que k é um resíduo de h módulo m. Definição 6: O conjunto dos inteiros {r1, r2,..., rs} é um sistema completo de resíduos módulo m se i. ri for incongruente a rjmódulo m , para todo i j ii. Para todo inteiro n existe um ri, i 1, 2,..., s tal que n ri (mod m). Observações: O sistema completo de resíduos mais simples que podemos obter é: {0,1, 2,...,m – 1} Mas não é o único possível. Os r1, r2,..., rm são congruente módulo m em alguma ordem, aos números; {0, 1,..., m – 1} Exemplo:  Para m 5, {0, 1, 2, 3, 4} é o conjunto dos menores restos não negativos módulo 5.  {-14, -13, 18, 24, 500} é um sistema completo de resíduos módulo 5. Teorema 12: Se k inteiros r1, r2,..., rk formam um sistema completo de resíduos módulo m então k m. Demonstração: Primeiro vamos mostrar que os inteiros t0, t1,..., tm-1, com ti i sendo 0 i m -1. Formando de fato um sistema completo de resíduos módulo m. Sabemos que pela divisão euclidiana para cada n inteiro existe um único par de inteiros q e s tal que; n m.q + s 0 s m n – s m.q Assim temos n s (mod m), sendo que s é um dos ti. Note que |ti – tj| m – 1, 0 i,j m – 1. O que implica ti tj (mod m) para i j. Pois se ti tj (mod m) m|(ti – tj). O que acarretaria ti – tj m.k para algum k inteiro. Assim |ti – tj| m e isso não acontece. De fato ti é incongruente tj módulo m, com i j. Portanto o conjunto {t0, t1,..., tm– 1} é um sistema completo de resíduos módulo m. Com isso cada ri é congruente a exatamente um dos ti, isso nos garante que; k m – 1 k m. Como o conjunto {r1, r2,..., rk} por hipótese forma um sistema completo de resíduos módulo m, por definição cada ti é congruente a exatamente um dos ri e isso implica; m – 1 k m k Portanto k m. Teorema 13: Se r1, r2,..., rm é um sistema completo de resíduos módulo m, a e b são inteiros com mdc (a, m) 1 então; a.r1 + b, a.r2 + b,.., a.rm + b. Também é um sistema completo de resíduos módulo m. Demonstração: Fazendo uso do teorema anterior. Agora vamos mostrar que quaisquer dois inteiros do conjunto; a.r1 + b, a.r2 + b,.., a.rm + b. São incongruentes modulo m. Suponhamos que (a.ri + b) (a.rj + b) (mod m), fazendo uso de propriedades de congruência temos; a.ri a.rj (mod m) Mas como mdc (a, m) 1, temos; ri rj (mod m) Implicando em i j (absurdo), pois o conjunto {r1, r2,..., rm} é S.C.R. Logo; a.ri + b a.rj + b (mod m) para i j. Portanto o conjunto a.r1 + b, a.r2 + b,.., a.rm + b. é S.C.R. A congruência módulo m permite a identificação de todos os números que deixam o mesmo resto quando divididos por m. Isso nos permite a criação de outros sistemas numéricos. Apresentaremos em seguida alguns exemplos que ilustram bem as potencialidades desta ferramenta. Exemplo 1: Encontrar o resto de 62009 quando dividido por 37. Veja que 62 36 (mod 37), e assim 62009 6. (62)1004 6. (-1)1004 6 (mod 37). Dessa forma o resto da divisão é 6, pois 62009 – 6 é múltiplo de 37. Exemplo 2: Ana, Bernardo e Carla arrumam laranjas para vender na feira, colocando 12 laranjas emcada saco. Ana tinha 389 laranjas, Bernardo 188 e Carla 97. Depois de arrumar todas as laranjas nos sacos, quantas sobraram ao todo? Para responder, temos que observar que precisamos considerar, para cada um deles, aquantidade de laranjas módulo 12. Como 389 5 ( mod 12); 188 8 (mod 12) e 97 1 (mod 12), quando Ana terminou de arrumar as laranjas nos sacos, sobraram 5 laranjas, das laranjas de Bernardo sobraram 5 e das de Carla sobrou 1. Portanto, no final sobraram 5 + 8 + 1 14 laranjas. Mas, 14 2 (mod 12). Isso significa que eles, em conjunto, poderiam completar mais um saco com 12 laranjas e sobrariam apenas 2laranjas. Exemplo 3: Sejam a, b e c números inteiros positivos cujos restos na divisão por 8 são 3, 5 e 1, respectivamente. Ache o resto da divisão de (a + b + c) por 8. Temos que a 3 (mod 8), b 5 (mod 8) e c 1 (mod 8). Somando membro a membroas três congruências, obtemos (a + b + c) 3 + 5 + 1 (mod 8) . Ou seja, (a + b + c) 9 (mod 8). Como 9 1 (mod 8), segue que (a + b + c) 1 (mod 8) . Logo o resto da divisão é 1. Exemplo 4: Verifique se o número 3099 + 61100 é um número divisível por 31. Observe que 30 -1 (mod 31). Portanto, 3099 (-1)99 (mod 31). Logo, 3099 - 1 (mod 31). Por outro lado, 61 -1 (mod 31). Portanto, 61100 (-1)100 (mod 31). Logo, 61100 1 (mod 31). Assim, 3099 + 61100 -1 + 1 (mod 31), que é o mesmo que 3099 + 61100 0(mod 31). Portanto, 3099 + 61100 é um número divisível por 31. Exemplo 5: Ache o dígito das unidades do número 3100. Suponha que a representação decimal de 3100 seja c0 + c1.10 + c2.102 + c3.103+ ...+ cn.10n, com c0, c1, c2, ..., cn inteiros não negativos, todos menores do que 10. O quequeremos encontrar é o valor de c0. Na linguagem das congruências, 3100 c0(mod 10). Agora, observe que 32 -1 (mod 10). Logo, 3100 (32)50 (-1)50(mod 10). Portanto, podemos escrever 3100 1 (mod 10) . Assim, o dígito das unidades de 3100 é 1. 2.5 Congruência Linear Chama-se de congruência linear em uma variável a uma congruência da forma; a.x b (mod m), onde x é uma incógnita. Se x0 é uma solução de a.x b (mod m) e x1 x0 (mod m) então x1 é também solução. De fato, pois se x1 x0 (mod m) então a.x1 a.x0 a.x b (mod m). Note que se um membro da classe de equivalência é solução então todo membro também é. Se x0 é uma solução da congruência linear a.x b (mod m), então todos os inteiros x0 + k.m, onde k é um inteiro arbitrário, também são soluções da congruência linear. Note que pela definição de congruência a.x0 b (mod m) se e somente se, o n divide a.x0 – b. Assim existe um inteiro y tal que a.x0 – b m.y. Desse modo, o problema de encontrar todas as soluções de uma congruência linearé idêntico ao de obter todas as soluções da equação diofantina a.x0 – m.y b. Duas soluções x0 e x1 da congruência a.x b (mod m) congruente módulo m isto é, x0 x1 (mod m) não são consideradas soluções distintas. O número de soluções da congruência é dado pelo número de soluções mutuamente incongruente módulo m, ou seja, quando falamos do número de soluções da congruência linear a.x b (mod m) estamos contando somente aquelas que são incongruente módulo m. Por exemplo, x 2 e x 7 satisfazem a congruência linear 4.x 3 (mod 5). Como 2 7 (mod 5), tratamos 2 e 7 como a mesma solução da congruência linear 4.x 3 (mod 5). Definição 7: Dizemos que uma solução x0 de a.x b (mod m) é única módulo m quando qualquer outra solução x1 for congruente a x0 módulo m. Teorema 14: Sejam a, b inteiros positivos e mdc (a, b) d. Se d não divide c então a equação a.x + b.y c não possui nenhuma solução inteira. Se d|c ela possui infinitas soluções e se x x0 e y y0 é uma solução particular então todas as soluções são dadas por; x x0 + ( ). k y y0 – ( ). k Onde k é um inteiro. Demonstração: Se d não divide c, então a equação a.x + b.y c não possui solução, pois como o mdc (a, b) d implica que d|a e d|b. Assim d deveria dividir c, já que ser está escrito como combinação linear de a e b. Suponha que d|c pelo Teorema 3 (Bezout) existem inteiros n0 e m0 tais que a.n0 + b.m0 d De d|c existe um inteiro k tal que c k.d. Multiplicando ambos os membros da igualdade acima por k obtemos. a.(n0.k) + b.(m0.k) k.d c Assim o par (x0, y0), sendo x0 n0.k e y0 m0.d é uma solução de a.x + b.y c. Note que é fácil verificar que os pares da solução da equação a.x + b.y c é da forma x x0 + ( ). k y y0 – ( ). k Veja que a.x + b.y a.(x0 + ( ). k) + b.( y0 – ( ). k) a.x0 + ( ).k + b.y0 - ( ). a.x0 + b.y0 Note que acabamos de mostrar que a partir de uma solução particular (x0, y0) podemos gerar infinitas soluções. Agora só basta mostrar que toda solução da equação a.x + b.y c é da forma x x0 + ( ). k y y0 – ( ). k Vamos supor que (x, y) é a solução de a.x + b.y c e ainda (x0, y0) é uma solução particular a.x0 + b.y0 c. Subtraindo as duas ultimas igualdade temos; a.x + b.y – a.x0 – b.y0 a(x – x0) + b.(y – y0) 0. O que implica em a.(x – x0) b.(y – y0). Como o mdc (a, b) d podemos escrever que mdc ( , ) 1. Dividindo a igualdade acima por d. .(x - x0) . (y – y0) | . (x – x0) Usando o Teorema de Euclides | (x – x0), portanto existe um k inteiro tal que; x – x0 k. x x0 +. k. Substituindo x na equação acima obtemos; y y0 – .k Teorema 15: A congruência linear a.x b (mod m) tem solução se, e somente se, d divide b, sendo d mdc(a, m). Demonstração: Por hipótese temos a.x b (mod m), assim m|(a.x - b) a.x – b m.k, sendo k Z - b m.k – a.x b a.x – m.k (1) Como o mdc (a, m) d, então d|a e d|m. Assim existem p, q Z tais que; a d.p m d.q Substituindo as duas ultimas equações na expressão (1), obtemos; b a.x – m.k b (d.p).x – (d.q).k b d.(p.x – d.q) b d.(r) tal que r Z Dessa forma d|b. Sabemos que uma equação da forma a.x + b.y c, onde a, b, c são inteiros é chamada de equação diofantina linear. Se x é solução da congruência a.x b (mod m), existe y Z tal que o par (x, y) é solução da equação diofantina a.x + b.y c. Isso nos leva dizer que a congruência linear a.x b (mod m) é equivalente à equação diofantina a.x – m.y b. Por hipótese temos d|b, assim o Teorema 14 nos garante que a equação diofantina a.x – m.y b possui infinitas soluções. Assim existem x0, y0 Z tais que; a.x0 – m.y0 b. m.(y0) a.x0 – b m|(a.x0 - b) Por definição de congruência obtemos a.x0 b (mod m), sendo x0 solução da congruência. Teorema 16: Sejam a, b, m inteiros tais que m 0 e mdc (a, m) d. No caso em que d não divide b a congruência a.x b (mod m) não possui nenhuma solução e quando d|b possui exatamente d solução incongruente módulo m. Demonstração: Sabemos que o inteiro x é solução de a.x b (mod m) se e, somente se existe um inteiro y tal que a.x b + m.y, ou seja, a.x – m.y b. Sabemos que de acordo o Teorema 14 esta equação não possui nenhuma solução caso d não divide b e se d|b então a dita equação possui infinitas soluções dadas por; x x0 – ( ).k y y0 – ( ).k Onde (x0, y0) é uma solução particular de a.x – m.y b. Assim a congruência a.x b (mod m) possuem infinitas soluções dadas por x x0 – ().k dm Estamos interessados em saber o número de soluções incongruentes. Tome x1, x2 soluções congruente módulo m. Então x0 – ( ).k1 x0 – ( ).k2 (mod m). O que implica ( ).k1 ( ).k2 (mod m). E como ( )|m e mdc ( , m) temos que pelo Teorema 11 nos permite o cancelamento. k1 k2 (mod m) Obs: O m foi substituído por d m| . Assim concluímos que as soluções incongruentes serão obtidas ao tomarmos x x0 – ( ). k, onde k percorre um sistema completo de resíduos módulo d. Teorema 17: Se mdc (a, m) 1 então a congruência linear a.x b (mod m) tem exatamente uma solução incongruente. Demonstração: Seja C um sistema completo de resíduos módulo m. Pelo teorema 13 o conjunto {a.x; x C} é também um sistema completo de resíduos módulo m. Por definição existe um único elemento x0 C tal que a.x0 é congruente a um inteiro dado b módulo m, ou seja, a.x0 b (mod m). Portanto, a congruência linear a.x b (mod m), onde mdc (a, m) 1, tem exatamente uma solução incongruente, a saber, x x0 (mod m). Teorema 18: Se a.c b.c (mod m) e mdc (c, m) d, então a b (mod ). Demonstração: Se a.c b.c (mod m), então m|(a.c – b.c); isto é, m|c.(a - b). Como o mdc (c, m) d, então c d.c’ e m d.m’. Assim, temos: d.m’|d.c’. (a - b) m’|c’. (a - b), Onde mdc (c’, m’) 1 Portanto, m’|(a - b). E daí, a b (mod m’); Isto é, a b (mod ) Exemplo 1: Resolver a congruência linear 36.x 53 (mod 131). Como o mdc (36, 131) 1, pelo Teorema 17 a congruência linear tem exatamente uma solução incongruente. Como 53 -78 (mod 131), pela transitividade de relação de congruência, 36.x -78 (mod 131) Pelo Teorema 11, 6.x -13 (mod 131) Usando as propriedades transitiva e simétrica da relação de congruência e o fato de que -144 -13 (mod 131), obtemos 6.x -144 (mod 131) Outra vez, pelo Teorema 11, x -24 (mod 131), x 107 (mod 131) Exemplo 2: Encontrar as soluções incongruentes da congruência linear 64.x 16 (mod 84). Como mdc (64, 84) 4 e ainda 4|16, pelo Teorema 16 existe exatamente quatro soluções incongruentes módulo 84. Pelo Teorema 11. 4.x 1 (mod 21). Temos que mdc (64, 16) 16 e mdc (16, 84) 4 e 21 Pelo Teorema 11 e pelas propriedades da relação de congruência, 4.x -20 (mod 21), x -5 (mod 21), x 16 (mod 21). Assim as quarto soluções incongruentes do sistema completo de resíduos módulo 84 { 0 , 1, 2, ..., 83} são inteiros da forma 16 + 2.t, onde t 0, 1, 2 e 3. Segue que o conjunto solução é {16, 37, 58, 79}; Isto é as soluções incongruentes são x 16 (mod 84), x 37 (mod 84).x 58 (mod 84), x 79 (mod 84). Exemplo 3:  3.x 1 (mod 17). O mdc (3, 17) 1 e 1|1 logo a congruência possui uma solução. Veja que: 1 3.6 (mod 17) por transitividade 3.x 3.6 (mod 17) x 6 (mod 17)  3.x 6 (mod 18) O mdc (3,18) 3 e 3|6 logo a congruência possui três soluções. Dividindo por 3 a congruência dada temos; x 2 (mod 6) Assim a solução geral é dada por x 2 + 6.t; t 0, 1, e 2. Obtendo x 2, x 8 e x 14. Exemplo 4:  Resolver a congruência linear 7.x 9 (mod 21). Veja que o mdc (7, 21) 7 e como 7 não divide 9, então não existe solução para a congruência linear dada. 3.EQUAÇÕES DIOFANTINAS LINEARES Diofantofoi um matemático e filósofo Grego. É considerado o maior algebrista grego, verdadeiro precursor da moderna teoria dos números e para alguns o consideramcomo pai da álgebra, principalmente devido à sua inovação com as notações, o primeiro a usar símbolos na resolução de problemas algébricos. Interessou-se por uma grande variedade de equações indeterminadas que eventualmente admitem infinitas soluções, porém ele procurava soluções racionais. Por isso faz-se justiça associar os problemas relativos aos números inteiros ao nome de Fermat que foi o primeiro a chamar atenção às questões aritméticas estritamente no conjunto dos números inteiros, no preâmbulo de um problema que propôs em 1657. Uma equação diofantina linear em duas variáveis é uma expressão da forma a.x + b.y c, na qual a, b, c são inteiros, com a e b não simultaneamente nulos e cujas soluções estão restritas ao conjunto dos números inteiros. Uma soluçãodessa equação é então um par de inteiros (x0, y0) tal que a.x0 + b.y0 c. Vale ressaltar que, apesar deste tipo de equações que visa soluções inteiras receberem o nome de Diofantinas devido a Diofanto de Alexandria, o primeiro matemático a encontrar uma solução geral de uma EDL foi o hindu Bramagupta (598 – 670), cuja resolução foi embasada no algoritmo de Euclides. Segundo Fernandes (2005), certamente muitas dessas equações podem ser resolvidas por tentativas, método muito utilizado na idade média. Todavia, há muitos problemas cujas possibilidades são limitadas, de modo que não são necessárias.Certamente muitas equações Diofantinas podem ser resolvidas por tentativa. Veja o seguinte exemplo. Vamos encontrar todas as soluções inteiras positivas da equação: 15.x + 12.y 96. Ora, essa equação é equivalente a 5.x + 4.y 32 x . Como estamos restritos aos números inteiros positivos, devemos ter: y 0 e x 0 y 0 e 32 – 4.y 0. Portanto o y {1, 2, 3, 4, 5, 6, 7}, com isso calcula-se o valor correspondente para x. Para y 1 temos x Para y 2 temos x Para y 3 x 4 Para y 4 temos x Para y 5 x Para y 6 temos x Paray 7 x Observemos que existe uma única solução x 4 e y 3. Usamos o método de tentativa para encontrar uma solução particular da equação dada no exemplo acima. Esse é, muitas vezes, o melhor caminho a seguir. A resolução de muitos problemas de aritmética depende da resolução de equações do tipo a.x + b.y c,onde a, b e c são números inteiros dados e x e y são incógnitas a serem determinadas em Z. É claro que se a 0 ou b 0 a equação tem resolução imediata. Por exemplo, se a 0 e b 0 então existe solução inteiras e b|c e, neste caso a solução geral é dada por x Z e y . Análogo para b 0, onde neste caso a solução geral é dada por y Z e x . Mas, antes de procurar uma solução para a equação diofantina, é conveniente saber se essa existe. Por isso desenvolveremos aqui resultados que possibilitem a nós respondermos as seguintes perguntas: Quais são as condições para que essa equação possua solução? Quantas são as soluções? Como calcular as soluções, caso existam? O resultado a seguir dá a condição necessária e suficiente para a existência de soluções de uma dada equação diofantina linear. Dada uma equação diofantina do primeiro grau a duas incógnitas x, y tais que: a.x + b.y c Com a, b e c números inteiros a fim de obter a solução de tais equações determinarão todos os pares ordenados (x, y) Z Z. Indicaremos por A o conjunto de todos os pares ordenados (x0, y0) Z Z tais que a.x0+ b.y0 c. Assim todo elemento de A é chamado de Solução Inteira da equação diofantina. Suporemos sempre que a, b não sejam simultaneamente nulos, pois se a b 0 a equação diofantina a.x+ b.y c tem solução se, e somente se, c 0 e, neste caso A Z Z. Apresentaremos agora uma condição para que o conjunto-solução A não seja vazio, isto é, que a equação diofantina admita solução. 3.1. Condição de Existência de Solução Teorema 19: A equação diofantina linear a.x + b.y c possui solução se, e somente se, o máximo divisor comum de a e b divide c. Demonstração: Suponhamos que (x0, y0) seja uma solução da equação, isto é: a.x0 + b.y0 c. Seja o mdc (a, b) d por definição de máximo divisor comum temos que d|a e d|b, então d divide qualquer combinação linear formada pelos inteiros a e b. Portanto d|(a.x0 + b.y0) c. Seja mdc(a, b) d. Se d|c, então c d.mpara algum inteiro m; além disso, existem inteiros x0 e y0 tais que a.x0 + b.y0 d. Logo, a.(x0.m) + b.(y0.m) d.m c e, portanto, (m.x0, m.y0) é uma solução da equação. Observação: No caso do mdc(a, b) d e d|c, a equação diofantina linear a.x + b.y c admite um número infinito de soluções, uma para cada valor arbitrário do inteiro t. Observação: Na Geometria Analítica, a equação a.x + b.y c representa uma reta r. Ao procurarmos soluções em Z da equação a.x + b.y c, estamos perguntando se a reta r, por ela representada, contém pontos que tenham ambas as coordenadas inteiras. O Teorema 1 nos diz que existem equações dessa forma sem soluções inteiras, por exemplo, a equação 12.x + 8.y 7 não tem soluções inteiras, já que mdc(12, 8) 4 que não divide 7. Fica, então, provado o fato surpreendente que a reta r de equação 12.x + 8.y 7 consegue evitar todos os pontos do plano cartesiano tal que o par (x, y) tenha coordenadas inteiras. 3.2.Soluções da equação a.x + b.y c Seja (x0, y0) uma solução particular da equação diofantina linear a.x + b.y c, em que a.b 0. Então qualquer solução inteira dessa equação é dada por X x0 + .k Y y0 - .k Onde mdc (a, b) d e k é um inteiro qualquer. Demonstração: Consideremos a equação diofantina; a.x + b.y c, com a.b 0 Primeiro vamos mostrar que se (x0, y0) é solução particular da equação então o par (x0 + .k, y0 - .k) é também solução para qualquer inteiro k. De fato, como a .d e b .d. Fazendo: a.( x0 + .k) + b.( y0 - .k) a.x0 + a. .k + b.y0 - b. .k a.x0 + b.y0 c Portanto (x0 + .k, y0 - .k) é também solução da equação diofantina dada. Agora vamos mostrar que se (X, Y) é solução da equação diofantina: a.x + b.y c, com a.b 0; Então existe um inteiro k tal que X x0 + .k Y y0 - .k É a solução geral. Note que vale se (x0, y0) e (X, Y) são soluções da equação então temos; a.X + b.Y a.x0 + b.y0 a.(X - x0) b.(y0 – Y) .d.(X - x0) d.(y0 – Y) .(X – x0) .(y0 – Y) Veja que divide o lado direito da igualdade e também o lado esquerdo. E ainda e são primos entre si, pois o mdc (a, b) d. Assim pelo Teorema de Euclides | (X – x0). Logo existe um inteiro k tal que; X – x0 .k X x0 + .k Tomando X e substituindo na igualdade acima obtemos Y. .(x0 – (x0 + .k)) .(y0 – Y) . .k .(y0 – Y) .k y0 - Y Y y0 - .k Proposição 11: Se (x0, y0) é uma solução da equação diofantina linear a.x + b.y c, então o par (x0 + b.t, y0 – a.t) também é solução dessa equação, para qualquer inteiro t. Demonstração: Como (x0, y0) é solução da equação a.x + b.y c, temos que a.x0 + b.y0 c. Assim, para qualquer inteiro t, vale: a.(x0 + b.t) + b.(y0 – a.t) a.x0 + a.b.t + b.y0 – a.b.t a.x0 + b.y0 c (note que somamos e subtraímos o inteiro a.b.t) O implica em (x0 + b.t, y0 – a.t) também ser uma solução da equação. Outra demonstração: Considere d mdc(a, b) 1, caso contrário divida a equação por “d” e sabemos que mdc( , ) 1. Sendo (x0, y0) solução temos que; a.x + b.y c a.x0 + b.y0 a.x – a.x0 b.y0 – b.y a.(x – x0) b.(y0 - y) Daí a|b.(y0 - y), mas a b, logo a|(y0 - y) temos y0 – y a.t implicando em y y0 – a.t com t Z. Analogamente, b|a.(x – x0) e b a temos então b|(x – x0) o que resulta em x – x0 b.t e ainda x x0 + b.t. Corolário1: Se mdc (a, b) 1, se a, b são relativamente primos então a equação a.x + b.y c sempre tem soluções inteiras para qualquer que seja c. Demonstração: Para resolver a equação diofantina linear a.x + b.y c, com a, b, e c inteiros e mdc(a, b) 1, equivale encontrar inteiros r e s tais que a.r+ b.s 1. Para isso vamos fazer o uso do algoritmo de Euclides. Sejam a, b inteiros com b 0. Pelo algoritmo da divisão existem q e r com 0 r b, únicos tais que a b.q + r. Se p é divisor comum de a, b então p|a e p|b. Como p|b implica que p|b.q. Fazendo–se a – b.q r, como p|a e p|b.q logo p|c. Assim p é divisor comum também de b, r isto é, mdc (a, b) mdc(b, r). Reciprocamente se p|b e p|r, como a b.q + r então p|a. Portanto o mdc (a, b) mdc(b, r). Assim concluímos que existem de fato r e s inteiros tais que a.r+ b.s 1. Para efeito de encontrar soluções inteiras, apenas o caso em que o mdc(a, b) 1 nos interessa. Pois se a equação possui solução e o máximo divisor comum for diferente de 1, isto é, (d 1) basta dividir ambos os membros da equação por d assim nos deparamos no caso de coeficientes a e b relativamente primos, e com o segundo membro ainda um número inteiro. Na busca de soluções inteiras de uma equação diofantina do primeiro grau, a saber, a.x + b.y n, vimos que podemos tomar o mdc(a, b) 1 e assim descobrir uma solução inteira dessa equação equivale a encontrar inteiros r e s tais que a.r + b.s 1. Para determinar uma solução particular em caso que a e b são números relativamente pequenos procede-se por inspeção. Se não for possível esse método, para encontrarmos os números r e s utilizamos o algoritmo de Euclides para o cálculo do mdc(a, b) d. Com a aplicação desse algoritmo obtemos inteiros m0 e n0 tais que a.m0 + b.n0 mdc(a, b) d. Multiplicando-se em ambos os lados dessa igualdade obtém-se: ( .m0.a) + ( .n0.b) ( .d) ( .m0).a + ( .n0).b n Portanto o par ordenado dado por x0 ( . m0) e y0 ( . n0) é a solução particular da equação. Satisfeita a condição de existência de solução para uma equação diofantina linear, para descobrir as soluções gerais deve-se inicialmente obter uma solução particular da mesma. E a partir dela encontrar todas as soluções da equação. Mas para isso fazemos uso do algoritmo de Euclides. Usualmente, o algoritmo para dividir dois números inteiros é dado por: Generalizando o algoritmo de Euclides obtemos: Vamos usar um exemplo de uma equação diofantina presente no artigo de Rocque e Pitombeira (1991) para evidenciar o processo de obter uma solução particular através das divisões sucessivas.  Determinar as soluções da equação diofantina 32.x + 9.y 7. Fazendo uso do algoritmo de Euclides para o calculo do mdc (32, 9) obtemos: 32 (3.9) + 5 (A) 9 (1.5) + 4 (B) 5 (1.4) + 1 (C) Nota-se que mdc(32, 9) mdc(9, 5) mdc(5, 4) mdc(4, 1) 1. Portanto pelo corolário anterior a equação dada possui solução. O próximo passo desse processo é escrever as equações (A), (B) e (C) em função dos restos das divisões euclidianas. 5 32 – (3.9) (A’) 4 9 – (1.5) (B’) 1 5 – (1.4) (C’) Combinando-se as equações, substitui-se (B’) em (C’); 1 5 – (1.4) 1 5 – [1.9 – (1.5)] 1 5 – (1.9) + (1.5) 1 (2.5) – (1.9) (D) Substituindo a equação (A’) em (D) obtém-se 1 (2.5) – (1.9) 1 2.[32 – (3.9)] – (1.9) 1 (2.32) – (6.9) – (1.9) 1 (2.32) – (7.9) 1 (2).(32) + (- 7).(9) (E). Note que os valores 2 e -7 correspondem r e s na demonstração do corolário anterior. Assim para encontrarmos uma solução particular da equação basta multiplicarmos a equação (E) por 7. 1 (2). (32) + (- 7). (9) 7.(2).(32) +7.(- 7).(9) 7.1 32.(14)+ 9.(- 49) 7 Logo a solução particular almejada é dada pelo par ordenado (14, - 49). Enquanto a solução geral é dada por: x x0 + b.k 14 + 9.k y y0 – a.k - 49 - 32.k, para qualquer k inteiro. Uma solução particular da equação diofantina linear se obtém por tentativas ou pelo algoritmo de Euclides. Em ambos os casos a solução geral da equação diofantina a.x + b.y c é obtida por proposição 3 e ou 4. Exemplo 1: Vamos encontrar uma solução particular da equação 5.x + 3.y 100. Como o mdc(5, 3) 1, a equação dada possui solução, pois 1|100. O nosso objetivo é encontrar inteiros x0, y0 tais que 5.x0 + 3.y0 1. Pelo algoritmo de Euclides temos; 5 1.3 + 2 3 1.2 + 1 2 1.2 + 0 Ou seja, 1 3 – 1.2 3 – 1.(5 – 1.3) 3 + 3 + 5.(-1) 5.(-1) + 3.2 Multiplicando por 100; 5.(-100) + 3.(200) 100 Logo a solução particular procurada é (-100, 200). Note que uma equação diofantina linear 39.x + 26.y 105 não possui solução, pois o mdc(39,26) 13 e como 13 não divide 105, segue-se que a equação dada não tem solução. Exemplo 2: Determinar todas as soluções inteiras e positivas da equação diofantina 18.x + 5.y 48. Determinamos o mdc (18, 5) pelo algoritmo de Euclides: 3 1 1 2 18 5 3 2 1 3 2 1 0 Daí tem: 18 5.3 + 3, então 3 18 - 5.3 5 3.1 + 2, então 2 5 - 3.1 3 2.1 + 1, então 1 3 - 2.1 2 1.2 + 0 Concluímos que o mdc (18, 5) 1 e que a equação possui solução, pois 1|48. Vamos escrever o 1 como combinação linear de 18 e 5. 1 3 - 2 3 - (5 - 3) 2.3 - 5 2.(18 - 5.3) - 5 18.2 + 5.(- 7) 18.2 + 5.(-7) 1 Multiplicando-se a equação por 48 obtemos; 18.96 + 5.(-336) 48 Logo o par de inteiros x0 96 e y0 - 336 é uma solução particular da equação e aplicando o a proposição 1.0 as demais soluções são dadas pelas formulas x x0 + b.t 96 + 5.t y y0 – a.t - 336 – 18.t, com t Z. As soluções inteiras são encontradas escolhendo o t de modo que satisfazem as desigualdades x 0 e y 0, assim têm que 96 + 5.t 0 e -336 –18.t 0 Isto é: t -19,2 e t -18, 6o que implica que t - 19 e, portanto: x 96 + 5.( - 19) 1 y - 336 – 18.( - 19) 6 Assim, o par de inteiros x 1 e y 6 é a única solução inteira e positiva da equação 18.x + 5.y 48. Exemplo 3: Dada a equação diofantina 14.x + 22.y 50, determine: a) A solução geral; b) A menor solução natural para x. Primeiro usamos o algoritmo de Euclides para calcular omdc(14, 22). 22 14.1 + 8 14 8.1 + 6 8 6.1 + 2 6 2.3 + 0, assim o mdc (14, 22) 2 Veja que a equação tem solução, pois 2|50. Escrevemos agora o mdc como combinação linear de 14 e 22. 2 8 - 6 8 – (14 - 8) -14 + 2.8 - 14 + 2.(22 - 14) 2.22 – 3.14 14.(-3) + 22.(2) 2 Multiplicamos a última equação por 25 para obter o termo independente da equação diofantina linear dada. 14. (- 75) + 22.(50) 50 Utilizamos as fórmulas da proposição 1.1 e encontramos a solução geral. X x0 + .t - 75 + .t - 75 + 11.t Y y0 - .t 50 - .t 50 – 7.t, para qualquer inteiro t. Para encontrarmos a menor solução natural para x. Fazemos; X 0 e y 0 - 75 + 11.t 0 50 – 7.t 0 t 7.t 50 t 6,8 t t 7,1 Assim, devemos ter t 7. Substituindo na expressão da solução geral obtemos x 2 e y 1. 3.3. Usar a congruência linear para resolver equações diofantinas A teoria das congruências lineares pode ser usada como uma forma de obter as soluções de uma equação diofantina linear caso elas existam. Uma solução de uma equação diofantina linear é par de inteiros x0, y0 que satisfaz a equação: a.x0 + b.y0 c e a.x0 – c - b.y0. O que implica na congruência ax0 b (mod m). Determinaremos agora uma solução qualquer x x0 da congruência a.x c (mod m) depois substituímos x0 na equação a.x + b.y c a fim de encontrar o valor correspondente y0 tal que a.x0 + b.y0 c. Apresentaremos agora alguns exemplos de resolução de Equações Diofantinas com a utilização das congruências lineares. Exemplo 1: Determine a solução geral da equação diofantina 12.x + 25.y 331 por congruência linear. Solução: Como o mdc(12, 25) 1 e 1|331, então a equação diofantina possui solução. 12.x – 331 25.(- y) daí 12.y 331(mod 25); 331 12.13 (mod 25); 12.x 12.13 (mod 25), por fim, x 13 (mod 25). Assim x0 13 é uma solução particular da equação diofantina linear. Substituindo este valor na equação diofantina, obtemos; y0 7. A solução geral é: x 13 + 25.t, y 7 – 12.t com t inteiro. Exemplo 2: 7.x + 6.y 9 Note que mdc(7, 6) 1 e 1 | 9, logo a equação diofantina possui solução. 7.x – 9 6.(- 7) daí temos 7.x 9 (mod 6); 9 7.3 (mod 6); 7.x 7.3 (mod 6); x 3 (mod 6). Assim x0 3 é uma solução particular. Substituindo este valor na equação obtemos y0 - 2. Portanto a solução geral é: x 3 + 6.t, y - 2 – 7.t para qualquer inteiro. 3.4.Equações Diofantinas Linear com 3 variáveis Seja a equação geral dada por; a1.x1 + a2.x2 + a3.x3 + ... + ak.xk c (I) Onde os ai´s são inteiros não nulos, e o mdc(a1, a2, ..., ak) d. Evidentemente se d c então a equação (I) não admite soluções inteiras. Mas por outro lado, se d|c e considerarmos d 1. Podemos encontrar as soluções através do seguinte método que reduz o número de variáveis da equação (I). Consideremos os inteiros a, b, p, q e escrevemos na forma de combinação linear tais que; a.q – b.p 1 E ainda denotarmos as variáveis x1 e x2 da seguinte forma; x1 a.u1 + b.u2 x2 p.u1 + q.u2 Então como x1 e x2 são inteiros acarretará em u1 e u2 também inteiros. Agora substituiremos as expressões de x1 e x2 na equação (I) e obtemos; a1.x1 + a2.x2 + a3.x3 + ... + ak.xk c (I) a1.(a.u1 + b.u2) + a2.(p.u1 + q.u2) + ... + ak.xk c a1.a.u1 + a1.b.u2 + a2.p.u1 + a2.q.u2 + a3.x3 + ...+ ak.xk c (a1.a + a2.p).u1 + (a1.b + a2.q).u2 + a3.x3 +...+ ak.xk c (II) Assim o conjunto (u1, u2, x3,..., xk) é uma solução da equação (II) se e somente se, (x1, x2, x3, ..., xk) é solução de (I). Note que a escolha dos inteiros a, b, p e q deve obedecer à condição de a.q – b.p 1. Considerando que a , p sendo d mdc (a1, a2), temos que o mdc (a, p) 1. Agora pelo algoritmo de Euclides encontramos q e b. A partir dessas escolhas podemos escrever a equação geral da seguinte forma; (- p.d).(a.u1 + b.u2) + a.d.(p.u1 + q.u2) + a3.x3 + ... + ak.xk c - a.p.d.u1 – b.p.d.u2 +a.d.p.u1 + a.d.q.u2 + a3.x3 + ...+ ak.xk c a.q.d.u2 – b.p.d.u2 + a3.x3 +...+ ak.xk c (a.q – b.p). d.u2 + a3.x3 +...+ ak.xk c 1. d.u2 + a3.x3 +...+ ak.xk c Dessa forma na última equação vale; (d, a3,..., ak, c) 1, com mdc (a1, a2) d Fazendo a repetição desse processo obtemos as soluções na forma paramétrica dada por x1 a11.u1 + a12.u2 +...+ a1k – 1.u k – 1 + b1 x2 a21.u1 + a22.u2 +...+ a2k – 1.u k – 1 + b2 ... ... ... ... xk a21.u1 + ak2.u2 +...+ akk – 1.uk – 1 + bk Onde os aij e os bi´s são inteiros e os ui´s são variáveis tomando valores inteiros. Exemplo 1: Encontrar todas as soluções inteiras de 10.x + 6.y + 5.z 8. O mdc (10, 6) 2. Escrevendo como combinação linear obtemos 10.x + 6.y 2. . Note que essa equação é equivalente a 5.x + 3.y , seno um inteiro. Uma solução particular desta é o par ordenado (- , 2. ), daí a solução geral para a equação diofantina 5.x + 3.y é dada por; x - + 3.u y 2. – 5.u, com u Z Note que a equação inicial pode ser escrita assim: 2. + 5.z 8 Que nos dá a solução geral 24 + 5.t, com t Z z - 8 – 2.t Dessa forma a solução geral da equação linear diofantina 10.x + 6.y + 5.z 8 é dada por: x - 24 – 5.t + 3.u y 48 + 10.t - 5.u z - 8 – 2.t Exemplo 2: Encontrar todas as soluções inteiras de 101.x + 102.y + 103.z 1. O mdc (101, 102) 1. Escrevendo como combinação linear obtém 101.x + 102.y , com um inteiro e (- , ) uma solução particular e a geral é dada por x - + 102.u e y – 101.u, sendo u um inteiro. Fazendo + 103.z 1, cuja solução particular é 0 104 e z - 1 o que nos oferece as equações; 104 + 103.t z - 1 – t com t inteiro Daí, x - 104 + 103.t + 102.u y 104 + 103.t - 101.u z - 1 – t Mostre que o número de soluções positivas de A.x + B.y N é no máximo finita. Demonstração: Seja a.x + b.y n, com x 0 e y 0. Tome (x0, y0) uma solução. Assim, a.x0 + b.y0 n (I). Somando e subtraindo o inteiro k.a.b na equação I com k Z, temos; a.x0 + b.y0 + k.a.b – k.a.b n a.x0 + a.k.b + b.y0 – b.a.k n a.(x0 + b.k) + b.(y0 – a.k) n Portanto a forma da solução geral é dada por; x x0 + b.k y y0 – a.k Para x 0, temos x0 + b.k 0 b.k - x0 k Para y 0, temos y0 – a.k 0 - a.k - y0 k Notemos que há certa condição para o inteiro k, pois e pertence aos reais. Com k Logo k está compreendido entre dois números reais, assim o conjunto k {k, k1,...,kn} Z é limitado. Portanto se existir a solução positiva da equação diofantina ela é finita dada por x0 + b.k e y0 – a.k. Outra demonstração que julgo necessária. É o fato de que a equação. a1.x1 + a2.x2 + a3.x3 + ... + ak.xk c (I) Admite solução inteira se, e somente se mdc(a1, a2,..., ak) d|c. Demonstração: Queremos mostrar que a1.x1 + a2.x2 + a3.x3 + ... + ak.xk c d|c Como o mdc(a1, a2,..., ak) d, então temos; d|a1 q1 Z tal que a1 d.q1 (1) d|a2 q2 Z tal que a2 d.q2 ... ... ... d|ak qk Z tal que ak d.qk (K) Somando (1) +...+ (K) a1 + a2+...+ ak d.q1 + d.q2 +...+ d.qk a1 + a2+...+ ak d.(q1 + q2 +...+ qk) Portanto d|a1 + a2+...+ ak, usando as propriedades da divisibilidade já estudadas d|c. Se d|c então existe q Z tal que c d.q. Como mdc (a1, a2,...,ak) d, temos que existem m1, m2,...mk Z tais que d m1.a1 + m2.a2 +...+ mk.ak. Multiplicando por q, temos; d.q m1.a1.q + m2.a2.q +...+ mk.ak.q d.q a1.m1.q + a2.m2.q +...+ ak.mk.q Fazendo x1 m1.q x2 m2.q . . . xk mk.q Têm – se a1.x1 + a2.x2 + a3.x3 + ... + ak.xk c 4. APLICAÇÕES DAS EQUAÇÕES DIOFANTINAS LINEARES No capitulo anterior, fizemos um estudo sobre as equações diofantinas analisando sua condição de existência, sua admissão de soluções e como encontra- las. Agora vamos realizar uma aplicação desse estudo na resolução de problemas aritméticos. Em certos problemas de agrupamentos aparecem naturalmente um caso de equação diofantina: 4.1 Problemas Envolvendo Equações Diofantinas Lineares Problema 1. Quantas quadras de basquete e quantas quadras de vôlei são necessárias para que 80 alunos joguem simultaneamente qualquer um dos esportes? (LA ROQUE; PITOMBEIRA, 1991, p. 39 [7]). Solução: As equipes de basquete e vôlei são compostas, respectivamente, de 5 e 6 jogadores. Como precisamos de duas equipes por quadra, modelamos nosso problema através da seguinte equação diofantina: 12.x + 10.y 80 Onde x e y representam, respectivamente, a quantidade de quadras de vôlei e basquetenecessárias para acomodar os 80 jogadores. Temos que o mdc(12, 10) 2 e a equação dada tem solução, pois 2|80. Utilizando o Corolário 3 e dividindo a equação 12.x + 10.y 80 por 2, obtemos a equação equivalente: 6.x + 5.y 40 onde mdc(6, 5) 1. Escrevendo 1 como combinação linear de 6 e 5 temos: 6.1 + 5.( - 1) 1 Multiplicando a equação por 40, obtemos: 6.40 + 5.( - 40) 40 Logo, o par de inteiros x0 40 e y0 - 40 é uma solução particular da equação proposta, e utilizando oCorolário 2 na equação equivalente 6.x + 5.y 40 já que mdc (6, 5) 1 as demais soluções são dadas pelasfórmulas: X x0 + b.t 40 + 5.t Com t Z Y y0 – a.t - 40 – 6.t Como o número de quadras é natural devemos restringir nossa resposta de modo que escolhendo t sejamsatisfeitas as desigualdades: x 0 e y 0, assim temos que 40 + 5.t 0 e - 40 -6.t 0 Isto é: t -8 e t -6,67, daí temos -8 t -7. O que implica que: Para t - 8, temos 0 quadras de vôlei e 8 quadras de basquete. Para t - 7, temos 5 quadras de vôlei e 2 quadras de basquete. Problema 2. Encontrar todos os números naturais N menores do que 10.000 tais que: O resto da divisão de N por 37 é 9; O resto da divisão de N por 52 é 15. Solução: Dividindo N por 37, obtemos um quociente x e resto 9, ou seja, (i) N 37.x + 9 Analogamente, representando o outro quociente por y, temos. (ii) N 52.y + 15 De (i) e (ii), segue que 37.x + 9 52.y + 15, ou seja, encontramos a equação diofantina linear. 37.x + 52.y 6 Inicialmente, é fácil perceber que 37 é primo e não divide 52, então o mdc(52, 37) 1 e como 1|6 a equação possui solução em Z. Para escrevermos 1 mdc(52, 37) como combinação linear dos números 52 e 37 vão recorrer ao algoritmo de Euclides: 1 2 2 7 52 37 15 7 1 15 7 1 0 52 1.37 + 15, então 15 52 - 1.37 37 2.15 + 7, então 7 37 - 2.15 15 2 .7 + 1, então 1 15 - 2 .7 7 7.1 + 0 Daí, 1 15 - 2.7 15 -2.(37 - 2.15) 5.15 - 2.37 5.(52 - 37) - 2.37 5.52 - 7.37. Assim, 1 mdc(52, 37) como combinação linear é representado por: 37.( - 7) - 52.( - 5) 1 Multiplicando a equação por 6, segue que 37.( - 42) - 52.( - 30) 6 Temos que x0 - 42 e y0 - 30 é uma solução particular da equação proposta, e utilizando o Corolário2 as demais soluções são dadas pelas fórmulas: X x0 + b.t -42 -52.t Com t Z Y y0 - a.t - 30 - 37.t Para encontrar as soluções da equação em N, basta determinarmos t de modo que sejam satisfeitas asdesigualdades: X 0 e Y 0, assim temos -42 -52.t 0 e - 30 -37.t 0 Temos assim as condições para t: -42 -52.t 0, onde t -0,808 e -30 -37.t 0, onde t -0,812. O que implica que se {t Z; t -1} temos que a equação 37.x - 52.y 6 possui uma infinidade de soluções em N. Retomando à pergunta inicial, os números N que estamos procurando são dados, por: N 37.x + 9 37.( -42 -52.t) + 9 - 1.545 -1924.t Para que N < 10.000, devemos ter; - 1.545 – 1.924.t 10.000 daí obtemost - 6,001 Logo se {t Z; t - 6} a equação N - 1.545 – 1.924.t nos fornece um número N 10.000. Agora para que esse número N seja natural e menor que 10.000 devem ser satisfeitas ao mesmo tempo as condições {t Z; t 1} e {t Z; t 6} que implicam que t { - 6,- 5, - 4,- 3,- 2,-1}. Assim, os seis possíveis valores naturais para N são: 379, 2303, 4227, 6151, 8075 e 9999. Problema 3 Se um trabalhador recebe 510 reais em tíquetes de alimentação, com valores de 20 reais ou 50 reais cada tíquete, de quantas formas pode ser formado o carnê de tíquetes desse trabalhador? Solução: Se x denota a quantidade de tíquetes de 20 reais e y a quantidade de tíquetes de 50 reais então aequação é: 20.x + 50.y 510 É fácil perceber que o mdc(50, 20) 10 e a equação dada tem solução, pois mdc(50, 20) 10|510. Utilizando o Corolário 3 e dividindo a equação 20.x + 50.y 510 por 10, obtemos a equação equivalente: 2.x + 5.y 51 onde mdc(5, 2) 1. Agora, escrevendo 1 como combinação linear de 2 e 5 temos: 2.( - 2) + 5.(1) 1 Multiplicando a equação por 51, obtemos: 2.( - 102) + 5.(51) 51 Onde x0 -102 e y0 51 é uma solução particular da equação proposta, e utilizando o Corolário 2 na equação equivalente 2.x + 5.y 51 já que mdc(5, 2) 1 as demais soluções são dadas pelas fórmulas: X x0 + b.t -102 + 5.t Com t Z Y y0 – a.t 51 – 2.t Na busca de soluções não negativas devem ser satisfeitas as desigualdades: x 0 e y 0, assim temos que -102 + 5.t 0 e 51 –2.t 0 Isto é: t 20,4 e t 25,5 O que implica que {t Z; 21 t 25}, assim t {21, 22, 23, 24, 25} e temos 5 possibilidades para os carnês, a saber: Para t 21, temos um carnê com 3 tíquetes de 20 reais e 9 tíquetes de 50 reais. Para t 22, temos um carnê com 8 tíquetes de 20 reais e 7 tíquetes de 50 reais. Para t 23, temos um carnê com 13 tíquetes de 20 reais e 5 tíquetes de 50 reais. Para t 24, temos um carnê com 18 tíquetes de 20 reais e 3 tíquetes de 50 reais. Para t 25, temos um carnê com 23 tíquetes de 20 reais e 1 tíquetes de 50 reais. Problema 4. Se o custo de uma postagem é de 83 centavos e os valores dos selos são de 6 e 15 centavos, comopodemos combinar os selos para fazer essa postagem? Solução: Se x denota a quantidade de selos de 6 centavos e y denota a quantidade de selos de 15 centavos,então a equação que representa essa situação é: 6.x + 15.y 83 É fácil ver que o mdc(15, 6) 3 e como 3 83 a equação diofantina 6.x + 15.y 83 não possui soluções inteiras e assim o problema de postagem não tem solução. Problema 5. O valor da entrada de um cinema é R$ 8,00 e da “meia” entrada é de R$ 5,00. Qual é o menornúmero de pessoas que podem assistir a uma sessão de maneira que a bilheteria seja de R$ 500,00? Solução: Inicialmente vamos identificar as variáveis do problema, seja x o número de pessoas que pagarão ovalor integral da entrada, e y o número de pessoas que pagarão o valor da meia entrada. Dessa forma a equação representativa é: 8.x + 5.y 500 Vamos encontrar o mdc(8, 5) pelo algoritmo de Euclides: 1 1 1 2 8 5 3 2 1 3 2 1 0 8 1.5 + 3, então 3 8 – 1.5 5 1.3 + 2, então 2 5 -1.3 3 1.2 + 1, então 1 3 – 1.2 2 2.1 + 0 Como o mdc(8, 5) 1, a equação apresenta solução, pois mdc(8, 5) 1|500. Agora para escrever 1 comocombinação linear de 8 e 5 basta eliminar os restos 2 e 3 das três primeiras igualdades anteriores do seguintemodo: 1 3 - 2 3 -(5 - 3) 2.3 - 5 2.(8 - 5) - 5 2.8 – 3.5 Isto é: 8.(2) + 5.( - 3) 1 Multiplicando a equação por 500, temos: 8.(1000) + 5.( - 1500) 500 Logo, o par de inteiros x0 1.000 e y0 - 1.500 é uma solução particular da equação proposta, e utilizandoo Corolário 2 as demais soluções são dadas pelas fórmulas: X x0 + b.t 1000 + 5.t Com t Z Y y0 - a.t -1500 -8.t O problema requer soluções inteiras e positivas, que serão encontradas escolhendo t de modo que sejamsatisfeitas as desigualdades: x 0 e y 0, assim têm que 1000 + 5.t 0 e -1500 -8.t 0 Isto é: t -200 e t -187,5 O que implica que {t Z; -200 t -187,5}. Agora para que encontremos o menor número de pessoas,devemos utilizar o maior valor inteiro de t, então se tem que t - 188. Daí, obtemos os valores; X 1000 + 5.(-188) 60 Y -1500 -8.( -188) 4 Sendo assim, para a bilheteria ser de R$ 500,00 com o menor número de pessoas possível, deve-se ter 60pessoas que irão pagar R$ 8,00 cada e 4 pessoas que irão pagar R$ 5,00 cada. Assim, nessas condições o menornúmero de pessoas será 64. Problema 6: Dois irmãos, João e José, pescaram em uma manhã “x” e “y” peixes, respectivamente. Sabendoque 3.x + 4.y 61, determine as possíveis quantidades de peixes que eles conseguiram juntos? Solução: Vamos inicialmente encontrar o mdc(3,4) pelo algoritmo de Euclides: 1 2 1 4 3 1 1 1 1 0 Como o mdc(3, 4) 1, a equação apresenta solução, pois mdc(3, 4) 1|61. Agora podemos escrever 1 comocombinação linear de 3 e 4 da seguinte forma: 3.( -1) + 4.(1) 1 Multiplicando a equação por 61, temos: 3.( -61) + 4.(61) 61 Logo, o par de inteiros x0 - 61 e y0 61 é uma solução particular da equação proposta, e utilizando o Corolário 2 as demais soluções são dadas pelas fórmulas: X x0 + b.t -61 + 4.t Com t Z Y y0 - a.t 61 -3.t O problema requer soluções inteiras e positivas, que serão encontradas escolhendo t de modo que sejamsatisfeitas as desigualdades: x 0 e y 0, assim temos que - 61 + 4.t 0 e 61 – 3.t 0 Isto é: 15,25 t 20,33… O que implica que t {16, 17, 18, 19, 20}. Assim as soluções da equação podem ser; Para t 16, temos que João pescou 3peixes e José 13. Para t 17, temos que João pescou 7peixes e José 10 Para t 18, temos que João pescou 11peixes e José 7 Para t 19, temos que João pescou 15peixes e José 4 Para t 20, temos que João pescou 19peixes e José 1. Logo as possíveis quantidades de peixes que os irmãos conseguiram juntos são 16, 17, 18, 19 e 20. Problema 7. João pediu a Pedro que multiplicasse o dia de seu aniversário por 12 e o mês do aniversáriopor 31 e somasse os resultados. Pedro obteve 368. Qual é o produto do dia do aniversário de Pedro pelo mêsde seu nascimento? Solução: Inicialmente vamos identificar as variáveis do problema, seja x o número que representa o dia do aniversário de Pedro, e y o número que representa o mês do aniversário de Pedro. Dessa forma a equaçãorepresentativa é: 12.x + 31.y 368 Vamos encontrar o mdc(12,31) pelo algoritmo de Euclides: 2 1 1 2 2 31 12 7 5 2 1 7 5 2 1 0 31 2.12 + 7, então 7 31 - 2.12 12 1.7 + 5, então 5 12 -1.7 7 1.5 + 2, então 2 7 - 1.5 5 2.2 + 1, então 1 5 - 2.2 2 1.2 + 0 Daí, podemos escrever o 1 como combinação linear de 12 e 31 da seguinte forma; 1 5 - 2.2 5 - 2.(7 -1.5) 3.5 - 2.7 3.(12 -7) - 2.7 3.12 + 5.(- 7) 3.12 + 5.(- 31 + 2.12) = 13.12 + 5.(-31) 1 Assim o mdc (12, 31) 1 é dado por: 12.(13) + 31.(-5) 1 Multiplicando a equação por 368, segue que. 12.(4784) + 31.(- 1840) 368 Temos que x0 4784 e y0 - 1840 é uma solução particular da equação proposta, e utilizando o Corolário2 as demais soluções são dadas pelas fórmulas: x x0 + b.t 4784 + 31.t Com t Z y y0 - a.t -1840 -12.t Para encontrar as soluções da equação basta determinarmos t de modo que sejam satisfeitas asdesigualdades: 1 x 31 e 1 y 12 Assim temos para x: 1 4784 + 31.t 31 Assim temos para y: 1 -1840 -12.t 12 Dessa forma fazendo algumas aproximações temos as condições para os valores de t; -154 t -153 Observa-se ainda que a único valor para t que satisfaz as condições de solução da equação é t -154. x 4784 + 31.(-154) 10 y - 1840 -12.(-154) 8 Portanto o aniversário de Pedro é no dia 10 de agosto, então temos o produto dado por 8.10 80. Outra solução para este problema dado pelos autores da REVISTA DAOLIMPÍADA DE MATEMÁTICA DO ESTADO DE GOIÁS, p. 13, 2003. Suponhamos quePedro nasceu no dia x, 1 x 31 do mês y, 1 y 12. Pelo enunciado, 12.x + 31.y 368. Observa-se que 4 é um divisor de 12 e de 368 e, como 31 e 4 são primos entre si, 4 tem que ser um divisor de y. Os possíveis valores de y são 4, 8 e 12. Somente y 8 resultará um valor inteiro para x, no caso x 10. O aniversário de Pedro é no dia 10 de agosto. O produto pedido é 80. Problema 8 Um fazendeiro deseja comprar filhotes de pato e de galinha, gastando um total de R$ 1.770,00. Um filhote de pato custa R$ 31,00 e um de galinha custa R$ 21,00. Quantos de cada um dos dois tipos o fazendeiro poderá comprar? Solução: Vamos modelar o problema da seguinte maneira. 31.x + 21.y 1770. Observe que mdc (31, 21) 1 e que 1 divide 1.770. Logo, a equação tem solução. Vamos encontrar uma solução particular. Para isso, usamos o Algoritmo da Divisão: 31 1.21 + 10; 21 2.10 + 1; 1 21 + (-2).10 21 + (-2).[31 + (-1). 21] 3.21 + (-2).31. Multiplicando ambos os lados por 1.770, obtemos: 1770 (- 3540).31 + (5310).21. Portanto, uma solução particular é x - 3540 e y 5310. A solução geral da equação é dada por: x - 3540 + 21.t e y 5310 -31.t. Observe que estamos interessados somente nas soluções positivas ou nulas, pois representam quantidades de animais. Assim, temos que impor as condições seguintes: - 3540 + 21.t 0 e 5310 -31.t 0. Portanto, 21.t 3540 e 31.t 5310, que é o mesmo que: t 168,57 e t 171,29. Assim, como t é um número inteiro, temos que 169 t 171. Desse modo, as soluções são: x - 3540 + 21.169 9 e y 5310 -31.169 71; ou x - 3540 + 21.170 30 e y 5310 -31.170 40; ou x - 3540 + 21.171 51 e y 5310 -31.171 9. Essas soluções dizem que o fazendeiro tem três alternativas de comprar: Que são 9 patos e 71 galinhas ou 30 patos e 40 galinhas, ou 51 patos e 9 galinhas. 4.2.Utilizando o Winplot Agora vamos usar o Winplot para construir alguns gráficos que representam as equações diofantinas lineares e percebermos as suas soluções inteiras nestas construções geométricas. O uso desse programa computacional é uma estratégia geométrica que viabiliza nosso estudo nas busca por soluções inteiras de uma equação diofantina linear. Exemplo 1: Represente graficamente as soluções inteiras e positivas da equação 20.x + 50.y 510 (Problema 3) com a ajuda do Winplot. Primeiro no Winplot escolhemos a opção plotar gráfico de “2a dimensão”. Figura 1:Tela Inicial do Winplot Na próxima janela selecione “Equação” e depois “Reta”. Figura 2: Instruções para construção do gráfico de uma reta Agora para plotar o gráfico da equação a.x + b.y c, basta digitar seus coeficientes. Figura 3:Inserindo os coeficientes de uma equação diofantina que representa uma reta no plano. Visualização geométrica do conjunto-solução da equação linear 20.x + 50.y 510 do Problema 3. Figura 4: Representação geométrica das soluções inteiras da equação diofantina do problema 3. Encontrar todas as soluções naturais da equação 3.x + 4.y 61. (Problema 6). Figura 5: Soluções da Equação Diofantina do problema 6 obtidas Winplot Caso a Equação Diofantina Linear tenha solução, observamos que quando o coeficiente angular das retas suporte a.x + b.y c for negativo, teremos um número finito de soluções inteiras e positivas. Analogamente, se ele for positivo, a Equação Diofantina Linear terá infinitas soluções inteiras e positivas. Analise o exemplo a seguir: Ao entrar num bosque, alguns viajantes avistam 37 montes de maçãs. Após serem retiradas 17 frutas, o restante foi dividido igualmente entre 79 pessoas. Qual pode ter sido a menor parte recebida de cada pessoa? (IEZZI, G. et al. 2003 [11]). Veja que se cada um dos 37 montes tem x maçãs e após serem retiradas 17 maçãs sobraram-nos r maçãs, assim temos a equação: 37.x -17 r Como o restante das maçãs será dividido igualmente entre 79 pessoas, temos que r é múltiplo de 79 e então é da forma r 79.y, sendo y a parte inteira que cabe a cada pessoa. Daí tem a seguinte equação diofantina linear. 37.x -79.y 17 As soluções desta equação são dadas pela abscissa x 9 + 79.te ordenada y 4 + 37.t, com t inteiro. Para que possamos repartir a menor quantidade de maçãs possível para cada pessoa basta tomar t 0 na equação y 4 + 37.t.Obtendo y 4, ou seja, cada uma das pessoas receberá 4 maçãs. Graficamente; Figura 6:Representação geométrica da única solução que apresenta as menores coordenadas inteiras. Deixamos aqui agora alguns problemas a serem resolvidos a cargo do leitor para que o mesmo pratique os conhecimentos adquiridos e desenvolvidos neste trabalho. Problema 9. Camila possui R$ 500,00 depositados num banco. Duas operações bancárias são permitidas, retirar R$ 300,00 e depositar R$ 198,00. Essas operações podem ser repetidas quantas vezes Camila desejar,mas somente o dinheiro inicialmente depositado pode ser usado. Qual o maior valor que Camila pode retirardo banco? (REVISTA DA OLIMPÍADA DE MATEMÁTICA DO ESTADO DE GOIÁS, abril. 2003). Problema 10. Um laboratório dispõe de 2 máquinas para examinar amostras de sangue. Uma delas examina 15 amostras de cada vez enquanto a outra examina 25. De quantos modos diferentes essas máquinas podem ser acionadas para examinar 2 mil amostras? (LA ROCQUE; PITOMBEIRA, 1991, p. 39 [7]). Problema 11. Um grupo de pessoas gastou 690 dólares num hotel. Sabendo que apenas alguns dos homensestavam acompanhados pelas esposas e que cada homem gastou 18 dólares e cada mulher gastou 15 dólares,determinar quantas mulheres e quantos homens estavam no hotel. (FONSECA, 2011, p. 116 [10]). Problema 12. Para participar de um evento comemorativo em um clube não sócio pagavam R$ 12,00 e sóciosR$ 8,00. Sabendo-se que foram arrecadados R$ 908,00 na portaria, quantas pessoas no máximo poderiamestar presentes neste evento? (FONSECA, 2011, p. 116 [10]). Problema 13. Temos duas balanças: uma que marca pesos múltiplos de 10 e outra que marca pesos múltiplos de 13. Como é que com essas balanças podemos pesar 107 gramas? Problema 14. Numa papelaria vedem-se dois tipos de canetas por 110 e 70 reais respectivamente. Ao fim de um dia a importância total recebida pela venda dessas canetas foi 6570 reais. Qual é o menor numero possível de canetas vendidas? E qual o maior? Problema 15. Dispondo de 100 reais, quais são as quantias que se podem gastar comprando selos de R$ 5,00 e de R$ 7,00. Problema 16: Um grupo de pessoas gastou 1000 dólares num hotel. Sabendo-se que apenas alguns dos homens estavam acompanhados pelas esposas e que cada homem gastou 19 dólares e cada mulher gastou 13 dólares, pede-se determinar quantas mulheres e quantos homens estavam no hotel? CONSIDERAÇÕES FINAIS Espera-se com esse trabalho de conclusão de curso, favorecer ao leitor um embasamento teórico e prático das Equações Diofantinas Lineares. Com uma linguagem clara de acessibilidade ao aluno de graduação. É notável a contribuição de Diofanto para a história da matemática, precisamente á álgebra, pois foi pioneirono desenvolvimento da notação álgebra em que algumas operações eram representadas por suas abreviações.Apesar de não ser o primeiro a trabalhar com equações indeterminadas ou a resolver equações quadráticas de maneira não geométrica, podemos considerar que Diofanto foi primeiro a dar os passos iniciais rumo a uma estrutura da simbologia algébrica que estudamos hoje. Daí a importância fundamental de se fazer um estudo acerca das equações, com vistas ás aplicações das mesmas na resolução dos problemas aritméticos. Além da estratégia de tentativa e erro as equações diofantinas lineares na busca por suas soluções permite articular outras estratégias de enfoque aritmético para possibilitar a evolução do uso da escrita algébrica. Houve-se um fortalecimento na demonstração dos conceitos básicos da Teoria Elementar dos Números que são necessários para dedução dos números de soluções de uma Equação Diofantina Linear. Compreende-se que uso das estratégias algébricas e geométricas para resolução de problemas aritméticos contidas neste trabalho estimula-se ao leitor a repensar sobre o processo de aprendizagem do conteúdo algébrico e a aprimorar os seus conhecimentos. Dessa forma, desejo que esse trabalho contribua significativamente para uma melhor compreensão da disciplina de Teoria dos números, considerada por muitos a área mais nobre da Matemática. Portanto produzir no discente a capacidade de identificar problemas que possam ser modelados e em seguida serem resolvidos por meio dessas equações. REFERÊNCIA BIBLIOGRAFIA [1] POLCINO Césarmilies: Números – Uma introdução á matemática [2] Dan Avritzer Hamilton Prado Bueno Marília Costa de Faria Maria Cristina Costa Ferreira. Fundamentos da álgebra. [3] BOYER, Carl. Benjamim. História da Matemática. 9. Ed. São Paulo: Editor Edgard Blucher, 1991. [4] BARROS, Alayde Ferreira dos Santos. Equações Diofantinas e suas Aplicações. 1998. 55p. Monografia (Especialista em Matemática), UESB-BA. [5] POMMER, Wagner Marcelo. Equações Diofantinas Lineares: um desafio motivadorpara alunos de ensino médio. 2008. 153p. Dissertação (Mestrado em EducaçãoMatemática), PUC-SP, 2008. [6] COSTA, Eduardo S., Equações Diofantinas Lineares e o Professor do Ensino Médio. 2007. 119f. Dissertação de Mestrado Acadêmico em Educação Matemática. Pontifícia Universidade Católica de São Paulo, São Paulo. [7] LA ROQUE, G., PITOMBEIRA, J.B., Uma Equação Diofantina e Suas Resoluções. In Revista do Professor de Matemática. São Paulo, v. 19, p. 39-47, 1991. [8] OLIVEIRA, Silvio. B., As Equações Diofantinas Lineares e o Livro Didático de Matemática para o Ensino Médio. 2006. 102 f. Dissertação de Mestrado Acadêmico em Educação Matemática. Pontifícia Universidade Católica de São Paulo, São Paulo. [9] OLIVEIRA, José Plinio. Introdução à Teoria dos Números. Coleção Matemática Universitária. 1998. Campinas-SP. [10] FONSECA, Rubens V., Teoria dos Números Belém: Universidade do Estado do Pará. 2011.