FANDOM


Sejam a, b e m inteiros, com m>0 natural. 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 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\leq 1. Então

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

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) Se 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}.

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.

Módulo 10 é Útil Para Mexermos com o Último Algarismo Editar

Afinal x e seu último algarismo são congruentes módulo 10.

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

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.

Páginas RelacionadasEditar

Divisibilidade 

Referências BibliográficasEditar

[1] E. Lozansky, C. Rousseau : Winning Solutions, Springer-Verlag, New York, 1996.