raı́zes primitivas
Uma raiz primitiva módulo n é um
inteiro b tal que
2
{1, b, b , . . . ( mod n)} = U(n).
Teorema. Existe alguma raiz primitiva
módulo n se, e só se,
k
k
n = 2, n = 4, n = p ou n = 2p onde
p é primo ı́mpar.
Estratégia para o teorema da raiz primitiva:
(1) Se a ≥ 3, b ≥ 3, mdc(a, b) = 1 então NÃO
existe raiz primitiva mod ab.
(2) Se p é primo ı́mpar, e a é um inteiro
ı́mpar tal que a é raiz primitiva mod pk
então a é raiz primitiva mod 2pk .
(3) Se p é um número primo ı́mpar e a é
raiz primitiva módulo p2 então a é raiz
primitiva módulo pk para todo k.
((3.5)Zp2 admite r.p.:-)
Pressupondo (1),(2) e (3), basta provar
que para todo primo p (ı́mpar), o grupo
U(p) é cı́clico.
Seja α a ordem máxima de elementos
de U(p). Queremos mostrar que
α = p − 1.
Seja a ∈ U(p) com ordem α.
α−1
Considere a lista 1, a, . . . , a . A
ordem de cada um desses elementos
divide α (Lagrange). Logo, são
exatamente as raı́zes do polinômio
α
x − 1 em Zp.
Se isso não esgota U(p), existe
b ∈ U(p) fora dessa lista.
Logo, a ordem, β, de b não divide α.
Segue que a ordem de
ab, µ := mmc(α, β) > α, absurdo.
(ab)µ = aµbµ . . .
(1) Temos ϕ(n) = ϕ(a)ϕ(b).
Como a ≥ 3 e b ≥ 3, segue que
ϕ(a) e ϕ(b) são pares.
Se mdc(k, n) = 1 então vale
ϕ(n)/2
ϕ(b)/2 ϕ(a)
k
= (k
)
= 1 em Za, e
ϕ(n)/2
ϕ(a)/2 ϕ(b)
k
= (k
)
= 1 em Zb.
ϕ(n)/2
Assim, k
= 1 em Zn, e portanto
ϕ(n)
ordn k | 2 < ϕ(n).
(2) Se p é primo ı́mpar, e a é um inteiro
ı́mpar tal que a é raiz primitiva mod pk ,
então a também é raiz primitiva mod 2pk .
De fato, abrevie α = ϕ(pk ) = ordpk a.
α
Temos a = 1 ∈ Zpk . Como a é ı́mpar, temos
também aα = 1 ∈ Z2. Pelo chinês, deduz-se
aα = 1 ∈ Z2pk . Seja β = ord2pk a. Temos β|α.
Mas é claro que aβ = 1 ∈ Zpk , seguindo
k
k
α = β = ϕ(p ) = ϕ(2p ).
Logo, a é raiz primitiva mod 2pk .
(3) Se p é um número primo ı́mpar e a é
2
raiz primitiva módulo p então a é raiz
k
primitiva módulo p para todo k.
Por hipótese, p(p − 1) = ordp2 a. Logo
ap(p−1) = 1 em Zp2 e assim em Zp, vale
1 = (ap)p−1 = ap−1 (por que?).
Concluı́mos que ∃t1 ∈ Z tal que ap−1 = 1 + t1p.
Note que t1 não pode ser divisı́vel por p, senão
p−1
a
= 1 em Zp2, contrariando ordp2 a = p(p − 1).
Daı́ vem
p
ap(p−1) = (1 + t1p)p = 1 + pt1p + 2 t21p2 + · · ·
= 1 + p2 (t
+
p(·
·
·
))
,
1
{z
}
|
t2
onde p 6 | t2 .
Repetindo, obtemos
pk (p−1)
a
=1+p
k+1
tk+1, com p 6 | tk+1 .
Vamos deduzir que a é raiz primitiva
k
mod. p . Indução.
Ilustremos a passagem de k = 2
(válido por hipótese), para k = 3.
p2(p−1)
Já sabemos que a
= 1 em Zp(2+1).
2
Logo, ordp3 a | p (p − 1).
Temos também
2
p(p−1) = (ordp2 a) | (ordp3 a) | p (p−1).
2
Se ordp3 a 6= p (p − 1) segue
ordp3 a = p(p − 1). Isso acarreta
ap(p−1) − 1 divisı́vel por p3, contradição
p(p−1)
2
com a
= 1 + p t2, p 6| tk+1 .
Faça como exercı́cio a passagem indutiva geral.
Onde usou ı́mpar? E o caso Zp2 ??
Determine raiz primitiva para Z27.
Verifique se 2 é raiz primitiva módulo 625.
Ache, se possı́vel, a,p tais que a é raiz primitiva
mod p mas não o é mod p2.
Zp?2
Provar que, se a é raiz primitiva mod. p, então
a ou a + p é raiz primitiva mod. p2.
Contas semelhantes às feitas
anteriormente
p(p − 1), ou
mostram que ordp2 a =
p − 1.
Idem para ordp2(a + p). Basta ver então que
ordp2 a = p − 1 ⇒ ordp2(a + p) = p(p − 1).
p−1
p−1
p−2
(a + p)
= a + (p − 1)a
= 1 − pap−2 mod p2.
p+
p−1
2
ap−3p2 + · · ·
Note por fim que pap−2 6= 0 mod p2 pois mdc(a, p) = 1.
Teste de Primalidade
Seja n > 1, n − 1 =
e1 e2
p 1 p2 · · ·
com p1 < p2 < · · · primos.
Suponha ∃ b1, b2, . . . entre 2 e n − 1
n−1
bi
n−1
pi
tais que
= 1 6= bi , i = 1, 2, . . .
em Zn.
Teste de Primalidade
Seja n > 1, n − 1 =
e1 e2
p 1 p2 · · ·
com p1 < p2 < · · · primos.
Suponha ∃ b1, b2, . . . entre 2 e n − 1
n−1
bi
n−1
pi
tais que
= 1 6= bi , i = 1, 2, . . .
em Zn. Então n é primo.
Seja s = ordn b1.
Seja s = ordn b1. Temos s | n − 1.
Seja s = ordn b1. Temos s | n − 1. Logo
e01 e02
0
s = p1 p2 · · · , com ei ≤ ei.
Seja s = ordn b1. Temos s | n − 1. Logo
e01 e02
0
s = p1 p2 · · · , com ei ≤ ei.
n−1
pi
n−1
pi
Como 1 6= bi em Zn, segue
e1−1 e2
= p1 p2 · · · não divisı́vel por s.
Seja s = ordn b1. Temos s | n − 1. Logo
e01 e02
0
s = p1 p2 · · · , com ei ≤ ei.
n−1
pi
Como 1 6= bi em Zn, segue
e1−1 e2
n−1
p2 · · · não divisı́vel por s.
pi = p 1
0
Isso obriga e1 = e1.
Seja s = ordn b1. Temos s | n − 1. Logo
e01 e02
0
s = p1 p2 · · · , com ei ≤ ei.
n−1
pi
Como 1 6= bi em Zn, segue
e1−1 e2
n−1
p2 · · · não divisı́vel por s.
pi = p 1
0
Isso obriga e1 = e1. Temos assim que
e1
p1 divide s,
Seja s = ordn b1. Temos s | n − 1. Logo
e01 e02
0
s = p1 p2 · · · , com ei ≤ ei.
n−1
pi
Como 1 6= bi em Zn, segue
e1−1 e2
n−1
p2 · · · não divisı́vel por s.
pi = p 1
0
Isso obriga e1 = e1. Temos assim que
e1
?
p1 divide s, que divide |Zn|
Seja s = ordn b1. Temos s | n − 1. Logo
e01 e02
0
s = p1 p2 · · · , com ei ≤ ei.
n−1
pi
Como 1 6= bi em Zn, segue
e1−1 e2
n−1
p2 · · · não divisı́vel por s.
pi = p 1
0
Isso obriga e1 = e1. Temos assim que
e1
?
p1 divide s, que divide |Zn| = ϕ(n).
Seja s = ordn b1. Temos s | n − 1. Logo
e01 e02
0
s = p1 p2 · · · , com ei ≤ ei.
n−1
pi
Como 1 6= bi em Zn, segue
e1−1 e2
n−1
p2 · · · não divisı́vel por s.
pi = p 1
0
Isso obriga e1 = e1. Temos assim que
e1
?
p1 divide s, que divide |Zn| = ϕ(n).
e1 e 2
⇒ n − 1 = p1 p2 · · · | ϕ(n)
Seja s = ordn b1. Temos s | n − 1. Logo
e01 e02
0
s = p1 p2 · · · , com ei ≤ ei.
n−1
pi
Como 1 6= bi em Zn, segue
e1−1 e2
n−1
p2 · · · não divisı́vel por s.
pi = p 1
0
Isso obriga e1 = e1. Temos assim que
e1
?
p1 divide s, que divide |Zn| = ϕ(n).
e1 e 2
⇒ n − 1 = p1 p2 · · · | ϕ(n) ≤ n − 1
Seja s = ordn b1. Temos s | n − 1. Logo
e01 e02
0
s = p1 p2 · · · , com ei ≤ ei.
n−1
pi
Como 1 6= bi em Zn, segue
e1−1 e2
n−1
p2 · · · não divisı́vel por s.
pi = p 1
0
Isso obriga e1 = e1. Temos assim que
e1
?
p1 divide s, que divide |Zn| = ϕ(n).
e1 e 2
⇒ n − 1 = p1 p2 · · · | ϕ(n) ≤ n − 1 ⇒= .
Seja s = ordn b1. Temos s | n − 1. Logo
e01 e02
0
s = p1 p2 · · · , com ei ≤ ei.
n−1
pi
Como 1 6= bi em Zn, segue
e1−1 e2
n−1
p2 · · · não divisı́vel por s.
pi = p 1
0
Isso obriga e1 = e1. Temos assim que
e1
?
p1 divide s, que divide |Zn| = ϕ(n).
e1 e 2
⇒ n − 1 = p1 p2 · · · | ϕ(n) ≤ n − 1 ⇒= .
⇒ n é primo.