Três garimpeiros encontraram um saco de pedras de ouro. Ao tentar dividir as pedras igualmente entre os 3 , sobrou 2 pedras. Se tentassem dividir por 5, sobrariam 4 pedras. Se tentassem dividir por 7, sobrariam 3 pedras. Qual é a menor quantidade possível de pedras de ouro que eles podem encontrar?
Passo 1
Vou listar claramente o que o enunciado pede e quais informações temos.
- Pergunta: qual é a menor quantidade possível de pedras de ouro que satisfaz todas as condições do enunciado?
- Informações (peguei do enunciado):
- Ao dividir as pedras por
sobra . Ou seja, - Ao dividir por
sobra . Ou seja, - Ao dividir por
sobra . Ou seja,
- Ao dividir as pedras por
Passo 2
Explicando a ideia que vou usar (passo a passo, sem assumir que já sabe):
- Uma congruência do tipo
significa que ao dividir por o resto é . Em outras palavras, existem inteiros tais que - Quando temos várias congruências como aqui, uma forma prática de resolver é combinar duas congruências de cada vez, encontrando uma congruência equivalente com módulo igual ao mínimo múltiplo comum (quando os módulos são primos entre si, o MMC é o produto).
- Vou primeiro combinar as duas primeiras congruências (
e ), encontrando uma fórmula geral para que já satisfaça essas duas. Depois uso essa fórmula para impor a condição do módulo .
Passo 3
Resolver as primeiras duas congruências:
Método algébrico (bem didático):
- Escrevo
a partir da primeira congruência: onde é inteiro. - Substituo na segunda congruência:
Subtraindo dos dois lados: - Agora precisamos achar
que satisfaça isso. O número tem inverso módulo porque . O inverso de modulo é porque . Multiplicando ambos os lados por esse inverso: - Logo
para algum inteiro . Substituindo de volta em : - Conclusão: qualquer
que satisfaça as duas primeiras congruências tem a forma
(Comentário rápido e intuitivo: listar os números
congruentes a
mod
levaria a encontrar
como o primeiro que também deixa resto
ao dividir por
. O procedimento algébrico acima é o mesmo raciocínio, só mais sistemático.)
Passo 4
Agora imponho a terceira congruência usando a fórmula encontrada:
e quero que também valha
Substituindo:
Simplifico os coeficientes módulo
:
-
porque é múltiplo de . -
porque .
Portanto a congruência fica muito simples:
Passo 5
Do resultado
segue que os valores de
são da forma
com inteiro
. Para obter o menor
pegamos o menor
que satisfaça isso, que é
. Substituo em
:
Passo 6
Verificação (para eu te dar confiança de que está certo):
-
deixa resto , então . -
deixa resto , então . -
deixa resto , então .
Tudo confere.
Passo 7
Observação sobre a unicidade: como os módulos
,
e
são pareswise coprimos, o Teorema Chinês dos Restos garante que as soluções formam uma classe única módulo
. Ou seja, todas as soluções positivas são
e portanto a menor solução positiva é mesmo
.