Aula 7 profmat - numeros primos e especiais - 06 10-17

Aula 7 do Profmat da UERJ - Números primos e números especiais - 06 10-17

1. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Aritmetica - MA14
AULA 7 - NUMEROS PRIMOS E
NUMEROS ESPECIAIS
Aline de Lima Guedes Machado
PROFMAT - IME/UERJ
Universidade do Estado do Rio de Janeiro
[email protected]
06 de Outubro 2017
1 / 27

2. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Sumario
1
Pequeno Teorema de Fermat
2
Primos de Fermat, de Mersenne e em PA
3
Numeros perfeitos
4
Decomposic~ao do Fatorial em Primos
5
A equac~aoEp(x!) =
2 / 27

3. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Sumario
1
Pequeno Teorema de Fermat
2
Primos de Fermat, de Mersenne e em PA
3
Numeros perfeitos
4
Decomposic~ao do Fatorial em Primos
5
A equac~aoEp(x!) =
3 / 27

4. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Pequeno Teorema de Fermat
Desde, pelo menos, 500 anos antes de Cristo, os chineses sabiam
que, sepe um numero primo, ent~ao,pj2
p
2:
Pierre de Fermat - seculo XVII - generalizou esse resultado.
O lema a seguir sera utilizado na demonstrac~ao do Teorema:
Lema 7.15: Sejapum numero primo. Os numeros

p
i

, onde
0<i<ps~ao todos divisveis porp.
Demonstrac~ao:
Parai= 1, o resultado e valido:

p
i

=

p
1

=
p!
1!(p1)!
=pepjp:
Para 1<i<p, temos quei!jp(p1):::(pi+ 1) por seremi
numeros consecutivos. Comop>i, (i!;p) = 1, ja que eles n~ao
possuem fatores comuns.Pelo Lema de Gauss (teorema 5.11),
ent~aoi!j(p1):::(pi+ 1) .
Pela denic~ao de numeros binomiais,

p
i

=
p(p1)(p2):::(pi+1)
i!
,
ent~aopj

p
i

, ja que
p(p1)(p2):::(pi+1)
i!
e um numero inteiro.
4 / 27

5. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Pequeno Teorema de Fermat
Pequeno Teorema de Fermat: Dado um numero primop, tem-se
quepja
p
a;8a2Z.
Demonstrac~ao:
Sep= 2,o resultado e valido:a
2
a=a(a1) e um numero par,
ja que e produto de dois numeros consecutivos.
Sepfor mpar, pode-se considerar apenas os casosa0, pois os
casos ondea<0 seriam analogos.
Induc~ao sobrea.
Base:a= 0.pj0, ok.
Hipotese: supor verdadeiro paraa, ou seja,pja
p
a
Passo de induc~ao: provar que vale paraa+ 1:pj(a+ 1)
p
(a+ 1)
De fato:
(a+1)
p
(a+1) =a
p
+

p
1

a
p1
+

p
2

a
p2
+:::+

p
p1

a+1a1
= (a
p
a) +

p
1

a
p1
+

p
2

a
p2
+:::+

p
p1

a.
Pela hipotesepdivide a primeira parcela. Pelo lema anterior,p
divide as demais parcelas. Logopdivide a soma toda.
5 / 27

6. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Pequeno Teorema de Fermat
Corolario: Sepe um numero primo e seae um numero natural
n~ao divisvel porp, ent~aopja
p1
1.
Demonstrac~ao:
Pelo Pequeno Teorema de Fermat,pja
p
a=a(a
p1
1):
Comop6 jaou (a;p) = 1;pj(a
p1
1):
OBS:Esse corolario tambem e chamado de Pequeno Teorema de
Fermat.
6 / 27

7. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Pequeno Teorema de Fermat
Exemplo: Dadon2N, mostre quen
5
en, quando escritos na base
10, possuem o mesmo algarismo da unidade, alem de quen
5
ne
sempre um numero multiplo de 30.
Demonstrac~ao:
7 / 27

8. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Pequeno Teorema de Fermat
Exemplo 2: Mostre que 5ja
12
1 sea2Ze (a;5) = 1.
Demonstrac~ao:
Exemplo 3: Mostre que 7ja
6
b
6
, seaebs~ao primos com 7.
Demonstrac~ao:
Exemplo 4: Mostre que 21ja
6
b
6
, seaebs~ao primos com 21.
Demonstrac~ao:
8 / 27

9. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Sumario
1
Pequeno Teorema de Fermat
2
Primos de Fermat, de Mersenne e em PA
3
Numeros perfeitos
4
Decomposic~ao do Fatorial em Primos
5
A equac~aoEp(x!) =
9 / 27

10. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Numeros de Fermat
A procura por numeros primos tornou-se um negocio lucrativo, uma vez
quesistemas criptogracos(conjunto de princpios e tecnicas empregadas
para tornar a escrita ininteligvel para aqueles que n~ao possam ter acesso a
tais informac~oes) mais usados na atualidade fazem uso de numeros primos
grandes.Exemplo:criptograa RSA.
OBS:A busca por numeros primos e constante e n~ao e tarefa facil.
Proposic~ao: Sejamaennumeros naturais maiores do que 1. Sea
n
+ 1 e
primo, ent~aoae par en= 2
m
, comm2N
Demonstrac~ao:
Sejaa
n
+ 1 primo, a>1 e n>1.atem que ser par, pois caso constrario,
a
n
+ 1 seria par maior que 2 e n~ao seria primo. Sen n~ao fosse pot^encia
de 2, ou seja, sentivesse outros divisores primospque n~ao o 2, teramos
n=n
0
p;n
0
2N. Da, por proposic~ao anterior (3.8), compmpar
teramos:a
n
0
+ 1j(a
n
0
)
p
+ 1 =a
n
0
p
+ 1 =a
n
+ 1 . Ou seja, encontraramos
um divisor dea
n
+ 1 diferente dele e 1, mas ele e primo.Absurdo.
10 / 27

11. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Numeros de Fermat
Numeros de Fermat:
Eles s~ao da formaFn= 2
2
n
+ 1;n= 0;1;2:::.
Fermat (1640) achava que esses numeros eram todos primos. De
fato:
F0= 3;F1= 5;F2= 17;F3= 257;F4= 65:537. Mas Euler (1732)
mostrou queF5= 4:294:967:297 = 641x6:700:417 era composto.
Primos de Fermat:
Os numeros de Fermat que s~ao primos s~ao chamados deprimos
de Fermat. Ate hoje n~ao se sabe se existem outros primos de
Fermat alem desses cinco.
OBS:No exemplo 6.18: (2
2
n
+ 1;2
2
m
+ 1) = 1, sen6=m.
Resultados como esse podem ter feito Fermat pensar
que seus numeros eram todos primos.
11 / 27

12. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Numeros de Mersenne
Outros numeros primos famosos.
Proposic~ao: Sejama>1 en>1 naturais. Sea
n
1 e primo, ent~aoa= 2 en
e primo.
Demonstrac~ao:
Suponha, por absurso,a>2. Ent~ao,a1>1 ea1ja
n
1 (proposic~ao 3.7).
Logo,a
n
1 n~ao e primo, ja quea16= 1.Absurdo. Logo a=2. Suponha,
por absurdo,nn~ao primo. Ent~ao,n=rs;r>1;s>1. Como
2
r
1j(2
r
)
s
1 = 2
rs
1 = 2
n
1, segue que 2
n
1 n~ao e primo.Absurdo.
Logone primo.
Numeros de Mersenne:
Eles s~ao da formaMp= 2
p
1, ondepe primo.
OBS:Nem todo numero de Mersenne e primo.
2
11
1 = 2047 = 23x89 n~ao e primo.
Os numeros de Mersenne obtidos que s~ao primos s~ao chamadosPrimos de
Mersenne. Novo recorde em 2016: PrimoM74:207:281com 22 bilh~oes de dgitos
- ocuparia 7000 folhas de papel!!!!!!!
12 / 27

13. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Primos em PA
Teorema de Dirichlet:
Em um PA de numeros naturais, com primeiro termo e raz~ao primos entre si,
existem innitos numeros primos.
Caso particular: Na PA 3,7,11,15,...,4n+3 existem innitos numeros primos.
Demonstrac~ao:
Todo primo mpar e da forma 4n+ 1 ou 4n+ 3.
Os numeros do tipo 4n+ 1 s~ao fechados em relac~ao a multiplicac~ao:
(4n+ 1)(4n
0
+ 1) = 4(4nn
0
+n+n
0
) + 1. Supor, por absurdo, que os primos da
forma 4n+ 3 s~ao nitos: 3<p1<p2< ::: <pk. Sejaa= 4(p1p2 pk) + 3.
an~ao e divisvel por nenhum desses primos. De fato, 3 n~ao dividea, pois 3 teria
que dividir o produto dospis, mas nenhum deles e o 3.p1n~ao dividea, poisp1
divide o produto, masp1n~ao divide 3, poisp16= 3. Logo a decomposic~ao em
fatores primos deateria que ser formada por primos da forma 4n+ 1. Mas o
produto 4n+ 1 so gera 4n
0
+ 1,absurdo, ja queae da forma 4n+ 3.
13 / 27

14. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Sumario
1
Pequeno Teorema de Fermat
2
Primos de Fermat, de Mersenne e em PA
3
Numeros perfeitos
4
Decomposic~ao do Fatorial em Primos
5
A equac~aoEp(x!) =
14 / 27

15. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Numeros perfeitos
Soma dos Divisores de um Numero
Sejannatural. Dene-seS(n) a soma de todos os seus divisores naturais.
S(1)=1.
Exemplo: Sejannatural.S(n) =n+ 1 se e somente sene um numero
primo.
Demonstrac~ao:
De fato, sene primo,nso tem como divisoresne 1. Logo, S(n)=n+1.
15 / 27

16. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Numeros perfeitos
Sendon2, temos uma formula especial para a soma dos divisores.
Soma dos divisores de um numero em func~ao da sua decomposic~ao em
fatores primos.
Sejan=p
1
1
p
2
2
:::p
r
ra decomposic~ao denem fatores primos. Ent~ao:
S(n) =
p

1
+1
1
1
p11
p

2
+1
2
1
p21
:::
p
r+1
r
1
pr1
Corolario: A func~aoS(n) e multiplicativa;
Se (m;n) = 1, ent~aoS(nm) =S(n)S(m).
Exemplos:
S(3) =
3
2
1
31
= 4
S(6) =S(2:3) =
2
2
1
21

3
2
1
31
= 12
S(18) =S(2:3
2
) =
2
2
1
21

3
3
1
31
= 39
S(28) =S(2
2
:7) =
2
3
1
21

7
2
1
71
= 56
OBS:S(18) = 396= 48 =S(3)S(6). Logo n~ao vale se (n;m)6= 1. 16 / 27

17. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Numeros perfeitos
Os numeros 6 e 28 com a propriedades de serem iguais a metade
da soma de seus divisores, tiveram o poder de fascinar os gregos
antigos, que os chamaram denumeros perfeitos.
Numero perfeito
ne um numero perfeito seS(n) = 2n.
Ate a Idade Media so conheciam os seguintes numeros perfeitos:
6, 28, 496, 8128, 33.550.336. Hoje s~ao conhecidos mais alguns.
Um fato curioso e quetodos os numeros perfeitos conhecidos
s~ao pares. N~ao se sabe se n~ao existem numeros perfeitos mpares.
17 / 27

18. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Numeros perfeitos
Caracterizac~ao de numeros perfeitos pares e numeros de Mersenne.
Teorema Euclides: Todo numero naturalnda forman= 2
p1
(2
p
1),
onde 2
p
1 e um numero primo de Mersenne e perfeito.
Demonstrac~ao:
Sejan= 2
p1
(2
p
1) e 2
p1
primo. Logo,p>1, pois caso contrario
2
1
1 = 1 n~ao seria primo. Da, n e par, pois 2
p1
e par. Como 2
p
1 e
mpar, (2
p1
;2
p
1) = 1. Ent~ao podemos usar o corolario anterior:
S(n) =S((2
p1
)(2
p
1)) =S(2
p1
)S(2
p
1) =
2
p1+1
1
21
2
p
=
2
p
1
21
2
p
= (2
p
1)22
p1
= 22
p1
(2
p
1) = 2n.ne perfeito.
Teorema Euler: Se um numero naturalne um numero perfeito, ent~ao ele
e da forman= 2
p1
(2
p
1), onde 2
p
1 e um numero primo de
Mersenne.
18 / 27

19. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Sumario
1
Pequeno Teorema de Fermat
2
Primos de Fermat, de Mersenne e em PA
3
Numeros perfeitos
4
Decomposic~ao do Fatorial em Primos
5
A equac~aoEp(x!) =
19 / 27

20. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Decomposic~ao do Fatorial em Primos
Lembrete:Seaebs~ao numeros naturais,

a
b

representa o quoci-
ente da divis~ao euclidiana deaporb. Seb>a>0, ent~ao

a
b

= 0.
Propriedade relacionada com os quocientes da divis~ao euclidiana.
"
a
b
c
#
=

a
bc

Lembrete:Dado um numero primope um numero naturalm,
Ep(m) e o expoente da maior pot^encia depque dividemou seja, o
expoente da pot^encia depque aparece na fatorac~ao dem.
Exemplo:E2(12) =E2(2
2
:3) = 2.
Note queEp(m:n) =Ep(m) +Ep(n):
Exemplo:Ep(6:12) = 3 =Ep(6) +Ep(12)
20 / 27

21. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Decomposic~ao do Fatorial em Primos
Teorema de Legendre:
Sejamnum numero natural epum numero primo. Ent~ao:
Ep(n!) =

n
p

+

n
p
2

+

n
p
3

+:::
Demonstrac~ao:
Note que a soma acima e nita, pois a partir de um certor,p
i
>n8ir:
Portanto,
h
n
p
i
i
= 0 seir:Induc~ao sobre n.
Basen= 1 verdadeira:Ep(1) =
h
1
p
i
= 0;ja quep
0
= 1.
Supor valida para qualquer naturalm, comm<n:
Sabemos que os multiplos depentre 1 ens~ao:p;2p;3p; :::;
h
n
p
i
p. Logo, os
unicos termos den! que contem o fatorps~ao esses acima. Da:
Ep(n!) =Ep(p;2p;3p; :::;
h
n
p
i
p) =Ep(
h
n
p
i
!p
h
n
p
i
) =Ep(
h
n
p
i
!) +
h
n
p
i
. Pela
hipotese de induc~ao, ja que
h
n
p
i
!<n:Ep(
h
n
p
i
!) = [
h
n
p
i
p
] + [
h
n
p
i
p
2] +:::e o
resultado segue da proposic~ao anterior.
21 / 27

22. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Decomposic~ao do Fatorial em Primos
Na pratica, para calcularEp(n!), basta dividirnporp;p
2
;p
3
; :::ate
p
i
<ne somar os quocientes dessas divis~oes.
Exemplo 1:E2(10!) =?
E2(10!) = 5 (quociente da divis~ao de 10 por 2)+2(quociente da
divis~ao de 10 por 2
2
= 4)+1(quociente da divis~ao de 10 por
2
3
= 8)=8
Exemplo 2:Determinar a decomposic~ao de 10! em fatores primos.
EncontrarEp(10!) para todo primop10:
E2(10!) = 8
E3(10!) = 3 + 1 = 4
E5(10!) = 2
E7(10!) = 1
Da: 10! = 2
8
3
4
5
2
7
1
. 10! termina em dois zeros!
22 / 27

23. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Decomposic~ao do Fatorial em Primos
O proximo resultado relacionaraEp(n!) com a representac~ao p-adica
den, ou seja, a representac~ao relativa a basepden
Teorema:
Sejamp;n2N,pprimo. Sen=nrp
r
+nr1p
r1
+:::+n1p+n0
e a representac~ao p-adica den, ent~ao:
Ep(n!) =
n(n0+n1+n2+:::+nr1+nr)
p1
Exemplo:E2(10!).
10 = (1010)2
E2(10!) =
10(0+1+0+1)
21
= 8
23 / 27

24. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
Sumario
1
Pequeno Teorema de Fermat
2
Primos de Fermat, de Mersenne e em PA
3
Numeros perfeitos
4
Decomposic~ao do Fatorial em Primos
5
A equac~aoEp(x!) =
24 / 27

25. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
A equac~aoEp(x!) =
Vamos determinar quando a equac~aoEp(x!) =tem soluc~ao em
x2Ne, nesse caso, determinar todas as soluc~oes.
e a maior quantidade do fatorpexistente emx!.
Os unicos termos dex! que contem o fatorps~ao os multiplos
depmenores ou iguais a x.
Ent~ao resolverEp(x!) =e o mesmo que resolver
Ep((mp)!) =, ondex=mp+r;0r<p.
Se existir soluc~ao deEp(x!) =, ent~ao as soluc~oes ser~ao da
forma:x=mp;mp+ 1;mp+ 2; :::;mp+ (p1);m2N:
25 / 27

26. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
A equac~aoEp(x!) =
Algoritmo para resolver a equac~aoEp(x!) =:
1
Escreverem expans~ao na basep, ou seja, escrever a
expans~ao p-adica de;
2
Vericar sese escreve exatamente como:
=p
s
+p
s1
+:::+p
1
+p
0
ou6=p
s
+p
s1
+:::+p
1
.
Se isso ocorrer, a equac~aoEp(x!) =n~ao tem soluc~ao.
Se n~ao ocorrer o que foi citado acima, partir para a
busca da soluc~ao.
3
Calcularms=
h
(p1)
p
s+1
1
i
. Semsfor igual zero, calcular os
proximosms1;ms2ate queml6= 0, ondeml=
h
(p1)
p
l+1
1
i
;
4
Calcularm
0
tal quem
0
=mmlp
l
;
5
Calcular
0
tal que
0
=ml(p
l
+p
l1
+:::+p
1
+p
0
);
6
ResolverEp((m
0
p)!) =
0
, ondem
0
<me

0
< , usando as etapas do algoritmo novamente.
26 / 27

27. Pequeno Teorema de Fermat
Primos de Fermat, de Mersenne e em PA
Numeros perfeitos
Decomposic~ao do Fatorial em Primos
A equac~aoEp(x!) =
A equac~aoEp(x!) =
ResolverE7(x!) = 700
N~ao tem soluc~ao pois 400 = 7
3
+ 7
2
+ 7
1
+ 7
0
.
ResolverE7(x!) = 855
Esse e um caso em que, apesar de6=p
s
+p
s1
+:::+p
1
+p
0
ou , a equac~ao
Ep(x) =n~ao tem soluc~ao. Esse e so o primeiro passo do algoritmo. Ao passar
novamente por essa linha do algoritmo e ela falhar, a equac~ao n~ao tem soluc~ao.
ResolverE5(x!) = 148
Soluc~oes:x= 600;601;602;603;604.
Vericando:E5(600!) =

600
5

+

600
25

+

600
125

+

600
625

=
=120 + 24 + 4 + 0 = 148 =E5(601!) =
=E5(602!) =E5(603!) =E5(604!)
JaE5(605!) =
h
605!
5
i
+

605
25

+

605
125

+

605
625

=
=121 + 24 + 4 + 0 = 149
27 / 27