Desafio das divisões

Para resolver essa questão, devemos encontrar o menor resultado comum das seguintes equações:

3w + 1 = N
4x + 2 = N
5y + 3 = N
6y + 4 = N

Para a equação 6y + 4 encontramos como 10 primeiras soluções os números: 4,10,16,22,28,34,40,46,52,58.

Desses, os números 28 e 58 satisfazem também 5y + 3, porém apenas o número 58 satisfaz tanto 4x + 2, quanto 3w + 1. logo o menor número inteiro positivo será 58.

Problemas que envolvem restos são sempre lindos, não é verdade? Pós OBM, hoje é um ótimo dia para aplicar Teoria dos Números!

Vamos lá, tem duas formas de resolver esse problema: uma perspicaz e outra um pouco mais conteudista, mas que envolve assuntos que eu particularmente amo.

[centro][b]Resolução 1: A Resolução Perspicaz[/b][/centro]

A primeira delas é observar que, segundo a dica, esse número sempre é duas unidades a menos que o divisor em questão. Repare, entretanto, que se sabemos o resto dele na divisão por [tex]3[/tex] e por [tex]4=2\cdot 2[/tex], não precisamos levar o resto na divisão por [tex]6=2\cdot [/tex]3 em conta, pois ele é decorrência desses outros dois restos!

Assim, vamos olhar para os restos na divisão por 3, 4 e 5, que são todos primos entre si. Com a dica, fica fácil de ver que tal número é [tex]3\cdot 4 \cdot 5-2=60-2=58[/tex], pois 60 é múltiplo dos três números, e ao retirarmos 2 unidades de 60, é claro que o resto dele na divisão por 3 é [tex]3-2=1[/tex], por 4 é [tex]4-2=2[/tex] e por 5 é [tex]5-2=3[/tex]. Resumidamente, garantimos que tal número é o menor inteiro positivo com tal propriedade pois todos os números que também satisfazem o problema são [tex]58+60x[/tex] para algum [tex]x[/tex] inteiro não negativo! Basicamente, [tex]581[/tex], resolvemos deixar o 6 de fora (na verdade, isso não fará diferença nenhuma pelo mesmo motivo que explicamos na solução 1). Enfim, com tudo isso em mente, uma solução será dada por:
$$
\large x_0=\displaystyle\sum^{3}_{i=1}\dfrac{m}{m_i}\cdot a_i\cdot b_i
$$ Com [tex]m=60[/tex], [tex]m_i[/tex] sendo cada um dos módulos na ordem que escrevemos, [tex]b_i[/tex] sendo o inverso modular de [tex]\dfrac{m}{m_i}[/tex] no módulo [tex]m_i[/tex] e [tex]a_i[/tex] sendo o resto que queremos para determinado [tex]m_i[/tex]. Assim:
$$
\large x_0=20\cdot 1 \cdot 2+15\cdot 2\cdot 3+12\cdot 3 \cdot 3=238
$$ Logo, 238 é uma solução particular (note que [tex]238=3\cdot79+1=4\cdot 59+2=5\cdot 47+3[/tex]), e além disso, esse teorema nos afirma que todas as soluções são únicas módulo [tex]m[/tex], e note que:
$$
\large 238 \equiv 58 \pmod {60}
$$ Assim, 58 é a menor solução possível para o problema, como queríamos! Ah, e repare que [tex]58=6\cdot 9+4[/tex], para mostrar de uma vez por todas que o 6 não fazia diferença alguma!

Além de tudo isso, há uma peculiaridade em relação a problemas sobre teoria dos números… eles nunca serão demais! E se existisse uma olimpíada focada só nesse tópico? Pode não ser a melhor ideia do mundo, mas eu me divertiria bastante! ᕙ(`▽´)ᕗ