MA14 - Aritmética .2cm Unidade 16 Resumo .5cm Congruências e

MA14 - Aritmética
Unidade 16
Resumo
Congruências e Números Binomiais
O Calendário
Abramo Hefez
PROFMAT - SBM
Aviso
Este material é apenas um resumo de parte do conteúdo da
disciplina e o seu estudo não garante o domı́nio do assunto.
O material completo a ser estudado encontra-se no
Capı́tulo 9 - Seções 9.3 e 9.4
do livro texto da disciplina:
Aritmética, A. Hefez, Coleção PROFMAT.
Colaborou na elaboração desses resumos Maria Lúcia T. Villela.
PROFMAT - SBM
Aritmética - Unidade 16 - Parte 1 - Resumo - Congruências e Números Binomiais
slide 2/8
O Teorema de Lucas
O resultado fundamental dessa Unidade, que se baseia sobre alguns
lemas técnicos, que omitiremos, é o seguinte teorema devido ao
matemático francês Edouard Lucas.
Teorema (E. Lucas)
Seja p um número primo e sejam m = m0 + m1 p + m2 p 2 + · · · e
n = n0 + n1 p + n2 p 2 + · · · dois números naturais representados
relativamente à base p. Tem-se que
m
m0
m1
m2
≡
· · · mod p.
n
n0
n1
n2
Este resultado pode ser provado de modo mais simples usando
identidades polinomiais sobre um corpo com p elementos.
PROFMAT - SBM
Aritmética - Unidade 16 - Parte 1 - Resumo - Congruências e Números Binomiais
slide 3/8
O lema a seguir é bastante útil.
Lema
Sejam p um número primo e α, β ∈ N, com α > β. Então p α−β é
pα
.
a maior potência de p que divide
β
p
Demonstração Usando o teorema que relaciona a maior potência
de p que divide o fatorial de um número e a representação desse
número na base p (Unidade 14), vê-se imediatamente que
Ep ((p α )!) =
pα − 1
p−1
e Ep ((p β )!) =
pβ − 1
.
p−1
Por outro lado, como
p α − p β = (p − 1)p α−1 + (p − 1)p α−2 + · · · + (p − 1)p β ,
segue-se, do mesmo resultado acima citado, que
Ep ((p α − p β )!) =
PROFMAT - SBM
p α − p β − (p − 1)(α − β)
.
p−1
Aritmética - Unidade 16 - Parte 1 - Resumo - Congruências e Números Binomiais
slide 4/8
Assim,
α p
Ep
= Ep (p α !) − Ep (p β !) − Ep ((p α − p β )!) = α − β.
pβ
Usando o resultado acima, vamos provar o seguinte (pouco
eficiente) teste de primalidade:
Teorema
Seja n ∈ N tal que
n
≡ 0 mod n, para todo i tal que 0 < i < n,
i
então n é primo.
Demonstração Seja p um número primo que divide n e seja
n = n1 p + · · · + nr p r a representação de n relativamente à base p,
com nr 6= 0. Se essa representação possui mais de um termo não
nulo, digamos ns p s , além de nr p r , então, pelo Teorema de Lucas,
PROFMAT - SBM
Aritmética - Unidade 16 - Parte 1 - Resumo - Congruências e Números Binomiais
slide 5/8
n
ns p s
≡
ns
6≡ 0 mod p,
ns
o que é uma contradição.
Portanto, n = nr p r . Se nr > 1, então, novamente pelo Teorema de
Lucas,
nr p r
(nr − 1)p r
≡
nr
(nr − 1)
6≡ 0 mod p,
o que também é uma contradição.
Portanto, n = p r . Se r > 1, então
r
p
6≡ 0 mod p r ,
p
r −1 é a maior potência de p que divide
pelo Lema acima, p
pois,
pr
. Novamente uma contradição. Só resta, portanto, a
p
possibilidade n = p.
PROFMAT - SBM
Aritmética - Unidade 16 - Parte 1 - Resumo - Congruências e Números Binomiais
slide 6/8
O Calendário
Existe uma fórmula que permite calcular o dia da semana de uma
data devida ao reverendo Christian Zeller, que a publicou em 1 882.
Para simplificarmos as contas, a fórmula terá validade a partir do
ano de 1 601 e ainda, devido à irregularidade do mês de fevereiro,
para dar maior uniformidade à fórmula, o colocaremos no final da
contagem dos meses, ou seja, o mês 1 de um ano será março,
seguido de abril etc., até chegar aos meses 11 e 12, que são janeiro
e fevereiro (do ano seguinte). Assim, os meses de janeiro e
fevereiro de um determinado ano serão considerados como os
meses 11 e 12 do ano anterior.
Uma data (d, m, A) será constituı́da por três números, onde d
representa o dia, m o mês, com a convenção acima (março= 1), e
A um ano posterior a 1 600, ou seja A > 1 601. Por exemplo, 20 de
janeiro de 1 958 será representado por (20, 11, 1 957) e 29 de
fevereiro de 2 016 por (29, 12, 2 015).
PROFMAT - SBM
Aritmética - Unidade 16 - Parte 1 - Resumo - Congruências e Números Binomiais
slide 7/8
Vamos ainda enumerar os dias da semana como segue: domingo
(1), segunda (2), terça (3) etc. e sábado (7).
Teorema (Zeller)
Tem-se a fórmula
13m − 1
A
A
A
s(d, m, A) = d +1+
+A+
−
+
mod 7.
5
4
100
400
PROFMAT - SBM
Aritmética - Unidade 16 - Parte 1 - Resumo - Congruências e Números Binomiais
slide 8/8