FANDOM


Sejam $ a $, $ b $ e $ m $ inteiros, com $ m $ inteiro positivo. Dizemos que $ a $ é congruente a $ b $ módulo $ m $ quando $ a $ e $ b $ possuírem o mesmo resto na divisão por $ m $. Neste caso, escreveremos $ a \equiv b \pmod{m} $. O número $ m $ é chamado de módulo da congruência. Esta definição foi criada pelo matemático alemão Carl Friedrich Gauss.

ObservaçãoEditar

Em alguns lugares, definimos o módulo apenas para $ m>1 $. De fato, o caso em que $ m=1 $ não tem muita coisa para se explorar: para quaisquer $ x $ e $ y $ inteiros, $ x\equiv y \pmod{1} $.

ProposiçãoEditar

Sejam $ a $, $ b $ e $ m $ inteiros, com $ m $ positivo. Então

$ a \equiv b \pmod{m} \Leftrightarrow m|(b-a). $

Proposição Editar

Sejam $ a $, $ b $ e $ m $ inteiros, com $ m $ positivo. Então $ a \equiv b \pmod{m} $ se, e somente se, existe $ t $ inteiro tal que $ a=b+mt $.

PropriedadesEditar

(i) $ a \equiv 0 \pmod{m} \Leftrightarrow m|a $.

(ii) (Reflexiva) Para todo $ a $ inteiro, $ a \equiv a \pmod{m} $.

(iii) (Simétrica) Se $ a \equiv b \pmod{m} $, então $ b \equiv a \pmod{m} $.

(iv) (Transitiva) Se $ a \equiv b \pmod{m} $ e $ b \equiv c \pmod{m} $, então $ a \equiv c \pmod{m} $.

(v) Se $ a \equiv b \pmod{m} $ e $ c \equiv d \pmod{m} $, então $ a+c \equiv b+d \pmod{m} $.

(vi) Se $ a \equiv b \pmod{m} $ e $ c \equiv d \pmod{m} $, então $ a-c \equiv b-d \pmod{m} $.

(vii) Se $ a \equiv b \pmod{m} $ e $ c \equiv d \pmod{m} $, então $ ac \equiv bd \pmod{m} $.

(viii) Se $ a \equiv b \pmod{m} $, então $ a^n \equiv b^n \pmod{m} $.

(ix) Se $ a \equiv b\pmod{m} $ e $ n|m $, então $ a \equiv b\pmod{n} $.

(x) Seja $ d $ um número diferente de $ 0 $ tal que $ d|a $, $ d|b $, $ d|m $. Então $ a \equiv b \pmod{m} $ se, e somente se, $ \frac{a}{d} \equiv \frac{b}{d} \pmod{\frac{m}{d}} $.

(xi) Se $ ab \equiv ac \pmod{m} $ e $ \operatorname{mdc}(a,m)=1 $, então $ b \equiv c \pmod{m} $.

Como Lidar Quando Aparecem Números Negativos na Congruência? Editar

Se tivermos analisando módulo $ m $ e quisermos que o número negativo fique positivo, basta somarmos $ m $ ou um múltiplo de $ m $.

Exemplos:

(1) $ -3 \equiv -3+4 \equiv 1 \pmod{4}. $

(2) $ -17 \equiv -17+20 \equiv 3 \pmod{5}. $

ExemploEditar

Prove que se $ x $ é um número inteiro, então os restos possíveis da divisão de $ x^2 $ por $ 4 $ só pode ser $ 0 $ ou $ 1 $.

Solução: Se $ x $ é inteiro, os restos possíveis da divisão de $ x $ por $ 4 $ são $ 0 $, $ 1 $, $ 2 $ ou $ 3 $. Vejamos cada caso:

$ x \equiv 0 \pmod{4} \Rightarrow x^2 \equiv 0 \pmod{4}, $

$ x \equiv 1 \pmod{4} \Rightarrow x^2 \equiv 1 \pmod{4}, $

$ x \equiv 2 \pmod{4} \Rightarrow x^2 \equiv 4 \equiv 0 \pmod{4}, $

$ x \equiv 3 \pmod{4} \Rightarrow x^2 \equiv 9 \equiv 1 \pmod{4}. $

ExemploEditar

Se $ a \equiv b \pmod{m} $ e $ d=\operatorname{mdc}(a,m) $, mostre que $ d|b $.

Solução: Sabemos que $ a \equiv b \pmod{m} $ se, e somente se, existe $ t $ inteiro tal que $ a=b+mt $. Mas, pela definição de máximo divisor comum, $ d|a $ e $ d|m $. Logo, $ d|a-mt $, isto é, $ d|b $.

Exemplo (OBM 2011 - 3ª Fase - Nível 2) Editar

OBM2011q1n2

Num tabuleiro $ 3 \times 3 $ escrevemos os números de $ 1 $ a $ 9 $, um em cada casa. Em seguida, achamos a soma dos números de cada linha, de cada coluna e de cada diagonal e contamos o número de somas que são múltiplos de três. Por exemplo, no tabuleiro ao lado as $ 8 $ somas (as três linhas, as três colunas e as duas diagonais) são múltiplos de $ 3 $.

É possível que nenhuma das $ 8 $ somas seja um múltiplo de $ 3 $? Lembre-se de que você deve justificar sua resposta.

Solução: Vamos pensar neste problema módulo $ 3 $, isto é, ao invés de pensarmos no número em si, vamos pensar nos seus restos na divisão por $ 3 $. Neste modelo, as possíveis fileiras (linhas, colunas ou diagonais) são

$ 0,0,1 $

$ 0,0,2 $

$ 0,1,1 $

$ 0,2,2 $

$ 1,1,2 $

$ 1,2,2 $

além de suas permutações. Com isso, em cada fileira devem haver dois números congruentes entre si (módulo $ 3 $) e um diferente. Consideremos $ x,y $ e $ z $ os números $ 0,1 $ e $ 2 $ (não necessariamente nessa ordem). Analisemos cada uma das possibilidades.

OBM2011q1n21

Na possibilidade acima, a soma dos números da diagonal é congruente a $ 0 $ módulo $ 3 $.

OBM2011q1n22

Quem aparece na diagonal? Observe que nas linhas faltam um $ x $, um $ y $ e um $ z $. Ou seja, aparecem $ x,y $ e $ z $ na diagonal e assim a soma dos elementos da diagonal é congruente a $ 0 $ módulo $ 3 $.

OBM2011q1n23

Nos outros casos, existirão uma linha ou coluna com os números congruentes a $ 0 $ módulo $ 3 $.

Portanto, é impossível que nenhuma das somas é múltiplo de $ 3 $.

Exemplo (OBM 2003 - 3ª Fase - Nível 2)Editar

Determine o menor número primo positivo que divide $ x^2+5x+23 $ para algum inteiro $ x $.

Solução: Vamos testar todos os divisores primos até achar o menor. Comecemos pelo $ 2 $. Para isto, usaremos módulo.

  • Módulo $ 2 $

Se $ x \equiv 0 \pmod{2} $, então $ x^2+5x+23 \equiv 1 \pmod{2} $.

Se $ x \equiv 1 \pmod{2} $, então $ x^2+5x+23 \equiv 1+1+1 \equiv 1 \pmod{2} $.

Logo, o primo procurado não é $ 2 $.

  • Módulo $ 3 $

Se $ x \equiv 0 \pmod{3} $, então $ x^2+5x+23 \equiv 2 \pmod{3} $.

Se $ x \equiv 1 \pmod{3} $, então $ x^2+5x+23 \equiv 1+2+2 \equiv 2 \pmod{3} $.

Se $ x \equiv 1 \pmod{3} $, então $ x^2+5x+23 \equiv 1+1+2 \equiv 1 \pmod{3} $.

Portanto, $ 3 $ não é o número desejado.

Podemos usar o mesmo raciocínio e mostrar que $ 5,7,11 $ e $ 13 $ não são os números desejados. Mas para $ 17 $ funciona. De fato, se $ x=-2 $, então $ x^2+5x+23=17 $.

Desta maneira, $ 17 $ é o número procurado.

Exemplo (OBM 2005 - 3ª Fase - Nível 2) Editar

Prove que o número $ 1^{2005}+2^{2005}+3^{2005}+...+2005^{2005} $ é múltiplo de $ 1+2+3+...+2005 $.

Solução: Considere $ E=1^{2005}+2^{2005}+3^{2005}+...+2005^{2005} $ e observe que

$ 1+2+3+...+2005=\frac{2005.2006}{2}=1003.2005 $.

Como $ \operatorname{mdc}(1003,2005)=1 $, para mostrarmos que $ 1003.2005|E $ é suficiente vermos que $ 1003|E $ e $ 2005|E $. Comecemos observando módulo $ 2005 $.

Para que apareça $ 0 $ módulo $ 2005 $, uma maneira interessante é fazermos surgir alguns cancelamentos. Para isso, note que

$ 2005^{2005} \equiv 0 \pmod{2005} $

$ 2004^{2005} \equiv (-1)^{2005} \equiv -1^{2005} \pmod{2005} $

$ 2003^{2005} \equiv (-2)^{2005} \equiv -2^{2005} \pmod{2005} $

$ \dots $

$ 1003^{2005} \equiv (-1002)^{2005} \equiv -1002^{2005} \pmod{2005} $.

Desta maneira,

$ E \equiv 1^{2005}+2^{2005}+3^{2005}+...+2005^{2005} \equiv $

$ \equiv 1^{2005}+2^{2005}+\dots+1002^{2005}-1002^{2005}-\dots-2^{2005}-1^{2005} \equiv 0 \pmod{2005} $.

Logo, $ 2005|E $. Por um raciocínio parecido, podemos mostrar que $ 1003|E $. Com efeito,

$ 2005^{2005} \equiv (-1)^{2005} \equiv -1^{2005}\pmod{1003} $

$ 2004^{2005} \equiv (-2)^{2005} \equiv -2^{2005} \pmod{1003} $

$ \dots $

$ 1004^{2005} \equiv (-1002)^{2005} \equiv -1002^{2005} \pmod{1003} $

$ 1003^{2005} \equiv 0 \pmod{1003} $.

Desta forma, podemos concluir que $ 1003|E $, de onde segue o resultado.

Exemplo (Cone Sul 1993)Editar

Prove que existe uma sequência $ a_1, a_2, \dots, a_k, \dots $ onde cada $ a_i $ é um dígito ($ a_i \in \{0,1,2,3,4,5,6,7,8,9\} $) e $ a_0=6 $ tais que para cada inteiro positivo $ n $ o número $ x_n=a_0+10a_1+100a_2+...+10^{n-1}a_{n-1} $ satisfaz o seguinte: $ x_n^2-x_n $ é divisível por $ 10^n $.

Solução: Vamos usar indução em $ n $.

Para $ n=1 $, vale que $ x_1=a_0=6 $ e assim $ x_1^2-x_1 \equiv 30 \equiv 0 \pmod{10} $.

Suponha agora que a afirmação seja válida para $ n=k $, isto é, podemos escolher $ a_1, a_2, \dots, a_{k-1} $ nas condições do enunciado tais que $ x_k^2-x_k $ é divisível por $ 10^k $. Como podemos provar que a afirmação é válida para $ n=k+1 $? Para $ n \geq 1 $, vale o seguinte: $ x_{n+1}=x_n+10^na_n $.

Assim, se quisermos que

$ x_{k+1}^2-x_{k+1} \equiv 0 \pmod{10^{k+1}} $,

precisamos encontrar um dígito $ a_k $ tal que

$ (x_k+10^ka_k)^2-(x_k+10^k) \equiv 0 \pmod{10^{k+1}} $.

Vamos reescrever isto de outra maneira:

$ x_k^2+2x_k.10^ka_k-x_k-10^ka_k \equiv 0 \pmod{10^{k+1}} $.

Como $ x_k^2-x_k $ é divisível por $ 10^k $, podemos dividir ambos os lados da congruência e o módulo por $ 10^k $, fazendo com que ela se torne

$ \frac{x_k^2-x_k}{10^k}+a_k(2x_k-1) \equiv 0 \pmod{10} \Leftrightarrow a_k(2x_k-1) \equiv -\frac{x_k^2-x_k}{10^k} \pmod{10} $.

E quando a $ 2x_k-1 $ visto módulo $ 10 $? Basta vermos que

$ x_k=a_0+10a_1+100a_2+...+10^{k-1}a_{k-1} $ e $ a_0=6 $,

de onde segue que

$ 2x_k-1 \equiv 1 \pmod{10} $,

de onde segue que $ a_k \equiv -\frac{x_k^2-x_k}{10^k} \pmod{10} $.

Basta tomarmos este $ a_k $ e resolveremos o problema.

Exemplo (Cone Sul 2004) Editar

Utilizando triangulinhos equiláteros de papel, de lado $ 1 $, forma-se um triângulo de lado $ 2^{2004} $. Desse triângulo retira-se o triangulinho de lado $ 1 $ cujo centro coincide com o centro do triângulo maior.

Determine se é possível cobrir totalmente a superfície restante, sem superposições nem buracos, dispondo-se somente de fichas em forma de trapézio isósceles, cada uma formada por três triangulinhos equiláteros de lado $ 1 $.

Solução: Uma primeira ideia aqui seria usar indução em no número de lados, que podemos chamar de $ n $. Temos um problema: ao aumentarmos o número de lados de $ n $ para $ n+1 $, não parece que a parte da figura que aumento pode ser coberta por trapézios conforme o enunciado.

Mas parece que se aumentarmos o número de lados de $ n $ para $ n+9 $ teremos um "complemento" que pode ser preenchido conforme o enunciado (veja a figura a seguir). Em outras palavras, parece que um triângulo de lado $ n $ satisfaz as condições do enunciado, então um de lado $ n+9 $ também satisfaz.

ConeSul2004q5
Desta forma, não faremos indução para mostrar que algo vale para todo número natural $ n $. Mas fique tranquilo, ainda podemos salvar a nossa indução. Observe que $ n $ e $ n+9 $ possuem o mesmo resto na divisão por $ 9 $

Então podemos provar que algo vale para todo $ n $ com certo resto na divisão por $ 9 $. Mas estamos interessados em $ n=2^{2004} $. Qual o resto de $ 2^{2004} $ na divisão por $ 9 $? Observe que

$ 2^3 \equiv -1 \pmod{9} $

$ (2^3)^2 \equiv (-1)^2 \pmod{9} $

$ 2^6 \equiv 1 \pmod{9} $

$ (2^6)^{334} \equiv 1^{334} \pmod{9} $

$ 2^{2004} \equiv 1 \pmod{9}. $

Logo, é suficiente provarmos que a afirmação do enunciado vale para todo $ n \equiv 1 \pmod{9} $.

(i) Para o caso $ n=1 $, não há o que fazer, pois o triângulo do centro foi removido e não teremos nenhuma figura para ser preenchida.

(ii) Vamos supor que um triângulo de lado $ n $ possa ser preenchido. Provaremos que o de lado $ n+9 $ também pode. Para isso, é suficiente mostrarmos que o complemento pode ser preenchido com trapézios.

Comece escolhendo um vértice qualquer e cubra um dos lados que o contém até restarem dois espaços para trapézios deitados(se você quiser acompanhar na figura acima, comece com o vértice que fica embaixo e na esquerda e faça isso com o lado horizontal).

Quanto a segunda linha (debaixo para cima), cubra até restar $ 4 $ espaços. Na terceira linha (debaixo para cima), deixe um espaço à esquerda e preencha até onde foi a segunda linha. Além disso, coloque uma peça acima das duas primeiras peças da terceira linha. Repita este procedimento para os outros dois vértices.

Desta forma, o complemento é preenchido e assim terminamos o passo indutivo. Logo todo $ n \equiv 1 \pmod{9} $ pode ser preenchido conforme o enunciado e assim vale para o caso em que $ n=2^{2004} $.

Exemplo (Cone Sul 2012) Editar

Demonstre que não existem inteiros positivos $ a,b,c,d $ primos entre si dois a dois, tais que $ ab+cd,ac+bd $ e $ ad+bc $ sejam divisores ímpares de

$ (a+b-c-d)(a-b+c-d)(a-b-c+d). $

Solução: Suponha, por absurdo, que $ a,b,c $ e $ d $ existam. A estratégia principal do problema será a seguinte: mostrar que $ ab+cd,ac+bd $ e $ ad+bc $ são primos entre si dois a dois. Depois mostraremos que

$ (ab+cd)(ac+bd)(ad+bc) \mid (a+b-c-d)(a-b+c-d)(a-b-c+d), $

mas que

$ |(a+b-c-d)(a-b+c-d)(a-b-c+d)|<|(ab+cd)(ac+bd)(ad+bc)|, $

nos dando um absurdo e, logo, mostrando que $ a,b,c $ e $ d $ não existem.

Começaremos mostrando que $ ab+cd,ac+bd $ e $ ad+bc $ são primos entre si dois a dois. Sem perda de generalidade, provaremos que $ ac+bd $ e $ ad+bc $ são primos entre si.

Suponha que eles não sejam primos entre si. Então existe um primo $ p $ que divide ambos. Mas quem garante que existe um número primo? Como existe um inteiro maior que $ 1 $ que divide ambos e este possui um divisor primo, então existe um primo que divide ambos. Usamos um número primo, pois é mais vantajoso trabalhar com eles aqui.

Observe que

$ p \mid (ac+bd)+(ad+bc) = (a+b)(c+d). $

Como $ p $ é primo, segue que $ p \mid a+b $ ou $ p \mid c+d $. Além disso,

$ p \mid (ac+bd)-(ad+bc) = (a-b)(c-d). $

Da mesma forma, $ p \mid a-b $ ou $ p \mid c-d $.

Porém não podemos ter $ p \mid a+b $ e $ p \mid a-b $ ao mesmo tempo. Com efeito, isso implicaria que $ p $ divide a soma e a diferença entre esses números e assim $ p \mid 2a $ e $ p \mid 2b $. Então, como $ a $ e $ b $ são coprimos, segue que $ p \mid \operatorname{mdc}(2a,2b)=2\operatorname{mdc}(a,b)=2 $.

Mas como $ ac+bd $ e $ ad+bc $ ímpares, $ p $ também será. Absurdo. Logo $ p $ não pode dividir $ a+b $ e $ a-b $. Analogamente, $ p $ não pode dividr $ c+d $ e $ c-d $ ao mesmo tempo.

Desta forma, $ p $ divide $ a+b $ e $ c-d $ ao mesmo tempo ou divide $ a-b $ e $ c+d $ ao mesmo tempo. Por simetria, o segundo caso é análogo. Portanto, podemos supor, sem perda de generalidade, que vale o primeiro caso.

Para facilitar a escrita, façamos $ P=(a+b-c-d)(a-b+c-d)(a-b-c+d) $. Observe que $ p \mid ac+bd $ e pelo enunciado $ ac+bd \mid P $, de onde segue que $ p \mid P $, ou seja,

$ P \equiv 0 \pmod{p}. $

Como $ p \mid a+b, c-d $, segue que

$ (a+b-c-d)(a-b+c-d)(a-b-c+d) \equiv 0 \pmod{p} \Leftrightarrow $

$ \Leftrightarrow (-c-d)(a-b)(a-b) \equiv 0 \pmod{p} \Leftrightarrow p \mid (-c-d)(a-b)(a-b) \Leftrightarrow p \mid (c-d) \text{ ou } p \mid (a-b). $

Isto contradiz algo que já provamos. Logo, $ ac+bd $ e $ ad+bc $ são primos entre si. Analogamente, podemos provar que $ ab+cd $, $ ac+bd $ e $ ad+bc $ são dois a dois primos entre si. Como estes são divisores de $ P $, segue que

$ (ab+cd)(ac+bd)(ad+bc) \mid P. $

Para facilitar a nossa escrita, faremos $ Q=(ab+cd)(ac+bd)(ad+bc) $. Como $ P $ é diferente de zero (pois é ímpar), segue que $ |Q| \leq |P| $.

Veremos agora que $ |P|<|Q| (*) $. Com efeito, mostraremos que

$ ab+cd>|a+b-c-d| (**) $

$ ad+bc>|a-b-c+d| (***) $

$ ac+bd>|a-b+c-d|. (****) $

Para mostrarmos $ (*) $ a partir daí, basta multiplicarmos estas três últimas desigualdades. Comecemos verificando $ (**) $. Vamos supor, sem perda de generalidade, que $ a+b \geq c+d $. Então $ |a+b-c-d|=a+b-c-d $ e assim

$ ab+cd-|a+b-c-d|=ab+cd-a-b+c+d=ab-a-b+cd+c+d= $

$ =ab-a-b+1+cd+c+d+1-2=(a-1)(b-1)+(c+1)(d+1)-2.(*****) $

Como $ a,b,c $ e $ d $ são maiores ou iguais a $ 1 $, segue que $ (a-1)(b-1)\geq 0 $ e $ (c+1)(d+1) \geq 4>2 $. Desta forma, a expressão que aparece em $ (*****) $ é maior do que zero, o que prova $ (**) $. Analogamente, podemos provar $ (***) $ e $ (****) $. Desta forma, $ (*) $ é verdade, o que nos dá uma contradição.

Portanto, não existem $ a,b,c $ e $ d $ que satisfazem as condições do enunciado.

Último (ou últimos) algarismosEditar

Módulo $ 10 $ é Útil Para Mexermos com o Último Algarismo. Afinal $ x $ e seu último algarismo são congruentes módulo $ 10 $.

E quando quisermos mexer com os dois últimos algarismos? Aí podemos usar módulo $ 10^2 $. De fato, um número e o número formado pelos seus dois últimos algarismos são congruentes módulo $ 10^2 $.

Em geral, um número e o número formado pelos seus $ n $ últimos algarismos são congruentes módulo $ 10^n $.

ExemploEditar

Prove que nenhum número inteiro terminado em $ 2 $, $ 3 $, $ 7 $ ou $ 8 $ possui raiz quadrada exata.

Solução: O enunciado equivale a dizer que se $ x $ é inteiro, então $ x^2 $ não pode ter restos $ 2 $, $ 3 $, $ 7 $ ou $ 8 $ na divisão por $ 10 $.

Observe que se $ x $ é inteiro, então ele deve ser congruente a um dos números $ 0,1,2,3,4,5,6,7,8 $ ou $ 9 $ módulo $ 10 $. Será que realmente é necessário olharmos para todos os casos? Não! Observe que os números $ 6,7,8 $ e $ 9 $ são congruentes a $ -4,-3,-2 $ e $ -1 $ módulo $ 10 $.

Desta forma, podemos pensar da seguinte maneira: se um número $ x $ é inteiro, ele deve ser congruente a $ 0,\pm 1, \pm 2, \pm 3, \pm 4, 5 $ módulo $ 10 $. Analisemos cada caso:

$ x \equiv 0 \pmod{10} \Rightarrow x^2 \equiv 0 \pmod{10}, $

$ x \equiv \pm 1 \pmod{10} \Rightarrow x^2 \equiv 1 \pmod{10}, $

$ x \equiv \pm 2 \pmod{10} \Rightarrow x^2 \equiv 4 \pmod{10}, $

$ x \equiv \pm 3 \pmod{10} \Rightarrow x^2 \equiv 9 \pmod{10}, $

$ x \equiv \pm 4 \pmod{10} \Rightarrow x^2 \equiv 16 \equiv 6 \pmod{10}, $

$ x \equiv 5 \pmod{10} \Rightarrow x^2 \equiv 25 \equiv 5 \pmod{10}. $

Logo, os possíveis restos na divisão de $ x^2 $ por $ 10 $ são $ 0,1,4,5,6 $ e $ 9 $.

Exemplo (Cone Sul 2005)Editar

Considere a sequência:

$ a_1 $ = último dígito da soma dos dígitos do número $ 2005 $

$ a_2 $ = último dígito da soma dos dígitos do número $ 20052005 $

$ a_3 $ = último dígito da soma dos dígitos do número $ 200520052005 $

$ \cdots $

$ a_n $ = último dígito da soma dos dígitos do número $ \underbrace {20052005\cdots 2005} _{n \text{ vezes } 2005} $.

Calcule $ a_1+a_2+\cdots+a_{2005} $.

Solução: A soma dos dígitos de $ \underbrace {20052005\cdots 2005} _{n \text{ vezes } 2005} $ é $ 7n $. Estamos interessados no último dígito, ou seja, no resto da divisão por $ 10 $. Aqui as sequências começam a ficar periódicas.

Observe que os primeiros dez termos são $ 7,4,1,8,5,2,9,6,3,0 $. A partir daí, a sequência começa a se repetir.

Como $ 2005=200\cdot 10+5 $, a sequência $ 7,4,1,8,5,2,9,6,3,0 $ aparecerá $ 200 $ vezes e depois aparecerão $ 7,4,1,8,5 $. Logo,

$ a_1+a_2+\cdots+a_{2005}=200(7+4+1+8+5+2+9+6+3+0)+7+4+1+8+5= $

$ =200.45+25=9025. $

Exemplo (OBM 2004 - 3ª Fase - Nível 2) Editar

A sequência de algarismos

$ 1,2,3,4,0,9,6,4,8,7,\dots $

é construída da seguinte maneira: cada elemento, a partir do quinto, é igual ao último algarismo da soma dos quatro anteriores.

(a) Os algarismos $ 2,0,0,4 $ juntos e nesta ordem, aparecem na sequência?

(b) Os algarismos iniciais $ 1,2,3,4 $, juntos e nesta ordem, aparecem novamente na sequência?

Solução:

(a) Observe que um número e seu último algarismo possuem a mesma paridade. Vamos analisar a paridade da sequência e mostrar que quatro pares consecutivos nunca aparecem. Para facilitar a escrita, consideraremos $ p $ e $ i $ para representar algum número arbitrário par e um ímpar, respectivamente.

Nessa notação, os quinze primeiros termos da sequência são:

$ i,p,i,p,p,i,p,i,p,p,i,p,i,p,p. $

Parece que as paridades $ i,p,i,p,p $ aparecem de cinco em cinco. Provemos, por indução, que isso é verdade. Suponha que ela se repita até o $ k $-ésimo período. Mostraremos que o $ (k+1) $-ésimo período também é da forma $ i,p,i,p,p $. Consideremos $ a,b,c,d,e $ as paridades do $ (k+1) $-ésimo período. Então $ a=p+i+p+p=i $. Da mesma forma, $ b=p $, $ c=i $, $ d=p $ e $ e=p $.

Portanto, a sequência nunca pode ter paridade $ p,p,p,p $ e com isso, $ 2,0,0,4 $ nunca pode aparecer.

(b) Existe uma quantidade finita de possibilidades para quatro termos consecutivos $ a,b,c,d $. De fato, existem $ 10^4 $ possibilidades. Assim, em algum momento a sequência irá começar a se repetir em algum momento e existirá um período. Provaremos que $ 1,2,3,4 $ também está no período.

Para isto, a estratégia será a seguinte: considere $ y $ o número da sequência antes dela virar o período e $ x $ o último algarismo do período. Provaremos que $ y=x $. Se repetirmos esse raciocínio, para todos os números que vem antes de $ y $ na sequência, provaremos que os termos anteriores estão no períodio, inclusive $ 1,2,3,4 $.

E para mostrar que $ y=x $? Como sabemos que $ 0 \leq x,y \leq 9 $, basta mostrarmos que $ y \equiv x \pmod{10} $. Observe que $ y,a,b,c,d $ e $ x,a,b,c,d $ aparecem consecutivamente. Logo,

$ y+a+b+c \equiv d \pmod{10} $

$ x+a+b+c \equiv d \pmod{10} $.

Se subtrairmos uma congruência da outra, concluiremos que $ y \equiv x \pmod{10} $.

Exemplo (Cone Sul 2000) Editar

Dizemos que um número é descendente se cada um de seus dígitos é menor do que ou igual ao dígito anterior, da esquerda para a direita. Por exemplo, $ 4221 $ e $ 751 $ são números descendentes, enquanto $ 476 $ e $ 455 $ não são descendentes. Determine se existem inteiros positivos $ n $ para os quais $ 16^n $ é descendente.

Solução: Verificar isso para $ 16^n $ para valores muito grandes de $ n $ parece dar trabalho. Mas nós temos uma vantagem: podemos olhar para os seus últimos algarismos. Se os seus últimos algarismos não forem descendentes, então o número também não será.

Vamos olhar para os quatro últimos algarismos, ou seja, analisemos módulo $ 10000 $. Queremos encontrar $ x $ menores que $ 1000 $ tais que

$ 2^{4n} \equiv x \pmod{10000}. (*) $

Podemos dizer algo sobre $ x $? Observe que $ 2^4|x $ e $ 2^4|2^{4n} $, segue que $ 2^4|x $. Com isso, existe $ k $ inteiro tal que

$ x=2^4k. $

Se substituirmos em $ (*) $,

$ 2^{4n} \equiv 2^4k \pmod{10000}. (**) $

Vamos encontrar mais informações sobre $ k $. Parece que não conseguimos muito porque o módulo é muito alto. Então peguemos um mais baixo. Como $ 10|10000 $, segue que

$ 2^{4n} \equiv 2^4k \pmod{10} \Leftrightarrow 16^n \equiv 16k \pmod{10} \Leftrightarrow 6k \equiv 6 \pmod{10}. $

Como $ 2|6k,6,10 $, segue que

$ \frac{6k}{2} \equiv \frac{6}{2} \pmod{\frac{10}{2}} \Leftrightarrow 3k \equiv 3 \pmod{5}. $

Como $ \operatorname{mdc}(3,5)=1 $, segue que

$ k \equiv 1 \pmod{5}. $

Com isso, existe $ q $ inteiro tal que $ k=5q+1 $. Se substituirmos em $ (*) $:

$ 2^{4n} \equiv 2^4(5q+1) \pmod{10000} \Leftrightarrow $

$ \Leftrightarrow 2^{4n} \equiv 10(8q+1)+6 \pmod{10000}. $

E por que escrevemos deste jeito? Separamos o último algarismo $ 6 $ dos outros. Desta maneira, percebemos que se retirarmo o último algarismo de $ 2^{4n} $, teremos um número da forma $ 8q+1 $.

Além disso, como $ 2^{4n} $ é descendente, segue que os algarismos de $ 8q+1 $ devem ser maior que $ 6 $. Mas ele é ímpar. Logo, seu último algarismo só pode ser $ 7 $ ou $ 9 $.

As possibilidades para os três últimos algarismos de $ 8q+1 $ são $ 999,997,987,977,887,877 $ e $ 777 $. Mas dentre esses, os que realmente podem ser da fora $ 8q+1 $ são $ 977 $ e $ 777 $.

Então os últimos quatro algarismos possíveis de $ 16^n $ descendentes são $ 7776 $ e $ 9776 $. Vamos analisar cada caso separadamente.

1º Caso: $ 16^n $ termina com $ 7776 $

Vamos pensar no quinto algarismo da direita para a esquerda. Ele pode ser $ 7,8 $ ou $ 9 $.

Analisemos quando ele é igual a $ 7 $, ou seja, os últimos cinco algarismos de $ 16^n $ são $ 77776 $? Não: se isso acontecesse, então $ 16^n \equiv 77776 \pmod{100000} $. Isto não acontece, pois $ n \geq 2 $ (já que $ 16^1 $ só tem dois algarismos) e assim $ \operatorname{mdc}(16^n,10^5)=2^5 $ que não divide $ 77776 $. Logo, o quinto algarismo da esquerda para a direita não pode ser $ 7 $. Pelo mesmo argumento, ele não pode ser $ 9 $.

E o caso este algarismo for $ 8 $. O sexto algarismo da direita para a esquerda pode ser $ 8 $ ou $ 9 $. Vamos analisar cada caso separadamente.

(i) O sexto algarismo da direita para a esquerda é $ 8 $.

Neste caso,

$ 16^n \equiv 887776 \pmod{1000000} $

isto não pode ocorrer, pois $ n\geq 2 $ e $ \operatorname{mdc}(16^n,100000)=2^6 $ não divide $ 887776 $.

(ii) O sexto algarismo da direita para a esquerda é $ 9 $. Neste caso, $ 16^n \equiv 987776 \pmod{1000000} $. O sétimo algarismo da direita para a esquerda deve ser $ 9 $. Então $ 16^n \equiv 9987776 \pmod{1000000} $, o que não pode acontecer pois $ n \geq 3 $ e $ \operatorname{mdc}(16^n,1000000)=2^7 $ não divide $ 9987776 $.

Portanto, o 1º Caso não possui soluções.

2º Caso: $ 16^n $ termina com $ 9776 $

O quinto e o sexto algarismos da direita para a esquerda devem ser iguais a $ 9 $. Então

$ 16^n \equiv 999776 \pmod{1000000} $

Isto não pode acontecer, pois $ \operatorname{mdc}(16^n,1000000)=2^6 $ não divide $ 999776 $. Com isso, o 2° Caso não tem solução.

E os casos em que $ 16^n $ tem $ 6 $ dígitos ou menos? Basta testá-los e ver que eles não são descendentes. Logo, não existem números que satisfazem as condições do enunciado.

Módulo 9 é Útil Para Mexermos com AlgarismosEditar

Pode ser quando estamos falando sobre soma dos algarismos ou quando estamos reeordenando-os.

ProposiçãoEditar

Sejam $ a $ e $ b $ inteiros, onde $ b $ pode ser obtido com uma permutação dos algarismos de $ a $. Então

$ a \equiv b \pmod{9} $

Exemplo (OBM 2000 - 3ª Fase - Nível 2)Editar

É possível encontrar duas potências de $ 2 $, distintas e com o mesmo número de algarismos, tais que uma possa ser obtida através de uma reordenação dos dígitos da outra?

Solução: Seja $ A=2^m $ e $ A'=2^n $, onde $ A' $ é uma reordenação dos dígitos de $ A $. Sem perda de generalidade, podemos supor que $ A $ é maior que $ A' $.

Como $ A $ e $ A' $ são potências de $ 2 $, então $ A $ é múltiplo de $ A' $, isto é, existe $ k $ inteiro tal que $ A=kA' $ (e, neste caso, $ k $ é uma potência de $ 2 $).

Observe que $ k $ deve ser menor que $ 10 $ (pois senão $ A $ teria mais algarismos que $ A' $). Desta forma, $ k=2 $, $ 4 $ ou $ 8 $. Vamos analisar cada possibilidade.

(i) $ k=2 $

$ A\equiv A' \pmod{9} \Leftrightarrow 2A' \equiv A' \pmod{9} \Leftrightarrow A' \equiv 0 \pmod{9}. $

Isto não ocorre, pois $ A' $ é uma potência de $ 2 $.

(ii) $ k=4 $

Aqui,

$ A\equiv A' \pmod{9} \Leftrightarrow 4A' \equiv A' \pmod{9} \Leftrightarrow 3A' \equiv 0 \pmod{9} \Leftrightarrow A' \equiv 0 \pmod{9}. $

Mas $ A' $ é uma potência de $ 2 $. Logo, este caso não nos dá nenhum número.

(iii)$ k=8 $

Neste caso,

$ A\equiv A' \pmod{9} \Leftrightarrow 8A' \equiv A' \pmod{9} \Leftrightarrow 7A' \equiv 0 \pmod{9} \Leftrightarrow A' \equiv 0 \pmod{9}. $

Esta última equivalência se deve ao fato de que $ \operatorname{mdc}(7,9)=1 $.

Portanto, não existe nenhum número nas condições do enunciado.

ProposiçãoEditar

Seja $ n $ um número inteiro e $ s(n) $ a soma dos seus algarismos. Então

$ n \equiv s(n) \pmod{9} $.

Exemplo (OBM 2002 - 3ª Fase - Nível 2)Editar

Mostre que, entre dezoito inteiros consecutivos de três algarismos, sempre existe algum que é divisível pela soma de seus algarismos.

Solução: Se escrevermos dezoito números consecutivos, os restos das divisões destes números por $ 18 $ serão $ 0, 1, 2, \dots, 17 $ (em alguma ordem). Talvez seja útil olharmos para o resto da divisão por $ 18 $ de alguma forma.

Provaremos o seguinte: todo número de três algarismos múltiplo de $ 18 $ é divisível pela soma de seus algarismos. Isto resolverá o problema, pois entre dezoito números consecutivos sempre existe um múltiplo de $ 18 $.

Considere $ x $ um múltiplo de $ 18 $ de três algarismos. Provaremos que $ s(x) $ (a soma dos algarismos de $ x $) divide $ x $. Sabemos que $ s(x) \equiv x \equiv 0 \pmod{9} $. Como $ x $ possui três algarismos, segue que $ s(x) \leq 9+9+9=27 $. Logo, $ s(x)=9 $, $ 18 $ ou $ 27 $.

Se $ s(x)=27 $ e $ x $ tem três algarismos, então $ x=999 $ que não é múltiplo de $ 18 $. Logo $ s(x)=9 $ ou $ 18 $. Em ambos os casos $ s(x) $ divide $ x $ (pois $ x $ é múltiplo de $ 18 $).

Logo, todo múltiplo de $ 18 $ cumpre as condições do enunciado.

Exemplo (Cone Sul 1994)Editar

O inteiro positivo $ N $ tem $ 1994 $ dígitos. Destes, $ 14 $ são iguais a zero e os números de vezes que aparecem os demais dígitos: $ 1,2,3,4,5,6,7,8,9 $, estão na razão $ 1:2:3:4:5:6:7:8:9 $, respectivamente. Demonstrar que $ N $ não é um quadrado perfeito.

Solução: Já que é mais fácil ver a soma dos algarismos de $ N $, vejamos ele módulo $ 9 $. Os $ 1994-14=1980 $ algarismos diferentes de zero estão na proporção $ 1:2:3:4:5:6:7:8:9 $. O que significa isso? Que a cada $ 1+2+\dots+9=45 $ partes, $ 1 $ corresponde ao algarismo $ 1 $, $ 2 $ correspondem ao algarismo $ 2 $ e assim por diante.

Cada uma dessas partes corresponde a $ \frac{1980}{45}=44 $ algarismos. Assim, as quantidades de algarismos $ 1,2,3,...,9 $ serão $ 1.44,2.44,3.44,...,9.44 $, respectivamente.

Com isso, a soma dos algarismos de $ N $ módulo $ 9 $ será

$ 1.1.44+2.2.44+3.3.44+...+9.9.44\equiv 44.(1^2+2^2+3^2+...+9^2) \equiv 3 \pmod{9}. $

Assim, $ N \equiv 3 \pmod{9} $. Mas um quadrado perfeito só pode ser congruente a $ 0,1,4 $ ou $ 7 $ módulo $ 9 $. Logo, $ N $ não pode ser quadrado perfeito.

Exemplo (Cone Sul 2016) Editar

Seja $ S(n) $ a soma dos dígitos do número inteiro positivo $ n $. Encontrar todos os $ n $ tais que $ S(n)(S(n)-1)=n-1 $.

Solução: Como $ S(n) $ não é tão grande (comparado a $ n $), então $ n $ não pode ser tão grande assim, isto é, ele não pode ter tantos algarismos. Vamos supor que $ n $ tem exatamente $ k $ algarismos. Então

$ 10^{k-1} \leq n \leq 10^k-1.(*) $

Além disso, $ S(n) \leq 9k $, de onde segue que

$ S(n)(S(n)-1) \leq 9k(9k-1). $

Pela igualdade do enunciado,

$ n-1 \leq 9k(9k-1). $

Se usarmos $ (*) $,

$ 10^{k-1}-1 \leq 9k(9k-1). $

Observe que esta desigualdade vale para $ k=1,2,3,4 $. É possível provar por indução em $ k $ que ela é falsa para $ k \leq 5 $ natural. Portanto, $ n $ só pode ter no máximo quatro algarismos.

Além disso, se usarmos a igualdade do enunciado e que $ S(n) \equiv n \pmod{9} $,

$ S(n)(S(n)-1)\equiv n-1 \equiv S(n)-1\pmod{9} \Rightarrow (S(n)-1)^2 \equiv 0 \pmod{9}. $

Se um número elevado ao quadrado é congruente a $ 0 $ módulo $ 9 $, então ele deixa resto $ 0 $, $ 3 $ ou $ 6 $ na divisão por $ 9 $. Assim $ S(n) \equiv 1,4 \text{ ou } 7 \pmod{9} $.

Vamos dividir em casos.

1° Caso: $ n $ tem $ 1 $ algarismo

Aqui $ S(n)=n $ e assim a igualdade do enunciado se reescreve como

$ n(n-1)=n-1 \Leftrightarrow n=1. $

Esta é a única solução deste caso.

2ºCaso: $ n $ tem $ 2 $ algarismos

Consideremos $ n=\overline{ab}=10a+b $. Então $ S(n)=a+b $. Vejamos que $ S(n) $ não pode ser tão grande assim. Então a equação do enunciado se reescreve como

$ (a+b)(a+b-1)=10a+b-1. $

Vamos "separar um $ a+b $" e jogá-lo para outro lado:

$ (a+b)(a+b-1)=9a+a+b-1 \Leftrightarrow (a+b)(a+b-2)=9a-1. $

Como $ a \leq 9 $, segue que

$ (a+b)(a+b-2)=9a-1 \leq 80 \Rightarrow a+b \leq 10. $

Mas $ S(n) $ deixa resto $ 1 $, $ 4 $ ou $ 7 $ na divisão por $ 9 $ e assim $ S(n)=1,4,7,10 $. Vejamos cada caso separadamente.

(i) $ S(n)=1 $

Se substituirmos na equação do enunciado, concluiremos que $ n=1 $. Mas este não pode ser solução deste caso, pois ele tem apenas um algarismo.

(ii) $ S(n)=4 $

Aqui $ n=13 $.

(iii) $ S(n)=7 $

Neste caso, $ n=43 $.

(iv) $ S(n)=10 $

Da mesma forma, $ n=91 $.

3º Caso: $ n $ tem $ 3 $ algarismos

Aqui $ n \geq 100 $, de onde segue que $ n-1 \geq 99 $ e pela equação do enunciado $ S(n)(S(n)-1) \geq 99 $. Desta forma, $ S(n) \geq 11 $. Além disso, a soma dos dígitos de um número de três algarismos é no máximo $ 27 $.

Mas $ S(n) $ só pode ter restos $ 1 $, $ 4 $ ou $ 7 $ na divisão por $ 9 $. Assim os valores possíveis para $ S(n) $ são $ 13,16,19,22,25 $.

Se $ S(n)=13 $, pela equação do enunciado $ n=157 $. Nenhum outro valor de $ S(n) $ nos dará uma solução válida (nestes casos $ S(n) $ não coincidirá com a verdadeira soma dos algarismos).

4º Caso: $ n $ tem $ 4 $ algarismos

Como $ n \geq 1000 $ segue que $ n-1 \geq 999 $ e pela equação do enunciado $ S(n)(S(n)-1) \geq 999 $. Com isso, $ S(n) \geq 33 $.

Além disso, a soma dos dígitos de um número de quatro algarismos é no máximo $ 36 $. Mas $ S(n) $ só pode ter restos $ 1 $, $ 4 $ ou $ 7 $ na divisão por $ 9 $. Assim $ S(n)=34 $, o que nos daria $ n=1123 $. A soma dos algarismos dele não é $ 34 $. Logo, ele não é uma solução.

Portanto, as soluções são $ 1,13,43,91 $ e $ 157 $.

Exemplo (Cone Sul 1995) Editar

Encontre um número de três dígitos, sabendo que a soma dos seus dígitos é $ 9 $, o produto das mesmas é $ 24 $ e além disso o número lido da direita à esquerda é $ \frac{27}{38} $ do número primitivo.

Solução: Seja $ \overline{abc} $ este número de três algarismos. Segundo o enunciado,

$ \overline{abc}=\frac{27}{38}\overline{cba} \Leftrightarrow 38 \overline{abc}= 27 \overline{cba}. $

Vamos analisar módulo $ 38 $ (pois este é o módulo que deixa a congruência mais simples):

$ 27 \overline{cba} \equiv 0 \pmod{38}. $

Como $ \operatorname{mdc}(27,38)=1 $,

$ \overline{cba} \equiv 0 \pmod{38}. $

De onde segue que $ \overline{cba} $ é múltiplo de $ 38 $. Podemos relacionar $ \overline{cba} $ usando módulo novamente. Como a soma dos seus dígitos é $ 9 $,

$ \overline{cba} \equiv c+b+a \equiv 0 \pmod{9}. $

E com isso, $ \overline{cba} $ também é múltiplo de $ 9 $. Como $ 38 $ e $ 9 $ são primos entre si, segue que $ 38.9|\overline{cba} $, isto é, existe $ k $ inteiro tal que $ \overline{cba}=38.9k=342k $. Como $ \overline{cba} $ é menor do que $ 1000 $, segue que $ k $ não pode ser maior que $ 2 $, ou seja, $ k=1 \text{ ou } 2 $.

Observe que, se $ k=2 $, então

$ \overline{cba}=342.2=684 \Leftrightarrow \overline{abc}=486. $

Mas isto não pode acontecer, pois o produto dos algarismos de $ \overline{abc} $ deve ser $ 24 $.

Logo, $ k=1 $ e assim a resposta é $ \overline{abc}=342 $.

Inverso ModularEditar

Se $ a $ é diferente de zero e $ ax=ay $, podemos concluir que $ x=y $. Isso vale para módulo? Se $ ax \equiv ay \pmod{m} $, podemos concluir que $ x \equiv y \pmod{m} $?

ProposiçãoEditar

Se $ \operatorname{mdc}(a,m)=1 $, então existe n inteiro tal que $ an \equiv 1 \pmod{n} $.

CorolárioEditar

Se $ \operatorname{mdc}(a,m)=1 $ e $ ax \equiv ay \pmod{m} $, então $ x \equiv y \pmod{m} $.

ExemploEditar

Se $ 2x \equiv 1 \pmod {3} $, como podemos fazer para livrarmos o $ x $ do $ 2 $? Basta multiplicarmos ambos os lados por $ 2 $ e assim

$ 2 \cdot 2x \equiv 2 \cdot 1 \pmod{3} \Leftrightarrow x \equiv 2 \pmod{3}. $

Páginas RelacionadasEditar

Divisibilidade 

BibliografiaEditar

  • E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996.
  • P. Zeitz : The Art and Craft of Problem Solving, Wiley; International Student edition, 2006.
O conteúdo da comunidade está disponível sob CC-BY-SA salvo indicação em contrário.