Teorema de Euler-Fermat

É uma generalização do Pequeno Teorema de Fermat .

O teorema diz que se $\operatorname{mdc}(a,n)=1$ , então

$a^{\varphi(n)} \equiv 1 \pmod{n}$ ,

onde $\varphi$ é a função φ de Euler. Para que você possa ver que esta é uma generalização, basta fazer $n=p$ e lembrar que $\varphi(p)=p-1$ , se $p$ é primo.

Exemplo[]

Se $a$ e $\sqrt[5]{a}$ são números inteiros, prove que eles terminam com o mesmo dígito.

Solução: Em outras palavras, devemos provar que eles congruentes módulo $10$ . Considere $b=\sqrt[5]{a}$ . Então $b^5=a$ . Devemos provar então que

$b^5 \equiv b \pmod{10}.$

Vamos dividir em casos.

1º Caso: $b$ é primo com $10$

Aqui temos uma vantagem: podemos usar o teorema de Euler-Fermat. De fato,

$\varphi(10)=\varphi(2 \cdot 5)=\varphi(2)\varphi(5)=1 \cdot 4=4.$

Assim

$b^4 \equiv 1 \pmod{10} \Rightarrow b^5 \equiv b \pmod{10}.$

2º Caso: $b$ é múltiplo de $10$

Neste caso, $b^5 \equiv 0 \pmod{10}$ e $b \equiv 0 \pmod{10}$ , de onde segue que

$b^5 \equiv b \pmod{10}.$

3º Caso: $b$ é múltiplo de $2$ , mas não de $5$

Então podemos escrever $b=2x$ em que $x$ é primo com $5$ . Assim,

$b^5 \equiv b \pmod{10} \Leftrightarrow 32x^5 \equiv 2x \pmod{10} \Leftrightarrow 2x^5 \equiv 2x \pmod{10} \Leftrightarrow x^5 \equiv x \pmod{5}.$

Essa última afirmação é verdadeira por causa do Pequeno Teorema de Fermat.

4º Caso: $b$ é múltiplo de $5$ , mas não de $2$

Aqui $b=5x$ com $x$ ímpar. Observe que

$b^5 \equiv b \pmod{10} \Leftrightarrow 5^5x^5 \equiv 5x \pmod{10} \Leftrightarrow 5x^5 \equiv 5x \pmod{10} \Leftrightarrow x^5 \equiv x \pmod{2}.$

A última afirmação é verdadeira, pois ambos os lados da igualdade são congruentes a $1$ módulo $2$ (já que são ímpares).

Exemplo (OBM 2014 - 3ª Fase - Níveis 2 e 3)[]

Encontre todos os inteiros $n$ , $n>1$ , com a seguinte propriedade: para todo $k$ , $0 \leq k <n$ , existe um múltiplo de $n$ cuja soma dos algarismos, na base decimal, deixa resto $k$ na divisão por $n$ .

Solução: Esse é um tipo de exercício em que vale muito a pena fazer casos pequenos para ter uma ideia melhor do que está acontecendo aqui.

(i) $n=2$
Devemos mostrar que existe um múltiplo de $2$ cuja soma dos algarismos deixa resto $0$ na divisão por $2$ e outro cuja soma deixa resto $1$ . Existem vários números nessas condições. Mas a parte mais legal aqui é a seguinte: todo múltiplo de $10$ é também um múltiplo de $2$ . Daí todo número terminado em $0$ será múltiplo de $2$ , independente de quais algarismos aparecem antes. Por isso, conseguimos algo melhor ainda: conseguimos múltiplos de $2$ de forma que a soma dos algarismos seja qualquer uma quisermos.

(ii) $n = 3$

Sabemos que um número é múltiplo de $3$ se, e somente se, a soma dos seus algarismos também for. Desta forma, a soma dos algarismos de um número múltiplo de $3$ não pode ter resto $1$ e nem $2$ na divisão por $3$ . Ou seja, $n = 3$ não satisfaz as condições do enunciado.

(iii) $n = 4$

Aqui temos uma vantagem parecida com o caso $n=2$ : todo múltiplo de $100$ é também um múltiplo de $4$ .Por isso, todo número terminado em $00$ é múltiplo de $4$ . Assim, sempre podemos encontrar números múltiplos de $4$ cuja soma dos algarismos vale o que quisermos. Em particular, sempre existem múltiplos de $4$ cuja soma dos algarismos deixa restos $0$ , $1$ , $2$ e $3$ na divisão por $4$ .

(iv) $n=5$

Também satisfaz as condições do enunciado: basta usarmos as mesmas ideias que aplicamos no caso $n=2$ .

(v) $n = 6$

Todo múltiplo de $6$ é também um múltiplo de $3$ e assim a soma dos seus algarismos também será um múltiplo de $3$ . Assim a soma dos seus algarismos não poderá ser $1,2,4$ ou $5$ .

(vi) $n = 7$

Uma boa maneira de controlarmos a soma dos algarismos aqui é escolhermos múltiplos de $7$ que são formados apenas por algarismos $0$ e $1$ . Note que números formados por esses algarismos pode ser escrito como a soma de potências de $10$ . Se quisermos construir esses números pensando se eles são múltiplos de $7$ ou não, precisamos os restos das potências de $10$ na divisão por $7$ . Como $\operatorname{mdc}(10,7)=1$ , pelo teorema de Euler-Fermat,

$10^{\varphi(7)} \equiv 1 \pmod{7} \Leftrightarrow 10^{6} \equiv 1 \pmod{7}.$

Por isso, todo número da forma $10^{6a}$ , para $a$ inteiro, possui resto $1$ na divisão por $7$ . Mas se controlarmos apenas essas potências de $10$ , todo número irá ter o mesmo resto que a soma dos algarismos na divisão por $7$ (afinal se for formado por $x$ algarismos $1$ , a soma dos algarismos será $x$ e o número será congruente a $x$ módulo $7$ ). Por isso, vale a pena outra potência de $10$ para nos ajudar. Vamos tomar potências da forma $10^{6b+1}$ . Isso porque elas não são tão chatas de se calcular:

$10^{6b+1} \equiv 10^{6b} \cdot 10 \equiv 10 \equiv 3 \pmod{7}.$

Vamos construir um número $m$ que seja múltiplo de $7$ e que a soma dos seus algarismos também seja. Suponha que $m$ seja formado pela soma de potências distintas de $10$ , onde $x$ delas são da forma $10^{6a}$ e $y$ delas são da forma $10^{6b+1}$ . Ou seja, ele é formado por $x + y$ algarismos iguais a $1$ . Então

$m \equiv x+3y \pmod{7}$ .

Além disso, se denotarmos a soma dos algarismos dele por $s(m)$ , podemos concluir que

$s(m) \equiv x+y \pmod{7}.$

Para que $m$ e $s(m)$ sejam múltiplos de $7$ , precisamos que

${\begin{cases}x+3y \equiv 0 \pmod{7}\\ x+y \equiv 0 \pmod{7}\end{cases}}.$

Ao subtrairmos uma congruência da outra,

$2y \equiv 0 \pmod{7} \Leftrightarrow y \equiv 0 \pmod{7}.$

E por isso,

$x \equiv 0 \pmod{7}.$

Ou seja, uma possibilidade seria tomarmos $x=y=7$ , isto é, $7$ potências distintas da forma $10^{6a}$ e $7$ da forma $10^{6b+1}$ e seria um número múltiplo de $7$ cuja soma dos algarismos também seja. Conseguimos usar essa mesma ideia para encontrar números que são múltiplos de $7$ cuja soma dos algarismos deixa resto $k$ na divisão por $7$ (para $k=0,1,2,3,4,5,6$ )? Sim! Só aqui teremos as congruências

${\begin{cases}x+3y \equiv 0 \pmod{7}\\ x+y \equiv k \pmod{7}\end{cases}}.$

Ao subtrairmos uma congruência da outra,

$2y \equiv -k \pmod{7}.$

Observe que $y$ existe, pois $\operatorname{mdc}(7,2)=1$ .

(vii) $n=8$

Aqui é parecido com o caso $n = 4$ , afinal todo múltiplo de $1000$ é também múltiplo de $8$ , ou seja, se o número terminar em $000$ , podemos colocar qualquer coisa nos seus algarismos, que o seu resultado será um múltiplo de $8$ .

(viii) $n=9$

Aqui é parecido com o caso $n = 3$ . Um número é múltiplo de $9$ se, e somente se, a soma dos seus algarismos também for. Ou seja, não conseguimos um número múltiplo de $9$ cuja soma dos algarismos deixe um resto diferente de zero na divisão por $9$ .

Esse é um belo caso em que casos pequenos nos ajudam a ter uma ideia. Parece que todo $n$ que não seja múltiplo de $3$ satisfaz as condições do enunciado. Veremos que isso é verdade. Mas primeiro, vamos começar mostrando que números múltiplos de $3$ não podem satisfazer as condições do enunciado. Vamos nos basear nos casos $n=3,6,9$ .

Suponha que $n$ seja múltiplo de $3$ . Vamos mostrar que ele não satisfaz as condições do enunciado, ou seja, existe algum $k$ entre $0$ e $n$ tal que $s(n\ell)$ não tem resto $k$ na divisão por $n$ (para todo $\ell$ inteiro). Considere $k$ tal que

$s(n\ell) \equiv k \pmod{n}$ .

Vejamos quais características $k$ pode ter. Observe que $3 \mid n$ . Assim,

$s(n\ell) \equiv k \pmod{3}.$

Mas $n\ell \equiv s(n\ell) \pmod{3}$ (afinal $n\ell \equiv s(n\ell) \pmod{9}$ e $3 \mid 9$ ), ou seja, $s(n\ell) \equiv 0 \pmod{3}$ (pois $n\ell \equiv 0 \pmod{3}$ ). Desta forma, $k \equiv 0 \pmod{3}$ . Por isso, $s(n\ell)$ não pode ter um resto $k$ que não seja múltiplo de $3$ . Portanto, os valores de $n$ que são múltiplos de $3$ não satisfazem as condições do enunciado.

Resta mostrarmos que todo inteiro maior do que $1$ que não é divisível por $3$ satisfaz as condições do enunciado. Ao analisarmos os casos $n=2,4,5,8$ , vemos que as potências de $2$ e de $5$ são mais fáceis de se analisar. Por exemplo, se um número inteiro terminar com $t$ zeros, então ele será múltiplo de $10^t$ . Em particular, como $10^t=2^t \cdot 5^t$ , esse número será múltiplo de $2^t$ e de $5^t$ . Por isso, vale a pena separarmos as potências de $2$ e de $5$ do número.

Considere $n=2^{\alpha}\cdot 5^{\beta} \cdot n_0$ , onde $n_{0}$ é primo com $2$ e com $5$ . Observe também que $n_{0}$ é primo com $3$ , já que $n$ não é divisível por $3$ . Para mostrar que ele satisfaz as condições do enunciado, devemos construir um múltiplo $m$ de $n$ cuja soma dos algarismos deixa resto $k$ na divisão por $n$ (para $0 \leq k <n$ ). Uma maneira interessante de mexer aqui é fazermos de modo parecido com o que fizemos no caso $n = 7$ : usarmos apenas algarismos $1$ e $0$ para podermos controlar a soma dos algarismos, ou seja, potências de $10$ .

Observe que se todas as potências de $10$ forem maiores do que $10^{\alpha}$ , então o número será múltiplo de $10^{\alpha}$ e portanto múltiplo de $2^{\alpha}$ . Da mesma forma, se todas as potências de $10$ forem maiores do que $10^{\beta}$ , então o número será múltiplo de $5^{\beta}$ . Desta forma, pegaremos potências maiores do que $10^{\max \{\alpha,\beta \}}$ , pois assim o número será múltiplo de $2^{\alpha}\cdot 5^{\beta}$ e se precisaremos nos preocupar com o número ser múltiplo de $n_{0}$ .

Precisamos controlar os restos da divisão das potências de $10$ por $n_{0}$ . Observe que, pelo teorema de Euler-Fermat, como $\operatorname{mdc}(n_0,10)=1$ ,

$10^{\varphi(n_0)} \equiv 1 \pmod{n_0}$ .

Desta forma, todo número da forma $10^{a\varphi(n_0)}$ deixa resto $1$ na divisão por $n_{0}$ para $a$ inteiro positivo. Mas apenas esse tipo de número não é suficiente. De fato, se tivermos $x$ desses números somando, o resto da divisão do número por $n_{0}$ será $x$ e a soma dos algarismos também terá o mesmo resto. Vamos tomar números da forma $10^{b\varphi(n_0)+1}$ já que podemos calcular seus restos. De fato,

$10^{b\varphi(n_0)+1} \equiv \left(10^{\varphi(n_0)}\right)^b\cdot 10 \equiv 10 \pmod{n_0}$ .

Lembre-se que vale a pena tomar $a\varphi(n_0)$ e $b\varphi(n_0)+1$ maiores do que $\alpha$ e $\beta$ para que o número seja múltiplo de $2^{\alpha}\cdot 5^{\beta}$ . Se tivermos $x$ potências da forma $10^{a\varphi(n_0)}$ e $y$ da forma $10^{b\varphi(n_0)+1}$ , então o número será formado por $x + y$ algarismos iguais a $1$ . Assim a soma dos algarismos de $m$ será $x + y$ . Como queremos que ela tenha resto $k$ na divisão por $n$ ,

$x+y \equiv k \pmod{n}.(*)$

Além disso, como $m$ é formado pela soma de $x$ potências da forma $10^{a\varphi(n_0)}$ e $y$ da forma $10^{b\varphi(n_0)+1}$ , podemos dizer que

$m \equiv x+10y \pmod{n_0}$ .

Mas queremos que $m$ seja múltiplo de $n_{0}$ . Por isso,

$x+10y \equiv 0 \pmod{n_0}.(**)$

Para terminarmos o problema, basta mostrarmos que existem $x$ e $y$ inteiros que satisfaçam $(*)$ e $(**)$ . Vamos mexer um pouco com a conta, para vermos que eles existem. Se lembrarmos que $n_0 \mid n$ e usarmos $(*)$ ,

$x+y \equiv k \pmod{n_0}.(***)$

Ao subtrairmos $(***)$ de $(**)$ ,

$9y \equiv -k \pmod{n_0}.$

Observe que existe $y$ que satisfaça essa congruência. De fato, isso ocorre pois $\operatorname{mdc}(n_0,9)=1$ . Se tomarmos também $x$ inteiro tal que $x \equiv y-k \pmod{n}$ termos $x$ e $y$ que satisfazem $(*)$ e $(**)$ . Ou seja, todo $n$ que não é múltiplo de $3$ satisfaz as condições do enunciado.

Exemplo (Cone Sul 2008)[]

Dizemos que um número capícua se ao inverter a ordem de seus algarismos obtivermos o mesmo número. Achar todos os números que tem pelo menos um múltiplo não-nulo que seja capícua.

Solução: Uma boa maneira de começar esse problema é explorar alguns capícuas. Em algum momento, você pode parar em números da forma $\underbrace{99\cdots 9}_{k}=10^{k}-1$ .

Aqui as coisas ficam interessantes, pois se $\operatorname{mdc}(n,10)=1$ , então, pelo Teorema de Euler,

$10^{\varphi(n)} \equiv 1 \pmod{n} \Leftrightarrow n \mid \left(10^{\varphi(n)}-1\right).$

Ou seja, para estes valores específicos de $n$ , teremos um capícua $10^{\varphi(n)}-1=\underbrace{99\cdots 9}_{\varphi(n)}$ que é múltiplo de $n$ .

Outro caso interessante também: se $n$ é múltiplo de $10$ , então terminar em zero e por isso não pode ser capícua: ao invertermos ele, teremos um número de menos algarismos.

Vejamos outros dois casos específicos: quando $n=2^k$ ou $n=5^k$ para algum natural $k$ . Considere aqui $I(n)$ o número formado pelos algarismos de $n$ invertidos. Para $t$ suficientemente grande, o número $I(n)\cdot 10^t+n$ é capícua e múltiplo de $n$ .

Com efeito, se $t$ for maior que a quantidade algarismos de $n$ e $n=\overline{a_k a_{k-1} \cdots a_1 a_0}$ , então

$I(n)\cdot 10^t+n=\overline{a_0 a_1 \cdots a_{k-1} a_k 00\cdots 00 a_k a_{k-1} \cdots a_1 a_0},$

ou seja, ele é um número capícua. Além disso, se $t \geq k$ , então $I(n)\cdot 10^t+n$ é múltiplo de $n$ . Pois nos casos em que $n=2^k$ e $n=5^k$ ocorre que $n \mid 10^k$ . Logo, nestes dois casos, $n$ possui um múltiplo capícua.

Resta um caso ainda: quando $\operatorname{mdc}(n,10)$ é diferente de $1$ e $n$ possui algum fator diferente de $2$ e de $5$ .

Aqui poderemos escrever $n=ma$ , onde $a=2^k$ ou $a=5^k$ e $m$ é um inteiro tal que $\operatorname{mdc}(m,10)=1$ .

Podemos até pegar $M=I(a)\cdot 10^t+a$ . Neste caso, se $t$ for maior do que a quantidade de algarismos de $a$ , então este número é capícua e múltiplo de $a$ . Mas ele não é múltiplo de $m$ . Precisamos "consertar" isto.

Aqui é a vez de entrar novamente o teorema de Euler. Pegaremos o número $\underbrace{M\cdots M}_{m \textrm{ blocos}}$ , mas com $t$ de tal forma que $M$ possui uma quantidade de algarismos múltiplo de $\varphi(m)$ , isto é, $b\varphi(m)$ para algum $b$ inteiro. E por que isto? Para usarmos o teorema de Euler. Mas quem garante que este $t$ exista? Se $a$ tiver $d$ algarismos, basta tomarmos $t=b\varphi(m)-d$ .

Observe aqui então que

$\underbrace{M\cdots M}_{m \textrm{ blocos}} \equiv M+M\cdot 10^{b\varphi(n)}+M\cdot 10^{2b\varphi(n)}+\cdots+M\cdot 10^{(m-1)b\varphi(n)}\equiv \underbrace{M+M+\cdots+M}_{m}\equiv$

$\equiv Mm \equiv 0 \pmod{m}.$

Desta forma, $\underbrace{M\cdots M}_{m \textrm{ blocos}}$ é capícua e múltiplo de $n$ .

Portanto, os números que satisfazem as condições do enunciado são aqueles que não são divisíveis por $10$ .

Exemplo[]

Prove que o inverso modular de $a$ módulo $n$ é

$a^{\varphi(n)-1}-n \left\lfloor\frac{a^{\varphi(n)-1}}{n} \right\rfloor.$

(Observação: Você pode saber mais sobre inverso modular aqui.)

Solução: Seja $x$ o inverso modular de $a$ módulo $n$ . Então

$ax \equiv 1 \pmod{n}$ .

Já que queremos falar sobre $x$ , seria legal se tivéssemos algo da forma

$x \equiv \text{coisa}\pmod{n}.$

Ou seja, é interessante que o número que o $\ a$ que aparece no lado esquerdo da congruência suma. Seria legal multiplicar ele por algo e o resultado ser congruente a $1$ módulo $n$ . Conhecemos algum múltiplo de $\ a$ que seja congruente a $1$ módulo $\ n$ ? Sim, pelo teorema de Euler-Fermat, $a^{\varphi(n)} \equiv 1 \pmod{n}$ e $a^{\varphi(n)}$ é múltiplo de $\ a$ . Desta forma, podemos fazer ele aparecer multiplicando ambos os lados da igualdade por $a^{\varphi(n)-1}$ :

${\color{red}a^{\varphi(n)-1}}ax \equiv {\color{red}a^{\varphi(n)-1}} \cdot 1 \pmod{n} \Leftrightarrow a^{\varphi(n)}x \equiv a^{\varphi(n)-1} \pmod{n} \Leftrightarrow x \equiv a^{\varphi(n)-1}\pmod{n}.$

Mas $x$ é um número tal que $0 \leq x <n$ . Assim, $x$ é o resto da divisão de $a^{\varphi(n)}$ por $n$ e com isso

$x=a^{\varphi(n)-1}-n \left\lfloor\frac{a^{\varphi(n)-1}}{n} \right\rfloor.$

Exemplo (IMO 2004)[]

Chamamos um inteiro positivo de alternante se quaisquer dígitos positivos na sua representação decimal possuem paridades diferentes.

Encontre todos os inteiros positivos $n$ tais que $n$ possui um múltiplo que é alternante.

Solução: Observe que se $n$ for um múltiplo de $20$ , todo múltiplo de $n$ também será múltiplo de $20$ e assim seu último algarismo será zero e o penúltimo será par, ou seja, teremos dois algarismos pares consecutivos e ele não pode ser alternante. Desta forma, nenhum número múltiplo de $20$ poderá satisfazer as condições do enunciado.

E quanto aos outros casos? Vale a pena começarmos com exemplo de alternantes que não sejam tão grandes assim. Talvez vale a pena olhar para

$\underbrace{101010\cdots 01}_{2(m-1)\text{ algarismos}}.$

Queremos controlar os restos da divisão de $10^x$ na divisão por $n$ . Uma maneira de fazermos isso é pelo teorema de Euler-Fermat. Mas só podemos usar ele quando $\operatorname{mdc}(10,n)=1$ . Por isso, vamos dividir em casos.

1º Caso: $\operatorname{mdc}(10,n)=1$

Observe que

$\underbrace{101010\cdots 10101}_{2(m-1)\text{ algarismos}}=1+100+10000+\cdots+\underbrace{100\cdots 0}_{2(m-2) \text{ algarismos}}+\underbrace{100\cdots 0}_{2(m-1) \text{ algarismos}}=$

$=1+10^2+10^4+\cdots+10^{2(m-2)}+10^{2(2m-1)}.$

Como essa é a soma de números de uma progressão geométrica de $2m$ termos e razão $10^2$ , segue que ela é igual a

$\frac{(10^2)^{2m}-1}{10^2-1}=\frac{10^{4m}-1}{99}.$

Queremos escolher um $m$ tal que esse número seja múltiplo de $n$ . Observe que $n \mid \frac{10^{4m}-1}{99}$ se, e somente se, $99n \mid 10^{4m}-1$ . Queremos analisar módulo $99n$ . E queremos que $10^{4m}$ tenha resto $1$ quando dividido por $99n$ . Como $\operatorname{mdc}(10,99n)=1$ , segue que

$10^{\varphi(99n)} \equiv 1 \pmod{99n} \Rightarrow 10^{4\varphi(99n)} \equiv 1 \pmod{99n}.$

Por isso, podemos escolher $m=\varphi(99n)$ e assim, para $\operatorname{mdc}(10,n)=1$ , teremos $\frac{10^{4m}-1}{99}$ um número alternante e múltiplo de $n$ .

E quais os outros casos que podemos analisar? Os casos em que $n$ não seja múltiplo de $20$ , mas que tenha um fator $2$ ou $5$ . Por isso, para sabermos melhor qual caso analisar, considere $n=2^{\alpha}5^{\beta}n_1$ com $\operatorname{mdc}(n_1,10)=1$ . Não podemos ter ao mesmo tempo $\alpha \geq 2$ e $\beta \geq 1$ pois aí teríamos $n$ múltiplo de $20$ . Desta forma, analisamos separadamente: quando $\beta \geq 1$ e quando $\alpha \geq 2$ . Comecemos com o caso em que $\beta \geq 1$ . Nele devemos ter $\alpha \leq 1$ (já no terceiro caso deveremos ter $\alpha \geq 2$ e $\beta=0$ , em outras palavras, $n=2^rn_1$ ).

2º Caso: $n=2\cdot 5^r n_1$ com $r \ge 1$ e $\operatorname{mdc}(n_1,10)=1$

Vamos fazer uns planos antes de sair fazendo as contas. Se conseguirmos mostrar que coisas da forma

$\underbrace{1\underbrace{0\cdots0}_{k-1}1\underbrace{0\cdots0}_{k-1}\cdots 1\underbrace{0\cdots0}_{k-1}1}_{m-1\text{ blocos de zeros}}$

são múltiplos de $n_1$ para algum valor de $m$ (argumentos parecidos com o caso anterior parecem funcionar), precisaríamos a partir daí encontrar um múltiplo de $x$ alternante de $k$ dígitos pois aí

$x \cdot \underbrace{1\underbrace{0\cdots0}_{k-1}1\underbrace{0\cdots0}_{k-1}\cdots 1\underbrace{0\cdots0}_{k-1}1}_{m-1 \text{ blocos de zeros}}=\overline{(\text{Dígitos de }x)(\text{Dígitos de }x)\cdots(\text{Dígitos de }x)}.$

Se $x$ for ímpar, alternante e múltiplo de $5^r$ , teremos um alternante múltiplo de $5^r n_1$ . Para termos um múltiplo de $n=2\cdot 5^r n_1$ , basta acrescentarmos o zero no final.

Feito o plano, hora de colocar na prática. Já que o número

$\underbrace{1\underbrace{0\cdots0}_{k-1}1\underbrace{0\cdots0}_{k-1}\cdots 1\underbrace{0\cdots0}_{k-1}1}_{m-1\text{ blocos de zeros}}$

parece importante, vamos dar um nome para ele: $A_k(n)$ . Será que esses números são múltiplos de $n_1$ para algum valor de $m$ ? Observe que

$A_k(n)=1+1\underbrace{0\cdots0}_{k \text{ zeros}}+1\underbrace{0\cdots 0}_{2k \text{ zeros}}+1\underbrace{0\cdots 0}_{3k \text{ zeros}}+\cdots+1\underbrace{0\cdots 0}_{(m-1)k \text{ zeros}}=1+10^k+10^{2k}+\cdots+10^{(m-1)k}.$

Como essa última é uma progressão geométrica de $m$ termos e razão $10^k$ , segue que

$A_k(n)=\frac{10^{mk}-1}{10^k-1}.$

Por isso escolhemos $m - 1$ blocos de zeros antes (se houvéssemos escolhido $m$ blocos de zero, teríamos $(m+1)k$ no expoente). Repare que $n \mid \frac{10^{mk}-1}{10^k-1}$ se, e somente se, $n(10^k-1) \mid 10^{mk}-1$ . Conseguimos alguma congruência da forma $10^x \equiv 1 \pmod{n(10^k-1)}$ ? Sim: pelo teorema de Euler-Fermat:

$10^{\varphi(n(10^k-1))} \equiv 1 \pmod{n(10^k-1)}.$

Por isso, basta tomarmos $m=\varphi(n(10^k-1))$ que aí teremos $A_k(n)$ múltiplo de $n$ .

E quanto a tomarmos um alternante múltiplo de $5^r$ ? Para todo $k$ inteiro positivo, vamos procurar inteiros de $k$ dígitos tais que $M_{k}$ seja divisível por $5^k$ .

Para $k = 1$ , basta tomarmos $M_1=5$ . E quanto a $k=2$ ? Ou seja, devemos procurar um número de dois algarismos que seja divisível por $25$ . Por mais que você saiba quais são os múltiplos de $25$ de dois algarismos ( $25$ , $50$ e $75$ ) e daí poderíamos escolhermos os alternantes, vejamos uma maneira de obtermos $M_2$ a partir de $M_1$ (afinal se conseguirmos uma boa maneira de obter $M_{k+1}$ a partir de $M_{k}$ conseguiremos usar indução).

Observe que em dois dos casos, podemos colocar um algarismo à esquerda e obtermos um número de $5^2$ (e se notarmos que $\ 0$ um múltiplo de $5$ , veremos que para obtermos $50$ também bastaria colocarmos o $5$ à esquerda). Por é válido suspeitar: e se colocarmos um algarismo à esquerda de $M_1$ ? Observe que colocar um algarismo $c$ à esquerda de $M_1$ equivale a tomar $M_1+10c$ .

Queremos que esse último número seja múltiplo de $25$ , ou seja, $25 \mid M_1+10c$ . Por sorte, $M_1$ e $10c$ já são múltiplos de $5$ e isso pode facilitar nosso trabalho. De fato, se lembrarmos que $\frac{M_1}{5}$ é inteiro, podemos escrever a nossa divisibilidade como sendo

$25 \mid 5\left(\frac{M_1}{5}+2c \right) \Leftrightarrow 5 \mid \frac{M_1}{5}+2c.$

Precisamos apenas que

$\frac{M_1}{5}+2c \equiv 0 \pmod{5} \Leftrightarrow 2c \equiv -\frac{M_1}{5} \pmod{5}.$

Como $\operatorname{mdc}(2,5)=1$ , existe um número $c$ que satisfaz essas condições. De fato, como $2$ e $5$ são primos entre si, segue que $2$ possui inverso modular e assim podemos multiplicar ambos os lados da igualdade por $3$ e assim

$c \equiv -\frac{3M_1}{5} \pmod{5}.$

Ou seja, existe algum número dentre $0,1,2,3,4$ que podemos colocar à direita de $M_1$ e fazer com que ele seja múltiplo de $25$ . Mais ainda, se funciona para $c$ , também funciona para $5+c$ , já que $5+c \equiv c \pmod{5}$ . Assim podemos colocar algum número dentre $5,6,7,8,9$ à direita de $M_1$ e obter outro número múltiplo de $25$ . Mas repare que também devemos construir um número alternante. E agora? Será que podemos controlar as paridades? Repare que $\ c$ e $5+c$ possuem paridades diferentes. Desta forma, basta tomarmos o que faz o número ficar alternante.

Vamos usar essas ideias para mostrar por indução que para todo $k$ inteiro positivo, existe um número $M_{k}$ de $k$ algarismos que é divisível por $5^k$ . Já fizemos o caso $k = 1$ . Suponha agora que existe um número $M_{k}$ de $k$ dígitos que seja múltiplo de $5^k$ . Para construirmos um número de $k+1$ algarismos múltiplo de $5^{k+1}$ , vamos colocar $c$ ou $5+c$ à esquerda do número, ou seja, tomar $M_k+10^kc$ e $M_k+10^k(5+c)$ . Será que para algum $c$ os dois números serão múltiplos de $5^{k+1}$ . Vejamos como fazer o primeiro número ser múltiplo. Observe que, como $\frac{M_k}{5^k}$ é um número inteiro,

$5^{k+1} \mid M_k+10^kc \Leftrightarrow 5^{k+1} \mid 5^k \left(\frac{M_k}{5^k}+2^kc \right) \Leftrightarrow 5 \mid \frac{M_k}{5^k}+2^kc \Leftrightarrow \frac{M_k}{5^k}+2^kc \equiv 0 \pmod{5} \Leftrightarrow$

$\Leftrightarrow 2^kc \equiv -\frac{M_k}{5^k}\pmod{5}.$

Existe algum $c$ nesta condição? Como $3$ é inverso modular de $2$ módulo $5$ , podemos multiplicar ambos os lados da igualdade por $3^k$ e assim

$c \equiv -\frac{3^kM_k}{5^k}\pmod{5}.$

Ou seja, existe $c$ que faz com que $M_k+10^kc$ seja múltiplo de $5^k$ . Esse mesmo valor valor de $c$ fará com que $M_k+10^k(5+c)$ também seja? Observe que esse número pode ser escrito $M_k+10^kc+10^k \cdot 5$ . Como $M_k+10^kc$ é múltiplo de $5^k$ e $10^k \cdot 5$ também (já que $10^k \cdot 5 = 5^{k+1} \cdot 2^k$ ), segue que $M_k+10^k(5+c)$ também será múltiplo de $5^{k+1}$ . Como $c$ e $5+c$ possuem paridades diferentes, basta escolhermos aquele que faça com que $M_{k+1}$ seja alternante. Em particular $M_{k}$ é ímpar.

Observe que $n_1 \mid A_r(n_1)$ e $5^r \mid M_r$ , de onde segue que $n_15^r \mid A_r(n_1)M_r$ . Mas será que $A_r(n_1)M_r$ é alternante? Observe que

$A_r(n_1)M_r=\overline{(\text{Dígitos de }M_r)(\text{Dígitos de }M_r)\cdots (\text{Dígitos de }M_r)}.$

Para esse número ser alternante, precisamos que o primeiro e o último dígito de $M_r$ possuam paridades distintas. Mas isso só ocorre quando ele possui uma quantidade par de dígitos. Para evitarmos passar por isso, tomemos $A_{2r}(n_1)$ . Aqui $5^r n_1 \mid A_{2r}(n_1)M_{2r}$ . E para fazermos o fator $2$ aparecer? Para isso, coloquemos o zero no final. Assim o número $10A_{2r}(n_1)M_{2r}$ irá satisfazer as condições deste caso.

3º Caso: $n=2^rn_1$ com $r \geq 2$ e $\operatorname{mdc}(n_1,10)=1$

Já que temos algo parecido para se mostrar, que tal usarmos uma ideia parecida. Para algum valor $t$ é legal pegarmos $A_t(n_1)N_u$ com $N_u$ tendo $t$ algarismos e sendo dividido por $2^r$ . Para pegarmos esse número alternante, podemos prestar atenção apenas em $N_r$ que possuem uma quantidade par de algarismos (em que o último algarismo seja par e o primeiro seja ímpar).

Vamos começar com $N_1$ um número com $2$ algarismos alternante. Podemos pegar $N_1=16$ . Observe que $2^3 \mid 16$ Já que queremos $N_2$ com quatro algarismos, para os expoentes não ficarem tão para trás, vamos pegar de forma que seja divisível por um expoente que tenha duas unidades a mais do que o anterior. Vamos colocar um número $\overline{ab}$ à esquerda de $N_1$ , isto é, tomemos o número $N_1+10^2\overline{ab}$ . Será que com alguma condição, conseguiremos aumentar o expoente em duas unidades, ou seja, $2^5 \mid N_1+10^2\overline{ab}$ ? Aqui, se lembrarmos que $\frac{N_1}{8}$ é inteiro, podemos reescrever essa divisibilidade como

$2^5 \mid 8\left(\frac{N_1}{8}+\frac{25}{2}\overline{ab}\right) \Leftrightarrow 2^2 \mid \frac{N_1}{8}+\frac{25}{2}\overline{ab} \Leftrightarrow \frac{\overline{ab}}{2} \equiv -\frac{N_1}{8}\pmod{4}.$

Para os candidatos para $\overline{ab}$ , devemos pegar números que sejam pares, alternantes, que as suas metades tenham todos os restos possíveis na divisão por $4$ e que o algarismo das dezenas seja ímpar. Candidatos interessantes são $10,12,14,16$ .

Em geral, vamos mostrar que existe um número alternante de $2r$ dígitos $N_r$ que seja divisível por $2^{2r+1}$ . O caso $r=1$ já está resolvido.

Suponha que tenhamos um número $N_r$ de $2r$ dígitos e que seja divisível por $2^{2r+1}$ . Vamos construir a partir desse um número $N_{r+1}$ com $2r+2$ algarismos que seja divisível por $2^{2r+3}$ . Conforme vimos no caso $r=1$ , vale a pena para algum $m$ dentre $10,12,14,16$ tomarmos $N_r+m10^{2r}$ (que equivale a colocar o número $m$ à esquerda de $N_r$ ). Só precisamos que para algum valor de $m$ seja possível que $2^{2r+3} \mid N_r+m10^{2r}$ . Se lembrarmos que $\frac{N_1}{2^r}$ é inteiro e o mesmo vale para $\frac{m}{2}$ , podemos reescrever isso como

$2^{2r+3} \mid 2^{2r+1}\left(\frac{N_r}{2^{2r+1}}+5^{2r}\cdot \frac{m}{2} \right) \Leftrightarrow 2^2 \mid \frac{N_r}{2^{2r+1}}+5^{2r}\cdot \frac{m}{2} \Leftrightarrow \frac{m}{2} \equiv -\frac{N}{2^{2r+1}} \pmod{4}.$

Como $\frac{m}{2}$ pode assumir qualquer resto possível na divisão por $4$ , existe $N_{r+1}=2^{2r+3} \mid N_r+m10^{2r}$ de $2r+2$ algarismos divisível por $2^{2r+3}$ .

Portanto, para resolvermos este caso, basta tomarmos o número $A_{2r}(n_1)N_r$ . Com efeito, $n_1 \mid A_{2r}(n_1)$ e $2^{2r+1} \mid N_r$ , de onde segue que $n \mid A_{2r}(n_1)N_r$ .

Com isso, os inteiros positivos $n$ tais que $n$ possui um múltiplo que é alternante são todos os números que não múltiplos de $20$ .

Curiosidade[]

Existe uma generalização do teorema de Euler que é chamada de teorema de Carmichael. Você não precisa disso para resolver problemas, mas é legal conhecer. Vamos definir $\lambda(n)$ como sendo o menor inteiro positivo tal que $a^m \equiv 1 \pmod n$ para todo $a$ inteiro primo com $n$ . A função $\lambda$ é chamada de função de Carmichael.