Congruência e anéis zn

Prévia do material em texto

Congrueˆncia e ane´is zn
Rodrigo Carlos Silva de Lima ‡
rodrigo.uff.math@gmail.com
‡
1
Suma´rio
1 Congrueˆncia e ane´is zn. 3
1.1 Congrueˆncias mo´dulo n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Propriedades ba´sicas de congrueˆncia . . . . . . . . . . . . . . . . . . . . . 6
1.3 Pequeno teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Ane´is zn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4.1 Teorema de Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
1.5 Aplicac¸o˜es de congrueˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
1.6 Congrueˆncia e divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2
Capı´tulo 1
Congrueˆncia e ane´is zn.
Esse texto ainda na˜o se encontra na sua versa˜o final, sendo, por enquanto, cons-
tituı´do apenas de anotac¸o˜es informais. Sugesto˜es para melhoria do texto, correc¸o˜es
da parte matema´tica ou gramatical eu agradeceria que fossem enviadas para meu
Email rodrigo.uff.math@gmail.com.
1.1 Congrueˆncias mo´dulo n
m Definic¸a˜o 1. Sejam n ≥ 2, a, b ∈ Z, dizemos que a e´ congruente a b mo´dulo
n se n|(a − b) e denotamos por a ≡ b mod n. Caso a na˜o seja congruente a` b
mod n escrevemos a 6≡ b mod n.
Se fizermos n = 1 enta˜o para quaisquer a, b inteiros valeria
a ≡ b mod 1
pois 1|a− b, por isso a restric¸a˜o de tomar n > 1.
b Propriedade 1. A congrueˆncia e´ uma relac¸a˜o de equivaleˆncia em Z.
ê Demonstrac¸a˜o.
• A congrueˆncia mo´dulo n e´ reflexiva, a ≡ a mod n, pois n|(a− a) = 0.
3
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 4
• A congrueˆncia mo´dulo n e´ sime´trica, se a ≡ b mod n enta˜o b ≡ a mod n,
pois se a ≡ b mod n, temos n|(a−b) implicando n|(b−a) logo b ≡ a mod n.
• A congrueˆncia mo´dulo n e´ transitiva, se a ≡ b mod n e b ≡ c mod n enta˜o
a ≡ c mod n. Se a ≡ b mod n temos n|(a − b) e com b ≡ c mod n segue
n|(b− c) de onde segue que n|(a− b+ b− c = a− c) logo n|(a− c) implicando
a ≡ c mod n.
b Propriedade 2. a ≡ b mod n ⇔ a e b possuem o mesmo resto na divisa˜o
euclidiana por n.
ê Demonstrac¸a˜o. ⇒. Supondo a ≡ b mod n , tem-se n|a−b. Podemos escrever
que a = qn + r e b = q ′n + r ′ , suponha por absurdo que r 6= r ′, daı´ um deles e´
maior, supondo sem perda de generalidade que r ′ > r tem-se 0 < r ′ − r < n
a− b = q(n− n ′) + r− r ′ ⇒ r ′ − r = q(n− n ′) + (b− a)
enta˜o n|(r ′ − r) o que e´ absurdo .⇐ . Se a e b possuem o mesmo resto enta˜o a = qn + r e b = q ′n + r, logo
a− b = (q− q ′)n de onde segue que n|a− b daı´ a ≡ b mod n.
Classe residual mo´dulo n
Vimos que a congrueˆncia mo´dulo n e´ uma relac¸a˜o de equivaleˆncia em Z, vamos
ver agora qual a classe de um inteiro a na congrueˆncia mo´dulo n
a = {x ∈ Z |x ≡ a mod n} = {x ∈ Z | n|(x− a)}
logo e´ o conjunto dos elementos x de Z tais que x e a deixam o mesmo resto na
divisa˜o por n.
b Propriedade 3. Seja n ≥ 2. Para cada a ∈ Z existe um u´nico r ∈ Z com
0 ≤ r ≤ n − 1 tal que a = r, logo com a relac¸a˜o de equivaleˆncia mo´dulo n temos
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 5
n classes residuais distintas k com k ∈ [0, n− 1]N
Z =
n−1⋃
k=0
k.
ê Demonstrac¸a˜o. Dado a ∈ Z, pela divisa˜o euclidiana por n temos um u´nico
r ∈ Z com 0 ≤ r ≤ n− 1 e q ∈ Z tal que
a = qn+ r, a− r = qn, n|a− r, a ≡ r mod n, a = r
logo temos a existeˆncia, vamos mostrar agora a unicidade, sendo r e s inteiros tais
que r = s ambos no intervalo [0, n − 1]N o ma´ximo da diferenc¸a possı´vel entre r e
s e´ n − 1 (se s = 0 e r = n − 1) e o mı´nimo e´ −(n + 1) (se r = 0 e s = n − 1) logo
−n− 1 ≤ r− s ≤ n− 1 e como temos que r = s temos que n|(r− s) pore´m no intervalo
de valores que r− s assume apenas 0 e´ divisı´vel por n logo r− s = 0, r = s.
$ Corola´rio 1. Se r e´ o resto da divisa˜o euclidiana de a por n enta˜o a ≡ r
mod n , e r e´ o menor valor natural que satisfaz essa propriedade.
m Definic¸a˜o 2 (Conjunto das classes residuais mo´dulo n). O conjunto quociente
de Z pela congrueˆncia mo´dulo n e´ representado por Zn e e´ chamado de conjunto
das classes residuais mo´dulo n
Zn = {k, k ∈ In−1}.
m Definic¸a˜o 3 (Sistema completo de resı´duos mo´dulo m). Um conjunto A ⊂ Z
e´ dito ser um sistema completo de resı´duos mo´dulo m, quando o resto dos seus
elementos na divisa˜o por n sa˜o os nu´meros [0, n− 1]N e |A| = n.
b Propriedade 4. Dados n nu´meros inteiros consecutivos existe apenas um
entre eles que e´ divisı´vel por n .
ê Demonstrac¸a˜o.
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 6
Unicidade
Dados n nu´meros consecutivos {y + 1, ..., y + n} a distaˆncia ma´xima entre eles e´
n− 1 que acontece quando tomamos os nu´meros extremos y+ n e y+ 1
y+ n− y− 1 = n− 1.
Suponha por absurdo que existem 2 dois nu´meros y1 e y2 nesse conjunto que
sejam mu´ltiplos de n com y2 > y1 , existe p natural tal que y2 = y1 + p, onde
0 < p < n, pelo fato de ambos serem mu´ltiplos de n, existem t1, t2 ∈ Z tais que
y2 = n.t2
y1 = n.t1
daı´ n.t2 = nt1 + p ⇒ n(t2 − t1) = p portanto n|p o que e´ absurdo pois na˜o existe
nu´mero entre 0 e n que seja mu´ltiplo de n.
Existeˆncia.
Temos y + 1 = nq + r onde 0 ≤ r < n, portanto existe p ∈ N tal que p < n e
r+ p = n e daı´ y+ 1+ p = nq+ r+ p = nq+ n = n(q+ 1) < y+ 1+ n,
y+ 1 ≤ y+ 1+ p ≤ y+ n
o nu´mero y+ 1+ p pertence ao conjunto {y+ 1, ..., y+ n} e e´ divisı´vel por n.
1.2 Propriedades ba´sicas de congrueˆncia
b Propriedade 5 (Soma). Se a ≡ b mod n e c ≡ d mod n enta˜o a+c ≡ b+d
mod n.
ê Demonstrac¸a˜o. a−b = qn, c−d = q ′.n logo a−b+c−d = (a+c)−(b+d) =
(q+ q ′)n logo a+ c ≡ b+ d mod n.
b Propriedade 6 (Produto por constante). Se a ≡ b mod n enta˜o a.c ≡ b.c
mod n onde c ∈ Z.
ê Demonstrac¸a˜o. Vale a − b = q.n daı´ ca − cb = cqn implicando a.c ≡ b.c
mod n.
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 7
$ Corola´rio 2. Se a ≡ b mod n e c ≡ d mod n enta˜o t ′a + tc ≡ t ′b + td
mod n onde t, t ′ sa˜o inteiros , pois t ′a ≡ t ′b mod n e tc ≡ td mod n, aplicando
propriedade de soma segue o resultado, em especial temos que
a− c ≡ b− d mod n.
$ Corola´rio 3 (Produto de congrueˆncias). Se a ≡ b mod n e c ≡ d mod n
enta˜o a.c ≡ b.d mod n. Vale a.c ≡ b.c mod n e b.c ≡ b.d mod n logo por
transitividade a.c ≡ b.d mod n.
b Propriedade 7 (Somato´rio de congrueˆncias). Se ak = bk mod n ∀ k ∈ In
enta˜o
n∑
k=1
ak =
n∑
k=1
bk mod n.
b Propriedade 8 (Produto´rio de congrueˆncias). Se ak = bk mod n ∀ k ∈ In
enta˜o
n∏
k=1
ak =
n∏
k=1
bk mod n.
ê Demonstrac¸a˜o. Por induc¸a˜o sobre n.
$ Corola´rio 4. Se a = b mod m enta˜o an = bn mod m pois n∏
k=1
a =
n∏
k=1
b
mod m.
b Propriedade 9. Se a+ c ≡ b+ c mod n enta˜o a ≡ b mod n
ê Demonstrac¸a˜o. Pois a+ c− b− c = a− b = q.n.
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 8
b Propriedade 10. Se at ≡ bt mod n enta˜o a ≡ b mod n
mdc(t, n)
.
ê Demonstrac¸a˜o. Vale t(a − b) = q.n podemos dividir em ambos lados por
mdc(t, n) daı´
t
mc(t, n)
(a− b) = q.
n
mdc(t, n)
como n
mdc(t, n)
6 | t
mc(t, n)
enta˜o n
mdc(t, n)
|(a− b) de onde segue o resultado.
$ Corola´rio 5. Se mdc(t, n) = 1 enta˜o at ≡ bt mod n implica a ≡ b mod n.
$ Corola´rio 6. Seja mdc(t, n) = 1 . at ≡ bt mod n ⇔ a ≡ b mod n. A parte
⇒) vem do corola´rio anterior e ⇐) ja´ provamos.
Z Exemplo 1. Se mdc(t, n) 6= 1 e at ≡ bt mod n podemos na˜o ter a ≡ b
mod n.
Como e´ o caso de 4.3 ≡ 2.3 mod 3 onde t = 3 = n, mdc(t, n) = 3 e na˜o vale
4 ≡ 2 mod 3 pois 3 6 |(4− 2) = 2.
b Propriedade 11. Se a ≡ b mod m e n|m enta˜o a ≡ b mod n.
ê Demonstrac¸a˜o. a − b = q.m e m = t.n daı´ a − b = q.t.n que implica a ≡ b
mod n.
b Propriedade 12 (Uma relac¸a˜o com mdc). Se a ≡ b mod m enta˜o mdc(a,m) =
mdc(b,m).
ê Demonstrac¸a˜o. Vale que a− b = qm, daı´ a = b+ q.m
mdc(a,m) = mdc(b+ q.m,m) = mdc(b,m).
CAPI´TULO 1. CONGRUEˆNCIA EANE´IS ZN. 9
b Propriedade 13 (Uma relac¸a˜o com mmc). Se a ≡ b mod mk ∀ k ∈ In enta˜o
a ≡ b mod mmc(mk)n1 .
ê Demonstrac¸a˜o. Vale a − b = qk.mk, a − b e´ mu´ltiplo de cada mk, logo o
mı´nimo mu´ltiplo comum deve dividir ele, enta˜o mmc(mk)n1 |a− b implicando
a ≡ b mod mmc(mk)n1 .
b Propriedade 14. Se a ≡ b (mod m)
enta˜o
f(a) ≡ f(b) (mod m)
para qualquer polinoˆmio f de coeficientes inteiros.
ê Demonstrac¸a˜o. Seja
f(x) =
n∑
k=0
akx
k
com ak inteiro para todo k natural.
Se a ≡ b (mod m) enta˜o ak ≡ bk (mod m) para todo k natural e ainda se para
todo k natural ak e´ inteiro, enta˜o akak ≡ akbk (mod m), aplicamos a soma em ambos
lados com k variando de 0 ate´ n, daı´ segue
n∑
k=0
aka
k ≡
n∑
k=0
akb
k (mod m)
logo
f(a) ≡ f(b) (mod m)
pois
f(a) =
n∑
k=0
aka
k, f(b) =
n∑
k=0
akb
k.
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 10
Z Exemplo 2. Calcular o valor de x tal que
n∑
k=1
k! ≡ x mod 10
com n ≥ 5.
n∑
k=1
k! = 1+ 2+ 6+ 24+
n∑
k=5
k! ≡ 3 mod 10.
b Propriedade 15. Sejam m,n tais que mdc(m,n) = 1 . Se a ≡ b mod m e
a ≡ b mod n enta˜o a ≡ b mod m.n.
ê Demonstrac¸a˜o. Se mdc(m,n) = 1 enta˜o existem x0, y0 ∈ Z tais que
mx0 + ny0 = 1
multiplicando por a− b segue
mx0 (a− b)︸ ︷︷ ︸
t1n
+ny0 (a− b)︸ ︷︷ ︸
t2m
= (a− b)
isso implica que m.n|(a− b).
b Propriedade 16. Duas pessoas X e Y tem idades x e y, com x > y, existe
idade em que a pessoa X tera´ u vezes a idade de Y ⇔ x ≡ y mod u− 1.
ê Demonstrac¸a˜o.
Z Exemplo 3. Duas pessoas X e Y tem idades x e y, com x > y, queremos
saber se existe alguma idade em que a pessoa X tera´ u vezes a idade de y e se
sim, qual e´ essa idade.
⇒). Supondo que exista uma idade em que a pessoa X tem u vezes a idade de
Y enta˜o, existe p natural tal que
u(y+ p) = x+ p⇒ uy− x = p(1− u)⇒ p = x− uy
u− 1
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 11
vale que x + p, y + p > 0 pois u > 0 por hipo´tese, agora x + p e y + p devem ser
inteiros
x+ p = x+
x− uy
u− 1
=
xu− x+ x− uy
u− 1
=
xu− uy
u− 1
=
u(x− y)
u− 1
da mesma maneira
y+ p = y+
x− uy
u− 1
=
yu− y+ x− uy
u− 1
=
x− y
u− 1
portanto u − 1|(x − y), o fato de y + p ser inteiro, implica que p e´ inteiro pois
y + p = n ∈ Z ⇒ p = n − y ∈ Z enta˜o se o problema e´ solu´vel vale que x ≡ y
mod u− 1.
⇐). Se vale x ≡ y mod u− 1 enta˜o o problema e´ solu´vel, pois existe t > 0 ∈ Z
tal que x− y = t(u− 1), tomamos p = t− y daı´
u(y+ p) = ut = u
(x− y)
u− 1
e
x+p = x−y+t = x−y+
(x− y)
u− 1
=
ux− uy− x+ y(x− y)
u− 1
=
u(x− y)
u− 1
= u(y+p)
enta˜o temos a soluc¸a˜o do problema.
1.3 Pequeno teorema de Fermat
F Teorema 1 (Pequeno Teorema de Fermat). Sejam, p um nu´mero primo e a
um nu´mero inteiro. Enta˜o,
ap ≡ a mod p.
ê Demonstrac¸a˜o. Vamos demonstrar primeiro para a natural por induc¸a˜o,
para a = 0 temos
0p = 0 ≡ 0 mod p.
Considerando agora va´lido para a
ap ≡ a mod p
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 12
, vamos demonstrar para a+ 1 temos
(a+ 1)p =
p∑
k=0
(
p
k
)
ak =
(
p
0
)
a0 +
p−1∑
k=1
(
p
k
)
ak +
(
p
p
)
ap ≡ 1+ ap mod p
onde abrimos o limite inferior e superior do somato´rio e usamos que P|
(
p
k
)
para
1 ≤ k ≤ p− 1 usando a hipo´tese temos
(a+ 1)p ≡ 1+ ap ≡ 1+ a mod p
logo
(a+ 1)p ≡ 1+ a mod p .
Agora se a e´ um inteiro negativo e p primo ı´mpar, temos a < 0, −a > 0, temos
(−a)p = −ap ≡ −a mod p
que e´ equivalente a
ap ≡ a mod p
, agora se a e´ inteiro negativo e p = 2 o u´nico primo par, temos a ≡ 0 mod 2 ou
a ≡ 1 mod 2, no primeiro caso a2 ≡ 0 ≡ amod p, no segundo a2 ≡ 1 ≡ a mod p em
ambos temos
a2 ≡ a mod 2
logo a demonstrac¸a˜o esta´ completa.
Z Exemplo 4. Mostre que 42|a7 − a. Pelo pequeno teorema de fermat temos
que 7|a7 − a, temos tambe´m que 2|a7 − a, falta mostrar que 3|a7 − a, mas a7 − a =
a(a6 − 1) = a(a3 − 1)(a3 + 1) = a(a− 1)(a+ 1)(a2 + a+ 1)(a2 − a+ 1) como temos
3 consecutivos, enta˜o seu produto e´ divisı´vel por 6 .
b Propriedade 17. Seja p primo. Se ap ≡ bp mod p enta˜o ap ≡ bp mod p2.
ê Demonstrac¸a˜o. Pelo pequeno teorema de fermat temos que ap ≡ a mod p
, bp ≡ b mod p e da hipo´tese ap ≡ bp mod p logo a ≡ b mod p ⇒ ak ≡ bk
mod p ∀ k daı´
bp − ap = (b− a)
p−1∑
k=0
akbp−1−k
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 13
p−1∑
k=0
akbp−1−k ≡
p−1∑
k=0
akap−1−k ≡ pap−1 ≡ 0 mod p
daı´ segue que p|(a− b) e p|
p−1∑
k=0
akbp−1−k logo p2|(bp − ap).
Logo ap ≡ bp mod p2.
b Propriedade 18. Se mdc(a, p) = 1 enta˜o
ap−1 ≡ 1 mod p
com p primo.
ê Demonstrac¸a˜o.
Se mdc(a, p) = 1 enta˜o existem x0, y0 ∈ Z tais que
ax0 + py0 = 1
olhando mod p tem-se
ax0 ≡ 1.
Do pequeno teorema de Fermat temos que
ap ≡ a mod p
multiplicando por x0 em ambos lados segue
ap−1ax0 ≡ ax0 mod p,
isto e´,
ap−1 ≡ 1 mod p.
Z Exemplo 5. Calcule o resto da divisa˜o de 1458333 por 11. Aplicaremos
congrueˆncia, primeiro verificamos que 1458 = 11.132 + 6 daı´ 1458 ≡ 6 mod 11 o
que implica
1458333 ≡ 6333 mod 11
agora aplicamos o pequeno teorema de Fermat de onde sabemos que 610 ≡ 1
mod 11, pois 11 e´ primo e mdc(6, 11) = 1, escrevemos 333 = 330 + 3 = 10.33 + 3
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 14
logo
6333 ≡ (610)33.63 = 36.6 mod 11
pore´m 36 ≡ 3 mod 11 e daı´
3.6 ≡ 18 ≡ 7 mod 11
e concluı´mos que 1458333 ≡ 7 mod 11 e por isso deixa resto 7 na divisa˜o por 11.
Z Exemplo 6. Calcule o resto da divisa˜o de 7158 por 13 .
Usamos que mdc(7, 13) = 1, podemos usar que
ap−1 ≡ 1 mod p
com p = 13 e a = 7, logo
712 ≡ 1 mod 13
158 = 12.13+ 2
logo
7158 ≡ ( 712︸︷︷︸
≡1
)13.72 = 49 = 3.13+ 10 ≡ 10 mod 13,
logo o resto da divisa˜o e´ 13 .
Z Exemplo 7. Descobrir N 6= 0 um nu´mero de treˆs dı´gitos tal que N2 =
N+ b.103, sendo que N e´ um nu´mero par .
Tomamos N = a2a1a0 = a2102 + a1.10+ a0 logo
(a2102 + a1.10+ a0)2 = a2102 + a1.10+ a0 + b.103
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 15
tomando a congrueˆncia mod 10, tem-se
a20 ≡ a0 mod 10
com a0 par podemos verificar que a0 = 0 ou a0 = 6, se a0 = 0 podemos
concluir tomando congrueˆncias mod 102 e mod 103 que a1 = a2 = 0 logo N = 0
o que na˜o queremos. Enta˜o a0 = 6, tomando congrueˆncia mod 102 segue
N2 ≡ (a1.10+ 6)2 = a1.10+ 6 mod 102
daı´ expandindo o termo ao quadrado e anulando termos mu´ltiplos de 102 segue
2.6.a1.10+ 62 ≡ 2a1.10+ 62 ≡ a1.10+ 6 mod 102 ⇒ a1.10 ≡ −30 ≡ 70 mod 102
o que implica a1 = 7 . Agora analisando mod 103 segue
N2 ≡ (a2.102 + 76)2 = a2102 + 76 ≡
expandindo o quadrado e usando mod 103, tem-se
≡ 2a2.102. 76︸︷︷︸
70+6
+762 ≡ 6.2︸︷︷︸
10+2
a2.102 + 762 ≡ 2.a2.102 + 762 ≡ a2102 + 76⇒
a2102 ≡ 76− 762 = −5700 ≡ −700 ≡ 300 mod 102
por isso a2 = 3 e temos portanto que N = 376 , seu quadrado e´ N2 = 141 376.
1.4 Ane´is zn.
m Definic¸a˜o 4 (Adic¸a˜o e multiplicac¸a˜o em Zn). Sejam n ≥ 2, a, b ∈ Z, definimos
a adic¸a˜o + como a operac¸a˜o que faz
a+ b = a+ b
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 16
e a multiplicac¸a˜o . como
a.b = a.b.
Caso fique claro que estamos operando em Zn algumas vezes iremos omitir a
barra sobre o elemento b, escrevendo apenas b.
b Propriedade 19. A adic¸a˜o e multiplicac¸a˜o na˜o dependem dos representantes
das classes residuais.
ê Demonstrac¸a˜o. Se a ≡ a ′ mod n e b ≡ b ′ mod n enta˜o
a+ b ≡ a ′ + b ′ mod n⇔ a+ b = a ′ + b ′ ⇔ a+ b = a+ b = a ′ + b ′ = a ′ + b ′.
O mesmo para o produto.
Simbolizaremos a estrutura (Zn,+, .), isto e´, o conjunto Zn munido das operac¸o˜es
definidas acima apenas como Zn. Denotaremos Tal conjunto por Zn ou zn .
b Propriedade 20. Zn e´ um anel comutativo com unidade.
ê Demonstrac¸a˜o. Propriedades da adic¸a˜o
• Existe elemento neutro 0, tal que 0+m = m pois 0+m = 0+m = m.
• Existeˆncia do sime´trico. Para a existe −atal que a + −a = 0. Se se a ≤ n
enta˜o existe t ∈ N tal que a + t = n e daı´ a+ t = 0 = a + t, portanto −a = t,
se a > n , a e´ representado por b onde b < n e aplicamos o mesmo processo
anterior.
• Comutatividade a+ b = a+ b = b+ a = b+ a.
• Associatividade
(a+ b) + c = (a+ b) + c = a+ (b+ c) = a+ (b+ c) = a+ (b+ c).
Temos com isso um grupo abeliano (Zn,+). Vejamos agora as propriedades da
multiplicac¸a˜o
• Existe elemento neutro 1, tal que 1.m = m pois 1.m = 1.m = m.
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 17
• Comutatividade a.b = a.b = b.a = b.a.
• Associatividade
(a.b).c = (a.b).c = a.(b.c) = a.(b.c) = a.(b.c).
Agora a propriedade que relaciona a adic¸a˜o e multiplicac¸a˜o, a distributividade.
•
(a+ b)c = (a+ b)c = ac+ bc = ac+ bc = a.c+ b.c
b Propriedade 21. Um elemento a ∈ Zn e´ invertı´vel ⇔ mdc(a, n) = 1.
ê Demonstrac¸a˜o. ⇒). Se a ∈ Zn e´ invertı´vel enta˜o existe b ∈ Zn tal que ab = 1,
daı´ a.b ≡ 1 mod n⇒ n|ab− 1⇒ tn = ab− 1 para algum t ∈ Z, (−t)n+ ab = 1 daı´
mdc(a, n) = 1.⇐). Se mdc(a, n) = 1, enta˜o existem x, y ∈ Z tais que ax + ny = 1, olhando em
zn, ax = 1 portanto a e´ invertı´vel.
b Propriedade 22. m gera Zn ⇔ m e´ invertı´vel em Zn.
ê Demonstrac¸a˜o.⇒). Se m gera Zn enta˜o existe n ∈ N tal que n.m = 1, portanto m e´ invertı´vel.⇐). Se m e´ invertı´vel enta˜o mdc(m,n) = 1 daı´ existem x0, y0 ∈ Z tais que
x0m+ y0n = 1, sendo t um elemento arbitra´rio de Z tem-se
tx0m+ ty0n = t
olhando sobre a congrueˆncia mod n tem-se (tx0)m = t, portanto m gera Zn.
b Propriedade 23. Zn e´ corpo ⇔ n e´ primo.
ê Demonstrac¸a˜o. ⇒). Vamos usar a contrapositiva de zn e´ corpo enta˜o n e´
primo que e´: se n na˜o e´ primo enta˜o zn na˜o e´ corpo. Se n na˜o e´ primo enta˜o existem
a, b ∈ Z tais que a.b = n com 1 < a, b < n, daı´
ab = n = 0
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 18
com a, b fora da classe do 0, daı´ Zn na˜o e´ domı´nio , na˜o vale a lei do corte, portanto
Zn na˜o e´ corpo.⇐). Se n e´ primo, enta˜o vale mdc(a, n) = 1 para todo 0 < a < n em Z, portanto
pela propriedade anterior a invertı´vel para todo elemento na˜o nulo, portanto Zn e´
corpo.
b Propriedade 24. O quadrado de um nu´mero inteiro tem um dos seguintes
algarismos de unidade {0, 1,4, 5, 6, 9}.
ê Demonstrac¸a˜o.
Analisamos em Z10 
a a2
0 0
1 1
2 4
3 9
4 16 = 6
5 25 = 5
6 36 = 6
7 49 = 9
8 64 = 4
9 81 = 1

Z Exemplo 8. Pelo lema de Euclides mdc(a, b) = mdc(a, b − ta), tomamos
a = k, b = n e t = 1 daı´ mdc(k, n) = mdc(k, n− k) = 1
tal fato pode ser usado em problemas para determinar inversos em um anel
Zn.
b Propriedade 25. Em zp com p primo, os u´nicos nu´meros que sa˜o inversos
de si mesmos sa˜o p− 1 e 1 .
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 19
ê Demonstrac¸a˜o. Seja x2 = 1, enta˜o (x − 1)(x + 1) = 0, o que implica x = 1 ou
x = −1 ≡ p− 1.
$ Corola´rio 7. Em Zp com p > 2 primo, o u´nico elemento que possui ordem 2
e´ p− 1, ja´ vimos que (p− 1)(p− 1) = 1 o elemento 1 possui ordem 1.
Z Exemplo 9. Quando n na˜o e´ primo, em Zn podem existir outros elementos
que na˜o sa˜o 1 e n−1 que satisfazem x2 = 1.Por exemplo em Z4k+4 vale (2k+2)2 = 1.
(2k+ 2)2 = 4k2 + 4k+ 1 = 4k (4k+ 4)︸ ︷︷ ︸
=0
+1 = 1.
1.4.1 Teorema de Wilson
b Propriedade 26 (Teorema de Wilson). p e´ primo ⇔
(p− 1)! ≡ −1 mod p.
ê Demonstrac¸a˜o. ⇒). Para p = 2 a propriedade vale, suponha enta˜o p > 2, p
primo. Tome A = {2 ≤ k ≤ p− 2, k ∈ N}, vale
p−2∏
k=1
k ≡ 1 mod p
pois para cada k ∈ A existe k ′ 6= k ∈ A tal que k.k ′ ≡ 1 mod p, daı´
p−1∏
k=1
k ≡ p− 1 ≡ −1 mod p
enta˜o
(p− 1)! ≡ −1 mod p.
⇐).
Se n = st e´ composto enta˜o vale (n − 1)! ≡ 0 mod n pois s e t aparecem como
fatores (se sa˜o distintos), caso sejam fatores iguais , inicialmente para n = 4 temos
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 20
3! = 3.2 = 6 ≡ 2 mod 4 e para s > 2 vale s2−1 > 2s logo (s2−1)! ≡ 0 mod s2, pois
s e 2s aparecem como fator, em qualquer caso se n e´ composto na˜o vale (n−1)! ≡ −1
mod n.
$ Corola´rio 8. Vale que
n∏
s=0
(s+1)p−1∏
k=sp+1
k ≡ (−1)n+1 mod p
onde p e´ primo .
n∏
s=0
p−1∏
k=1
(k+ sp) ≡
n∏
s=0
p−1∏
k=1
(k) ≡
n∏
s=0
(−1) ≡ (−1)n+1 mod p
Z Exemplo 10. Z24 possui ϕ(24) = ϕ(8.3) = ϕ(8)ϕ(3) = (23−22)(3−1) = 4.2 =
8 elementos, que sa˜o os elementos n, tais que mdc(n, 21) = 1, 0 < n < 24, n ∈ N.
Sendo
1, 5, 7, 11, 13, 17, 19, , 23
Todos elementos diferentes da identidade tem ordem 2, pois
52 = 25 = 24+1, 72 = 49 = 2.24+1, 112 = 121 = 5.24+1, 132 = 169 = 7.24+1, 172 = 289 = 12.24+1, 192 = 361 = 15.24+1
e 23 sabemos que tem ordem 2.
Z Exemplo 11. Z∗10 e´ um grupo cı´clico. Z∗10 , possui ϕ(10) = 4 elementos, eles
sa˜o 1, 3, 7, 9 pois 1.1 = 1, 3.7 = 21 ≡ 1 e 9.9 = 81 ≡ 1. O grupo e´ gerado por 3, pois
• 32 = 9.
• 33 = 9.3 = 27 ≡ 7
• 34 = 33.3 = 7.3 = 21 ≡ 1
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 21
Enta˜o < 3 >= Z∗10. O nu´mero de divisores de 4 e´ 3, que sa˜o os nu´meros 1, 2 e 4.
Enta˜o ele possui apenas um grupo na˜o trivial com 2 elementos, que e´ < 9 >, daı´
segue tambe´m que < 3 >=< 7 >= Z∗10.
Z Exemplo 12. Z∗8 na˜o e´ um grupo cı´clico. O nu´mero de elementos desse
grupo e´ ϕ(8) = 4, enta˜o ele possui subgrupos com 1, 2,4 elementos. Os elementos
do grupo sa˜o
• Triviais 1 e 7.
• Na˜o triviais: 3 pois 3.3 = 9 ≡ 1.
• 5 pois 5.5 = 25 ≡ 1.
• Logo o grupo e´ {1, 3, 5, 7} = Z∗8 na˜o e´ cı´clico.
Z Exemplo 13. Z∗17 e´ um grupo cı´clico. Tal grupo possui ϕ(17) = 16 elementos,
os divisores de 16 sa˜o 1, 2,4, 8, 16, ele possui enta˜o 5 subgrupos, com respectiva-
mente 1, 2,4, 8, 16 elementos.
• < 1 >= {1} e´ subgrupo trivial
• 3 gera o grupo pois
32 = 9
33 = 10
34 = 13
35 = 5
36 = 15
37 = 11
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 22
38 = 16
39 = 14
310 = 8
311 = 7
312 = 4
313 = 12
314 = 2
315 = 6
• Possui ϕ2(17) = 8 geradores. Que sa˜o dados por 3s com mdc(16, s) = 1.
33 = 10
35 = 5
37 = 11
39 = 14
311 = 7
313 = 12
315 = 6
• Subgrupos de ordem 8, temos que saber s tal que mdc(16, s) = 2, tais valores
sa˜o 2, 6, 10, 14
32 = 9
36 = 15
310 = 11
314 = 2.
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 23
• Subgrupos de ordem 4, temos que saber os valores de s tais que mdc(16, s) =
4, tais valores sa˜o 4 e 12 os elementos sa˜o
34 = 13
312 = 4.
• Subgrupos de ordem 2, mdc(16, s) = 8, apenas para s = 8 e o elemento e´
38 = 16.
1.5 Aplicac¸o˜es de congrueˆncias
1.6 Congrueˆncia e divisibilidade
Z Exemplo 14. o quadrado de um nu´mero deixa sempre resto 0, 1 ou 4 na
divisa˜o por 5. Analisamos pela seguinte tabela, usando congrueˆncia mod 5 .
a 0 1 2 3 4
a2 0 1 4 4 1
Z Exemplo 15. Descobrir os valores de n tais que
n∑
k=1
k! e´ quadrado perfeito .
Por inspec¸a˜o podemos observar que n = 0, 1, 3 resultam tem 0, 1, 9 e os valores
com n = 2,4 na˜o geram quadrados perfeitos, se n ≥ 5 temos
n∑
k=1
k! =
4∑
k=1
k! +
n∑
k=5
k! ≡
4∑
k=1
k! mod 5
logo para os valores n ≥ 5 na˜o temos quadrados perfeitos.
Z Exemplo 16. Mostrar que 9|9|(10n+ 3.4n+2 + 5) para todo n natural. Em Z9
CAPI´TULO 1. CONGRUEˆNCIA E ANE´IS ZN. 24
val que 10n = 1, daı´ temos
10n + 3.4n+2 + 5 = 1+ 34n + 5 = 6+ 3.4n = 3(2+ 4n)
como 2 + 4n ≡ 2 + 1 = 3 mod 3 enta˜o a expressa˜o entre parentheses e´ divisı´vel
por 3 e a expressa˜o pedida e´ divisı´vel por 9.
Z Exemplo 17. Mostrar que para n ı´mpar vale
7|(22n+1 + 3n+2).
Substituindo n = 2s+ 1 ficamos com
24s+3 + 32s+3 = (24)s.8+ 9s9.3 ≡ 2s + (−1)2s ≡ 0 mod 7
onde usamos 16 ≡ 2 mod 7, 9 ≡ 2 mod 7, 8 ≡ 1 mod 7 e 6 ≡ −1 mod 7.
	Congruência e anéis zn.
	Congruências módulo n
	Propriedades básicas de congruência
	Pequeno teorema de Fermat
	Anéis zn.
	Teorema de Wilson
	Aplicações de congruências
	Congruência e divisibilidade