Álgebra A - Grupos e Teorema de Euler

Prévia do material em texto

A´lgebra A – Grupos e Teorema de Euler
Elaine Pimentel
1o Semestre - 2010
Semi-grupos, mono´ides e grupos
Um semi-grupo (G, ·) e´ tal que
(i) a · (b · c) = (a · b) · c.
Um mono´ide e´ um semigrupo G que conte´m um
(ii) elemento neutro e tal que a · e = e · a = a.
Um grupo e´ um mono´ide G tal que
(iii) para todo a ∈ G, ∃a−1 tal que a−1 · a = a · a−1 = e.
Propriedades
Um grupo e´ abeliano se o produto · e´
comutativo. Para grupos em geral temos:
• a ∈ G e a · a = a ⇒ a = e.
• ∀a, b, c ∈ G tal que a · b = a · c ⇒ b = c.
• (a−1)−1 = a.
• (a · b)−1 = b−1 · a−1.
Homomosfismos
A func¸a˜o f : G −→ H e´ um homomorfismo
se
f (a · b) = f (a) · f (b) ∀a, b ∈ G.
Se f e´ injetivo, enta˜o f e´ um monomorfismo
Se f e´ sobrejetivo, enta˜o f e´ um
epimorfismo .
Se f e´ bijetivo, enta˜o f e´ um isomorfismo .
Exemplos
•O mapeamento f : Z→ Zn dado por x 7→ x e´
um epimorfismo.
• Se A e´ um grupo abeliano, enta˜o a 7→ a−1 e´
um automorfismo e o mapeamento a 7→ a2 e´
um endomorfismo.
• Se n > 1 e k ∈ N∗ enta˜o g : Zn→ Zkn dado por
x 7→ kx e´ um monomorfismo.
Subgrupos, subgrupos c´ıclicos
Seja G um grupo e H um subconjunto de G
que e´ fechado com relac¸a˜o ao produto de G.
Se H e´ um grupo, enta˜o H e´ um sub-grupo
de G.
Se G e´ um grupo, enta˜o o grupo gerado pelo
elemento a ∈ G e´ chamado um grupo c´ıclico
. Representamos H = 〈a〉.
Grupos c´ıclicos
Todo grupo c´ıclico infinito e´ isomorfo ao
grupo aditivo Z e todo grupo c´ıclico finito e´
isomorfo ao grupo aditivo Zn.
Seja G um grupo e a ∈ G. A ordem de a e´
igual ao nu´mero de elementos de 〈a〉.
Se m = e´ a ordem de a, m finito, m > 0, enta˜o
•m e´ o menor inteiro tal que am = e.
• ak = e se e somente se m|k.
• 〈a〉 = {a, a2, . . . , am−1, am = e}.
Func¸a˜o de Euler
Definic¸a˜o. Seja n um inteiro positivo. A
func¸a˜o de Euler φ(n) e´ definida como o
nu´mero de inteiros positivos na˜o excedendo
n que sa˜o relativamente primos com n.
A tabela abaixo apresenta os valores de φ(n)
para 1 ≤ n ≤ 12.
n 1 2 3 4 5 6 7 8 9 10 11 12
φ(n) 1 1 2 2 4 2 6 4 6 4 10 4
Func¸a˜o de Euler
U(n) = {a ∈ Zn : mdc(a, n) = 1}
φ(n) = #U(n).
Se p e´ primo:
φ(p) = p− 1
Se 0 ≤ a < pk e´ divis´ıvel por p, enta˜o
a = p.b onde 0 ≤ b < pk−1
Ha´ pk−1 inteiros positivos menores que pk divis´ıveis
por p =⇒ ha´ pk − pk−1 que na˜o sa˜o divis´ıveis por p. Ou
seja,
φ(pk) = pk−1(p− 1)
Func¸a˜o de Euler
Teorema. Se m,n sa˜o inteiros positivos tais
que mdc(m,n) = 1, enta˜o
φ(mn) = φ(m).φ(n)
Exemplo. φ(100) = φ(22).φ(52) = (2.1).(5.4) = 40
Pelo teorema acima temos que, se
n = p
e1
1 . . . . .p
ek
k
, enta˜o,
φ(n) = p
e1−1
1 . . . . .p
ek−1
k
(p1 − 1). . . . .(pk − 1)
Teorema de Euler
Vai ser necessa´rio, para decodificac¸a˜o de
mensagens, saber calcular a func¸a˜o de Euler.
Tambe´m vamos ter que aplicar o teorema de
Euler. O teorema de Euler e´ uma
generalizac¸a˜o do teorema de Fermat para o
caso em que o mo´dulo na˜o e´ primo:
Teorema de Euler. Se n e´ um inteiro positivo
e a e´ um inteiro tal que mdc(a, n) = 1, enta˜o
aφ(n) ≡ 1 (mod n)
Teorema de Euler
Exemplo. U(8) = {1, 3, 5, 7} e φ(8) = 4. Observe que, se a, b, c ∈ U(8),
enta˜o a.b ∈ U(8) e, se c 6= b, enta˜o
a.b 6≡ a.c (por que?)
Para ver como isso funciona, tome a = 3. Enta˜o,
3.1 ≡ 3 (mod 8)
3.3 ≡ 1 (mod 8)
3.5 ≡ 7 (mod 8)
3.7 ≡ 5 (mod 8)
Logo,
(3.1).(3.3).(3.5).(3.7) ≡ 1.3.5.7 (mod 8)
34.1.3.5.7 ≡ 1.3.5.7 (mod 8)
34 ≡ 1 (mod 8)
Teorema de Euler
Teorema de Euler Se n e´ um inteiro positivo e a um
inteiro tal que mdc(n, a) = 1, enta˜o
aφ(n) ≡ 1 (mod n)
Prova. Escrevendo U(n) = {b1, . . . , bφ(n)}, temos que:
(a.b1). . . . .(a.bφ(n)) ≡ b1. . . . .bφ(n) (mod n)
Logo,
aφ(n).b1. . . . .bφ(n) ≡ b1. . . . .bφ(n) (mod n)
Como mdc(b1. . . . .bφ(n), n) = 1, podemos cortar o termo
comum dos dois lados e portanto,
aφ(n) ≡ 1 (mod n)
Exerc´ıcios propostos - Cap´ıtulo 8
4, 6, 8, 9, 10, 18