( \mathbf{1 , 0} ponto) Sejam m e n inteiros positivos com m<n. Se os três últimos algarismos de 1978^{m} são os mesmos que os três últimos algarismos de 1978^{n}, encontre m e n tais que m+n assuma o menor valor posível.
BOM TRABALHO!

Passo 1

O enunciado pede: encontrar inteiros positivos m e n, com m<n, tais que os três últimos algarismos de 1978^{m} são os mesmos que os três últimos algarismos de 1978^{n}, e fazer isso de forma que m+n seja o menor possível.
Informações relevantes dadas:
  • Precisamos que os três últimos algarismos sejam iguais, ou seja, que
1978^{m}\equiv1978^{n}\pmod{1000}.
  • m e n são inteiros positivos e m<n.
  • Objetivo: minimizar m+n.

Passo 2

Ideia e ferramentas que vou usar (explicando devagarzinho):
  • Trabalhar com congruências módulo 1000. Como 1000=8\cdot125 e \gcd(8,125)=1, pela Teoria dos Restos Chineses (CRT) essa congruência módulo 1000 é equivalente ao sistema das congruências simultâneas módulo 8 e modulo 125:
1978^{m}\equiv1978^{n}\pmod{8} \quad\text{e}\quad 1978^{m}\equiv1978^{n}\pmod{125}.
  • Vou tratar cada módulo separadamente e depois combinar as condições.
  • Conceito importante que vou usar: se a é invertível modulo t e a^m\equiv a^n\pmod{t}, então podemos “cortar” a^m (ou seja, multiplicar pelo inverso) para obter a^{n-m}\equiv1\pmod{t}. O menor inteiro positive d com a^d\equiv1\pmod{t} chama-se ordem multiplicativa de a modulo t; então n-m deve ser múltiplo dessa ordem.
  • Também vou usar que \varphi(125)=100, então a ordem de um elemento invertível modulo 125 divide 100.

Passo 3

Condição módulo 8. Primeiro reduzo a base:
1978\equiv 1978-8\cdot247 = 1978-1976 = 2 \pmod{8},
portanto 1978^{k}\equiv 2^{k}\pmod{8} para todo k.
Agora explico os valores de 2^k módulo 8:
2^1\equiv 2,\quad 2^2\equiv4,\quad 2^3\equiv8\equiv0,\quad\text{e para }k\ge3\text{ temos }2^k\equiv0\pmod{8}.
Logo, para que 2^{m}\equiv2^{n}\pmod{8} com m<n existem apenas estas possibilidades:
  • Se m=1 então para igualar precisamos 2^{n}\equiv2\pmod{8}, o que força n=1 (impossível porque n>m).
  • Se m=2 então precisamos 2^{n}\equiv4\pmod{8}, o que força n=2 (impossível porque n>m).
  • Se m\ge3 então 2^{m}\equiv0 e para qualquer n\ge3 também 2^{n}\equiv0, portanto a congruência modulo 8 fica satisfeita sempre que m\ge3 e n\ge3.
Conclusão intermediária: devemos ter m\ge3 e n\ge3, caso contrário não conseguimos ter m<n e a congruência modulo 8 simultaneamente.

Passo 4

Condição módulo 125. Primeiro reduzo a base modulo 125:
1978\equiv 1978-125\cdot15 = 1978-1875 = 103 \pmod{125}.
Então a condição é
103^{m}\equiv103^{n}\pmod{125}.
Como \gcd(103,125)=1, o número 103 é invertível modulo 125, então posso multiplicar ambos os lados por (103^{m})^{-1} e obter
103^{n-m}\equiv1\pmod{125}.
Isto significa que n-m é um múltiplo da ordem multiplicativa de 103 módulo 125. Denotando por d=\operatorname{ord}_{125}(103), temos d\mid(n-m). Como \varphi(125)=100, sabemos que d divide 100. Nosso próximo passo é determinar d.

Passo 5

Cálculo da ordem de 103 módulo 125. Observação útil: 103\equiv-22\pmod{125}. Então podemos estudar 22 em vez de 103. Note:
103^{k}=(-22)^{k}=(-1)^{k}22^{k}.
Se eu achar a ordem de 22 modulo 125, posso inferir a ordem de -22.
Vou calcular potências de 22 módulo 125 passo a passo (explico cada conta para que você possa fazer na prova sem calculadora, usando reduções simples):
  • 22^{2}=484. Reduzindo modulo 125:
484-125\cdot3=484-375=109,\quad\text{logo }22^{2}\equiv109\pmod{125}.
  • 22^{4}=(22^{2})^{2}\equiv109^{2}=11881. Reduzindo:
11881-125\cdot95=11881-11875=6,\quad\text{logo }22^{4}\equiv6\pmod{125}.
  • 22^{5}=22^{4}\cdot22\equiv6\cdot22=132\equiv132-125=7\pmod{125}.
  • 22^{10}=(22^{5})^{2}\equiv7^{2}=49\pmod{125}.
  • 22^{20}=(22^{10})^{2}\equiv49^{2}=2401. Reduzindo:
2401-125\cdot19=2401-2375=26,\quad\text{logo }22^{20}\equiv26\pmod{125}.
  • 22^{25}=22^{20}\cdot22^{5}\equiv26\cdot7=182\equiv182-125=57\pmod{125}.
  • 22^{50}=(22^{25})^{2}\equiv57^{2}=3249. Reduzindo:
3249-125\cdot25=3249-3125=124\equiv-1\pmod{125}.
A grande conclusão daqui é que 22^{50}\equiv-1\pmod{125}. Então elevando ao quadrado,
22^{100}\equiv(-1)^{2}\equiv1\pmod{125}.
Isto mostra que o menor período (a ordem) de 22 divide 100. Além disso, como 22^{50}\equiv-1 e não 1, a ordem de 22 não divide 50; portanto a ordem de 22 é exatamente 100.
Agora relaciono com -22. Para (-22)^{d}=1 vale (-22)^{d}=(-1)^{d}22^{d}.
  • Se d é par, então (-22)^{d}=22^{d} e o menor d par com 22^{d}=1 é d=100.
  • Se d é ímpar, então precisaríamos de 22^{d}\equiv-1, mas já vimos que o menor expoente com 22^{k}\equiv-1 é k=50, que é par; assim não existe expoente ímpar que dê -1. Logo não há d ímpar com (-22)^{d}=1.
Portanto a ordem de -22 modulo 125 (isto é, de 103) também é 100:
d=\operatorname{ord}_{125}(103)=100.

Passo 6

Combinação das condições e minimização de m+n.
Resumindo:
  • Da análise módulo 125 obtivemos que n-m deve ser múltiplo de 100. Ou seja, n-m=100k com k\in\mathbb{Z}_{>0}.
  • Da análise módulo 8 obtivemos que é necessário ter m\ge3 e n\ge3 (caso contrário a congruência módulo 8 não pode ocorrer com m<n).
Queremos minimizar m+n. Escrevendo n=m+100k, temos
m+n = 2m+100k.
Para minimizar, tomamos o menor k possível, isto é k=1 (pois k deve ser positivo porque n>m), e o menor m possível compatível com a condição m\ge3, que é m=3. Assim:
m=3,\qquad n=3+100=103,
e
m+n=3+103=106.
Ainda é preciso verificar rapidamente que não existe solução com m<3 dando soma menor:
  • Se m=1 então, para satisfazer módulo 125 precisaríamos n-1 múltiplo de 100, ou seja n=1+100k. Mas modulo 8 teríamos 2^{1}=2 e 2^{n}\equiv0 quando n\ge3, então não dá igualdade. O único n que daria 2^{n}\equiv2 seria n=1 (impossível).
  • Se m=2 raciocínio semelhante: 2^{2}\equiv4 módulo 8, e a única potência de 2 congruente a 4 módulo 8 é 2^{2}, logo não há n>2 com essa propriedade.
Portanto não existe par com m<3 e m<n que satisfaça ambas as congruências. Assim a escolha m=3,n=103 dá a menor soma possível 106.

Passo 7

Verificação final curta (consistência):
  • Módulo 8: como m\ge3 e n\ge3, temos 1978^{m}\equiv2^{m}\equiv0 e 1978^{n}\equiv2^{n}\equiv0\pmod{8}, logo coincidem modulo 8.
  • Módulo 125: como n-m=100 e 103^{100}\equiv1\pmod{125} (de fato 103 tem ordem 100), temos 103^{n}\equiv103^{m}\pmod{125}, logo também coincidem modulo 125.
  • Então, pelas propriedades do CRT, coincidem módulo 1000. Tudo consistente.

Resposta

m=3
n=103
m+n=106

Exercícios relacionados