Aplicações da Congruência Linear

Probleminhas

1. APLICAÇÕES DA TEORIA DAS CONGRUÊNCIAS LINEARESO texto abaixo foi escrito em 28 de outubro de 2003.
Trata-se de probleminhas que são simples na sua aparên-
cia, porém para uma melhor compreensão há a necessi-
dade de se usar resultados da Teoria dos Números. Uti-
lizaremos a teoria das congruências lineares para solu-
cionar tais probleminhas.
Problema 1- UM PROBLEMA DE QUEBRAR OS OVOS.
A senhora Clara vende ovos em sua barraquinha na feira do Bagaço.
Certo dia, um bebum chamado Zé di Munes, ao passar por lá, quebrou todos
os ovos que estavam na barraca da senhora Clara. Inconformada com o pre-
juízo, chamou a polícia a qual conduziu vítima e acusado até uma delegacia.
Zé di Munes concordou em pagar o prejuízo, porém, ao ser interrogada pelo
delegado sobre a quantidade de ovos quebrados, Julieta disse apenas que se
somados de dois em dois, de três em três, de quatro em quatro, de cinco em
cinco e de seis em seis, sempre sobrava um ovo. Mas somados de sete em
sete não sobrava ovo. E agora? Se fosse você? Como resolveria o problema?
Solução:Sexé a quantidade de ovos existentes na barraca da senhora
Clara, então devemos ter
x= 2k1+ 1
x= 3k2+ 1
x= 4k3+ 1
x= 5k4+ 1
x= 6k5+ 1
x= 7k
ou de modo equivalente
x1 = 2k1
x1 = 3k2
x1 = 4k3
x1 = 5k4
x1 = 6k5
1

2. x= 7k:
As cinco primeiras equações nos dão o seguinte sistema de congruências
x1(mod2)
x1(mod3)
x1(mod4)
x1(mod5)
x1(mod6):
Para resolver este problema, vamos lembrar de um resultado da teoria
das congruências.
Teorema A-Sexa(mod m1)exa(mod m2);entãoxa(mod m);
ondem=mmc(m1; m2).
PeloTeorema A, devemos terx1(mod mmc(2;3;4;5;6));ou seja,
x1(mod60):Entãox= 60q+1;para umq2Zf0g(ou vários) que deve
satisfazer o problema inicial. Pelo que vimos até agora,xdeve ser tal que
x= 60q+ 1 = 7k:
Mas
60q+ 1 = 7k)60q 1(mod7):
Como16(mod7);obtemos por transitividade60q6(mod7)ou
61061(mod7):
Precisaremos de mais um resultado da teoria dos números.
Teorema B-Sejama; b; c; m2N;comc6= 0em >1:Temos que
acbc(mod m),ab(mod
m
mdc(c; m)
):
PeloTeorema B
610q61(mod7))10q1(mod7):
(1) 2

3. Agora note que1 20(mod7)e de (1) já sabemos que10q1(mod7):
Então pela transitividade da congruência resulta que
10q 20(mod7):
(2)
Usando oTeorema Bem (2) resulta queq 2(mod7):Isso nos dá
q= 7k2comk2N f0g:Substituindo-se esse resultado emx= 60q+ 1;
obtemos
x= 420k119ondek2N f0g:
(3)
De acordo com(3), a menor quantidade de ovos que poderia ter na barraca
de dona Clara ocorre quando k=1,ou seja, x=301.
Venhamos e convenhamos, mesmo com essa menor quantidade, o fato de
se quebrarem todos é um azar danado hein? Bem, o nal de estória nem me
perguntem que eu também não sei.
Problema 2- O PROBLEMA DO PINÓQUIO.
Sabe-se que Pinóquio ao passar por um bosque respondeu exatamente vinte
perguntas. Para cada mentira seu nariz crescia 5cm e para cada verdade,
diminuia 3cm. Em dois momentos se nariz havia crescido 22cm. Quais
foram esses momentos?
Solução-O problema consiste em obter inteirosxey, satisfazendo a
condição
5x2y= 22
(4)
Fazendo-se algumas inspeções poder-se-i-a chegar à resposta. Porém re-
solveremos a equação diofantina acima utilizando congruência linear. Deter-
minaremos inicialmentexsatisfazendo
5x22(mod3)
(5)
e depois voltamos à equação (4) para determinarmosy.
Como221(mod3), segue de (5) e da transitividade da congruência
que
5x1(mod3)
(6)
Como110(mod3);segue de (6) e da transitividade da congruência que
5x10(mod3):PeloTeorema Bresulta quex2(mod3);ou de modo
equivalente,x= 3k+ 2, ondek2N f0g:Substituindo-se esse resultado na
equação (4) obtemosy= 5k4:
3

4. Assim, a solução do problema é
x= 3k+ 2ey= 5k4com o mesmok2N f0g:
Comk= 1obtemosx= 5ey= 1, ou seja, cinco mentiras e uma verdade
e portanto na sexta pergunta.
Comk= 2obtemosx= 8ey= 6, ou seja, oito mentiras e seis verdade
e portanto na décima quarta pergunta.
Problema 3- O PROBLEMA DOS TRÊS MARINHEIROS (OU
DAS MOEDAS).
Um navio que voltava de Serendibe trazendo grande partida de especiarias,
foi assaltado por violenta tempestade. A embarcação teria sido destruida pela
fúria das ondas se não fosse a bravura e o esforço de três marinheiros que,
no meio da tormenta, manejaram as velas com extrema perícia. O coman-
dante, querendo recompensar os denodados marujos, deu-lhes certo número
de catis(moedas). Esse número, superior a duzentos, não chegava a trezen-
tos. As moedas foram colocadas numa caixa para que no dia seguinte, por
ocasião do desembarque, o almoxarife as repartisse entre os três corajosos
marinheiros. Aconteceu, porém que, durante a noite, um dos marinheiros
acordou, lembrou-se das moedas e pensou: será melhor que eu tire a minha
parte, assim não terei ocasião de discutir ou brigar com meus amigos. E, sem
nada a dizer aos companheiros, foi, pe ante pé, até onde se achava guardado
o dinheiro, dividiu-o em três partes iguais, mas notou que a divisão não era
exata e que sobrava um catil. "Por causa desta mísera moedinha é capaz de
haver amanhã discussão e rixa. O melhor é jogá-la fora". E o marinheiro
atirou a moeda ao mar, retirando-se cauteloso. Levava a sua parte e deixava
no mesmo lugar a parte que cabia aos companheiros. Horas depois o segundo
marinheiro teve a mesma idéia. Foi à arca em que se depositara o prêmio
coletivo e dividiu-o em três partes iguais. Sobrava uma moeda. Ao marujo,
para evitar futuras dúvidas veio a lembrança de atirá-la no mar. E dali voltou
levando consigo a parte a que se julgava com direito. O terceiro marinheiro,
ignorando, por completo, a antecipação dos colegas, teve o mesmo alvitre.
Levantou-se de madrugada e foi, pé ante pé, à caixa dos catis. Dividiu as
moedas que lá encontrou em três partes iguais; a divisão não foi exata. So-
brou um catil. Não querendo complicar o caso, o marujo atirou ao mar a
moedinha excedente, retirou a terça parte para si e voltou tranquilo para o
seu leito. No dia seguinte, na ocasião do desembarque, o almoxarife do navio
encontrou um punhado de catis na caixa. Soube que essas moedas pertencia
aos três marinheiros. Dividiu-as em três partes iguais, dando a cada um dos
marujos uma dessas partes, ainda dessa vez a divisão não foi exata. Sobrava
4

5. uma moeda, que o almoxarife guardou como pagamento do seu trabalho e de
sua habilidade.É claro que nenhum dos marinheiros reclamou, pois cada um
deles estava convencido de que já havia retirado da caixa a parte que lhe cabia
do dinheiro. Pergunta-se anal: Quantas eram as moedas? Quanto recebeu
cada um dos marujos?
Solução-SejaAa quantidade de moedas existentes inicialmente. As situ-
ações vividas pelos três marinheiros podem ser descritas da seguite maneira:
À noite:
O primeiro marinheiro divide asAmoedas em três partes iguais, sobra
uma moeda que é jogada fora e retira para siBmoedas restando2Bmoedas
na caixa.
(A1)=3 =B
(7)
O segundo marinheiro divide as2Bmoedas em três partes iguais, sobra
uma moeda que é jogada fora e retira para siCmoedas restando2Cmoedas
na caixa.
(2B1)=3 =C
(8)
O terceiro marinheiro divide as2Cmoedas em três partes iguais, sobra
uma moeda que é jogada fora e retira para siDmoedas restando2Dmoedas
na caixa
(2C1)=3 =D
(9)
Pela manhã:
O almoxarife divide as2Dmoedas em três partes iguais aEmoedas que
cabem a cada um dos marinheiros, sobra uma moeda a qual ca para ele
pelos seus serviços.
(2D1)=3 =E
(10)
Da equação(10)obtemosD= (3E+ 1)=2;
que substituindo-se na equação(9)nos dáC= (9E+ 5)=4;
que substituindo-se na equação (8) obtém-seB= (27E+ 19)=8;
que substituindo-se na equação (7) resulta8A65 = 81E:
A última equação nos diz que devemos determinarAtal que
8A65(mod81)
(11)
Note agora que65 16(mod81):Deste fato, da equação (11) e usando
a transitividade da congruência obtemos8A 16(mod81):OTeorema
Bnos dáA 2(mod81):Então, devemos ter
5

6. A= 81k2ondek2N f0g:
(12)
Por exemplo, tomandok= 3na equação (12) temosA= 241;que satisfaz
as condições do problema.
Problema 4- O PROBLEMA DO HOTEL.
Um grupo de pessoas gastou 1000 dólares em um hotel. Sabedo-se que
apenas alguns dos homens estavam acompanhados pelas esposas e que cada
homem gastou 19 dólares e que cada mulher gastou 13 dólares, pode-se de-
terminar quantas mulheres e quantos homens estavam no hotel?
Solução-Sendoxa quantidade de homens eya quantidade de mulheres
devemos ter
19x13y= 1000
(13)
ou de modo equivalente
19x 1000(mod13)
(14)
Como1000 25(mod13)e25 38(mod13), obtemos pela tran-
sitividade da congruência19x 38(mod13):OTeorema Bnos dá
x 2(mod13);donde resulta que
x=13k+ 2
(15)
Das equações(13)e (15) obtemos
y= 19k+ 74
(16)
Considerando que existem mais homens do que mulheres, devemos ter
x > y;ou seja,
13k+ 2>19k+ 74
o que nos dák <2;25;ou seja,k 3. Parak=3obtemosx= 41
ey= 17;os únicos valores que satisfazem o problema.
O problema do hotel foi retirado do site de Paulo Marques de Feira de
Santana na Bahia, em 19 de dezembro de 2002. Lá o problema foi resolvido
utilizando-se a técnica das equações diofantinas e obteve-se como solução
geral
x=5013key= 150 + 19kcomk 7:
O leitor pode tirar suas conclusões a respeito das duas soluções.
6

7. Espero que tenham gostado destes probleminhas.
Contato: [email protected]
Prof. Elzimar de Oliveira Runo.
7