Seja
tal que
, onde cada
é um inteiro tal que
. Nestas condições mostre que:
se, e somente se,
Passo 1
O enunciado dá um número natural
escrito na base decimal como
com cada dígito
inteiro e
. A pergunta é mostrar a equivalência:
Vou trabalhar com uma notação curta para a parte que aparece repetida: definirei
Com isso o que precisamos provar equivale a
A resolução verdadeira começa agora.
Passo 2
Reescrevendo
em função de
e
:
Isto é só recolher os termos: multiplicando
por
recuperamos todas as potências até
menos a unidade, e depois somamos
.
Passo 3
Agora uso aritmética modular (congruências) mod
. Uma regra simples diz que podemos reduzir coeficientes módulo
. Note que
porque
é múltiplo de
. Aplicando essa redução à expressão de
obtemos, em congruências:
Explicando devagar: dizer
significa que
divide
. Essa equivalência é válida porque substituir
por
muda o valor por um múltiplo de
.
Passo 4
Queremos que
divida
, isto é
. Usando a congruência do passo anterior, isso é equivalente a
Ou seja,
Aqui estou apenas reescrevendo
como
.
Passo 5
Para transformar essa relação numa expressão envolvendo
precisamos “dividir” por
modulo
. Isso é possível porque
, então
tem inverso multiplicativo módulo
. Vou encontrar esse inverso: o número
é inverso de
modulo
porque
Portanto, multiplicando a congruência
por
(o inverso de
), obtemos
Isto é permitido porque se
então
para qualquer
, e escolhemos
.
Passo 6
Calculemos
módulo
. Note que
porque
. Assim
Portanto a congruência do passo anterior vira
que é equivalente a
Em palavras:
(que era equivalente a
) é equivalente a
.
Passo 7
Juntando os passos: começando de
obtemos
, que pelo passo 3 é equivalente a
; pelo passo 5 e 6 isso é equivalente a
, ou seja
. As implicações são reversíveis (cada passo usou equivalências), logo temos a bicondicional desejada:
o que, lembrando a definição de
, é exatamente