Profmat UEM PR - Roberto Luiz Spenthof

RESUMO DO CONTEDO DA 2 PROVA MA14 ARITMTICA I

UNIDADE 12 Teorema Fundamental da Aritmtica

Proposio 1. Sejam a, b,
*
p , com p primo. Se | p ab , ento | p a ou | p b .
Corolrio. Se
1
, , ,
n
p p p so nmeros primos e, se
1
|
n
p p p , ento
i
p p = para algum
1, , i n = .
Teorema 1 (Teorema Fundamental da Aritmtica). Todo nmero natural maior do que 1 ou
primo ou se escreve de modo nico (a menos da ordem dos fatores) como um produto de
nmeros primos.
Teorema 1. Dado um nmero natural 1 n , existem primos
1 r
p p < < e
*
1
, ,
r
,
univocamente determinados, tais que
1
1
r
r
n p p

= .
Proposio 2. Seja
1
1
r
r
n p p

= um nmero natural escrito na forma acima. Se ' n um
divisor de n, ento
1
1
'
r
r
n p p

= , onde 0
i i
_ _ , para 1, , i r = .
Teorema 2. Sejam
1
1
n
n
a p p

= e
1
1
n
n
b p p

= . Pondo min ,
i i i
= ,
max ,
i i i
= , 1, , i n = , tem-se que ( )
1
1
,
n
n
a b p p

= e
1
1
,
n
n
a b p p

l
=
l
.
Teorema 3. Existem infinitos nmeros primos.
Lema 1. Se um nmero natural 1 n no divisvel por nenhum nmero primo p tal que
2
p n _ , ento ele primo.

UNIDADE 13 Pequeno Teorema de Fermat

Lema 1. Seja p um nmero primo. Os nmeros
p
i
1

( )
, onde 0 i p < < , so todos divisveis por
p.
Teorema 1 (Pequeno Teorema de Fermat). Dado um nmero primo p, tem-se que p divide o
nmero
p
a a , para todo a .
Corolrio. Se p um nmero primo e se a um nmero natural no divisvel por p, ento p
divide
1
1
p
a

.

UNIDADE 14 Primos de Fermat e de Mersenne

Proposio 1. Sejam a e n nmeros naturais maiores do que 1. Se 1
n
a primo, ento a
par e 2
m
n = , com m .
Definio. Os nmeros de Fermat so os nmeros da forma
2
2 1
n
n
F = , com n .
Corolrio.
( ) , 1
n m
F F = , se n m = .
Proposio 2. Sejam a e n nmeros naturais maiores do que 1. Se 1
n
a primo, ento
2 a = e n primo.
Definio. Os nmeros de Mersenne so os nmeros da forma 2 1
p
p
M = , onde p um
nmero primo.
Profmat UEM PR - Roberto Luiz Spenthof
Corolrio. ( ) , 1
p q
M M = , se p e q so nmeros primos distintos.
Teorema (de Dirichlet). Em uma PA de nmeros naturais, com primeiro termo e razo
primos entre si, existem infinitos nmeros primos.
Proposio 3. Na progresso aritmtica 3, 7, 11, 15, , 3 4 , n existem infinitos nmeros
primos.
Proposio 4. Na progresso aritmtica 1, 5, 9, 13, 17, , 4 1, n existem infinitos nmeros
primos.

UNIDADE 15 Nmeros Perfeitos

Definio. Seja n um nmero natural maior do que 1. Denotamos por ( ) S n a soma de todos
os divisores de n.
Proposio 1. Seja
1
1
r
r
n p p

= , onde
1
, ,
r
p p so nmeros primos e
*
1
, ,
r
.
Ento,

( )
1
1 1
1
1
1 1
1 1
r
r
r
p p
S n
p p


=


Corolrio. A funo ( ) S n multiplicativa; isto , se ( ) , 1 n m = , ento
( ) ( ) ( ) S n m S n S m = .
Lema 1. Seja
*
n . Tem-se que
( ) 1 S n n = se, e somente se, n um nmero primo.
Teorema 1 (Euclides-Euler). Um nmero natural n um nmero perfeito par se, e somente
se,
( )
1
2 2 1
p p
n

= , onde 2 1
p
um primo de Mersenne.

UNIDADE 16 Decomposio do Fatorial em Fatores Primos

Definio. O smbolo
b
a
l
l
l
l
significa o quociente da diviso de b por a, na diviso euclidiana.
Proposio 1. Sejam a e
*
, b c . Temos que
a
b a
c bc
l l
l l
l l l
l
l l =
l l
l
l
l
l
.
Teorema 1 (Legendre). Sejam n um nmero natural e p um nmero primo. Ento,

( )
2 3
!
p
n n n
E n
p
p p
l l l
l l l =
l l l
l l l

onde ( ) !
p
E n o expoente de p na decomposio em fatores primos de ! n . Para calcular
( ) !
p
E n , usamos o seguinte algoritmo:

1 1
1 2 2
1 s s s
n pq r
q pq r
q pq r

=
=
=

Como
1 2
q q , segue que, para algum s, tem-se que
s
q p < . Portanto, segue-se que
Profmat UEM PR - Roberto Luiz Spenthof
( )
1 2
!
p s
E n q q q = .
Lema 2. Sejam
1
, , ,
m
a a b nmeros naturais, com 0 b = . Tem-se que

1 1 m m
a a a a
b b b
l l l

l l l
_
l l l
l l l

.
Corolrio. Se
1
, ,
m
a a so nmeros naturais, ento natural o nmero
( )
1
1
!
! !
m
m
a a
a a

.
Teorema 2. Sejam
*
, p n com p primo. Suponha que
1
1 1 0
r r
r r
n n p n p n p n

=
seja a representao p-dica de n. Ento ( )
( )
0 1
!
1
r
p
n n n n
E n
p

=

.

UNIDADE 17 Aritmtica dos Restos

Definio. Seja m um nmero natural diferente de zero. Dizemos que dois nmeros naturais a
e b so congruentes mdulo m se os restos de sua diviso euclidiana por m so iguais, e
escrevemos mod a b m = .
Proposio 1. A operao = uma relao de equivalncia. De fato, seja m , com
1 m . Para todos , , a b c , tem-se que:
(i) mod a a m =
(ii) se mod a b m = , ento mod b a m =
(iii) se mod a b m = e mod b c m = , ento mod a c m = .
Proposio 2. Suponha que , a b so tais que b a _ . Tem-se que mod a b m = se, e
somente se, | m b a .
Definio. Chamamos de sistema completo de resduos mdulo m a todo conjunto de
nmeros naturais cujos restos pela diviso por m so os nmeros 0, 1, , 1 m , sem repeties
e numa ordem qualquer.
Proposio 3. Sejam , , , , a b c d m , com 1 m .
(i) Se mod a b m = e mod c d m = , ento mod a c b d m = .
(ii) Se mod a b m = e mod c d m = , ento mod ac bd m = .
Corolrio 1. Para todos
*
n , , a b , se mod a b m = , ento mod
n n
a b m = .
Corolrio 2. Sejam
*
, , a b m , com 1 m . Se 0 mod a b m = , ento, para todo n ,
tem-se que
2 2
mod
n n
a b m = e
2 1 2 1
0 mod
n n
a b m

= .
Teorema (Pequeno Teorema de Fermat). Se p um nmero primo e a , ento
mod
p
a a p = , e se | p a , ento
1
1 mod
p
a p

= .
Proposio 4. Sejam , , , a b c m , com 1 m . Tem-se que
mod mod a c b c m a b m = = =
Proposio 5. Sejam , , , a b c m , com 0 c = e 1 m . Temos que
Profmat UEM PR - Roberto Luiz Spenthof

( )
mod mod
,
m
ac bc m a b
c m
= = =
Corolrio. Sejam , , , a b c m , com 1 m e ( ) , 1 c m = . Temos que
mod mod ac bc m a b m = = =
Proposio 6. Sejam , , a k m , com 1 m e
( ) , 1 k m = . Se
1
, ,
m
a a um sistema
completo de resduos mdulo m, ento
1
, ,
m
a ka a ka tambm um sistema completo de
resduos mdulo m.
Proposio 7. Sejam , a b ,
1
, , , ,
r
m n m m \ 0, 1 . Temos que
(i) se mod a b m = e | n m, ento mod a b n = ;
(ii) mod
i
a b m = , 1, , i r =
1
mod , ,
r
a b m m
l
= =
l
;
(iii) se mod a b m = , ento
( ) ( ) , , a m b m = .

UNIDADE 18 Aplicaes das Congruncias

Apenas exemplos.

UNIDADE 19 Os Teoremas de Euler e Wilson

Proposio 1. Sejam , a m , com 1 m . A congruncia 1 mod aX m = possui uma
soluo
0
x se, e somente se, ( ) , 1 a m = . Alm disso, x uma soluo da congruncia se, e
somente se,
0
mod x x m = .
Definio (Funo fi de Euler). Designaremos por ( ) m quantidade de nmeros naturais
entre 0 e 1 m que so primos com m. Assim, ( ) 1 m m _ , para todo natural m e
( ) 1 m m = se, e somente se, m um nmero primo.
Resultado Importante (Gauss).
( )
| d n
d n =
_

Proposio 2. Obtm-se um sistema reduzido de resduos
1
, ,
s
r r mdulo m a partir de um
sistema completo de resduos
1
, ,
m
a a mdulo m, eliminando os elementos
i
a que no sejam
primos com m. Seja
( ) 1
, ,
m
r r

um sistema reduzido de resduos mdulo m e seja a tal que

( ) , 1 a m = . Ento
( ) 1
, ,
m
ar ar

um sistema reduzido de resduos mdulo m.

Teorema 1 (Euler). Sejam , m a com 1 m e
( ) , 1 a m = . Ento
( )
1 mod
m
a m

= .
Corolrio (Pequeno Teorema de Fermat). Sejam , a p , onde p um nmero primo e
( ) , 1 a p = . Tem-se que
1
1 mod
p
a p

= .
Proposio 3. Sejam , ' m m , com 1 m , ' 1 m e ( ) , ' 1 m m = . Ento
( ) ( ) ( ) ' ' m m m m =
Lema 1. Se p um nmero primo e r, um nmero natural, ento tem-se que

( )
1
1
1
r r r r
p p p p
p

1

= =

( )

Profmat UEM PR - Roberto Luiz Spenthof
Teorema 2. Se
1
1
n
n
m p p

= a decomposio de m em fatores primos, ento

( )
1
1
1
1 1
1 1
n
n
n
m p p
p p

1 1

=




( ) ( )


que pode ser reescrita como:
( )
( ) ( )
1 1
1 1
1 1 1
1 1
n n
n n n
p p p p p p

= .
Proposio 4. Dado
*
a , existe
*
h tal que 1 mod
h
a m = se, e somente se,
( ) , 1 a m = .
Definio. Define-se a ordem de a com respeito a m como sendo o nmero natural
( )
*
min ; 1 mod
i
m
ord a i a m = = .
Lema 2. Temos que 1 mod
n
a m = se, e somente se, ( ) |
m
ord a n .
Corolrio. Sejam , a m , com
( ) , 1 a m = . Temos que
( ) ( ) |
m
ord a m .
Proposio 5. Todo divisor de
n
F da forma
1
2 1
n
k

.
Corolrio. Na progresso aritmtica de primeiro termo 1 e razo 2
r
, para r fixo, existem
infinitos nmeros primos.
Teorema 3 (Lucas). Sejam a e m dois nmeros naturais tais que
( ) , 1 a m = . Suponha que
1
1 mod
m
a m

= , e que 1 mod , , 1
k
a m k k m = \ < ; ento, m primo.
Teorema 4 (Wilson). p um nmero primo se, e somente se,
( ) 1 ! 1 mod p p p = . Em
outras palavras, p primo se, e somente se,
( ) 1 ! 1 0 mod p p = .

UNIDADE 20 Resoluo de Congruncias

Proposio 1. Dados
*
, , a c m , com 1 m , as congruncias mod aX c m = e
0 mod aX c m = possuem soluo se, e somente se,
( ) , | a m c .
Teorema 1. Sejam
*
, , a c m , com 1 m e
( ) , | a m c . Se
0
x a soluo minimal (i.e, a
menor soluo) da congruncia mod aX c m = (respectivamente, 0 mod aX c m = ), ento
( )
0 0 0 0
, , 2 , , 1
m m m
x x x x d
d d d

onde ( ) , d a m = formam um sistema completo de solues incongruentes da congruncia.
Corolrio 1. Se
( ) , 1 a m = , ento as congruncias mod aX c m = e 0 mod aX c m =
possuem uma nica soluo mdulo m.
Corolrio 2. Sejam 1 m e ' R um conjunto reduzido de resduos mdulo m. Seja
*
a ,
com ( ) , 1 a m = . Ento, para todo ' r R , a congruncia mod rX a m = possui uma nica
soluo em ' R .
Teorema 2 (Teorema Chins dos Restos). O sistema
Profmat UEM PR - Roberto Luiz Spenthof

1 1
2 2
mod
mod
mod
r r
X c n
X c n
X c n
=
=
=

onde ( ) , 1
i j
n n = , para todo par ,
i j
n n com i j = , possui uma nica soluo mdulo
1 2 r
N n n n = . Tal soluo pode ser obtida como se segue:
1 1 1 r r r
x N y c N y c = , onde
i i
N N n = e
i
y soluo de 1 mod
i i
NY n = , 1, , i r = .

UNIDADE 21 Aritmtica das Classes Residuais

Definio. O conjunto

; mod a x x a m
l
= =
l
chamado de classe residual mdulo m
do elemento a de .
Proposio 1. As classes residuais mdulo m possuem as seguintes propriedades:
(i) a b
l l
=
l l
se e somente se mod a b m = ;
(ii) Se a b
l l
= 2
l l
, ento a b
l l
=
l l
;
(iii)
a
a

l
=
l

.
Proposio 2. Para cada a existe um, e somente um r , com r m < , tal que
a r
l l
=
l l
.
Corolrio. Existem exatamente m classes residuais mdulo m distintas, a saber:
0 , 1 , , 1 m
l l l

l l l
.
Definio. Em
m
definimos as seguintes operaes:
Adio: a b a b
l l l
=
l l l

Multiplicao: a b a b
l l l
=
l l l

Propriedades da Adio: Para todos , ,
m
a b c
l l l

l l l
, temos
1
) A Associatividade:
( ) ( ) a b c a b c
l l l l l l
=
l l l l l l
;
2
) A Comutatividade: a b b a
l l l l
=
l l l l
;
3
) A Existncia de zero: 0 a a
l l l
=
l l l
para todo
m
a
l

l
;
4
) A Existncia do simtrico: Para todo a m < , tem-se que 0 a m a
l l l
=
l l l
.
Propriedades da Multiplicao: Para todos , ,
m
a b c
l l l

l l l
, temos
1
) M Associatividade: ( ) ( ) a b c a b c
l l l l l l
=
l l l l l l
;
2
) M Comutatividade: a b b a
l l l l
=
l l l l
;
3
) M Existncia de unidade: 1 a a
l l l
=
l l l
;
) AM Distributividade: ( ) a b c a b a c
l l l l l l l
=
l l l l l l l
.
Proposio 3.
m
a
l

l
invertvel se, e somente se,
( ) , 1 a m = .
Corolrio.
m
um corpo se, e somente se, m primo.