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} (pois o 0 é único resto possível na divisão por 1, ou seja, todos possuem o mesmo resto).

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 ab \equiv ac \pmod{m} e \operatorname{mdc}(a,m)=1, então b \equiv c \pmod{m}.

Exemplo (Cone Sul)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}, precisamos encontrar um dígito a_k tal que (x_k+10^ka_k)^2-(x_k+10^k) \equiv  0 \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

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

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

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.

Se k fosse igual a 2, então

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.

Páginas RelacionadasEditar

Divisibilidade 

Referências BibliográficasEditar

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

Interferência de bloqueador de anúncios detectada!


A Wikia é um site grátis que ganha dinheiro com publicidade. Nós temos uma experiência modificada para leitores usando bloqueadores de anúncios

A Wikia não é acessível se você fez outras modificações. Remova o bloqueador de anúncios personalizado para que a página carregue como esperado.