(
ponto) Sejam
e
inteiros positivos com
. Se os três últimos algarismos de
são os mesmos que os três últimos algarismos de
, encontre
e
tais que
assuma o menor valor posível.
BOM TRABALHO!
Passo 1
O enunciado pede: encontrar inteiros positivos
e
, com
, tais que os três últimos algarismos de
são os mesmos que os três últimos algarismos de
, e fazer isso de forma que
seja o menor possível.
Informações relevantes dadas:
- Precisamos que os três últimos algarismos sejam iguais, ou seja, que
-
e são inteiros positivos e . - Objetivo: minimizar
.
Passo 2
Ideia e ferramentas que vou usar (explicando devagarzinho):
- Trabalhar com congruências módulo
. Como e , pela Teoria dos Restos Chineses (CRT) essa congruência módulo é equivalente ao sistema das congruências simultâneas módulo e modulo :
- Vou tratar cada módulo separadamente e depois combinar as condições.
- Conceito importante que vou usar: se
é invertível modulo e , então podemos “cortar” (ou seja, multiplicar pelo inverso) para obter . O menor inteiro positive com chama-se ordem multiplicativa de modulo ; então deve ser múltiplo dessa ordem. - Também vou usar que
, então a ordem de um elemento invertível modulo divide .
Passo 3
Condição módulo
. Primeiro reduzo a base:
portanto
para todo
.
Agora explico os valores de
módulo
:
Logo, para que
com
existem apenas estas possibilidades:
- Se
então para igualar precisamos , o que força (impossível porque ). - Se
então precisamos , o que força (impossível porque ). - Se
então e para qualquer também , portanto a congruência modulo fica satisfeita sempre que e .
Conclusão intermediária: devemos ter
e
, caso contrário não conseguimos ter
e a congruência modulo
simultaneamente.
Passo 4
Condição módulo
. Primeiro reduzo a base modulo
:
Então a condição é
Como
, o número
é invertível modulo
, então posso multiplicar ambos os lados por
e obter
Isto significa que
é um múltiplo da ordem multiplicativa de
módulo
. Denotando por
, temos
. Como
, sabemos que
divide
. Nosso próximo passo é determinar
.
Passo 5
Cálculo da ordem de
módulo
. Observação útil:
. Então podemos estudar
em vez de
. Note:
Se eu achar a ordem de
modulo
, posso inferir a ordem de
.
Vou calcular potências de
módulo
passo a passo (explico cada conta para que você possa fazer na prova sem calculadora, usando reduções simples):
-
. Reduzindo modulo :
-
. Reduzindo:
-
. -
. -
. Reduzindo:
-
. -
. Reduzindo:
A grande conclusão daqui é que
. Então elevando ao quadrado,
Isto mostra que o menor período (a ordem) de
divide
. Além disso, como
e não
, a ordem de
não divide
; portanto a ordem de
é exatamente
.
Agora relaciono com
. Para
vale
.
- Se
é par, então e o menor par com é . - Se
é ímpar, então precisaríamos de , mas já vimos que o menor expoente com é , que é par; assim não existe expoente ímpar que dê . Logo não há ímpar com .
Portanto a ordem de
modulo
(isto é, de
) também é
:
Passo 6
Combinação das condições e minimização de
.
Resumindo:
- Da análise módulo
obtivemos que deve ser múltiplo de . Ou seja, com . - Da análise módulo
obtivemos que é necessário ter e (caso contrário a congruência módulo não pode ocorrer com ).
Queremos minimizar
. Escrevendo
, temos
Para minimizar, tomamos o menor
possível, isto é
(pois
deve ser positivo porque
), e o menor
possível compatível com a condição
, que é
. Assim:
e
Ainda é preciso verificar rapidamente que não existe solução com
dando soma menor:
- Se
então, para satisfazer módulo precisaríamos múltiplo de , ou seja . Mas modulo teríamos e quando , então não dá igualdade. O único que daria seria (impossível). - Se
raciocínio semelhante: módulo , e a única potência de congruente a módulo é , logo não há com essa propriedade.
Portanto não existe par com
e
que satisfaça ambas as congruências. Assim a escolha
dá a menor soma possível
.
Passo 7
Verificação final curta (consistência):
- Módulo
: como e , temos e , logo coincidem modulo . - Módulo
: como e (de fato tem ordem ), temos , logo também coincidem modulo . - Então, pelas propriedades do CRT, coincidem módulo
. Tudo consistente.