UNIVERSIDADE ESTADUAL DO SUDOESTE DA BAHIA - UESB

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

2

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

3

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

4

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.

5

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

6

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

7

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.

8

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

9

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

10

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

11

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

12

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).

13

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

14

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.

15

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.

16

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.

17

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

18

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

19

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:

20

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.

a b

r q

21

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

22

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.

23

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.

24

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

25

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,

26

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;

27

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

28

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).

29

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

30

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.

31

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

32

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;

33

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.

34

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.

35

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;

36

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;

37

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.

38

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 – (d

m).k

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.

39

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),

40

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)

41

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.

42

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.

43

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:

44

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.

45

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

46

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.

47

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.

48

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:

49

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

50

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

51

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

52

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

53

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).

54

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

...

...

...

...

55

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í,

56

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.

57

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

58

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

59

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:

60

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.

61

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

62

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:

63

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.

64

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

65

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

66

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.

67

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:

68

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”.

69

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.

70

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.

71

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.

72

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?

73

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?

74

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.

75

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.

76

[10] FONSECA, Rubens V., Teoria dos Números Belém: Universidade do Estado do

Pará. 2011.