Teoria Dos números

8. Congruências

8.1 Definições preliminares

(i) Sejam a, b, n Z, n>0. Dizemos que a é congruente a b(módulo n) se n | (b-a). A notação que iremos utilizar é (a b mod (n)).

(ii) Chamaremos classe de congruência de um inteiro a, ao conjunto ={k Z | k a mod(n)}. O conjunto de todas as classes de congruências é denotado Z/(n).

E a escolha de um representante para uma classe é chamada resíduo.

Obs.: Questões concernentes a restos e divisibilidade por n podem ser verificadas em qualquer sistema completo de resíduos.

8.2 Propriedades iniciais:

8.2.1 Relação de equivalência

(i) (reflexiva) a a mod (n)

(ii) (simétrica) a b mod (n) b a mod (n)

(iii)(transitiva) Se a b mod (n) e b c mod (n) então a c mod (n)

Obs. A partir destas propriedades notamos que as classes de equivalência definidas anteriormente ou coincidem (quando os representantes são congruentes) ou são disjuntas (quando os representantes não são congruentes). Além disso, O conjunto dos inteiros pode ser escrito como uma união disjunta de classes de congruências (tomando um sistema completo de resíduos)

8.2.2 Compatibilidade

(i) Se a b mod (n) e c d mod (n) então: para todo x inteiro ax c mod (n) bx d mod (n)

(ii) Se a b mod (n) e c d mod (n) então temos que: a+c b+d mod (n). Em particular, se a b mod (n) então a+c b+c mod (n) para qualquer c inteiro

(iii) Se a b mod (n) e c d mod (n) então temos que: a.c b.d mod (n) em particular, se a b mod (n) então ax bx mod (n) para todo x inteiro

Obs. A partir destas propriedades de compatibilidade podemos definir soma e produto de classes de congruência.

8.2.3Leis de cancelamento

(i) Se mdc(x,n) d então temos que ax bx mod (n) a b(mod n/d).

(ii) Em particular, se mdc(x,n) 1 então ax bx mod (n) a b mod (n)

(iii) Ainda como conseqüência que quando d | n e

ad bd mod (n) então a b mod (n/d)

Obs. A partir destas leis de cancelamento podemos identificar quando um inteiro é inversível módulo n, e isto ocorrerá se e somente se ele for coprimo com n.

8.2.4 Descida e subida

Sejam n e d naturais tais que d | n. n=qd

(i) (descida) Se Se a b mod (n) então a b mod (d)

(ii) (subida) Se Se a b mod (d) então módulo n temos que Se a b+ kd mod (n) com k<q.

8.2.4 Decomposição

Sabemos do teorema fundamental da aritmética que podemos fatorar n da seguinte forma:

Esta decomposição é preciosa em termos de congruência pois:

De modo que o mais importante é saber resolver a congruência módulo potências de primos.

8.2.5 Restos como sistema de resíduos.

Dados a e n inteiros, n>0, existe um único inteiro r no conjunto {0, 1, 2, ..., n-1} dos restos na divisão por n tal que a = r mod(n)

8.3 Equações do primeiro grau

Estaremos interessados em resolver equações do tipo ax b mod (n).

(i) Uma condição necessária e suficiente para que a equação ax b mod (n) do primeiro grau tenha solução é que d=mdc(a,n) | b. Se este for o caso, então o número de soluções não congruentes (módulo n) da equação é extamente d.

(ii) Um importante caso especial é a equação

ax 1 mod (n) que quando tem solução dizemos que a é inversível módulo n e isso ocorre se e somente se a e n são coprimos

Obs. Notamos que o mdc(a,n) não depende da escolha de um particular a, isto é, se a b mod (n)

Então mdc(a,n) = mdc(b,n) portanto a condição de ser inversível módulo n é uma condição da classe de congruência e não de um particular resíduo que represente a classe.

(iii) Existe uma relação natural entre as equações de primeiro grau módulo n e as equações diofantinas lineares em duas variáveis onde à equação ax+by= c

Associamos a equação ax c mod (b) e à equação

ax b mod (n) associamos a equação ax+ny=b.

8.4 Resíduos e resíduos inversíveis

Lembramos que dados a e n inteiros, n>0, existe um único r no conjunto {0, 1, ..., n-1} tal que a r mod (n)

E além disso, dois restos distintos numca são congruentes. Desta feita o conjunto {0, 1, ..., n-1} representa todos os inteiros em questões relativas a divisibilidade e a restos na divisão por n.

(i) Um sistema completo de resíduos módulo n é um conjunto de inteiros {a1, a2, ...,ak} satisfazendo as propriedades que todo inteiro a é congruente módulo n a um dos ai e que estes são dois a dois incongruentes módulo n.

(ii) As principais propriedades dos sistemas completos de resíduos é que todos tem a mesma cardinalidade “n” e que se {a1, a2, ...,ak} é um sistema completo de resíduos e b é coprimo com n então o conjunto {ba1, ba2, ..., bak} é também um sistema completo de resíduos módulo n

(i) Um sistema completo de resíduos inversíveis módulo n é um conjunto de inteiros {a1, a2, ...,ak} satisfazendo as propriedades que todo inteiro a que seja inversível módulo n, isto é, coprimo com n, é congruente módulo n a um dos ai e que estes são dois a dois incongruentes módulo n.

(ii) As principais propriedades dos sistemas completos de resíduos inversíveis módulo n é