Iniciacao cientifica sobre teoria dos numeros

Prévia do material em texto

Um Estudo Sobre a
Teoria dos Números
Diego Marques Mesquita
Orientador: Prof. Dr. Romulo Campos Lins
Universidade Estadual Paulista
"Júlio de Mesquita Filho"
Rio Claro - SP
2011
1
Capítulo 1
Introdução
Neste relatório venho abordar um assunto que me chamou atenção na se-
mana de estudos da matemática no ano de 2010 na UNESP - RC, Teoria dos
Números. O Prof.Dr. Pedro Luiz Aparecido Malagutti não abordou especifi-
camente esse assunto em sua palestra "Matemágica", porém ao longo de sua
apresentação a "Teoria dos Números" ficava cada vez mais explícita, e devido
ao belo espetáculo proporcionado, me ocorreu o interesse de pesquisar sobre a
disciplina, por motivo de curiosidade e para ter um maior aproveitamento na
disciplina no ano em que eu for fazê-la.
Procurei saber qual professor do Departamento de Matemática fosse mais
familiarizado com o assunto em questão. Pesquisei, e cheguei à conclusão que
teria um bom desenvolvimento da pesquisa se fosse orientado pelo Prof.Dr.
Romulo Campos Lins, com a qual agradeço ter aceitado em ser meu orientador,
com o objetivo de me fazer amadurecer matematicamente e pessoalmente.
No início pensei que seria um assunto fácil de lidar, pelo fato de ter me
envolvido com a palavra "Números" desde criança. Porém vi o quanto a dis-
ciplina pode ser abstrata, não deixando de ser bela e fundamental para o
professor tanto de ensino médio como de universidade.
A Teoria dos Números é uma área da Matemática de grande interesse na
Graduação. Por um lado, em seus aspectos mais elementares, ela se relaciona
com muito do que é estudado de Matemática na educação básica, o que permite
comparar o tratamento da Matemática escolar com o tratamento dado na
Matemática "superior". Boa parte do "espírito"da Teoria dos Números reside
na solução de problemas, solução que muitas vezes depende de se perceber
padrões e testar conjecturas.
Irei relatar o desenvolvimento da pesquisa enunciando os aspectos funda-
mentais que rege a disciplina e relacionando-os com um estudo sistemático
das ideias elementares mas fundamentais da Teoria dos Números, seguindo o
livro de Ivan M. Vinogradov, Elements of number theory, que expõe a teoria
2
dos números de forma bem interessante, juntamente com o livro Introdução à
Teoria dos Números de José Plínio de Oliveira Santos, por ser um ótimo livro
introdutório e ser em português.
Como a Teoria dos números reside na solução de problemas não foi possível
estudar todo o conteúdo fornecido na disciplina, pois uma parte da iniciação
científica foi focada só na resolução de problemas.
Assim este relatório será estruturado da seguinte forma: Primeiro apresen-
tarei a teoria trabalhada e logo após enunciarei os problemas.
3
Capítulo 2
Teoria da Divisibilidade
2.1 Conceitos fundamentais
Como a teoria dos números se dedica ao estudo das propriedades dos números
inteiros, irei citar conceitos essenciais dos inteiros: a soma, a diferença e o
produto de inteiros é inteiro, já a divisão pode ser ou não.
Definição 2.1.1. Caso a divisão de a por b, com a, b inteiros e b 6= 0,
resulte em um inteiro (isto é, existe um q inteiro tal que a = bq), dizemos que
b é chamado divisor de a (ou que: a é múltiplo de b, ou b divide a).
Notação: b | a. Se b não divide a escrevemos b - a.
Algumas propriedades relativas à divisibilidade:
• Vale a propriedade transitiva: se m|a e a|b então m|b
• Se sabemos que em uma equação da forma k+ l+ ...+n = p+ q+ ...+ s,
todos os termos, exceto talvez um, são múltiplos de b, então este termo
também é múltiplo de b
• (divisão inteira) Cada número inteiro é representado, de maneira única,
em termos de b inteiro positivo, na forma a = bq + r, 0 ≤ r < b. Ex: 177
= 14.12 + 9, 0 < 9 < 14.
Definição 2.1.2 (MDC). É o maior divisor comum de um conjunto de
números inteiros.
Notação: (a,b,c,...,z)
Notemos que como a quantidade de divisores comuns é finita, é evidente
que exista o maior deles, e que este seja positivo.
EX: (16,24)=8
4
Definição 2.1.3. Se (a,b,c,...,z)=1 dizemos a,b,c,...,z são primos entre si.
EX: (16,25)=1, assim 16 e 25 são primos entre si.
EX: Os numeros 8,13,21 são primos entre si dois a dois, pois (8,13)=(8,21)=(13,21)=1
Definição 2.1.4 (Primorial). Definimos o primorial de n como sendo o
produto de todos os primos menores ou iguais a n.
Notação: n# =
∏
p≤n
p
Algumas propriedades relativas ao MDC:
• Se a é um múltiplo de b, então o conjunto dos divisores comuns dos números
a e b coincide com o conjunto dos divisores de b, em particular, (a, b) = b;
• Para todo inteiro positivo t, (ta, tb) = t(a, b);
• Se c > 0 e a e b são divisíveis por c, então (a
c
, b
c
) = 1
c
(a, b);
Corolário 2.1.1. Se (a, b) = d, temos que (a
d
, b
d
) = 1
• O problema de encontrar o MDC de mais de dois números é o mesmo
problema de encontrar para dois números.
Teorema 2.1.1. Seja d > 0 o máximo divisor comum de a e b. Então
existem inteiros n0 e m0 tais que d = n0a+m0b
Demonstração. Seja B o conjunto de todas as combinações lineares {na+mb}
onde n e m são inteiros. Vamos escolher n0 e m0 tais que c = n0a +m0b seja
o menor inteiro positivo pertencente ao conjunto B. Vamos provar que c|a e
c|b. Como as demonstrações são similares, mostraremos apenas que c|a. A
prova é por contradição. Suponhamos que c - a. Neste caso existem q e r tais
que a = cq + r com 0 < r < c. Portanto r = a − qc = a − q(n0a + m0b) =
(1 − qn0)a + (−qm0)b. Isto mostra que r ∈ B, pois (1 − qn0) e (−qm0) são
inteiros, o que é uma contradição, uma vez que 0 < r < c e c é o menor
elemento positivo de B. Logo c|a e de forma análoga se prova que c|b.
Por outro lado, se D | a, D | b, então D | d = n0a + m0b, de modo que
D ≤ d. �
Teorema 2.1.2. Se a e b são inteiros e a = qb+r, onde q e r são inteiros,
então (a, b) = (b, r).
Demonstração. Da relação a = qb+ r podemos concluir que todo divisor de b
e r é um divisor de a. Esta mesma relação, escrita na forma r = a − qb, nos
diz que todo divisor de a e b é um divisor de r. Logo o conjunto dos divisores
comuns de a e b é igual ao conjunto dos divisores comuns de b e r, o que garante
o resultado. �
5
Este teorema está na base do Algoritmo de Euclides (ou das divisões suces-
sivas) para se determinar o MDC de dois inteiros a, b, um deles 6= 0. Vejamos
um exemplo de como este algorítmo funciona.
Calculo do MDC de 1126 e 522.
Começamos representando a divisão inteira de 1126 por 522:
1126 = 2× 522 + 82
Em seguida, dividindo 522 pelo resto 82, depois 82 pelo resto 30 e assim, su-
cessivamente, até obtermos resto zero.
522 = 6 × 82 + 30
82 = 2 × 30 + 22
30 = 1 × 22 + 8
22 = 2 × 8 + 6
8 = 1 × 6 + 2
6 = 3 × 2
Da última equação temos que (6, 2) = 2 e agora, pelo teorema, podemos
concluir da equação 8 = 1 × 6 + 2, que (8, 6) = (6, 2), e utilizando o teorema
sucessivamente nas equações, temos que (6, 2) = (8, 6) = (22, 8) = (30, 22) =
(82, 30) = (522, 82) = (1126, 522). Determinamos, desta forma, o máximo
divisor comum de 522 e 1126, que é o último resto não-nulo da sequência de
igualdades acima.
Definição 2.1.5 (MMC). Dados inteiros não-nulos a1, a2, ..., an o menor
inteiro positivo que é múltiplo de todos eles é chamado mínimo múltiplo comum
desses números.
Notação: [a1, a2, ..., an]
Teorema 2.1.3. O MMC dos números inteiros não-nulos a1, ..., an é menor
ou igual ao módulo do produto deles.
Demonstração.
∣∣∣∣∣
n∏
i=1
ai
∣∣∣∣∣ é múltiplo de todos os termos ai, logo é múltiplo comum
de a1, ..., an. Como [a1, ..., an] é o menor múltiplo comum de a1, ..., an, temos
que [a1, ..., an] ≤
∣∣∣∣∣
n∏
i=1
ai
∣∣∣∣∣ �
Teorema 2.1.4. O conjunto dos múltiplos comuns de a e b, coincide com
o conjunto formado pelos números da forma
ab
(a, b)
t, t ∈ Z
6
Demonstração. Seja M algum múltiplo comum dos inteiros a eb. Como M
é múltiplo de a, tem-se M = ak, para algum k inteiro. Mas também M é
múltiplo de b, pelo qual
ak
b
também tem que ser inteiro .
Assim, escrevendo (a, b) = d, temos a = a1d, b = b1d, e podemos escrever
ak
b
=
a1k
b1
, onde (a1, b1) = 1. Tem-se então que k é divisível por b1, k = b1t =
b
d
t. Assim M =
ab
d
t
O menor positivo dos múltiplos se obtém para t = ±1.
∴ [a, b] = | ab |
(a, b)
�
Corolário 2.1.2. O MMC de números primos entre si, é o produto deles.
Achei bem interessante essas definições de MMC e MDC, pois no funda-
mental foram introduzidas de uma maneira totalmente diferentes, primeiro
definiam MMC e depois comentavam sobre o MDC, e agora sei o quanto ali-
enado estou sobre a matemática, afinal das contas, o MMC pode ser definido
através do MDC.
Agora falarei sobre Congruência, ou aritmética modular, uma das ferramen-
tas mais importantes da Teoria dos Números. Uma congruência é um conceito
muito importante e que está relacionado com divisibilidade e os restos de uma
divisão de números inteiros. Foi o brilhante Gauss que observou que usávamos
com muita frequência frases do tipo a dá o mesmo resto que b quando divididos
por m,e que essa relação tinha um comportamento semelhante à igualdade, e
foi ele quem introduziu a notação e a chamou de congruência.
O que não é muito comum é o estudo das muitas aplicações que o tema
possui no cotidiano de todas as pessoas. Diferentes códigos numéricos de iden-
tificação, como códigos de barras, números dos documentos de identidade,
CPF, CNPJ, criptografia, calendários e diversos fenômenos periódicos estão
diretamente ligados ao tema, conforme mostrarei ao longo do relatório.
2.2 Congruência
Definição 2.2.1. Se c e b são inteiros, dizemos que c é congruente a b
módulo m > 1 se m | (c− b).
Notação: c ≡ b (mod m)
Note que a congruência é uma relação de equivalência, ou seja, valem as
propriedade reflexiva, simétrica e transitiva.
7
Corolário 2.2.1. Se a e b são inteiros, temos que a ≡ b (mod m) se, e
somente se, existir um inteiro k tal que a = b+ km
Teorema 2.2.1. Se a, b, c e m são inteiros tais que a ≡ b (mod m), então
1. a+ c ≡ b+ c (mod m)
2. ac ≡ bc (mod m) (2.1)
Dem:(1) Como a ≡ b (mod m), temos que a − b = km e, assim, a − b =
(a+c)− (b+c) = km segue que a+c ≡ b+c (mod m). (2) Já que a−b = km
então ac−bc = ckm, como c, k ∈ Z então ck ∈ Z o que implica quem | (ac−bc)
e, portanto, ac ≡ bc (mod m)
Teorema 2.2.2. Se a, b, c, d e m são inteiros tais que a ≡ b (mod m) e
c ≡ d (mod m), então
1. a+ c ≡ b+ d (mod m)
2. ac ≡ bd (mod m)
Dem:(1) De a ≡ b (mod m) e c ≡ d (mod m) temos a−b = km e c−d = k1m.
Somando - se membro a membro obtemos (a+ c)− (b+ d) = (k + k1)m e isto
implica a+ c ≡ b+ d (mod m). De forma análoga temos a veracidade de (2).
Teorema 2.2.3. Se a, b, c e m são inteiros e ac ≡ bc (mod m), então
a ≡ b (mod m
d
), onde d = (c,m)
Dem:De ac ≡ bc (mod m) temos ac − bc = c(a − b) = km. Se dividirmos
os dois membros por d, teremos c
d
(a − b) = km
d
. Logo
m
d
| c
d
(a − b) e, como
(m
d
, c
d
) = 1 segue que m
d
| (a− b), o que implica a ≡ b (mod m
d
).
Perceba que a lei do cancelamento na congruência só vale quando m e c
forem primos entre si
Definição 2.2.2. Se a e b são dois inteiros com a ≡ b (mod m), dizemos
que b é um resto ou resíduo de a, módulo m.
8
Definição 2.2.3. O conjunto de inteiros {r1, r2, ..., rs} é um sistema com-
pleto de resíduos módulo m se
1. ri 6≡ rj(modm) para i 6= j;
2. Para todo inteiro n existe um ri tal que n ≡ ri(modm)
Exemplo. {0, 1, 2, ...,m − 1} é um sistema completo de resíduos módulo
m.
Proposição 2.2.1. Dadosm inteiros incongruentes dois a dois com respeito
ao módulo m, eles formam um sistema completo de restos deste módulo.
Dem: Como são incongruentes, resta apenas observar que qualquer inteiro é
congruente a algum deles.
Teorema 2.2.4. Se (a,m) = 1 e x percorre um sistema completo de restos
módulo m então ax+ b, onde b ∈ Z, também percorre um sistema completo de
restos módulo m.
Dem: Observe que para cada x há um ax + b. Precisamos apenas mostrar
que dados ax1+ b e ax2+ b não congruentes, x1, x2 são também incongruentes
entre si com respeito ao módulo m.
Supondo
x1 ≡ x2 (mod m)
temos que
ax1 + b ≡ ax2 + b (mod m)
contradição. Assim, segue o resultado.
Definição 2.2.4. Os números de uma mesma classe, com respeito ao mó-
dulo m, que são primos entre si com m formam um sistema reduzido de restos
módulo m.
A função φ(m) é definida como a quantidade de números a, 1 ≤ a ≤ m tais
que (a,m) = 1.
Teorema 2.2.5. Se (a,m) = 1 e x percorre um sistema reduzido de restos
módulo m então ax também percorre um sistema reduzido de restos módulo m.
9
Dem: Observe que existem tantos números ax quanto números x, e que
(x,m) = 1, (a,m) = 1, de onde concluímos que (ax,m) = 1, ou seja, os ax são
todos primos comm. Além disto, ax1 ≡ ax2 (mod m)⇒ x1 ≡ x2 (mod m).
2.2.1 Teoremas de Euler e Fermat
Teorema 2.2.6 (Euler). Se m > 1 e (a,m) = 1 então aφ(m) ≡ 1 (mod m)
Dem: Com efeito, se x percorre um sistema reduzido de restos, x = r1, r2, ..., rφ(m),
e se (a,m) = 1 e for um sistema reduzido de resíduos módulo m, ari é con-
gruente a exatamente um dos rj, 1 ≤ j ≤ φ(m), e portanto o produto dos ari
deve ser congruente ao produto dos rj módulo m, isto é
ar1.ar2. ... .arφ(m) ≡ r1.r2. ... .rφ(m) (mod m)
aφ(m)
φ(m)∏
i=1
ri ≡
φ(m)∏
i=1
ri (mod m)
assim segue que
aφ(m) ≡ 1 (mod m)
uma vez que, cada ri sendo primo com m, seu produto também é.
Teorema 2.2.7 (Pequeno teorema de Fermat). Seja p primo. Se p - a
então ap−1 ≡ 1 (mod p)
Demonstração. Basta observar que se p é primo, φ(p) = p− 1. �
2.2.2 Congruência com uma incógnita
Esta subseção tem como objetivo estudar as congruências do tipo
F (x) ≡ 0 (mod m), onde F (x) é um polinômio de grau n, se o coeficiente líder
não for divisível por m, n é chamado de grau de congruência.
Observação: Se x1 é solução da congruência F (x) ≡ 0 (mod m) e
x0 ≡ x1 (mod m) então x0 também será solução da congruência. Assim, a
congruência terá como solução os resíduos do sistema completos de restos que
a satisfazem.
Exemplo: As soluções da congruência x5 + x+ 1 ≡ 0 (mod 7) são
x ≡ 2 (mod 7) e x ≡ 4 (mod 7).
10
Teorema 2.2.8. Se (a,m) = 1 então a congruência ax ≡ b (mod m) terá
exatamente uma solução.
Dem: Pelo Teorema 2.2.5, sabemos que ax percorre um sistema completo de
restos do módulo m quando (a,m) = 1. Consequentemente, para um valor de
x tomado do sistema completo, apenas um, fará com que ax seja congruente
a b módulo m.
∴ Se (a,m) = 1 a congruência ax ≡ b (mod m) admite apenas uma única
solução.
Teorema 2.2.9. Seja (a,m) = d. A congruência ax ≡ b (mod m) não
tem solução caso b não seja divisível por d, mas se o for, então a congruência
terá exatamente d soluções módulo m.
Dem: Primeiramente provemos que para a congruência ax ≡ b (mod m) só
admite solução se d | b.
De fato, tomemos a congruência ax ≡ b (mod m), que por definição significa
(ax− b) = km, k ∈ Z.
Se dividirmos ambos os lados da igualdade por d teremos:
(ax− b)
d
= k
m
d
⇒ a
d
x− b
d
= k
m
d
Note que
a
d
, m
d
∈ Z, pois (a,m) = d. Logo para que a congruência tenha solu-
ção
b
d
tem que ser um número inteiro, e para isso b tem que ser um múltiplo
de d. Portanto d | b.
Acabamos de provar que a congruência ax ≡ b (mod m) admite solução ape-
nas quando b é divisível por d. Agora provemos que são d soluções.
Como a, b e m são divisíveis por d, temos que: a = a1d, b = b1d,m = m1d.
Assim a congruência fica dessa forma: (a1d)x ≡ b1d (mod m1d), que é equiva-
lente a:
a1x ≡ b1 (mod m1) (2.2)
Percebam que (a1,m1) = 1. Logo a congruência (2.2) admite uma única
solução com respeito ao módulo m1. Seja x1 esta solução. Então todos os
números x que formam esta soluçãoserão da forma
x ≡ x1 (mod m1) (2.3)
Se tomarmos com respeito ao módulom os números (2.3) formam mais de uma
solução, já que estão presentes no sistema completo de restos deste módulo.
Tais números são:
x1, x1 +m1, x1 + 2m1, x1 + 3m1, · · ·+ x1 + (d− 1)m1
11
Tendo no total d números.
∴ A congruência ax ≡ b (mod m) admite d soluções.
Corolário 2.2.2. Existem
m
(a,m)
valores de b, 0 ≤ b ≤ m − 1 tais que
ax ≡ b(mod m) tem solução.
Discussão: Como a congruência linear só admite solução quando o termo
b é divisível pelo (a,m), esse corolário nos dá informação de quantos b existem
tais que a congruência linear tem solução.
Exemplo: Para quais (quantos) valores de b a congruência linear 16x ≡ b
(mod 6) admite solução?
Sabemos que o sistema completo de restos com respeito ao módulo 6 varia de
0 a 5. Dividindo 6 por 2 = (16, 6) temos o número 3. Assim temos três opções
de valores de b para que a congruência tenha solução. Dentre o sist. completo
de restos, nota-se que as opções são: 0, 2 e 4 por serem dividíveis por 2.
Esse exemplo foi simples, mas foi útil para mostrar o porquê de ter sido posto
esse corolário simples neste relatório, simples porém pode servir de curiosidade.
Método das frações contínuas
Nos limitaremos ao caso em que (a,m) = 1. Para determinar as soluções
da congruência ax ≡ b(mod m) enunciaremos apenas um método, baseado na
teoria das frações contínuas.
1
Temos a seguinte expansão em fração contínua,
m
a
= q1 +
1
q2 +
1
q3+
.
.
.
1
qn
Consideremos as últimas frações reduzidas:
Pn−1
Qn−1
, Pn
Qn
, que por sua vez é
numericamente igual a
m
a
. Por uma propriedade das frações contínuas, temos
que:
mQn−1−aPn−1 = (−1)n ⇒ aPn−1 ≡ (−1)n (mod m)⇒ aPn−1.b ≡ (−1)n.b (mod m)
1
Poderíamos usar o teorema de Euler: se aφ(m) ≡ 1 (mod m), aφ(m)−1 é o inverso mul-
tiplicativo de a módulo m.
12
Ou seja, x ≡ (−1)n−1Pn−1.b (mod m)(*). Logo para determinar a solução
basta achar Pn−1.
Exemplo: 111x ≡ 75 (mod 321)
Primeiramente tiramos o MDC de 111 e 321: (111, 321) = 3 e perceba que
3 | 75, logo há três soluções.
Simplificando a congruência temos: 37x ≡ 25 (mod 107)
Agora utilizemos o método das frações contínuas:
107 37 ⇒ 37 33
33 2 4 1
⇒ 33 4 ⇒ 4 1
1 8 0 4
Para obtenção do Pn−1 utilizaremos do seguinte esquema:
qs q1 q2 ... qs ... qn
Ps 1 q1 P2 ...Ps−1 Ps ... Pn−1 Pn
Onde Ps = qsPs−1 + Ps−2.
Assim, aplicando o esquema em nosso exemplo, temos:
qs 2 1 8 4
Ps 1 2 3 26 107
Como Pn é numericamente igual a 107, temos que o Pn−1 = 26.
Portanto quando n = 4, Pn−1 = 26. Já que b = 25, usando a igualdade (*)
obtemos a solução da congruência 37x ≡ 25 (mod 107), que é:
x ≡ (−1)4−1.26.25 (mod 107)⇒ x ≡ 99 (mod 107)
Assim as soluções da congruência 111x ≡ 75 (mod 321) são:
x ≡ 99; 99 + 107; 99 + 2 . 107 (mod 321)⇒ x ≡ 99; 206; 313 (mod 321)
2.3 Sistema de Congruências de Primeiro Grau
Essa seção foi o último tópico estudado da teoria, pois nos focamos mais na
resolução de problemas, problemas esses que relatarei logo após essa seção.
13
Enunciarei apenas o sistema mais simples de congruências; x ≡ b1(mod
m1), x ≡ b2(mod m2),· · · , x ≡ bk(mod mk). Sendo que os módulos são primos
dois a dois.
Teorema 2.3.1 (Teorema do Resto Chinês). Sejam m1,m2, . . . ,mk intei-
ros > 1, primos entre si dois a dois, isto é, (mi,mj) = 1 se i 6= j. Neste caso,
o sistema de congruências

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
x ≡ a3 (mod m3)
. . .
x ≡ ak (mod mk)
sempre tem solução.
Demonstração. Se os números a,m são 'pequenos' e são poucas congruências
no sistema, podemos tentar resolver por inspeção. Por exemplo, consideremos
o sistema {
x ≡ 2 (mod 5)
x ≡ 5 (mod 7)
Considerando apenas as soluções positivas, a primeira congruência tem
por solução os números {2, 7, 12, 17, 22, 27, 32, 37, 42, 47, . . . } e a segunda os
números {5, 12, 19, 26, 33, 40, 47, 54, . . . }. A intersecção dos dois conjuntos é
{12, 47, . . . }. Se estendermos suficientemente os dois conjuntos, nos conven-
ceremos de que todas as soluções são caracterizadas por x = 12 + 35t, para
t inteiro (não necessariamente positivo), o que se demonstra ser verdadeiro
verificando que 12+ 35t ≡ 2+ 0 ≡ 2 (mod 5) e 12+ 35t ≡ 5+ 0 ≡ 5 (mod 7).
Generalizando o caso de duas congruências, a pergunta é: se m1,m2 são
primos entre si, é sempre verdade que as PAs a1+tm1 e a2+sm2 têm intersecção
não nula? Em outras palavras,
a1 + tm1 = a2 + sm2
tem solução? A resposta é positiva, pois, como (m1,m2) = 1 existem x0, y0
tais que m1x0 +m2y0 = 1, e disto segue
m1x0 +m2y0 = 1⇒
(a2 − a1)m1x0 + (a2 − a1)m2y0 = (a2 − a1)
14
e basta tomarmos t = (a2−a1)x0 e −s = (a2−a1)y0. Encontrada uma solução
X, as outras serão da forma X +m1m2k.
Embora pudéssemos seguir este método, resolvendo{
x ≡ X (mod m1m2)
x ≡ a3 (mod m3)
e assim por diante, o caso geral de várias congruências é melhor tratado de
outra maneira. Para o sistema
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
x ≡ a3 (mod m3)
. . .
x ≡ ak (mod mk)
vamos construir diretamente uma solução S = S1 + S2 + . . . + Sk. O fato
de a representarmos como soma de k parcelas já expressa nossa intenção de
que cada uma delas irá resultar em ai (mod mi) e 0 (mod mj) para j 6= i. A
construção é a seguinte:
Começamos definindo Mi, 1 ≤ i ≤ k:
Mi =
k∏
t=1
mt
mi
Assim, Mi é divisível por todo mj, j 6= i. Além disto, como os m são primos
dois a dois,
(Mi,mi) = 1
de modo que Mi tem inverso multiplicativo M
′
i , (mod mi). Agora definimos
Si = aiMiM
′
i
para 1 ≤ i ≤ k, e, finalmente,
S = S1 + S2 + . . .+ Sk =
= a1M1M
′
1 + a2M2M
′
2 + · · ·+ akMkM
′
k
É simples verificar que
aiMiM
′
i ≡ ai × 0×M
′
i ≡ 0 (mod mj)
para j 6= i (já que mj |Mi), e que
aiMiM
′
i ≡ ai × 1 ≡ ai (mod mi)
já que M
′
i é o inverso multiplicativo de Mi, (mod mi). �
15
Exemplo: Resolva o sistema: x ≡ b1 (mod 4), x ≡ b2 (mod 5), x ≡ b3
(mod 3)
Resolução: Utilizando o Teorema do Resto Chinês temos que:
Mi =
k∏
t=1
mt
mi
=⇒
M1 =
4. 5. 3
4
= 15,M2 =
4. 5. 3
5
= 12,M3 =
4. 5. 3
3
= 20
Perceba que (15, 4) = 1, (12, 5) = 1 e (20, 3) = 1 . Assim, como enunciado no
teorema, Mi tem inverso multiplicativo (mod mi), i = 1, 2, 3.
Logo,
15 .M ′1 ≡ 1 (mod 4)⇒ b1 . 15 .M ′1 ≡ b1 (mod 4)
12 .M ′2 ≡ 1 (mod 5)⇒ b2 . 12 .M ′2 ≡ b2 (mod 5)
20 .M ′3 ≡ 1 (mod 3)⇒ b3 . 20 .M ′3 ≡ b3 (mod 3)
No caso, M ′1 = 3, M
′
2 = 3 e M
′
3 = 2. Assim,
S = b1 . 15 . 3 + b2 . 12 . 3 + b3 . 20 . 2
ou seja,
x ≡ b1 . 45 + b2 . 36 + b3 . 40 (mod 60)
16
Capítulo 3
Problemas
Enunciarei agora os problemas mais interessantes (pois me fizeram entender
toda a teoria trabalhada, além de aprimorar meu raciocínio matemático), tra-
balhados ao decorrer do ano.
1. Critério de divisibilidade por 3 e por 9: Um número escrito na
base decimal é divisível por 3 (ou por 9) apenas se a soma de seus
dígitos é divisível por 3 (ou, respectivamente, 9). Demonstre a vali-
dade deste critério
Dem: Um inteiro anan−1 . . . a1a0 (os ai são os dígitos) representado na base
10, corresponde ao número
an10
n + an−110n−1 + ...+ a110 + a0, 0 ≤ ai ≤ 9
Queremos obter um critério de divisibilidade por 3. Utilizaremos congruências
para obter esse critério.
100 ≡ 1 (mod 3)
101 ≡ 1 (mod 3)
. . .
10n ≡ 1 (mod 3)
Logo, an10
n + an−110n−1 + ...+ a110 + a0 ≡ an + an−1 + · · ·+ a0 (mod 3)
Assim se queremos que um número qualquer seja divisível por três, o mesmo
tem que ser congruente a zero módulo 3. Como
n∑
i=0
ai10
i ≡
n∑
i=0
ai (mod 3)
17
temos:
n∑
i=0
ai10
i ≡ 0 (mod 3)⇔
n∑
i=0
ai ≡ 0 (mod 3)
∴ Um número é divisível por 3 ⇔ a soma de seus dígitos for divisível por 3.
Análogo para o critério de divisibilidade por 9, pois 10n ≡ 1 (mod 9),∀n ∈N.
2. Demonstre que: Um número escrito na base 10 é divisível por
11 apenas se a soma - subtração alternada de seus dígitos é divisível
por 11.
Dem: Assim como fizermos para verificar a veracidade com o número três,
utilizaremos congruências.
100 ≡ 1 (mod 11)
101 ≡ −1 (mod 11)
102 ≡ 1 (mod 11)
. . .
102n ≡ 1 (mod 11)
102n+1 ≡ −1 (mod 11)
Assim sucessivamente.
Portanto, um número é divisível por 11 se, e somente se, a soma dos algarismos
de ordem par menos a soma dos algarismos de ordem ímpar é divisível por 11,
ou seja, se a soma/subtração alternada de seus dígitos é divisível por 11.
Perceba que, assim como os exemplos acima, podemos fazer um critério
de divisibilidade para todos os números inteiros utilizando congruências. Esse
método é muito eficaz, pena que na atualidade não seja muito "empolgante" ter
um conhecimento desses, pois hoje se quisermos saber se um número é divisível
por outro basta colocarmos na calculadora que ela mostrará. A beleza desse
método é justamente saber como nossos antepassados "se viravam". Por outro
lado, a idéia de se utilizar congruências gera resultados muito mais gerais
(que podem ser descritos em termos de teoria dos grupos: tente encontrar um
critério de divisibilidade por 7, usando congruências).
3. Mostre que 32n+5 + 24n+1 é divisível por 7 para todo n > 0.
18
Dem: De fato, perceba que podemos escrever as parcelas dessa soma do
seguinte modo:
32n+5 = (32)n.35
e
24n+1 = (24)n.2
Como estamos interessados em saber se essa soma é divisível por 7, veremos o
comportamento dela na congruência com respeito ao módulo 7. Assim temos,
32n+5 + 24n+1 ≡ (32)n.35 + (24)n.2 ≡ 2n.5 + 2n.2 (mod 7)
pois note que 32 ≡ 2 (mod 7) e 24 ≡ 2 (mod 7). Perceba também que pode-
mos colocar 2n em evidencia, logo temos
2n.5 + 2n.2 = 2n(5 + 2) = 2n.7 ≡ 0 (mod 7)
Portanto, para todo n > 0, temos que 32n+5+24n+1 ≡ 0 (mod 7), ou seja, essa
soma é divisível por 7.
4. Prove que para todos a e b, e p primo, ap + bp ≡ (a+ b)p (mod p).
Dem: Para provarmos a veracidade desta congruência necessitarei enunciar o
seguinte lema:
Lema 3.1. Se p é primo e 0 < k < p então
(
p
k
) ≡ 0 (mod p)
Dem: De fato,(
p
k
)
=
p!
k!(p− k)! =
p(p− 1)(p− 2) · · · (p− (k + 1))
k!
Claramente, isso é múltiplo de p. Como o coeficiente binomial é sempre inteiro,
k! divide o produto do numerador; mas p é primo, não pode ser "parcialmente
dividido", só pode ser dividido pelo próprio p ; k é menor que p, então p é um
termo que fica sobrando no coeficiente; e por isso, o resultado é divisível por
p.
Voltando à demonstração principal.
(a+ b)p = ap +
(
p
1
)
ap−1b+ · · ·+
(
p
p-1
)
abp−1 + bp
19
Pelo o Lema acima, as parcelas onde 0 < k < p são congruente a zero módulo
p. Assim,
(a+ b)p = ap+
(
p
1
)
ap−1b+ · · ·+
(
p
p-1
)
abp−1+ b
Lema 3.1⇒≡ ap+ bp (mod p)
5. Mostre que 1 + 2 + · · ·+ (n− 2) + (n− 1) ≡ 0 (mod n).
Dem: Sabemos que a soma de uma P.A (Progressão Aritmética) é dada por
Sn =
n(a1 + an)
2
Logo, nossa soma pode ser escrita da seguinte forma:
n(n+ 1)
2
Perceba que para esse número ser divisível por n apenas é necessário que
n seja ímpar, pois se n é ímpar tem - se que n+ 1 é par, logo é divisível por 2
fazendo que esse produto seja inteiro.
Logo quando n é ímpar
n.
(
n+ 1
2
)
≡ 0 (mod n)
6. Para p primo e (a, p) = 1, prove que ap−2b é uma solução de ax ≡ b
(mod p) e resolva 3x ≡ 17 (mod 29).
Dem: Pelo Teorema 2.2.7(Pequeno Teorema de Fermat), temos, nestas con-
dições do exercício, que:
ap−1 ≡ 1 (mod p)
Multiplicando b em ambos os lados da igualdade modular obtemos
ap−1b ≡ b (mod p)
20
Ora, procuramos um tal x que satisfaça ax ≡ b (mod p), se observamos
bem, já temos um número que é congruente a b (mod p), sendo este número
contendo uma potência de a. Logo se tomarmos x ≡ ap−2b (mod p), teremos
a seguinte situação:
a.ap−2.b = ap−1b ≡ b (mod p)
Agora que já demonstramos esta relação, apliquemo-na à congruência linear
3x ≡ 17 (mod 29).
Já que esta satisfaz as condições acima, temos que:
3 . 329−2 . 17 = 328.17
328≡1≡ 17 (mod 29)
7. Prove que um quadrado perfeito não pode ser da forma 3k + 2.
Conclua que se p ≥ 5 é um primo, então p2 + 2 é sempre composto.
Dem: Analisemos o comportamento de um quadrado perfeito.
Se a ≡ 0 (mod 3) então a2 ≡ 0 (mod 3).
Se a ≡ 1 (mod 3) então a2 ≡ 1 (mod 3).
Se a ≡ 2 (mod 3) então a2 ≡ 4 ≡ 1 (mod 3)
Por essa análise concluímos que o resto da divisão de um quadrado perfeito
qualquer por 3 nunca será 2, o resto sempre será 0 ou 1.
Se p ≥ 5 é primo então p2 + 2 é composto, já que p 6≡ 0 (mod 3), logo
p2 + 2 ≡ 3 ≡ 0 (mod 3).
8. Determine todos os primos da forma n3 − 1.
Fatorando n3 − 1 obtemos:
n3 − 1 = (n− 1)(n2 + n+ 1) (∗)
Para que n3 − 1 seja primo, n− 1 = 1 (I) ou n2 + n+ 1 = 1 (II).
De (I), temos diretamente que n = 2.
21
Resolvendo (II),
n2 + n+ 1 = 1→ n2 + n = 0→ n(n+ 1) = 0⇒
{
n = 0 ou
n = −1
Substituindo devidamente estes valores de n em (∗),
n = 2⇒ n3 − 1 = 7 que é primo
n = 0⇒ n3 − 1 = −1, não é primo.
n = −1⇒ n3 − 1 = −2, não é primo.
Logo o único primo da forma n3 − 1 é 7.
9. Faça uma lista de alguns números primos ímpares p que podem
ser escritos como soma de dois quadrados, isto é, p = x2+y2 com x e y
inteiros. Qual é o resto quando os primos em sua lista são divididos
por 4? Prove que isto sempre acontece, começando por mostrar que
de x e y um deve ser ímpar e outro par.
Lista com alguns primos p que satisfazem p = x2 + y2:
5 = 22 + 12
13 = 32 + 22
17 = 42 + 12
29 = 52 + 22
· · ·
O resto na divisão por 4 é sempre 1. Provaremos primeiro que quando isso
acontece necessariamente, entre x e y, um deve ser ímpar e o outro par.
Primeiramente, suponha que x e y são pares.
Se x e y são pares, x = 2m e y = 2t, m, t ∈ Z. Fazendo a soma do quadrado
de ambos temos:
(2m)2 + (2t)2 = 4m2 + 4t2 = 4(m2 + t2)
não é primo, pois é um múltiplo de 4 Suponha que ambos são ímpares, assim
x = 2a + 1 e y = 2b + 1, a, b ∈ Z. Fazendo a soma do quadrado de ambos
temos:
(2a+ 1)2 + (2b+ 1)2 = 4a2 + 4a+ 1 + 4b2 + 4b+ 1 = 4(a2 + a+ b+ b2) + 2
não é primo, pois é um múltiplo de 2
Resta apenas a possibilidade de um ser par e o outro ímpar. Se x = 2k e
y = 2t+1, x2 + y2 = 4k2 +4t2 +4t+1 = 4(k2 + t2 + t) + 1, quer dizer, o resto
22
de sua divisão por 4 é 1.
10. Mostre que para todo n inteiro > 0 existe uma sequência de n
inteiros > 0 na qual todos os números são compostos.
Dem: Precisamos encontrar um modo de fazer uma sequência em que todos
os termos tem fatores em comum com 2,3,... e que não são primos.
Quando pensamos em fator comum lembramos logo do fatorial. Sabemos
também que se a é um múltiplo de n, e somarmos n ou qualquer um dos seus
divisores d, iremos obter como resultado um número que também é divisível
por d.
Assim, sabemos que ao tomarmos o fatorial de um número n e somarmos
2, 3, 4, ..., n obteremos números que são múltiplos de 2, 3, 4, ...,n respectiva-
mente. Estamos criando uma sequência de inteiros consecutivos que são todos
compostos.
Mas veja que não obtemos uma sequência de n números compostos, pois
não somamos n números, e sim (n− 1) números.
Por essa análise, concluímos que se quisermos uma sequência de n números
compostos basta efetuarmos esse procedimento, porém tomando (n + 1)! e
somando 2, 3, ..., n+ 1.
Exemplo: 4 números compostos: (4 + 1)! + 2 = 122, (4 + 1)! + 3 =
123, (4 + 1)! + 4 = 124, (4 + 1)! + 5 = 125. Números que são múltiplos de
2, 3, 4 e 5 respectivamente.
Esse método sempre funciona, porém como o fatorial 'cresce' muito rápido,
pode ficar computacionalmente complicado achar uma sequência de n números
compostos.
Assim, enunciarei outro método, também eficaz, em que as multiplicações
sejam menos numerosas.
Queremos um número,que assim como o fatorial, tenha fatores em comum
com 2, 3,...
Perceba que no fatorial, existem fatores, digamos, repetidos. Pegue o exem-
plo do 4! = 4.3.2.1; perceba que nessa multiplicação temos dois fatores em
comum com o 2: 4 e 2. Ou seja, não é necessário que coloquemos fatores
repetidos, devido o número já estar sendo composto por causa deste fator.
Logo, um modo de fazer com que a multiplicação seja mais fácil, basta
eliminarmos esses fatores repetidos, ou seja, ao invés de fazer (n+1)! fazermos
o primorial de (n+1) (produto de todos os números primos menores ou iguais
a n+ 1).
Exemplo de primorial: 5# = 2.3.5 = 30
Assim, para conseguir um sequência de n números compostos basta fazer
(n+ 1)# + 2, (n+ 1)# + 3, . . . , (n+ 1)# + (n+ 1).
23
Exemplo: Obtenha uma sequência de 4 números compostos.
(4 + 1)# = 2.3.5 = 30; 30 + 2 = 32; 30 + 3 = 33; 30 + 4 = 34; 30 + 5 = 35.
Assim temos a sequência de 4 números compostos 32, 33, 34, 35.
11. Suponhamos que m > 0, (a,m) = 1, b é um inteiro e x percorre
um sistema completo de restos. Demonstrar que
∑
x
{
ax+ b
m
}
=
m− 1
2
Dem: Primeiramente, definimos a parte fracionária de um número real como
o número menos sua parte inteira:
{x} = x− [x]
Como x percorre um sistema completo de restos, ax + b também. Além
disto, se y0 é o menor resíduo positivo de y, módulo m, y = y0+tm para algum
inteiro t, e { y
m
}
=
{
y0 + tm
m
}
=
{
t+
y0
m
}
=
{y0
m
}
de modo que, para fins do cálculo, podemos considerar que os ax+ b são todos
os números 0 ≤ x ≤ m− 1. Assim,
∑
x
{
ax+ b
m
}
=
m−1∑
k=0
{
k
m
}
=
{
0
m
}
+
{
1
m
}
+ . . .+
{
m− 1
m
}
=
=
0
m
−
[
0
m
]
+
1
m
−
[
1
m
]
+ . . .+
m− 1
m
−
[
m− 1
m
]
Repare que se 0 ≤ k ≤ m− 1, k
m
< 1, logo
[
k
m
]
= 0.
Portanto,
m−1∑
k=0
{
k
m
}
=
m−1∑
k=0
k
m
=
1
m
m−1∑
k=0
k
Como
m−1∑
k=0
k =
(m− 1)m
2
segue que
1
m
(m− 1)m
2
=
(m− 1)
2
24
12. Os Números de Mersenne são da forma 2n−1, com n natural.
Quando 2n − 1 é primo esses números são conhecidos como Primos
de Mersenne. Demonstre que se 2n − 1 é primo então n também é
um número primo.
Dem: Suponha que n é um número composto, assim nosso objetivo é demons-
trar que 2n − 1 também é composto.
Se n é composto, n = km. Perceba que
2n − 1 = 2km − 1 = (2k − 1).(2k(m−1) + 2k(m−2) + 2k(m−3) + . . .+ 22k + 2k + 1)
Ou seja, 2km− 1 é divisível por 2k − 1 > 1. Portanto 2n− 1 é composto.
Aplicação de congruência no cotidiano.
Mostrarei agora como se são obtidos os digitos de controle do CPF.
O número de CPF de uma pessoa, é constituído de 11 dígitos, sendo um
primeiro bloco com 9 algarismos e um segundo, com mais dois algarismos, que
são dígitos de controle ou verificação.
O décimo dígito (que é o primeiro dígito verificador) é o resultado de uma
congruência, módulo 11 de um número obtido por uma operação com os pri-
meiros nove algarismos.
Se a1 a2 a3 a4 a5 a6 a7 a8 a9 é a seqüência formada pelos 9 primeiros dígitos,
devemos multiplicá-los, nessa ordem, pela base {1, 2, 3, 4, 5, 6, 7, 8, 9} e somar
os produtos obtidos. Se a soma obtida é S, então o décimo dígito a10 é dado
por S − a10 ≡ 0(mod11). Note que tal número será o próprio resto da divisão
por 11 da soma obtida. Por exemplo,
25
2 3 5 3 4 3 1 0 4
1 2 3 4 5 6 7 8 9
Efetuando as multiplicações correspondentes, teremos:
2× 1 + 3× 2 + 5× 3 + 3× 4 + 4× 5 + 3× 6 + 1× 7 + 0× 8 + 4× 9 = 116.
Dividindo o número 116 por 11, teremos
116 11
6 10
Dessa forma o primeiro dígito de controle será o algarismo 6.
A determinação do segundo dígito de controle é feita de modo similar, sendo
que agora acrescentamos o décimo dígito (que é o que acabamos de calcular)
e usamos uma base de multiplicação de 0 a 9.
2 3 5 3 4 3 1 0 4 6
0 1 2 3 4 5 6 7 8 9
Efetuando as multiplicações correspondentes, teremos:
2× 0+3× 1+5× 2+3× 3+4× 4+3× 5+1× 6+0× 7+4× 8+6× 9 = 145.
Dividindo o número 145 por 11, teremos
145 11
2 13
Logo o CPF completo é 235.343.104-62.
26
Capítulo 4
Considerações Finais
Mesmo podendo aparentar que o conteúdo relatado foi pouco, esse mesmo
conteúdo foi muito trabalhoso, pois em Teoria dos Números, assim como em
muitas outras disciplinas, uma definição não é dada apenas por dar, e sim
por ser requisitada em ampla escala. Cada definição, teorema, proposição, foi
estudada com sua devida cautela para que houvesse um total entendimento do
que está trabalhando, afinal não adianta pesquisar apenas para dizer que está
pesquisando.
Esse projeto de Iniciação Científica foi de bom proveito, pois além de apren-
der sobre o conteúdo pesquisado, aprendi muitas outras coisas, que muitas
vezes não fazia parte de Teoria dos Números, que eram necessárias para que
o objetivo fosse comprido. Foi apresentado o Postulado de Bertrand, afim de
expandir a pesquisa além da referência bibliográfica.
Essa pesquisa fez crescer muito meu raciocínio matemático, já que o modo
em que ela foi conduzida fez conciliar a teoria com a prática, e isso em mate-
mática é fundamental, ainda mais em álgebra que sua dificuldade é exatamente
por isso.
Nunca pensei que a resolução de diversos problemas seria tão útil, pois
para cada problema era necessário consultar a teoria, sendo que ainda houve
problemas que ficaram em aberto. Um problema que ficou sem resolução mas
que fez crescer minha habilidade matemática, foi um em que meu orientador
me desafiou, e até hoje não quis que ele o resolvesse para mim:
"Demonstre que se n é par então [(1 +
√
2)n] é impar. E se n é ímpar então
[(1 +
√
2)n] é par"
E agora que terminou esse projeto, vejo que fiz muito bem em não querer
que o Prof. Romulo me desse a resolução, pois é só tentando aprender que se
aprende.
27
Capítulo 5
Referências Bibliográficas
[1] Vinogradov,I.M. - Elements of number theory.NY: Dover Publications,1954
[2] Santos,José Plínio de Oliveira - Introdução à Teoria dos Números. Rio de
Janeiro, IMPA,CNPq, 2000.
[3] Sá, Ilydio Pereira de - Aritmética modular e algumas de suas aplicações.
Rio de Janeiro, UNIFESO
28