Olimpíadas ⇒ Equações Diofantinas Lineares Tópico resolvido

[emanuel9393MOD]

Se um macaco sobe uma escada de dois em dois degraus, sobra um degrau; se ele sobe de três em três degraus, sobra dois degraus. Quantos degraus a escada possui, sabendo que o número de degraus é múltiplo de sete e está compreendido entre [tex3]40[/tex3] e [tex3]100[/tex3]?

[Cássio]

Olá Patrick.

Esse problema pode ser pensado como um sistema de congruência. Sendo [tex3]x[/tex3] a quantidade de degraus, temos:

[tex3]\begin{cases}x\equiv 1\pmod{2} \\ x\equiv 2\pmod{3}\\ x\equiv 0\pmod{7}\end{cases}[/tex3]

Caso conheça o Teorema Chinês do Resto é mais rápido calcular as soluções. Mas vou fazer no modo de substituição.

[tex3]x\equiv 1\pmod{2},[/tex3] então existe inteiro [tex3]q_0[/tex3] tal que [tex3]x=2q_0+1.[/tex3]

[tex3]x\equiv 2\pmod{3} \iff\ 2q_0+1\equiv 2\pmod{3}\iff 2q_0\equiv 1\pmod{3},[/tex3] fazendo por tentativa, encontramos [tex3]q_0\equiv 2\pmod{3}[/tex3]. Logo, existe [tex3]q_1\in\mathbb{Z},[/tex3] tal que [tex3]q_0=3q_1+2[/tex3]

[tex3]\Longrightarrow x=2q_0+1=2(3q_1+2)+1=6q_1+5[/tex3]

[tex3]x\equiv 0\pmod{7}\iff 6q_1+5\equiv 0\pmod{7}\iff 6q\equiv 2\pmod{7}.[/tex3] Como [tex3]\text{mdc}(2,7)=1,[/tex3] então [tex3]3q_1\equiv 1\pmod{7}.[/tex3] Procurando por tentativa, encontramos
[tex3]q_1\equiv 5\pmod{7}\Longrightarrow q_1=7q_2+5 \ \\ \ \\ \Longrightarrow x=6q_1+5=6(7q_2+5)+5=42q_2+35.[/tex3]

Bom, se [tex3]q_2\le 0\ \Longrightarrow x\le 35[/tex3]
Se [tex3]q\ge 2\Longrightarrow x\ge 119.[/tex3]

A única possibilidade é [tex3]q=1\Longrightarrow x=77.[/tex3]

Abraço.