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
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
2
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
3
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.
4
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
5
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
6
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.
7
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
8
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
9
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
10
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
11
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).
12
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
Zeb
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
Note que o c da definição é uma solução da equação b.x
pode não ter solução em N, por exemplo, 2.x
b.c.
a. Esta equação
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
13
Para todo a, d
iv.
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
não é único, pois 0.c
0, para todo c
0. Neste caso o quociente
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
1eq
1 ou a
-1eq
-1, ou seja a
Z tal que 1
q.a. O que implica a
1.
Proposição 2:
Se a, b, c e d são inteiros com a
Demonstração: Existe u, v
0eb
0, tais que a|b e c|d então ac|bd.
Z tais que se a|b então b
u.a e se c|d então d
Multiplicando-se as equações membro a membro temos que b.d
v.c.
(u.v).ac daí ac|bd.
Proposição 3:
Se a, b e c são inteiros com a
Demonstração: Existe u, v
Logo, c
0eb
0, tais que a|b e b|c então a|c.
Z tais que se a|b então b
a.u e se b|c então c
b.v.
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
Demonstração: Existe u, v
b.v. Logo a
a
Z tais que se a|b então b
a.(u.v) que implica u.v
b.
a.u e se também b|a então a
1, assim u|1 e daí temos que u
1 e que
b.
14
Proposição 5:
Sejam a e b inteiros e diferentes de zero, se a|b então |a|
Demonstração: Existe u
|a|.|u|. Como u
Z com u
0,temos que |u|
|b|.
0 tal que se a|b então b
1, desse modo segue que |b|
a.u, ou seja |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
Logo, quaisquer que sejam os inteiros x e y temos que b.x + c.y
a.(u.x) + a.(v.y)
a.v.
(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)
Dados a, b
max D(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.
15
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
D12
12 e de b
{ 1, 2, 4, 6, 12} e D4
4, sendo denotados por D12 e D4. Assim,
{ 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
conjunto. Logo, D12
D4
D4 e tomar o maior número em módulo desse
{ 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
que a
Z, com b
b.q + r, onde 0
r
0, existe um único par de inteiros q e r, de modo
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
b.q
a, então a
b.q + b e daí r
b.q + r, onde r
Zer
0. Se a
b. Logo, podemos afirmar que a
a
b.(q + 1). Se
b.(q + 1), temos que b.q + r
b.q + r, com 0
r < b.
16
2ª) Prova da unicidade:
Suponhamos que existam inteiros q1, q2, r1, r2, onde q1
q2 e r1
que satisfaçam às igualdades: a
bea
r2
b. Se b
r1 e b
b.q1 + r1, com 0
r2, então b
implica que b.(q2 - q1)
r1
r1 - r2 e temos que a
r1 - r2. Fazendo k
r2, com r1
r2 e
b.q2 + r2, com 0
b.q1 + r1
b.q2 + r2 o que
(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
também que b.(q2 - q1)
0. Se b
0, temos (q2 - q1)
r2 e concluímos
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
Seja K
0eb
0.
{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
ii.
Como d
K, então existem x0 e y0
0
d
Z tais que;
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;
r
a
(a.x0 + b.y0).q + r
a
a.x0 .q + b.y0. q + r
a.(1 – x0. q) + b.(-y0). q
17
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
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’
iii.
0
r’
d.q’
b
d
d|b
Se d’|a e d’|b temos;
a. x0
d’.k. x0
a
d’. k
b
d’. q
e
a.x0 + b.y0
d
Portanto d’|d o que implica d
d’.q.y0
b.y0
d’.(k.x0 + q.y0)
d’. (k.x0 + q.y0)
mdc (a, b).
Lema 1.
Sejam a e b dois inteiros positivos e a
b)
b.q + r, com 0
r
b. Então mdc(a,
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
18
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 -1.qn + rn, com 0
rn
................................
.................................
rn -2
rn -1
rn.qn+1 + rn+1, com rn+1
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:
19
a
b
r
q
Mudando o esquema temos;
q
a
b
r
Aplicando o dispositivo prático do cálculo do mdc(a, b) dispomos os números;
a
q1
q2
q3
b
r1
r2
r1
r2
r3
...
...
qn
qn+1
rn-2
rn-1
rn
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
PBO existe d1
min A
{(m.a + n.b)
0. Como d1
d1
0; m, n
Z}. Note que A
A, então existem r, s
, logo pelo
Z, tais que;
r.a + s.b
E observando que d|a e d|b resultam que d|d1, daí temos d
d1.
20
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
Portanto, d1 é divisor comum positivo de a e b, logo d1
t
d1
min A.
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:
963
1
2
6
1
4
657
306
45
36
9
306
45
36
9
0
21
963
657.1 + 306, então 306
657
306.2 + 45, então 45
306
45.6 + 36, então 36
45
36.1 + 9, então 9
36
9.4 + 0
963 – 657.1
657 – 306.2
306 - 45 .6
45 - 36 .1
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
15.306
45 -(306 – 45 6)
7.657 – 15.(963 - 657)
- 306 + 7.(657 – 306.2)
- 306 + 7.45
7.657 –
963.(-15) + 657.2.
Assim, a expressão do mdc(963, 657)
963.x + 657.y
9 como combinação linear é:
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)
uso do teorema de Bézout existem r, s
Z tais que:
r.a + s.b
Suponhamos que d
r.a + s.b
1. Fazendo
1
mdc (a, b) e ainda temos que existem r, s
Z tais que
1. Como d|a e d|b isso implica d|(r.a + s.b) daí d|1 o que resulta d
assim o mdc (a, b)
1,
1.
Portanto a e b são primos entre si.
22
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
De mdc (a. b)
Z tal que b.c
1 temos que existem r, s
a.k.
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)
Demonstração: Inicialmente nota-se que
e
d, então mdc ( , )
1.
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
Pelo Teorema 4, os inteiros
e
1.
são primos entre si assim, o mdc ( , )
1.
23
Exemplificando:
Seja os números 12 e 30, cujo mdc (12, 30)
temos que mdc ( ,
)
mdc (2, 5)
6 daí pelo corolário acima
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
se ele tem exatamente quatro divisores distintos:
1e
Z é primo
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
ne0
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
24
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,
25
1520
7.q + a, com 0
segue-se 1520
a
6. E ainda pela unicidade do resto na divisão euclidiana
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.
Se m|(a – b) então existe k
a–b
q.m – p.m
a–b
(q – p).m
m|(a – b)
Z tal que;
a–b
a
k.m
k.m + b
Por outro lado, a divisão euclidiana garante que existem q e r pertencentes a Z tais
que;
26
a
q.m + r
com 0
r
|m|
Assim temos;
k.m + b
b
q.m + r
(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:
24 mod 7, pois 7|(3 – 24) donde que – 21
3
7. (- 3).
Proposição 8:
Seja m
0 um inteiro e a, b, c
Reflexiva: a
i.
Z. Então a congruência módulo m satisfaz;
b (mod m)
Demonstração:
Como m|0, pois existe c
Assim m|(a – a)
a
Simétrica: Se a
ii.
Z tal que 0
m.c (0
m.0).
a (mod m).
b (mod m) então b
a (mod m).
Demonstração:
Se a
b (mod m) então para algum k1
b
a – k1. M
b
a + (- k1). M
Assim existe um inteiro x
Logo por definição b
iii.
- k1 tal que b
Z temos a
b + k1.m. Daí;
a + x.m
a (mod m).
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
a–b
k1.m
b–c
k2.m
c (mod m) então existem k1 e k2 inteiros tais que;
27
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
Note que 12|(a – 7) o que implica a – 7
3 (mod 4) para todo a
12.k, k
Z.
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
1.
(a + c)
b (mod m) então;
(b + c) (mod m).
Demonstração:
Como a
b (mod m) então para algum k
Note que a – b
implica (a + c)
2.
(a – c)
Z, temos a – b
k.m;
(a + c) – (b + c), assim escrevemos (a + c) – (b + c)
k.m e isso
(b + c) (mod m).
(b – c) (mod m).
28
Demonstração:
Note que (a – c) – (b – c)
a – b e ainda a – b
k.m;
Fazendo;
(a – c) – (b – c)
3.
a.c
k.m
(a – c)
(b – c) (mod m).
b.c (mod m).
Demonstração:
Por hipótese temos a – b
Como c
k.m, para algum k
Z, podemos escrever a.c – b.c
O que implica a.c
Z.
(c.k).m;
b.c (mod m).
Teorema 8:
Se a, b, c, d, m inteiros tais que a
1) (a + c)
b (mod m) e c
d (mod m) então;
(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)
Portanto (a + c)
2) (a – c)
(k1 + k2).m
(b + d) (mod m).
(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
29
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)
a.c
b.c (mod m) implica a
1, então
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
0ea
b (mod m) então ak
bk (mod m).
Demonstração:
Fazendo uso da seguinte identidade:
ak – bk
Como a
(a – b).(ak – 1 + ak – 2.b + ak – 3.b2 +…+a.bk – 2 + bk– 1 )
b (mod m) então m|(a – b) e ainda para algum q
a–b
Z, temos;
m.q
Das duas ultimas igualdade concluímos que:
ak – bk
Portanto m|(ak – bk)
ak
m.x
tal que x
Z
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.
30
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
Observações:
ri (mod m).
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
31
n–s
Assim temos n
s (mod m), sendo que s é um dos ti.
Note que |ti – tj|
Pois se ti
m – 1, 0
tj (mod m)
Assim |ti – tj|
m.q
m – 1. O que implica ti
i,j
m|(ti – tj). O que acarretaria ti – tj
tj (mod m) para i
j.
m.k para algum k inteiro.
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
Portanto k
k
m
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;
32
a.ri
Mas como mdc (a, m)
1, temos;
ri
Implicando em i
a.rj (mod m)
rj (mod m)
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
(mod 12) e 97
5 ( mod 12); 188
8
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.
33
Temos que a
3 (mod 8), b
5 (mod 8) e c
membroas três congruências, obtemos (a + b + c)
b + c)
9 (mod 8). Como 9
1 (mod 8). Somando membro a
3 + 5 + 1 (mod 8) . Ou seja, (a +
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 (mod 31). Por outro lado, 61
(-1)99 (mod 31). Logo, 3099
-1 (mod 31). Portanto, 61
100
(-1)
100
-
(mod 31).
Logo, 61100
1 (mod 31). Assim, 3099 + 61100
3099 + 61100
0(mod 31). Portanto, 3099 + 61100 é um número divisível por 31.
-1 + 1 (mod 31), que é o mesmo que
Exemplo 5:
Ache o dígito das unidades do número 3100.
Suponha que a representação decimal de 3 100 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
10). Portanto, podemos escrever 3100
-1 (mod 10). Logo, 3100
(32)50
(-1)50(mod
1 (mod 10) . Assim, o dígito das unidades de
3100 é 1.
34
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
solução. De fato, pois se x1
b (mod m) e x1
x0 (mod m) então x1 é também
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
Duas soluções x0 e x1 da congruência a.x
isto é, x0
b.
b (mod m) congruente módulo m
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
Como 2
4.x
2 e x
7 satisfazem a congruência linear 4.x
3 (mod 5).
7 (mod 5), tratamos 2 e 7 como a mesma solução da congruência linear
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)
+ b.y
se x
d. Se d não divide c então a equação a.x
c não possui nenhuma solução inteira. Se d|c ela possui infinitas soluções e
x0 e y
y0 é uma solução particular então todas as soluções são dadas por;
35
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
mdc (a, b)
c não possui solução, pois como o
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
De d|c existe um inteiro k tal que c
d
k.d. Multiplicando ambos os membros da
igualdade acima por k obtemos.
a.(n0.k) + b.(m0.k)
Assim o par (x0, y0), sendo x0
n0.k e y0
k.d
c
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
x
x0 + ( ). k
y
y0 – ( ). k
Vamos supor que (x, y) é a solução de a.x + b.y
particular a.x0 + b.y0
c é da forma
c e ainda (x0, y0) é uma solução
c.
Subtraindo as duas ultimas igualdade temos;
36
a.x + b.y – a.x0 – b.y0
O que implica em a.(x – x0)
que mdc ( , )
a(x – x0) + b.(y – y0)
b.(y – y0). Como o mdc (a, b)
0.
d podemos escrever
1. Dividindo a igualdade acima por d.
.(x - x0)
Usando o Teorema de Euclides
x – x0
. (y – y0)
| . (x – x0)
| (x – x0), portanto existe um k inteiro tal que;
k.
x
x0 +. k.
Substituindo x na equação acima obtemos;
y
y0 –
.k
Teorema 15:
A congruência linear a.x
b, sendo d
b (mod m) tem solução se, e somente se, d divide
mdc(a, m).
Demonstração:
Por hipótese temos a.x
b (mod m), assim m|(a.x - b)
a.x – b
Como o mdc (a, m)
m.k, sendo k
-b
m.k – a.x
b
a.x – m.k
Z
(1)
d, então d|a e d|m. Assim existem p, q
a
d.p
m
d.q
Z tais que;
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.
37
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
m), existe y
b (mod
Z tal que o par (x, y) é solução da equação diofantina a.x + b.y
Isso nos leva dizer que a congruência linear a.x
equação diofantina a.x – m.y
c.
b (mod m) é equivalente à
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
a.x0 – m.y0
Z tais que;
b.
a.x0 – b
m.(y0)
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
b a congruência a.x
0 e mdc (a, m)
d. No caso em que d não divide
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
existe um inteiro y tal que a.x
b (mod m) se e, somente se
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
Assim a congruência a.x
b.
b (mod m) possuem infinitas soluções dadas por
x
x0 – (
m
).k
d
Estamos interessados em saber o número de soluções incongruentes. Tome x1, x2
soluções congruente módulo m. Então x0 – ( ).k1
O que implica ( ).k1
x0 – ( ).k2 (mod m).
( ).k2 (mod m). E como ( )|m e mdc ( , m)
temos que
pelo Teorema 11 nos permite o cancelamento.
38
k1
Obs: O m foi substituído por d
k2 (mod m)
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
módulo m, ou seja, a.x0
onde mdc (a, m)
C tal que a.x0 é congruente a um inteiro dado b
b (mod m). Portanto, a congruência linear a.x
b (mod 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),
39
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
Como o mdc (36, 131)
53 (mod 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)
6.x
-13 (mod 131)
Pelo Teorema 11,
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)
40
Exemplo 2:
Encontrar as soluções incongruentes da congruência linear 64.x
Como mdc (64, 84)
16 (mod 84).
4 e ainda 4|16, pelo Teorema 16 existe exatamente quatro
soluções incongruentes módulo 84. Pelo Teorema 11.
4.x
Temos que mdc (64, 16)
1 (mod 21).
16 e mdc (16, 84)
4e
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
(mod 84), x
16 (mod 84), x
37 (mod 84).x
58
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.x
x

3.6 (mod 17)
por transitividade
3.6 (mod 17)
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
Obtendo x
2, x
0, 1, e 2.
8ex
14.
41
Exemplo 4:

Resolver a congruência linear 7.x
Veja que o mdc (7, 21)
9 (mod 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.
42
Ora, essa equação é equivalente a 5.x + 4.y
32
x
. Como estamos
restritos aos números inteiros positivos, devemos ter:
y
0ex
0
0 e 32 – 4.y
y
0.
Portanto o y
{1, 2, 3, 4, 5, 6, 7}, com isso calcula-se o valor correspondente para x.
Para y
temos x
1
Para y
2
temos x
Para y
3
x
Para y
4
temos x
Para y
5
x
Para y
6
temos x
Paray
7
4
x
Observemos que existe uma única solução x
4ey
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
tem resolução imediata. Por exemplo, se a
0eb
e b|c e, neste caso a solução geral é dada por x
onde neste caso a solução geral é dada por y
0 ou b
0 a equação
0 então existe solução inteiras
Zey
Zex
. Análogo para b
0,
.
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:
43
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)
de todos os pares ordenados (x0, y0)
Z
Z
Z. Indicaremos por A o conjunto
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
diofantina a.x+ b.y
c tem solução se, e somente se, c
b
0 a equação
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
Seja o mdc (a, b)
c.
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)
Seja mdc(a, b)
c.
d. Se d|c, então c
inteiros x0 e y0 tais que a.x0 + b.y0
Logo, a.(x0.m) + b.(y0.m)
d.m
d.mpara algum inteiro m; além disso, existem
d.
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.
44
Observação:
Na Geometria Analítica, a equação a.x + b.y
procurarmos soluções em Z da equação a.x + b.y
c representa uma reta r. Ao
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
mdc(12, 8)
7 não tem soluções inteiras, já que
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
que a.b
c, em
0. Então qualquer solução inteira dessa equação é dada por
Onde mdc (a, b)
X
x0 + .k
Y
y0 - .k
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 + b.y0
a.x0 + a. .k + b.y0 - b. .k
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
45
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)
d.(y0 – Y)
.d.(X - x0)
.(X – x0)
Veja que
b.(y0 – Y)
.(y0 – Y)
divide o lado direito da igualdade e também o lado esquerdo. E ainda
são primos entre si, pois o mdc (a, b)
Assim pelo Teorema de Euclides
e
d.
| (X – x0). Logo existe um inteiro k tal que;
X – x0
X
.k
x0 + .k
Tomando X e substituindo na igualdade acima obtemos Y.
.(x0 – (x0 + .k))
. .k
.k
Y
.(y0 – Y)
.(y0 – Y)
y0 - 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.
46
Outra demonstração:
Considere d
mdc( , )
mdc(a, b)
1, caso contrário divida a equação por “d” e sabemos que
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
y0 – a.t com t
a.t implicando em y
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
mdc(a, b)
c, com a, b, e c inteiros e
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
únicos tais que a
0. Pelo algoritmo da divisão existem q e r com 0
r
b,
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
então p|a. Portanto o mdc (a, b)
b.q + r
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.
47
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)
tais que a.m0 + b.n0
d. Com a aplicação desse algoritmo obtemos inteiros m 0 e n0
mdc(a, b)
d. Multiplicando-se em ambos os lados dessa
igualdade obtém-se:
( .m0.a) + ( .n0.b)
( .d)
Portanto o par ordenado dado por x0
( .m0).a + ( .n0).b
( . m0) e y0
n
( . 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:
48
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
Nota-se que mdc(32, 9)
(3.9) + 5
(A)
9
(1.5) + 4
(B)
5
(1.4) + 1
(C)
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) – (7.9)
1
1
2.[32 – (3.9)] – (1.9)
1
(2.32) – (6.9) – (1.9)
(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
49
y0 – a.k
y
- 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
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
Ou seja, 1
100.
3 – 1.2
1. Pelo algoritmo de Euclides temos;
5
1.3 + 2
3
1.2 + 1
2
1.2 + 0
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
o mdc(39,26)
105 não possui solução, pois
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:
18
3
1
1
2
5
3
2
1
3
2
1
0
50
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
Concluímos que o mdc (18, 5)
1.2 + 0
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)
Logo o par de inteiros x0
96 e y0
48
- 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
y
x0 + b.t
y0 – a.t
96 + 5.t
- 336 – 18.t, com t
Z.
As soluções inteiras são encontradas escolhendo o t de modo que satisfazem
as desigualdades
x
0ey
0 e -336 –18.t
0, assim têm que 96 + 5.t
0
Isto é:
t
-19,2 e t
-18, 6o que implica que t
x
y
Assim, o par de inteiros x
equação 18.x + 5.y
- 19 e, portanto:
96 + 5.( - 19)
1
- 336 – 18.( - 19)
1ey
6
6 é a única solução inteira e positiva da
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
51
8
6
6.1 + 2
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.
Y
X
x0 +
.t
- 75 +
.t
- 75 + 11.t
y0 - .t
50 -
.t
50 – 7.t, para qualquer inteiro t.
Para encontrarmos a menor solução natural para x. Fazemos;
X
0
e
- 75 + 11.t
t
7.t
t
6,8
t
7,1
y
0
50 – 7.t
0
0
50
t
Assim, devemos ter t
7.
Substituindo na expressão da solução geral obtemos x
2ey
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
solução qualquer x
b (mod m). Determinaremos agora uma
x0 da congruência a.x
c (mod m) depois substituímos x0 na
52
equação a.x + b.y
b.y0
c a fim de encontrar o valor correspondente y0 tal que a.x0 +
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)
12.x – 331
1 e 1|331, então a equação diofantina possui solução.
25.(- y) daí 12.y
(mod 25), por fim, x
331(mod 25); 331
13 (mod 25). Assim x0
12.13 (mod 25); 12.x
12.13
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)
7.x – 9
1 e 1 | 9, logo a equação diofantina possui solução.
6.(- 7) daí temos 7.x
(mod 6). Assim x0
obtemos y0
9 (mod 6); 9
7.3 (mod 6); 7.x
7.3 (mod 6); x
3
3 é uma solução particular. Substituindo este valor na equação
- 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
Onde os ai´s são inteiros não nulos, e o mdc(a1, a2, ..., ak)
(I)
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).
53
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
(a1.a + a2.p).u1 + (a1.b + a2.q).u2 + a3.x3 +...+ ak.xk
c
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
Considerando que a
(a, p)
,p
1.
sendo d
mdc (a1, a2), temos que o mdc
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
- a.p.d.u1 – b.p.d.u2 +a.d.p.u1 + a.d.q.u2 + a3.x3 + ...+ ak.xk
a.q.d.u2 – b.p.d.u2 + a3.x3 +...+ ak.xk
(a.q – b.p). d.u2 + a3.x3 +...+ ak.xk
1. d.u2 + a3.x3 +...+ ak.xk
c
c
c
c
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
...
...
...
...
54
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
O mdc (10, 6)
8.
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
2. – 5.u, com u
y
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
- 8 – 2.t
z
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
- 8 – 2.t
z
Exemplo 2:
Encontrar todas as soluções inteiras de 101.x + 102.y + 103.z
O mdc (101, 102)
102.y
-
, com
+ 102.u e y
Fazendo
1.
1. Escrevendo como combinação linear obtém 101.x +
um inteiro e (- , ) uma solução particular e a geral é dada por x
– 101.u, sendo u um inteiro.
+ 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í,
55
x
- 104 + 103.t + 102.u
y
104 + 103.t - 101.u
-1–t
z
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
a.x0 + b.y0
n, com x
0ey
0. Tome (x0, y0) uma solução. Assim,
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;
Para x
0, temos x0 + b.k
x
x0 + b.k
y
y0 – a.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
Com
e
pertence aos reais.
k
Logo k está compreendido entre dois números reais, assim o conjunto k
k1,...,kn}
{k,
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.
56
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
Como o mdc(a1, a2,..., ak)
c
d|c
d, então temos;
d|a1
q1
d|a2
Z tal que a1
q2
d.q1
Z tal que a2
(1)
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
existem m1, m2,...mk
Z tal que c
Z tais que d
d.q. Como mdc (a1, a2,...,ak)
d, temos que
m1.a1 + m2.a2 +...+ mk.ak. Multiplicando por q,
temos;
Fazendo x1
d.q
m1.a1.q + m2.a2.q +...+ mk.ak.q
d.q
a1.m1.q + a2.m2.q +...+ ak.mk.q
m1.q
x2
m2.q
.
.
.
xk
mk.q
Têm – se
a1.x1 + a2.x2 + a3.x3 + ... + ak.xk
c
57
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 encontralas. 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
equivalente: 6.x + 5.y
40 onde mdc(6, 5)
80 por 2, obtemos a equação
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
58
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
(6, 5)
40 já que mdc
1 as demais soluções são dadas pelasfórmulas:
X
x0 + b.t
40 + 5.t
Com t
y0 – a.t
Y
Z
- 40 – 6.t
Como o número de quadras é natural devemos restringir nossa resposta de modo
que escolhendo t sejamsatisfeitas as desigualdades:
x
0ey
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
De (i) e (ii), segue que 37.x + 9
52.y + 15
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:
59
52
52
1.37 + 15, então 15
37
2.15 + 7, então 7
15
2 .7 + 1, então 1
7
1
2
2
7
37
15
7
1
15
7
1
0
52 - 1.37
37 - 2.15
15 - 2 .7
7.1 + 0
Daí,
1
15 - 2.7
Assim, 1
15 -2.(37 - 2.15)
5.15 - 2.37
5.(52 - 37) - 2.37
5.52 - 7.37.
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)
Temos que x0
- 42 e y0
6
- 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
Com t
Y
y0 - a.t
-42 -52.t
Z
- 30 - 37.t
Para encontrar as soluções da equação em N, basta determinarmos t de modo que
sejam satisfeitas asdesigualdades:
X
0eY
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
O que implica que se {t
-0,808 e -30 -37.t
Z; t
0, onde t
-0,812.
-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
Logo se {t
Z; t
10.000 daí obtemost
- 6} a equação N
�
- 6,001
- 1.545 – 1.924.t nos fornece um número N
10.000.
60
Agora para que esse número N seja natural e menor que 10.000 devem ser
satisfeitas ao mesmo tempo as condições {t
que t
Z; t
1} e {t
Z; t
6} que implicam
{ - 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
É fácil perceber que o mdc(50, 20)
mdc(50, 20)
510
10 e a equação dada tem solução, pois
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)
Onde x0
-102 e y0
51
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
Com t
y0 – a.t
Y
-102 + 5.t
Z
51 – 2.t
Na busca de soluções não negativas devem ser satisfeitas as desigualdades:
x
0ey
0, assim temos que �-102 + 5.t
0 e 51 –2.t
0
Isto é:
t
20,4 e t
25,5
61
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
É fácil ver que o mdc(15, 6)
83
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:
62
8
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
1
1
2
5
3
2
1
3
2
1
0
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)
Logo, o par de inteiros x0
1.000 e y0
500
- 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
Com t
Y
y0 - a.t
1000 + 5.t
Z
-1500 -8.t
O problema requer soluções inteiras e positivas, que serão encontradas escolhendo
t de modo que sejamsatisfeitas as desigualdades:
x
0ey
0, assim têm que 1000 + 5.t
0 e -1500 -8.t
0
Isto é:
t
O que implica que {t
Z; -200
-200 e t
t
-187,5
-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.
63
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:
4
Como o mdc(3, 4)
1
2
1
3
1
1
1
1
0
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)
Logo, o par de inteiros x0
- 61 e y0
61
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
Y
x0 + b.t
-61 + 4.t
Com t
Z
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
0ey
0, assim temos que - 61 + 4.t
0 e 61 – 3.t
0
64
Isto é:
15,25
O que implica que t
t
20,33…
{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:
31
31
2.12 + 7, então 7
12
1.7 + 5, então 5
7
1.5 + 2, então 2
2
2
1
1
2
12
7
5
2
1
7
5
2
1
0
31 - 2.12
12 -1.7
7 - 1.5
65
5
2.2 + 1, então 1
2
1.2 + 0
5 - 2.2
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
31 + 2.12) = 13.12 + 5.(-31)
Assim o mdc (12, 31)
3.(12 -7) - 2.7
3.12 + 5.(- 7)
3.12 + 5.(-
1
1 é dado por:
12.(13) + 31.(-5)
1
Multiplicando a equação por 368, segue que.
12.(4784) + 31.(- 1840)
Temos que x0
4784 e y0
368
- 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
y
y0 - a.t
Z
-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
1
-1840 -12.t
12
Assim temos para y:
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.
66
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
Pelo enunciado, 12.x + 31.y
x
31 do mês y, 1
y
12.
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
Observe que mdc (31, 21)
1770.
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:
1
21 + (-2).10
31
1.21 + 10;
21
2.10 + 1;
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
Portanto, 21.t
3540 e 31.t
0 e 5310 -31.t
5310, que é o mesmo que: t
Assim, como t é um número inteiro, temos que 169
t
0.
168,57 e t
171,29.
171. Desse modo, as
soluções são:
67
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”.
68
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.
69
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.
70
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.
71
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?
72
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?
73
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.
74
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.
75
[10] FONSECA, Rubens V., Teoria dos Números Belém: Universidade do Estado do
Pará. 2011.
76