Aritmética Teorema de Euler

Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina.
O material completo a ser estudado encontra-se no Capı́tulo 10 Seções 10.1 e 10.2 do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desse resumo a professora Liane Mendes
Feitosa Soares.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 1/21
Aritmética
Teorema de Euler
Carlos Humberto Soares Júnior
PROFMAT - SBM
Teorema de Euler
Neste vı́deo estudaremos um importante teorema da Teoria dos
Números: O Teorema de Euler.
Teorema (Euler)
Dados inteiros a, m primos entre si, com m > 1, temos que
aϕ(m) ≡ 1
PROFMAT - SBM
mod m.
Aritmética , , Teorema de Euler
slide 3/21
Teorema de Euler
aX ≡ 1 mod m tem solução inteira?
x0 é solução ⇔ m|(ax0 − 1) ⇔ aX + mY = 1 tem solução inteira
⇔ (a, m) = 1 (pela proposição 5.10)
Se x1 é outra solução então x0 ≡ x1 mod m.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 4/21
Teorema de Euler
Proposição
Dados inteiros a e m, em que m > 1, então a congruência aX ≡ 1
mod m tem solução inteira se, e somente se, (a, m) = 1. Além
disso, se x0 é uma soluções inteira da congruência, um inteiro x
será solução se, e somente se, x ≡ x0 mod m.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 5/21
Exemplo
Observação: Uma solução da congrência aX ≡ 1 mod m
determina e é determinada por qualquer outra solução
A congruência 7X ≡ 1 mod 8 tem x0 = 7 como solução e as
soluções inteiras são x ≡ 7 mod 8, isto é, x = 7 + 8t, t ∈ Z.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 6/21
Sistema completo de resı́duos
Definição
Um sistema completo de resı́duos módulo m é qualquer lista de
inteiros a1 , . . . , am , dois a dois incongruentes.
Equivalentemente, o resto da divisão dos ai 0 s por m são os
números 0, 1, . . . , m − 1, sem repetições e numa ordem
qualquer.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 7/21
Sistema reduzido de resı́duos
Definição
Um sistema reduzido de resı́duos módulo m é qualquer lista de
inteiros r1 , . . . , rs , tais que:
1
(ri , m) = 1, ∀i = 1, . . . , s;
2
ri 6≡ rj mod m, se i 6= j;
3
para cada n ∈ Z primo com m tem-se que n ≡ ri mod m
para algum i = 1, . . . , s.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 8/21
Sistema reduzido de resı́duos
Podemos, a partir de um sistema completo de resı́duos módulo m,
obter um sistema reduzido de resı́duos módulo m.
Basta eliminarmos os números que não são primos com m.
Exemplo
0, 1, 2, 3, 4, 5, 6, 7 forma um sistema completo de resı́duos módulo
8. Portanto 1, 3, 5, 7 é um sistema reduzido de resı́duos módulo 8.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 9/21
A função ϕ de Euler
Dois sistemas reduzidos de resı́duos módulo m têm o mesmo
número de elementos, o qual denotaremos por ϕ(m).
ϕ(m) corresponde ao número de naturais entre 0 e m − 1 que são
primos com m.
Convencionaremos ϕ(1) = 1.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 10/21
A função ϕ de Euler
Definição
A função ϕ : N → N assim definida é chamada de função fi de
Euler.
Observações:
por definição ϕ(m) ≤ m − 1;
ϕ(m) = m − 1 ⇔ m é primo.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 11/21
Exercı́cios
Exercı́cio
Se n = kd com k, d ∈ N, então
]{m ∈ N / 1 ≤ m ≤ n, (m, n) = d} = ϕ(k).
De fato,
1 ≤ m ≤ n e (m, kd) = d ⇐⇒ m = rd, com
1≤r ≤k e
(r , k) = 1
Portanto,
]{m ∈ N / 1 ≤ m ≤ n, (m, n) = d} = ]{r ∈ N / 1 ≤ r ≤
k, (r , k) = 1} = ϕ(k).
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 12/21
Exercı́cios
Exercı́cio
P
Se n ∈ N, então
ϕ(d) = n.
d|n
De fato, tome I = {1, 2, . . . , n} e para cada divisor d de n defina
Id = {m ∈ I / (m, n) = d}.
Claramente, se d 6= d 0
Id ∩ Id 0 = ∅;
∪d|n Id = I .
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 13/21
Exercı́cios
Exercı́cio
P
Se n ∈ N, então
ϕ(d) = n.
d|n
Portanto, n = ]I =
P
]Id .
d|n
Observe que os elementos de Id são os múltiplos de d da forma sd,
em que (s, dn ) = 1 e 1 ≤ s ≤ dn . Portanto
n
]Id = ϕ( ).
d
Quando d percorre os divisores de n, os números dn também o
fazem. Logo
X
X n
X
n=
]Id =
ϕ( ) =
ϕ(d).
d
d|n
PROFMAT - SBM
d|n
Aritmética , , Teorema de Euler
d|n
slide 14/21
Teorema de Euler
Teorema (Euler)
Sejam m, a ∈ N, com m > 1 e primo com a. Então
aϕ(m) ≡ 1
mod m.
Seja r1 , . . . , rϕ(m) um sistema reduzido de resı́duos módulo m.
Então ar1 , . . . , arϕ(m) também é um sistema reduzido de resı́duos
módulo m.
Logo,
aϕ(m) .r1 . · · · .rϕ(m) = (ar1 ). · · · .(arϕ(m) ) ≡ r1 . · · · .rϕ(m)
mod m
Portanto
aϕ(m) ≡ 1
PROFMAT - SBM
mod m.
Aritmética , , Teorema de Euler
slide 15/21
Calculando ϕ(m)
Propriedade
Dados m, m0 ∈ N com (m, m0 ) = 1, tem-se
ϕ(m.m0 ) = ϕ(m).ϕ(m0 ).
Propriedade
Sejam p, r ∈ N, em que p é primo. Então
1
ϕ(p r ) = p r − p r −1 = p r (1 − ).
p
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 16/21
Calculando ϕ(m)
Teorema
Seja m > 1 um número natural e m = p1α1 · · · pnαn sua
decomposição primária. Então
1
1
α1
αn
··· 1 −
ϕ(m) = p1 · · · pn 1 −
p1
pn
Podemos escrever
ϕ(m) = p1α1 −1 · · · pnαn −1 (p1 − 1) · · · (pn − 1)
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 17/21
Pequeno Teorema de Fermat
Corolário
Sejam p, a ∈ N, com p primo e (a, p) = 1. Então
ap−1 ≡ 1
mod p.
ϕ(p) = p − 1.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 18/21
Exercı́cio
Exercı́cio
Determinar o resto da divisão de 32014 por 28.
Sabemos que
3ϕ(28) ≡ 1
mod 28
Como
ϕ(28) = ϕ(22 .7) = 21 .10 .(2 − 1).(7 − 1) = 12
Temos
312 ≡ 1
PROFMAT - SBM
mod 28
Aritmética , , Teorema de Euler
slide 19/21
Exercı́cio
Exercı́cio
Determinar o resto da divisão de 32014 por 28.
Portanto
32004 = (312 )167 ≡ 1
mod 28 ⇒
⇒ 32014 = 32004 .310 ≡ 310 ≡ 25
PROFMAT - SBM
Aritmética , , Teorema de Euler
mod 28
slide 20/21
Exercı́cio
Exercı́cio
Determinar os possı́veis restos da divisão de a100 por 125.
ϕ(125) = ϕ(53 ) = 53 − 52 = 100;
Se (a, 125) = 1 então por Euler
a100 ≡ 1
mod 125
Se (a, 125) 6= 1 então 5|a ⇒ a = 5k .b e (5, b) = 1
⇒ a100 = 5100k .b 100 ≡ 5100k mod 125
Como
5100 = 53 .597 ≡ 0
mod 125 ⇒ 5100k ≡ 0
mod 125.
Portanto, os possı́veis restos são 0 e 1.
PROFMAT - SBM
Aritmética , , Teorema de Euler
slide 21/21