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} $.

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.

Ú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 $.

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.44+2.44+3.44+...+9.44\equiv 44.(1+2+3+...+9) \equiv 44.45 \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 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 $.

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.