md aula11 2014 1

Prévia do material em texto

4.2 – A função de Euler 
 
 
Definição 4.1 
 
 Chamamos de função de Euler φ a função que atribui a cada inteiro 
positivo m o número de inteiros positivos menores ou iguais a m e relativamente 
primos com m. 
 
 
 
Teorema 4.2 
 
 O valor de φ(m) é dado por 
 






−





−





−=
r21 p
11...
p
11
p
11m φ(m) , 
 
onde r21 p..., ,p ,p são divisores primos de m , isto é, 
 
r21 a
r
a
2
a
1 p...ppm ⋅⋅⋅= . 
 
Demonstração 
 
m},{1,2,3,...A = 
 
}p de múltiplo éx |A{xA 11 ∈= 
 
}p de múltiplo éx |A{xA 22 ∈= 
. 
. 
. 
}p de múltiplo éx |A{xA rr ∈= 
 
 
 Como o valor de φ(m) é o número de elementos no complementar da 
união dos iA em A , temos: 
 
 
)A...An(An(A)φ(m) r21 UUU−= 
 
 ∑ ∑∑
≤≤ ≤<≤
−+−=
ji1 kji1
kjiji
i
i )AAn(A)An(A)n(An(A) III 
 
 )A...An(A1)(... r21r III−++ 
 
Como 
 
mn(A) = , 
i
i p
m)n(A = , 
ji
ji pp
m)An(A =I , 
kji
kji ppp
m)AAn(A =II , 
. 
. 
. 
rkji
rkji p...ppp
m)A...AAn(A =III , 
 
temos: 
 
φ(m) ∑∑∑
≤<<≤≤<≤=
−+−=
rkji1 kjirji1 ji
r
1i i ppp
m
pp
m
p
m
m +...+
rkji
r
p...ppp
m1)(− 
 
 




−+−= ∑∑∑
≤<<≤≤<≤= rkji1 kjirji1 ji
r
1i i ppp
1
pp
1
p
11m




−++
rkji
r
p...ppp
11)(... 
 
 





−





−





−=
r21 p
11...
p
11
p
11m 
 
 
 
Observação 
 
 
1}m)mdc(x,mx|INn{xφ(m) =∧<∈= 
 
Exemplo 4.6 
 
Calcular o número de inteiros positivos menores do que 2100 e 
relativamente primos com ele? 
 
Solução 
 
 Como 7532m 22 ⋅⋅⋅= , temos que 
 
 






−





−





−





−=
7
11
5
11
3
11
2
11 2100φ(2100) 
 
 
 480
7
6
5
4
3
2
2
1
 2100 =























= 
 
 
Observação 
 
Alguns valores de φ(m) para pequenos valores de m : 
 
m 1 2 3 4 5 6 7 8 9 10 
φ(m) 1 1 2 2 4 2 6 4 6 4 
 
 
 
Observação 
 
n(A(m))φ(m) = 
 
{1}A(2) = 
{1,2}A(3) = 
{1,3}A(4) = 
{1,2,3,4}A(5) = 
{1,5}A(6) = 
,6}{1,2,3,4,5A(7) = 
{1,3,5,7}A(8) = 
,8}{1,2,4,5,7A(9) = 
{1,3,7,9}A(10) = 
 
Observação 
 
Para m primo, 1mφ(m) −= . 
 
 
Exemplo 4.7 
 
Determine o número de permutações simples dos elementos 
n321 a,...,a,a,a , nas quais 1a está em primeiro lugar ou 2a está em segundo 
lugar. 
 
Solução 
 
Se 1A representa o conjunto das permutações em que 1a está em primeiro 
lugar e 2A representa o conjunto das permutações em que 2a está em segundo 
lugar, 
 
)An(A)n(A)n(A)An(A 212121 IU −+= . 
 
 2)!(n1)!(n22)!(n1)!(n1)!(n −−−=−−−+−= 
 
 
Exemplo 4.8 
 
Dentre as permutações simples dos n elementos n321 a,...,a,a,a , 
determine o número daquelas em que 1a não está em primeiro lugar, 2a não está 
em segundo lugar e nem 3a está em terceiro lugar. 
 
Solução 
 
 Definimos iA , para 1,2,3i = , como o conjunto das permutações em que 
ia , para 1,2,3i = , está no i-ésimo lugar. Devemos encontrar o número de 
elementos no complementar da união de 321 A,A,A . Temos então que 
 
)An(A)An(A)n(A)n(A)n(An!N 3121321 II ++−−−= 
 
 )AAn(A)An(A 32132 III −+ 
 
 3)!(n2)!(n31)!3(nn! −−−+−−= 
 
 
4.3 – Permutações Caóticas 
 
 
Definição 4.2 
 
 Uma permutação de n321 a,...,a,a,a é chamada de caótica quando nenhum 
ia se encontra na posição original, isto é, na i-ésima posição. 
 
 Seja iA o conjunto das permutações de n321 a,...,a,a,a ., tendo ia na i-
ésima posição. O número de permutações caóticas, nD ,é dado pelo número de 
elementos que não pertencem a nenhum dos iA , isto é, o número de elementos 
no complementar da união dos iA . Assim, temos que 
 
=nD ∑ ∑∑
≤≤ ≤<≤
−+−
ji1 kji1
kjiji
i
i )AAn(A)An(A)n(An! III 
 
 )A...An(A1)(... r21r III−++ 
 
Como existem n termos na primeira soma, 2nC termos na segunda, 
3
nC termos na 
terceira, ..., nnC termos na última, e 
 
)!1(n)n(A i −= , 
)!2(n)An(A ji −=I , 
)!3(n)AAn(A kji −=II , 
. 
. 
. 
1)A...AAn(A rkji =III , 
 
temos 
 
11)(...3)!(nC2)!(nC1)!n(nn!D n3n2nn −++−−−+−−= 
 
 
n!
n!1)(...
3!
n!
2!
n!
1!
n!
n! n−++−+−= 
 
 





−++−+−=
n!
11)(...
3!
1
2!
1
1!
11n! n 
Exemplo 4.9 
 
Determine o número de permutações caóticas de 3 objetos a , b e c . 
 
Solução 
 
 
2
3!
1
2!
1
1!
113!Dn =





−+−= 
 
 
 
Observação 
 
Configuração Inicial Permutações Caóticas 
 
 →c b a a c b b a c 
 
 
 
Exemplo 4.10 
 
Quantas permutações dos inteiros 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, têm 
exatamente 4 dos números em suas posições originais. 
 
Solução 
 
 Os 4 números que permanecem nas posições originais podem ser 
escolhidos de 410C maneiras distintas. Devemos então multiplicar esse número 
pela permutação caótica dos 6 números restantes. Assim, 
 
 
55650
6!
1
5!
1
4!
1
3!
1
2!
1
1!
116!
!6!4
!10DC 6
4
10 =





+−+−+−= .