bc1405 – Congruências

— Congruências —

Para inteiros {a,b,n}, com {n\neq 0}, dizemos que {a} é congruente a {b} módulo {n}, e escrevemos

\displaystyle   a\equiv b \pmod n \ \ \ \ \ (44)

se {n|(a-b)}. Como {n|(a-b) \Leftrightarrow -n|(a-b)} nos restringiremos ao caso {n>0}. O caso {n=1} é trivial pois quaisquer dois inteiros são congruentes. Geralmente, os casos interessantes são para {n>1}. Para {n=2}, por exemplo, dois inteiros são congruentes se, e só se, eles diferem por um inteiro par, ou seja, têm mesma paridade.

Por exemplo, {152 \equiv 5 \pmod 7} ({152=21\cdot 7 +5}) e {-152 \equiv 2 \pmod 7} ({152=(-22)\cdot 7 +2}). Também, {7\equiv 15 \pmod 8}, {3\equiv 21 \pmod6}.

Dados {a} e {b} congruentes, usando o Teorema da Divisão, dividimos ambos por {n} e temos únicos {q_a,r_a,q_b,r_b} tais que {a=nq_a+r_a} e {b=nq_b+r_b} de modo que {0\leq r_a,r_b<n}, portanto, {-n < r_a - r_b < n} e temos

\displaystyle   a-b = n(q_a-q_b) + (r_a - r_b) \ \ \ \ \ (45)

com {n|(a-b)~\text{ e }~n|n(q_q-q_b)} logo {n|(r_a-r_b)} e como o único múltiplo de {n} que satisfaz {-n < r_a-r_b < n} é o {0} temos

\displaystyle r_a=r_b.

Concluindo, se {a} é congruente a {b} módulo {n} então {a} e {b} deixam o mesmo resto quando divididos por {n}. Por outro lado, se {a} e {b} deixam o mesmo resto quando divididos por {n} então {n|(a-b)} pois {a-b = n(q_a-q_b)}. O que estabelecemos foi

Proposição 24 {a\equiv b \pmod n \Longleftrightarrow a\mod n = b\mod n}.

Observação 2 Segue da equivalência dada na proposição acima e do Teorema da Divisão que todo inteiro é congruente a um, e somente um, dentre os números {\{0,1,2,\dots,n-1\}}

Claramente, {\equiv \pmod n} é uma relação de equivalência; é reflexiva ({a\equiv a \pmod n}), é simétrica ({a\equiv b \pmod n \Leftrightarrow b\equiv a \pmod n}), e é transitiva ({a\mod n = b\mod n ~\text{ e }~b\mod n = c\mod n \Leftrightarrow a\mod n = c\mod n }).

Proposição 25 {\equiv} é uma relação de equivalência sobre {{\mathbb Z}}.

Além de ser relação de equivalência, congruência é compatível com as operações aritméticas dos inteiros.

Proposição 26 Para quaisquer inteiros {a,b,c,d,n}, se {a\equiv b\pmod n} e {c\equiv d \pmod n} então valem

  1. {a+c \equiv b+d \pmod n}
  2. {a-c \equiv b-d \pmod n}
  3. {a\cdot c \equiv b\cdot d \pmod n}

Note que, em particular, vale quando {c=d}.

Demonstração: Da hipótese temos que {n|(a-b)} e {n|(c-d)} e do exercício 31, item 7 temos que {n|x(a-b)+y(c-d)} para quaisquer {x,y\in{\mathbb Z}}, daí

  1. o item 1 segue de { (a-b)+ (c-d) = (a+c)- (b+d)};
  2. o item 2 segue de { (a-b) - (c-d) = (a-c)- (b-d)};
  3. o item 3 segue de { c(a-b)+ b(c-d) = ac - bd}.

\Box

Corolário 27 Para quaisquer inteiros {a,b,c} e {n>0}

\displaystyle  a+c \equiv b+c \pmod n \Rightarrow a \equiv b \pmod n.

Demonstração: Segue do item 2. \Box

Corolário 28 Se {a\equiv b \pmod n}, então {a^k \equiv b^k \pmod n}, para todo {k\in{\mathbb N}}.

Demonstração: Segue do item 3. \Box

Por exemplo, {10 \equiv -1 \pmod {11}}, portanto {10^{200} \equiv -1^{200} \pmod {11}}, e como {1 \equiv -1^{200} \pmod {11}} temos {1 \equiv 10^{200} \pmod {11}}, portanto, {11| 10^{200}-1}.

Exercício 37 Mostre, usando indução, que para {n} pares de inteiros {a_i} e {b_i}, tais que {a_i\equiv b_i \pmod n} ({i\in\{1,2,\dots,n\}}) valem
\displaystyle {\sum_{i=1}^n a_i \equiv \sum_{i=1}^n b_i \pmod n }
\displaystyle {   \prod_{i=1}^n a_i \equiv \prod_{i=1}^n b_i \pmod n }

Proposição 29 Se {ca \equiv cb \pmod n} e {\mathrm{mdc}(c,n)=d>0} então

\displaystyle a\equiv b \pmod{\frac nd}.

Demonstração: Se {ca \equiv cb \pmod n} então existe {q} tal que {nq=ca-cb=c(a-b)}. Como {d>0} divide {n} e divide {c} temos {\frac nd q=\frac cd (a-b)}, portanto {\frac nd | \frac cd (a-b)m }mas {\mathrm{mdc}(\frac nd,\frac cd) =1}, portanto {\frac nd \big| (a-b)}. \Box

Corolário 30 Se {\mathrm{mdc}(c,n)=1} então

\displaystyle  ac\equiv bc \pmod n \Rightarrow a\equiv b \pmod n .

Corolário 31 Se {ca \equiv cb \pmod p} e {p} primo que não divide {c} então

\displaystyle a\equiv b \pmod{p}.

Exemplo 6 (critério de divisibilidade por 9) Seja {a_r\dots a_0} a representação decimal de {n}. De {10\equiv 1 \pmod{9}} temos, pela proposição 26 que {10^s \equiv 1 \pmod{9}}, {a\cdot 10^s \equiv a \pmod{9}} {(\forall a)}, portanto, pelo exercício 37

\displaystyle a_0+a_110+a_210^2-\cdots+a_r10^r \equiv a_0+a_1+a_2+\cdots+ a_r \pmod{9}.

Exemplo 7 (critério de divisibilidade por 11) Seja {a_r\dots a_0} a representação decimal de {n}. De {10\equiv -1 \pmod{11}} temos que {a\cdot 10^s \equiv a\cdot (-1)^s \pmod{11}} portanto

\displaystyle a_0+a_110+a_210^2-\cdots+a_r10^r \equiv a_0-a_1+a_2-\cdots+(-1)^ra_r \pmod{11}.

Exemplo
{ISBN} — International Standard Book Number}

Um dos livros texto tem ISBN 8-585-81825-5.

O ISBN tem dez dígitos. O último é um dígito de controle. Os primeiros nove dígitos codificam informações como a língua e a editora do livro. Um código ISBN válido { d_0-d_1d_2d_3-d_4d_5d_6d_7d_8-d_9} satisfaz

\displaystyle  10d_0+9d_1+8d_2+7d_3+6d_4+5d_5+4d_6+3d_7+2d_8+1d_9\equiv 0\pmod{11}

quando {d_9} vale {10} é usado a letra {X}.

Exercício 38 Mostre que {31|20^{15}-1}. (dica: {20\equiv -11 \pmod{31}})

Demonstração: {20\equiv -11 \pmod{31}} portanto {20^2 \equiv 121 \equiv - 3 \pmod{31}}. Multiplicando as congruências {20^3 \equiv 33 \equiv 2 \pmod{31}} logo {20^{15} \equiv 2^5 \equiv 1 \pmod{31}}. \Box

Exercício 39 Qual o resto da divisão de {{5^3}^{20}} por {13}?

Demonstração: Nas potências de {5}

\displaystyle  \begin{array}{rcl}  & 5^0 \equiv 1 \pmod{13} & 5^4 \equiv 1 \pmod{13}\\ & 5^1 \equiv 5 \pmod{13} & 5^5 \equiv 5 \pmod{13} \\ & 5^2 \equiv -1 \pmod{13} & 5^6 \equiv -1 \pmod{13} \\ & 5^3 \equiv -5 \pmod{13} & 5^7 \equiv -5 \pmod{13} \; \cdots \end{array}

os restos se repetem com período {4}. Portanto precisamos conhecer {3^{20} \mod 4}: {3 \equiv -1 \pmod 4} logo {3^{20} \equiv 1 \pmod 4}, portanto {{5^3}^{20} \equiv 5 \pmod{13}}. \Box

Exercício 40 Qual os dois últimos algarismos de {3^{200}}.

Demonstração: {3^{200}=9^{100} = (10-1)^{100}=\sum_{k=0}^{100}\binom{100}k100^{100-k}(-1)^k \equiv -\binom{100}{99}10+\binom{100}{100}\pmod{100}\equiv 1 \pmod{100}}. Portanto, {01}. \Box

— Sistema completo de restos —

{S\subset {\mathbb Z}} é um sistema completo de restos módulo {n} se para todo {a\in{\mathbb Z}} existe um, e só um, {b\in S} tal que {a\equiv b\pmod n}. Por exemplo, alguns sistemas completos de resíduos módulo {5} são os conjuntos:

\displaystyle  \begin{array}{rcl}  &\{-2,-1,0,1,2\},\\ &\{0,1,2,3,4\},\\ &\{1,2,3,4,5\},\\ &\{12,24,35,-4,18\}. \end{array}

Conforme vimos, observação 2, {\{0,1,\dots,n-1\}} é um sistema completo de restos módulo {n}.

Para qualquer sistema completo de restos módulo {n} deve haver uma bijeção com {\{0,1,\dots,n-1\}} (por quê?) logo todo sistema completo de restos módulo {n} tem que ter cardinalidade {n}.

Observação 3 {\equiv} é uma relação de equivalência; uma classe de equivalência é dada por todos os inteiros que deixam o mesmo resto quando divididos por {n}. Um sistema completo de restos é um conjunto formado por um representante de cada classe de equivalência.

Por exemplo, definimos para {r\in{\mathbb Z}}

\displaystyle [r]_n := \{a\in{\mathbb Z}\colon a\equiv r \pmod n\}

e temos as classes que equivalência módulo {5} dadas por {[0]_5, ~ [1]_5, ~[2]_5,~ [3]_5,~ [4]_5.} Ademais, no exemplo acima identificamos que {[0]_5=[5]_5=[35]_5}, e {[-2]_5=[3]_5=[18]_5}, e {[-1]_5=[4]_5=[24]_5}, e {[2]_5=[12]_5} e {[-4]_5=[1]_5}.

Exemplo 8 A equação {X^3- 117Y^3 +1 = 5} não tem solução inteira. Toda solução inteira da equação deve satisfazer a congruência {X^3- 117Y^3 +1 \equiv 5 \pmod 9} que, Como {117} é múltiplo de {9}, equivale a {X^3 +1 \equiv 5 \pmod 9} a qual não tem solução.

Vejamos, se {x\in {\mathbb Z}} então é congruente a um (e só um) elemento {r} do sistema completo de restos {\{0,1,2,3,4,5,6,7,8\}}, portanto, {x^3 \equiv r^3 \pmod 9} {(r\in S)} e

{r} {0} {1} {2} {3} {4} {5} {6} {7} {8}
{r^3\mod 9} {0} {1} {8} {0} {1} {8} {0} {1} {8}

porém nenhum inteiro dentre {{0,1,8}} satisfaz {X^3 +1 \equiv 5 \pmod 9}.
(uma história curiosa a respeito dessa equação pode ser lida na página 81 de COUTINHO, C.; Números inteiros e criptografia RSA. IMPA-SBM, 2009.[512.7 COUn Estante:4H])

Exercício 41 A congruência {X^2 +1 \equiv 0 \pmod 8} não tem solução.

Demonstração: Consideremos o seguinte sistema completo de restos módulo {8} (verifique): {\{0,\pm 1,\pm 2,\pm 3,4\}}. Se {x\in {\mathbb Z}} então existe um único {r\in \{0,\pm 1,\pm 2,\pm 3,4\}} tal que {x\equiv r \pmod 8}, assim {x^2\equiv r^2 \pmod 8} e

{r} { 4} {\pm 3} {\pm 2} { \pm1} {0}
{r^2\mod 8} {0} {1} {4} { 1} {0}

portanto {x^2+1} é congruente a um dentre { 1,2,5}. \Box

Exercício 42 Sejam {m_1 , m_2 , \dots , m_k} inteiros positivos e defina para todo {k > 2},

\displaystyle  \mathrm{mmc}(m_1 , m_2 , \dots , m_k ) := \mathrm{mmc}(\mathrm{mmc}(m_1 , m_2 , \dots , m_{k-1} ), m_k )  \ \ \ \ \ (46)

Prove que se {a \equiv b \pmod {m_i}} para todo {i}, então

\displaystyle   a \equiv b \pmod{\mathrm{mmc}(m_1 , m_2 , \dots ,m_k )}. \ \ \ \ \ (47)

— Exercícios —

  1. Sejam {a,b,r,s} inteiros, {s\neq 0}. Prove que {a\equiv b \pmod r} se, e somente se,{as\equiv bs \pmod {rs}}.

  2. Prove que se {a} é um cubo então {a^2} é congruente a {0}, ou {1}, ou {9}, ou {28} módulo 36.
  3. Determinar todos os inteiros positivos {m} tais que as soluções de {X^2 \equiv 0 \pmod m} também sejam soluções de {X \equiv 0 \pmod m}.
  4. Determinar os restos das divisões
    1. {2^{50}} por {7};
    2. {41^{65}} por {7}.
  5. Verifique
    1. {89|(2^{44}-1)};
    2. {97|(2^{11}-1)}.
  6. Qual os dois últimos algarismos de {7^{7^{100}}}. (dica: {7^k \mod 100} é periódico)

Deixe uma resposta

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s