Resolva cada um dos problemas-enigma a seguir:
Mahaviracarya, 850. Havia 63 pencas de banana iguais junto a 7 bananas. Elas foram divididas igualmente entre 23 viajantes. Qual é o número de bananas em cada penca?
[Sugestão: Considere a equação diofantina 63 x+7=23 y.]

Passo 1

Beleza, então vamos lá: o enunciado diz que tem 63 pencas de banana, todas com o mesmo número de bananas (vamos chamar esse número de ), mais 7 bananas soltas. No total, todas essas bananas são divididas igualmente entre 23 viajantes, e cada viajante recebe bananas.
Conteúdo: equação diofantina linear e congruência modular.
O que vamos precisar:
  • Montar a equação .
  • Transformar isso numa congruência pra achar (porque queremos que seja múltiplo de 23).
  • Usar o algoritmo de Euclides estendido pra achar o inverso modular e resolver a congruência.

Passo 2

Primeiro, escrevemos a condição de divisão exata como congruência módulo 23:
63x equiv -7 pmod23.
Isso equivale a
17x equiv 16 pmod23
Agora simplificamos e módulo 23:
  • .
  • .
    Logo a congruência vira

Passo 3

Para resolver 17k equiv 1 pmod23, precisamos achar o inverso de -4cdot17 + 3cdot23 = 1 módulo 23, ou seja, um número tal que
Como , existe solução. Usamos o algoritmo de Euclides estendido:
23 = 1·17 + 6
17 = 2·6 + 5
6 = 1·5 + 1
5 = 5·1 + 0
Agora voltamos substituindo para expressar 1 como combinação de 23 e 17:
1 = 6 − 1·5
= 6 − 1·(17 − 2·6) = 3·6 − 1·17
= 3·(23 − 1·17) − 1·17 = 3·23 − 4·17
Logo
Isso diz que é o inverso de módulo 23. Como queremos um número entre 0 e 22, somamos 23:
.
Então o inverso de é .

Passo 4

Agora multiplicamos a congruência x equiv 19 cdot 16 pmod23 pelo inverso 19:
304 div 23 = 13) resto (5,
Calculando x equiv 5 pmod23.
Agora reduzimos módulo 23:
ou seja,
Portanto

Resposta

Cada penca tem 5 bananas.

Exercícios relacionados