Teoria Numeros Almeida

Prévia do material em texto

Teoria dos Nu´meros e Aplicac¸o˜es
Paulo J. Almeida
Departamento de Matema´tica da Universidade de Aveiro
Conteu´do
1 Introduc¸a˜o 3
2 Os Inteiros 7
2.1 Conceitos ba´sicos . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Divisibilidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Algoritmo de Euclides . . . . . . . . . . . . . . . . . . . . . . 16
2.4 Teorema Fundamental da Aritme´tica . . . . . . . . . . . . . . 21
2.5 Equac¸o˜es Diofantinas Lineares . . . . . . . . . . . . . . . . . . 27
2.6 Factorizac¸a˜o de Fermat . . . . . . . . . . . . . . . . . . . . . . 30
3 Congrueˆncias 33
3.1 Introduc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2 Testes de Divisibilidade . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Congrueˆncias Lineares . . . . . . . . . . . . . . . . . . . . . . 41
3.4 Sistemas de Congrueˆncias . . . . . . . . . . . . . . . . . . . . 43
3.5 Me´todo ro´ de Pollard . . . . . . . . . . . . . . . . . . . . . . . 49
3.6 Armazenamento de ficheiros . . . . . . . . . . . . . . . . . . . 50
3.7 Detecc¸a˜o de erros . . . . . . . . . . . . . . . . . . . . . . . . . 52
4 Func¸a˜o de Euler 55
4.1 Sistema Reduzido de Res´ıduos . . . . . . . . . . . . . . . . . . 55
4.2 Pequeno teorema de Fermat e Teorema de Euler . . . . . . . . 56
4.3 pseudoprimos . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.4 Sistema criptogra´fico RSA . . . . . . . . . . . . . . . . . . . . 63
5 Congrueˆncias polinomiais 66
5.1 Res´ıduos quadra´ticos . . . . . . . . . . . . . . . . . . . . . . . 66
5.2 Congrueˆncias Polinomiais gerais . . . . . . . . . . . . . . . . . 76
1
5.3 Atirar moedas ao ar electronicamente . . . . . . . . . . . . . . 86
5.4 Prova de conhecimento nulo . . . . . . . . . . . . . . . . . . . 88
5.5 Ra´ızes Primitivas . . . . . . . . . . . . . . . . . . . . . . . . . 89
6 Func¸o˜es Aritme´ticas 94
6.1 A func¸a˜o de Mo¨bius, µ(n) . . . . . . . . . . . . . . . . . . . . 94
6.2 As func¸o˜es d(n) e σ(n) . . . . . . . . . . . . . . . . . . . . . . 99
6.3 Nu´meros perfeitos . . . . . . . . . . . . . . . . . . . . . . . . . 101
7 Equac¸o˜es Diofantinas 104
7.1 Introduc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
7.2 Congrueˆncias . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
7.3 Me´todo descendente de Fermat . . . . . . . . . . . . . . . . . 110
7.4 Soma de dois quadrados . . . . . . . . . . . . . . . . . . . . . 114
8 Fracc¸o˜es Continuadas 120
8.1 Introduc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
8.2 Fracc¸o˜es Continuadas finitas . . . . . . . . . . . . . . . . . . . 121
8.3 Fracc¸o˜es continuadas simples . . . . . . . . . . . . . . . . . . . 125
8.4 Fracc¸o˜es continuadas perio´dicas . . . . . . . . . . . . . . . . . 130
8.5 Equac¸o˜es de Pell . . . . . . . . . . . . . . . . . . . . . . . . . 132
2
Cap´ıtulo 1
Introduc¸a˜o
A teoria dos nu´meros e´ das a´reas mais antigas da matema´tica, tendo sido es-
tudada pelo ser humano ha´ va´rios mile´nios. Nesta introduc¸a˜o iremos dar uma
breve descric¸a˜o da raza˜o pela qual esta a´rea e´ ta˜o fascinante e importante.
De uma forma geral, em teoria dos nu´meros estudamos nu´meros e suas
propriedades. Neste curso, lidaremos especialmente com os inteiros 0,±1,±2,,
. . . , e iremos discutir va´rias propriedades e relac¸o˜es entre estes nu´meros. Ire-
mos tambe´m ver variadas aplicac¸o˜es da teoria dos nu´meros, nomeadamente
a` cieˆncia da computac¸a˜o e a` criptologia. Desde ha´ 5000 anos que se desen-
volvem me´todos para representar os inteiros, tendo, as que utilizam sistemas
com bases, permitido algoritmos1 muito mais eficientes de fazer aritme´tica.
Os Babilo´nios criaram a base 60, que actualmente ainda utilizamos nas nos-
sas medic¸o˜es de tempo. Os Maias utilizaram a base 20, tendo introduzido
um s´ımbolo para representar o zero. A base 10 foi pela primeira vez utilizada
na India ha´ aproximadamente seis se´culos. Actualmente, os computadores
utilizam a base 2. O desenvolvimento de algoritmos eficientes para efectuar
aritme´tica tem sido extremamente importante, devido, por exemplo, ao facto
de a criptologia necessitar de inteiros com centenas ou milhares de algaris-
mos. Durante este curso iremos mencionar alguns destes algoritmos e a sua
importaˆncia.
Os gregos, da escola de Pita´goras (se´c VI a.C.), fizeram pela primeira
vez a distinc¸a˜o entre nu´meros primos e nu´meros compostos. Questo˜es sobre
primos teˆm interessado os matema´ticos desde a antiguidade:
Apo´s termos visto alguns primos, uma das primeiras questo˜es que surge
1O termo algoritmo, que agora se aplica a qualquer procedimento para resolver um
problema, originalmente referia-se a procedimentos aritme´ticos.
3
e´ sobre se existe um nu´mero infinito deles. Esta questa˜o foi resolvida de uma
forma muito elegante por Euclides (se´c IV a.C.). Iremos ver este resultado
mais tarde.
Outra questa˜o que surge com naturalidade e´ se existem fo´rmulas que nos
fornec¸am todos os primos. O polino´mio
n2 + n+ 41
da´ valores primos para n ∈ {0, 1, . . . , 39} mas quando n e´ 40 ou 41, o valor
de n2 + n+ 41 ja´ na˜o e´ primo. Iremos ver que na˜o ha´ polino´mios que deˆem
sempre nu´meros primos.
Pierre de Fermat (1601-1665), um grande matema´tico do se´culo XVII,
conjecturou que os nu´meros da forma
Fn = 2
2n + 1
sa˜o primos para qualquer n ≥ 0. Fermat verificou que os primeiros valores,
F0 = 3, F1 = 5, F2 = 17, F3 = 257 e F4 = 65537, sa˜o realmente primos.
O seguinte valor e´ F5 = 4294967297, um nu´mero demasiado grande para ser
testado a´ ma˜o. Em 1732, Leonard Euler (1707-1783) provou que 641 divide
F5, e, portanto, F5 e´ composto. Desde enta˜o, foi provado que muitos outros
Fn sa˜o compostos, e, ate´ agora, na˜o foi encontrado nenhum primo da forma
Fn, para n > 4.
Qual e´ o n-e´simo primo? Para qualquer n, esta questa˜o pode ser respon-
dida ao fim de um limitado per´ıodo de tempo. Por exemplo, o primeiro primo
e´ 2, o quinto e´ 11 e o primo que esta´ na posic¸a˜o 664999 e´ 10006721. Mas ate´
agora nunca foi encontrada uma maneira de saber o n-e´simo primo, sem se
saber todos os primos anteriores.
Quantos primos sa˜o menores que n? Legendre (1752-1833) e Gauss (1777-
1855) conjecturaram que ha´ aproximadamente
n
log n
primos menores que n. Se dividirmos o nu´mero de primos menores que n,
por aquela fracc¸a˜o, verificamos que quanto maior for n mais este cociente se
aproxima de 1. Este resultado e´ conhecido como o Teorema dos Nu´meros
Primos, e foi pela primeira vez provado em 1896, por Hadamard (1865-1963)
e por de la Valle´e Poussin (1866-1962).
4
Uma problema que e´ agora de importaˆncia capital na criptologia e´ a dis-
tinc¸a˜o entre nu´meros primos e compostos. O grego Eratostenes desenvolveu
um me´todo, a que actualmente chamamos crivo de Eratostenes que encon-
tra todos os primos menores que um determinado limite. Os detalhes deste
processo e a sua validade sera˜o estudados neste texto.
Por vezes, e´ necessa´rio determinar se um nu´mero espec´ıfico e´ primo. O
matema´tico iraquiano Ibn al-Haytham (c. 1000) verificou que um nu´mero n
e´ primo quando
n divide (n− 1)! + 1.
Por exemplo, 4! + 1 = 25, portanto 5 e´ primo, enquanto que 6 - (5! + 1),
ou seja, 6 e´ composto. Este e´ um resultado muito interessante (conhecido
por Teorema de Wilson), no entanto, parece ser impratica´vel usa´-lo para
determinar se nu´meros muito grandes sa˜o primos ou na˜o.
Na China antiga, os matema´ticos pensavam que os nu´meros primos eram
precisamente os inteiros positivos n que dividissem 2n−2. Pore´m ha´ nu´meros
compostos que verificam esta propriedade, nomeadamente 341. A estes com-
postos chamamos pseudoprimos. Mas se n na˜o dividir 2n − 2 enta˜o n e´
de certeza composto. Esta propriedade e suas generalizac¸o˜es permitem-nos
desenvolver va´rios testes de primalidade.
Uma outragrande a´rea da Teoria dos Nu´meros consiste em resolver
questo˜es aditivas:
• Quando e´ que um quadrado perfeito se pode escrever como soma de
dois quadrados perfeitos?
Devido ao teorema de Pita´goras, este problema e´ equivalente ao problema
de encontrar triangulos rectangulos com lados inteiros. Todos conhecemos o
triplo (3, 4, 5) (i.e. 32 + 42 = 52). Quantos mais havera´?
O problema anterior consiste em encontrar todas as soluc¸o˜es inteiras da
equac¸a˜o x2 + y2 = z2. A este tipo de equac¸o˜es chamamos equac¸o˜es diofanti-
nas, em honra ao matema´tico grego Diofanto (200?-284?), que foi o primeiro
a tentar descobrir as soluc¸o˜es inteiras de diversas equac¸o˜es. Fermat general-
izou a equac¸a˜o de Pita´goras, x2 + y2 = z2, e considerou a equac¸a˜o
xn + yn = zn,
onde n ≥ 3. Na margem da sua co´pia de um livro sobre os resultados de
Diofanto, Fermat escreveu que tinha uma magn´ıfica demonstrac¸a˜o de que a
5
equac¸a˜o na˜o tem quaisquer soluc¸o˜es inteiras com x, y e z na˜o nulos. Infeliz-
mente, Fermat tambe´m escreveu que a margem do livro era demasiado pe-
quena para reproduzir essa demonstrac¸a˜o. Este resultado e´ conhecido como
o o u´ltimo teorema de Fermat, e foi finalmente provado em 1995 por Andrew
Wiles (1953-).
Uma outra questa˜o aditiva famosa e´ a Conjectura de Goldbach (1690-
1764). Esta conjectura afirma que todos os nu´meros pares sa˜o soma de dois
primos. Em 2000, foi publicado um romance cujo tema e´ esta conjectura
intitulado O tio Petros e a Conjectura de Goldbach e uma editora inglesa
ofereceu um milha˜o de libras a quem a provasse.
O Teorema fundamental da aritme´tica diz-nos que qualquer inteiro pos-
itivo (maior que um) pode ser escrito de forma u´nica, como produto de
primos. Fermat, Euler, Pollard e muitos outros matema´ticos, desenvolveram
te´cnicas de factorizac¸a˜o imaginativas, no entanto, utilizando a te´cnica mais
eficiente ate´ agora descoberta, ainda seriam precisos bilio˜es de anos de tempo
computacional para factorizar um nu´mero com 200 algarismos.
O matema´tico alema˜o Carl Friedrich Gauss, considerado um dos maiores
matema´ticos de sempre, desenvolveu a teoria das congrueˆncias, no in´ıcio do
se´culo XIX. As congrueˆncias consistem essencialmente em substituir inteiros
pelos restos da sua divisa˜o por um outro inteiro. Muitas questo˜es de teo-
ria dos nu´meros podem ser expressas utilizando congrueˆncias, sendo muitas
vezes facilitada a sua resoluc¸a˜o. Usando congrueˆncias, obteˆm-se testes de di-
visibilidade, muito simples. Ha´ muitas aplicac¸o˜es das congrueˆncias a` cieˆncia
da computac¸a˜o, incluindo aplicac¸o˜es ao armazenamento de dados, ou gerac¸a˜o
de nu´meros pseudo-aleato´rios.
Uma das mais importantes aplicac¸o˜es da teoria dos nu´meros a` cieˆncia da
computac¸a˜o e´ a a´rea da criptografia. Va´rios sistemas criptogra´ficos utilizam
congrueˆncias. O sistema RSA, e´ baseado num teorema de Euler que envolve
congrueˆncias e na disparidade de tempos entre multiplicar dois nu´meros e
factorizar o resultado desse produto. Outros sistemas importantes tem como
base outra questa˜o de teoria dos nu´meros chamada problema do logaritmo
discreto. Iremos descrever em pormenor estes sistemas durante o curso.
6
Cap´ıtulo 2
Os Inteiros
2.1 Conceitos ba´sicos
Em teoria dos nu´meros iremos estudar propriedades dos nu´meros inteiros, em
particular, propriedades aditivas e multiplicativas. O conjunto dos inteiros,
com as operac¸o˜es adic¸a˜o, +, e multiplicac¸a˜o, ·, forma um domı´nio de integri-
dade, i. e sa˜o va´lidas as seguintes propriedades, para quaisquer inteiros a, b
e c:
• a+ b e a · b sa˜o inteiros;
• a+ b = b+ a e a · b = b · a;
• (a+ b) + c = a+ (b+ c) e (a · b) · c = a · (b · c);
• (a+ b) · c = a · c+ b · c;
• a+ 0 = a e a · 1 = a;
• a equac¸a˜o a+x = 0 tem uma soluc¸a˜o inteira. Representamos a soluc¸a˜o
desta equac¸a˜o por −a;
• Se c 6= 0 e a · c = b · c enta˜o a = b.
Por convenc¸a˜o, escrevemos ab, em vez de a · b e b− a em vez de b+ (−a).
Os inteiros podem ser ordenados usando o conjunto dos inteiros positivos
{1, 2, 3, . . . }. Temos a seguinte definic¸a˜o:
7
Definic¸a˜o. Se a e b sa˜o inteiros, escrevemos a < b (leˆ-se a menor que b) ou
b > a (b maior que a), se b− a for um inteiro positivo.
Temos as seguintes propriedades
• a+ b e ab sa˜o positivos sempre que a e b o forem;
• para qualquer inteiro a, a > 0, a = 0 ou a < 0;
• Se a < b e c > 0 enta˜o ac < bc.
Precisamos de so´ mais uma propriedade para completar o nosso conjunto
de axiomas:
• Princ´ıpio da Boa ordenac¸a˜o. Qualquer conjunto na˜o vazio de in-
teiros positivos tem um elemento mı´nimo (ou primeiro elemento).
Por esta propriedade obtemos a existeˆncia de um elemento ma´ximo do
conjunto dos inteiros menores ou iguais que um certo nu´mero e permite-nos
fazer a seguinte definic¸a˜o:
Definic¸a˜o. A parte inteira de um nu´mero real x e´ o maior inteiro menor ou
igual a x. Denotamos este inteiro por [x].
Exemplo. Temos [5
2
] = 2, [−5
2
] = −3, [pi] = 3, [−2] = −2 e [0] = 0.
Recordemos que um nu´mero x real e´ racional se e so´ se existem inteiros
a e b, com b 6= 0, tais que x = a
b
. Um nu´mero real que na˜o seja rational e´
irracional. Vamos agora ver uma aplicac¸a˜o do Princ´ıpio da Boa Ordenac¸a˜o:
Teorema 2.1.
√
2 e´ irracional
Demonstrac¸a˜o: Suponhamos que
√
2 e´ racional. Enta˜o existem inteiros
positivos a e b tais que
√
2 = a
b
. Como b
√
2 e´ um inteiro positivo, o conjunto
S = {k√2 | k, k√2 sa˜o inteiros positivos} e´ na˜o vazio, logo tem primeiro
elemento. Seja s = t
√
2 esse elemento. Enta˜o s
√
2 = 2t e´ um inteiro positivo.
Temos enta˜o que u = s
√
2−s = (s−t)√2 pertence a S, pois u = s(√2−1) > 0
e s > t. Mas como s−u = s(2−√2) e√2 < 2, obtemos u < s, o que contradiz
o facto de s ser o primeiro elemento de S. Portanto,
√
2 e´ irracional. 2
8
Ao longo deste texto vamos assumir que o leitor esta´ familiarizado com
os princ´ıpios da induc¸a˜o matema´tica, assim como com as notac¸o˜es∑
,
∏
,
(
m
n
)
e as suas propriedades.
Exerc´ıcios
1. Seja k um inteiro. Mostre que [x+ k] = [x] + k, para qualquer nu´mero
real x.
2. Seja x um nu´mero real e n um inteiro positivo. Mostre que [ [x]
n
] = [x
n
].
3. Mostre que o conjunto dos nu´meros racionais positivos na˜o tem ele-
mento mı´nimo.
4. * Utilizando o Princ´ıpio da Boa Ordenac¸a˜o prove que
√
3 e´ irracional.
5. ** Sejam a e b nu´meros irracionais tais que 1
a
+ 1
b
= 1. Mostre que
qualquer inteiro positivo pode ser escrito de maneira u´nica da forma
[ka] ou [kb], para algum inteiro k.
6. Determine o valor das seguintes somas:
n∑
i=1
1
i(i+ 1)
n∑
i=1
1
i2 − 1
7. Mostre que, para todo o inteiro positivo n,
a)
n∑
i=1
i =
n(n+ 1)
2
;
b)
n∑
i=1
i2 =
n(n+ 1)(2n+ 1)
6
;
c)
n∑
i=1
i3 =
(
n∑
i=1
i
)2
.
9
8. ** Encontre uma fo´rmula de recorreˆncia para
n∑
i=1
ip, para quaisquer
inteiros positivos n e p.
9. Mostre que, para quaisquer inteiros a e b e qualquer inteiro positivo n,
a) an − bn = (a− b)
n−1∑
i=0
aibn−1−i;
b) Se n for ı´mpar enta˜o an + bn = (a+ b)
n−1∑
i=0
(−1)ian−1−ibi;
c) (a+ b)n =
n∑
i=0
(
n
i
)
aibn−i, sendo o coeficiente binomial
(
n
i
)
definido
por (
n
i
)
=
n!
i!(n− i)! .
10. * O coeficiente multinomial
(
n
i1i2c...ik
)
e´ definido por(
n
i1i2 · · · ik
)
=
n!
i1!i2! · · · ik!
com i1 + i2 + · · ·+ ik = n
a) Mostre que os coeficientes multinomiais sa˜o nu´meros inteiros;
b) Mostre que, para quaisquer inteiros positivos n e k e quaisquer
inteiros a1, a2, . . . , ak,(
k∑
i=1
ai
)n
=
∑
i1+i2+···+ik=n
(
n
i1i2 · · · ik
)
ai11 a
i2
2 · · · aikk .
11. Calcule os seguintes produtos
n∏
j=2
(
1− 1
j
) n∏
j=2(
1− 1
j2
)
10
12. A sequeˆncia de Fibonacci e´ definida por recorreˆncia por
f0 = 0
f1 = 1
fn+1 = fn−1 + fn, para n ≥ 1
Determine fi para 2 ≤ i ≤ 15 e mostre que
a)
n∑
i=1
fi = fn+2 − 1, para n ≥ 1.
b)
n∑
i=1
f2i = fnfn+1, para n ≥ 1.
13. Sejam
α =
1 +
√
5
2
, β =
1−√5
2
e seja fn o n-e´simo nu´mero de Fibonacci. Prove que
a) as soluc¸o˜es da equac¸a˜o x2 = x+1, sa˜o α e β (α e´ o famoso nu´mero
de ouro);
b) para qualquer n ≥ 0,
fn =
αn − βn√
5
;
c) fn ≥ αn−2, para n ≥ 1.
14. Mostre que todos os nu´meros inteiros, excepto as poteˆncias de 2 sa˜o
somas de inteiros consecutivos.
2.2 Divisibilidade
Uma das noc¸o˜es fundamentais para o estudo dos nu´meros e´ a de divisibilidade:
Definic¸a˜o. Sejam a e b dois inteiros. Se a 6= 0 e existir um inteiro c tal
que b = ac, dizemos que a divide b, e escrevemos a|b. Se a na˜o divide b,
escrevemos a - b.
11
Por exemplo
7|1001, 13|1001, 11|996710, 5|(78 − 1), 101 - (2100 − 3), 3 - 54865489796432
Alguns inteiros positivos, como 1, 2, 3, 13 e 10006721, so´ sa˜o divis´ıveis
por eles pro´prios e por 1. Estes nu´meros eram chamados nu´meros primos
pelos antigos, mas verificou-se, por razo˜es que veremos mais tarde, que era
prefer´ıvel excluir 1 desta lista. Assim, a definic¸a˜o moderna de um nu´mero
primo e´ a seguinte:
Definic¸a˜o. A qualquer inteiro maior que 1 cujos u´nicos divisores positivos
sejam ele pro´prio e 1, chamamos nu´mero primo. Um inteiro maior que 1 que
na˜o seja primo e´ um nu´mero composto
O seguinte resultado e´ conhecido como o algoritmo da divisa˜o e afirma
que se a e b forem dois inteiros positivos enta˜o existem dois u´nicos inteiros q
e r, tais que
a = bq + r, 0 ≤ r < b
Teorema 2.2. Se a, b, d, r e s sa˜o inteiros tais que d 6= 0, d|a e d|b enta˜o
d|(ra+ sb). Em particular d|(a+ b), d|a− b e d|ra.
Demonstrac¸a˜o: Por hipo´tese, existem inteiros u e v tais que a = du e
b = dv. Donde
ra+ sb = rdu+ sdv = d(ru+ sv).
Como d 6= 0, temos d|(ra+ sb). 2
Teorema 2.3. Se a, b e c sa˜o inteiros, a 6= 0, b 6= 0, a|b e b|c, enta˜o a|c.
Demonstrac¸a˜o: Por hipo´tese, existem inteiros u e v tais que b = au e
c = bv. Portanto, c = auv. Como a 6= 0, a|c. 2
Como aplicac¸a˜o do resultado anterior obtemos:
Corola´rio 2.4. Se n e´ um inteiro maior que 1, enta˜o o menor divisor de n
maior que 1 e´ primo
12
Demonstrac¸a˜o: Seja m o menor divisor de n maior que 1 (se n e´ primo,
m = n). Se m na˜o fosse primo enta˜o existia 1 < u < m tal que u|m. Mas
enta˜o u|n o que contradiz o facto de m ser o menor divisor de n maior que
1. Portanto m e´ primo. 2
Teorema 2.5. Se a, b e k sa˜o inteiros, a 6= 0 e k 6= 0, enta˜o a | b se e so´ se
ak | bk.
Demonstrac¸a˜o: Se a|b enta˜o existe um inteiro u tal que b = au. Donde
bk = aku. Como ak 6= 0, temos ak | bk. Se ak | bk enta˜o existe um inteiro v
tal que bk = (ak)v. Como k 6= 0 temos b = av. Como a 6= 0, obtemos a | b.
2
Teorema 2.6. Se n e´ um inteiro maior que 1 enta˜o n e´ primo ou n e´ um
produto finito de primos.
Demonstrac¸a˜o: Suponhamos que existem inteiros maiores que 1 que
na˜o sa˜o primos, nem sa˜o um produto finito de primos. Seja N o menor
destes inteiros. Como N na˜o e´ primo, tem de ser composto. Seja 1 < u < N
um inteiro que divide N . Enta˜o N = uv para algum inteiro v. Note que
1 < v < N . Portanto, por definic¸a˜o de N , u e v sa˜o primos ou um produto
finito de primos. Logo, tambe´m uv e´ um produto finito de primos. 2
Teorema 2.7.
Se n e´ um nu´mero composto enta˜o existe um primo p ≤ √n tal que p|n.
Demonstrac¸a˜o: Se n e´ composto enta˜o existem inteiros positivos a, b >
1 tais que n = ab. Claramente, na˜o podemos ter a, b >
√
n. Sem perda
de generalidade podemos assumir que a ≤ b. Enta˜o a ≤ √n. Se a e´ primo
obtemos o resultado. Se a na˜o e´ primo, seja p o menor divisor de a. Enta˜o
p ≤ a ≤ √n e p | n. 2
13
O resultado anterior permite-nos obter o Crivo de Erato´stenes (se´c. III
a.C.) que separa os nu´meros primos dos compostos. Comecemos por escrever
todos os nu´meros entre 2 e um limite desejado n (por exemplo 100). O 2 e´
o primeiro elemento, portanto na˜o lhe fazemos nada e marcamos os nu´meros
de dois em dois. Marcamos assim os nu´meros 4, 6, 8, 10, . . . . O primeiro
elemento que ainda na˜o foi marcado e´ o 3. Deixamo-lo ficar e marcamos os
nu´meros 6, 9, 12, 15, . . . . Este processo termina quando o primeiro elemento
que ainda na˜o esta´ marcado for maior que
√
n. Todos os nu´meros que na˜o
foram marcados sa˜o primos.
Teorema 2.8 (Euclides). Ha´ um nu´mero infinito de primos
Demonstrac¸a˜o: Suponhamos que ha´ um nu´mero finito de primos, que
denotamos por p1, p2, . . . , pk. Seja
N = p1p2 · · · pk + 1.
Pelo teorema anterior, N tem um divisor primo, digamos p. Enta˜o p = pi
para algum 1 ≤ i ≤ k. Claramente, pi|(p1p2 · · · pk). Usando teorema 2.2,
pi|(N − p1p2 · · · pk). Mas N − p1p2 · · · pk = 1 e obtemos uma contradic¸a˜o.
Portanto, ha´ um nu´mero infinito de primos. 2
Exerc´ıcios
1. Prove as seguintes afirmac¸o˜es:
a) se a 6= 0 enta˜o a|0 e a|a;
b) se d 6= 0 e d|a, enta˜o d|(−a) e (−d)|a;
c) se a|b e b|a, enta˜o a = b ou a = −b;
d) d|a se e so´ se d | |a|.
2. Seja x um nu´mero real positivo e d um inteiro positivo. Mostre que o
nu´mero de inteiros positivos menores ou iguais a x que sa˜o divis´ıveis
por d e´ igual a [x
d
].
3. Determine o nu´mero de inteiros positivos menores ou iguais a 1000 que
sa˜o divis´ıveis por 5, por 7, por 25 e por 49.
14
4. Determine o nu´mero de inteiros positivos menores ou iguais a 1000 que
na˜o sa˜o divis´ıveis por 3, 5 ou 7.
5. Mostre que 3 | (a3 − a), para qualquer inteiro a.
6. Mostre que o produto de dois inteiros da forma 4k + 1 e´ ainda desta
forma.
7. Mostre que o quadrado de qualquer inteiro ı´mpar e´ da forma 8k + 1.
8. Utilize a induc¸a˜o matema´tica para mostrar que a soma dos cubos de
treˆs inteiros consecutivos e´ divis´ıvel por 9.
9. Seja fn o n-e´simo nu´mero de Fibonacci. Mostre que
a) fn e´ par se e so´ se 3 | n;
b) 3 | fn se e so´ se 4 | n.
10. * Mostre que fm+n = fmfn+1+fm−1fn, para quaisquer inteiros positivos
m e n, com m > 1. Conclua que se m | n enta˜o fm | fn.
11. * Mostre que (2 +
√
3)n + (2 − √3)n e´ um inteiro par, para qualquer
inteiro n ≥ 0. Conclua que [(2 +√3)n] e´ sempre ı´mpar.
12. Utilize o crivo de Eratostenes para encontrar todos os primos menores
que 200.
13. Verifique se os nu´meros 323, 343 e 899 sa˜o primos.
14. Mostre que, se p - n para qualquer primo p ≤ n 13 , enta˜o ou n e´ primo
ou n e´ produto de dois primos.
15. Nu´meros de Fermat. Aos nu´meros da forma Fk = 2
2k + 1, k ≥ 0,
chamamos nu´meros de Fermat.
a) Mostre que, se 2n + 1 e´ primo enta˜o n e´ uma poteˆncia de 2;
b) Mostre que Fn = F0F1 · · ·Fn−1 + 2 e deduza que quaisquer dois
nu´meros de Fermat sa˜o primos entre si;
c) Deduza da al´ınea anterior que ha´ uma infinidade de primos.
15
16. Nu´meros de Mersenne. Aos nu´meros da forma Mk = 2
p− 1, com p
primo, chamamos nu´meros de Mersenne. M2, M3, M5 eM7 sa˜o primos
masM11 = 2047 = 23×89 ja´ na˜o e´ primo. Ate´ agora foram encontrados
44 primos de Mersenne, o u´ltimo dos quais e´ 232582657 − 1, encontrado
em Setembro de 2006 e que tem 9 808 358 algarismos. Mostre que se
a, n > 1 e an − 1 e´ primo enta˜o a = 2 e n e´ primo.
17. * Seja n > 1 inteiro e sejam p1, . . . , pt, os primos menores que n. Mostre
que
t∏
i=1
pi < 4
n
18. * Sejam n > 3 inteiro e p um primo tal que 2n
3
< p ≤ n. Mostre que
p -
(
2n
n
)
.
19. ** A conjectura de Bertrand diz que, para qualquer inteiro n > 1, existe
um primo p tal que n < p < 2n. Prove esta conjectura.
20. Se pn e´ o n-e´simo primo, mostre que pn ≤ 2n.
2.3 Algoritmo de Euclides
Definic¸a˜o. Sejam a e b dois inteiros tais que pelo menos um deles e´ na˜o
nulo. Chamamos ma´ximo divisorcomum ao maior elemento do conjunto dos
divisores comuns de a e b e denotamos este elemento por (a, b).
Sejam a e b dois inteiros positivos. Pelo algoritmo da divisa˜o, existem
dois inteiros q0 e r0, tais que
a = q0b+ r0, com 0 ≤ r0 < b
Se r0 6= 0 podemos utilizar o algoritmo da divisa˜o para os inteiros b e r0.
Enta˜o existem q1 e r1 tais que
b = q1r0 + r1, com 0 ≤ r1 < r0
Procedendo desta forma obtemos uma sequeˆncia de inteiros na˜o negativos
r0, r1, . . . , rn, tais que r0 > r1 > · · · > rn ≥ 0. Note que este processo tem
de terminar ao fim de um nu´mero finito de passos e que o u´ltimo resto, que
denotamos por rk+1, e´ nulo.
16
Teorema 2.9. Se a e b sa˜o dois inteiros positivos e rk e´ o u´ltimo resto na˜o
nulo obtido pelo algoritmo de Euclides, enta˜o rk = (a, b). Mais, o algoritmo
de Euclides permite encontrar inteiros u e v tais que
au+ bv = (a, b)
Demonstrac¸a˜o: O algoritmo de Euclides pode ser esquematizado pelo
seguinte sistema de equac¸o˜es:
a = bq0 + r0
b = r0q1 + r1
r0 = r1q2 + r2
...
rk−2 = rk−1qk + rk
rk−1 = rkqk+1
(2.1)
Seja d = (a, b). Vamos provar por induc¸a˜o que d | ri e d | ri+1, para
qualquer 0 ≤ i ≤ k − 1. Como d|a e d|b, temos d|(a− bq0), i.e., d|r0. Como
d|b e d|r0 enta˜o d|(b − r0q1) = r1. Agora, suponhamos que d|ri e d|ri+1,
queremos provar que d|ri+1 e d|ri+2. Usando a hipo´tese de induc¸a˜o, obtemos
que d|(ri − ri+1qi+2). Mas ri − ri+1qi+2 = ri+2. Portanto d|ri+2.
Acaba´mos de provar que d|ri para todo 0 ≤ i ≤ k. Em particular, d|rk.
Como d, rk > 0, temos d ≤ rk.
Reciprocamente, a u´ltima equac¸a˜o em (2.1) e o facto de rk 6= 0, diz-nos
que rk|rk−1. Usando a penu´ltima equac¸a˜o, obtemos rk|rk−2. Por induc¸a˜o,
conclu´ımos que rk|ri, para qualquer 0 ≤ i ≤ k. Usando a segunda equac¸a˜o,
temos rk|b e usando a primeira, rk|a. Logo, rk|d. Portanto, rk = d.
Agora, provamos a segunda parte do teorema. Seja r−2 = a e r−1 = b.
Sabemos que
ri = ri−2 − ri−1qi, (2.2)
para qualquer 0 ≤ i ≤ k. Vamos provar por induc¸a˜o que, para qualquer
0 ≤ i ≤ k, existem inteiros ui e vi tais que ri = uia+ vib. Como r0 = a− bq0,
o resultado e´ va´lido para i = 0. Suponhamos, por hipo´tese de induc¸a˜o que o
resultado e´ verdadeiro para i e para i− 1. Enta˜o
ri+1 = ri−1 − riqi+1
= ui−1a+ vi−1b− (uia+ vib)qi+1
= (ui−1 − uiqi+1)a+ (vi−1 − viqi+1)b
= ui+1a+ vi+1b
17
Portanto, para qualquer 0 ≤ i ≤ k, ri = uia + vib. Em particular, existem
inteiros u e v, tais que rk = ua+ vb. 2
Definic¸a˜o. Sejam a e b inteiros e pelo menos um deles e´ na˜o nulo. Se
(a, b) = 1 enta˜o dizemos que a e b sa˜o primos entre si.
Teorema 2.10. Seja d = (a, b). Um inteiro n divide a e b se e so´ se n|d.
Demonstrac¸a˜o: Suponhamos que n|d. Como d|a, temos n|a. Como d|b,
temos n|b.
Reciprocamente, suponhamos que n|a e n|b. Enta˜o existem inteiros u e v,
tais que a = nu e b = nv. Por hipo´tese (a, b) = d, o que implica que existem
inteiros s e t, tais que d = as+ bt. Mas enta˜o
d = nus+ nvt = n(us+ vt),
i.e. n|d. 2
Teorema 2.11. Seja d = (a, b) e k um inteiro arbitra´rio. Enta˜o
(a) (a, b+ ka) = (a, b);
(b) (ak, bk) = |k|(a, b);
(c)
(
a
d
,
b
d
)
= 1.
Demonstrac¸a˜o: Seja e = (a, b + ka). Como e|a, temos e|ka. Tambe´m
temos e|(b + ka), logo e|(b + ka − ka) = b. Pelo teorema anterior, e|d.
Claramente, d|(b + ka) e d|a, donde d|e. Como ambos e e f sa˜o positivos,
temos e = d.
Seja f = (ak, bk). Queremos provar que f = |k|d. Como d|a e d|b,
temos |k|d | ka e |k|d | kb. Donde, |k|d | f , i.e. existe um inteiro u tal que
f = |k|du e u > 0, porque d, f > 0. Enta˜o |k|du | ak. Pelo teorema 2.5, du|a.
Analogamente, du|b. Pelo teorema anterior, du|d, i.e. existe um inteiro v, tal
que d = duv. Portanto, u = 1 e f = |k|d.
18
Pelo resultado anterior, d
(
a
d
,
b
d
)
= (a, b) = d. Portanto,
(
a
d
,
b
d
)
= 1.
2
Definic¸a˜o. Sejam a1, a2, . . . , an inteiros na˜o nulos. Dizemos que estes nu´me-
ros sa˜o primos entre si dois a dois, se o maior divisor comum entre cada par
destes inteiros for 1.
Exerc´ıcios
1. Mostre que dois nu´meros de Fibonacci consecutivos sa˜o primos entre
si.
2. Mostre que, se a, b e c sa˜o primos entre si dois a dois enta˜o (a, b, c) = 1.
3. Use o algoritmo de Euclides para encontrar o maior divisor comum
entre
a) 77 e 91;
b) 182 e 442;
c) 2311 e 3701.
4. Escreva (17, 37) como combinac¸a˜o linear de 17 e 37.
5. Escreva (399, 703) como combinac¸a˜o linear de 399 e 703.
6. Mostre que, se a|c, b|c e (a, b) = 1 enta˜o ab|c.
7. Encontre inteiros r e s tais que
a) 547r + 632s = 1;
b) 398r + 600s = 2;
c) 922r + 2163s = 7.
19
8. Averigue se ha´ inteiros r e s tais que 1841r + 3647s = 1. Justifique.
9. Mostre que, se na˜o existem primos p tais que p|a e p|b, enta˜o (a, b) = 1.
10. Mostre que, se p e´ primo e a e´ um inteiro, enta˜o ou (a, p) = 1 ou
(a, p) = p.
11. Sejam a, b, c e d inteiros tais que b 6= 0, d 6= 0, (a, b) = 1, (c, d) = 1 e
a
b
+ c
d
e´ um inteiro. Mostre que |b| = |d|.
12. Considere o algoritmo de Euclides e seja rk = (a, b).
a) Mostre que
(i) a ≥ 2r0 e b ≥ 2r1;
(ii) ri ≥ ri+2, para qualquer 0 ≤ i ≤ k − 2;
(iii) a ≥ 2 k2 .
b) Qual e´ o maior nu´mero de passos de a ≤ 10n?
13. Teorema de Lame´. Sejam a e b inteiros positivos tais que a > b e k
o comprimento do algoritmo de Euclides para a e b. Seja α =
1 +
√
5
2
.
Mostre que
k ≤ log b
logα
− 1.
Sugesta˜o: Prove primeiro que
a) rk−i ≥ fi+2, para 0 ≤ i ≤ k;
b) b ≥ αk+1;
14. O mı´nimo mu´ltiplo comum de dois inteiros positivos a e b e´ o inteiro
[a, b] que satisfaz as seguintes condic¸o˜es:
• [a, b] ≥ 1;
• a|[a, b] e b|[a, b];
• Se a|c e b|c enta˜o [a, b]|c;
Mostre que [a, b] existe e e´ u´nico. De facto ab = (a, b)[a, b].
15. * A Se´rie de Farey de ordem n consiste das fracc¸o˜es h
k
ordenadas por
ordem crescente, onde h e k sa˜o inteiros, 0 ≤ h ≤ k ≤ n e (h, k) = 1.
20
a) Encontre a se´rie de Farey de ordem 7;
b) Mostre que se a
b
, c
d
e e
f
sa˜o termos sucessivos de uma se´rie de Farey
enta˜o
c
d
=
a+ e
b+ f
;
c) Mostre que se a
b
e c
d
sa˜o termos sucessivos de uma se´rie de Farey
enta˜o ad− bc = −1;
d) Mostre que se a
b
e c
d
sa˜o termos sucessivos de uma se´rie de Farey
enta˜o b+ d > n.
2.4 Teorema Fundamental da Aritme´tica
O teorema fundamental da aritme´tica, tambe´m conhecido como o teorema da
factorizac¸a˜o u´nica, afirma que se duas pessoas escreverem um inteiro n > 1
como produto de primos, obtera˜o o mesmo resultado, com a poss´ıvel excepc¸a˜o
da ordem pela qual os primos sa˜o escritos nos dois produtos. Ao longo deste
curso iremos constantemente usar este teorema que bem merece o seu nome.
Comecemos por provar um resultado, que utilizaremos posteriormente para
provar o teorema fundamental da aritme´tica.
Teorema 2.12. Se p|(ab), enta˜o p|a ou p|b.
Demonstrac¸a˜o: Suponhamos que p - a. Enta˜o (a, p) = 1. Pelo teorema
2.9, existem inteiros u e v, tais que au + pv = 1. Multiplicando ambos os
membros da u´ltima equac¸a˜o por b, obtemos abu+pbv = b. Como p|ab, temos
p|b. 2
A seguir generalizamos o resultado anterior de duas maneiras diferentes.
Teorema 2.13. Se p e´ um primo e p|(a1a2 · · · ak) enta˜o p|aj, para algum
1 ≤ j ≤ k. Em particular, se p|ak enta˜o p|a.
Demonstrac¸a˜o: Vamos provar o resultado pretendido usando induc¸a˜o
em k. Se k = 1 e´ trivial que o resultado e´ verdadeiro. Suponhamos, por
hipo´tese de induc¸a˜o que o resultado e´ va´lido para k, i. e., se p divide o
produto de k inteiros enta˜o divide um desses inteiros. Suponhamos agora
que p | (b1b2 · · · bkbk+1).
21
Se p | (b1b2 · · · bk) enta˜o, usando a hipo´tese de induc¸a˜o, p|bj, para algum
1 ≤ j ≤ k.
Se p - (b1b2 · · · bk), enta˜o (p, b1b2 · · · bk) = 1, donde existem inteiros u e v,
tais que pu+ b1b2 · · · bkv = 1. Multiplicandopor bk+1, obtemos
pubk+1 + b1b2 · · · bkbk+1v = bk+1.
Portanto, p|bk+1. Portanto o resultado e´ va´lido para k + 1.
Usando induc¸a˜o, o teorema esta´ provado, para qualquer inteiro k. 2
Teorema 2.14. Se (n, a) = 1 e n|ab, enta˜o n|b.
Demonstrac¸a˜o: Pelo teorema 2.9, se (n, a) = 1 enta˜o existem inteiros u
e v, tais que nu+ av = 1, donde nbu+ abv = b. Como n|ab, obtemos n|b. 2
Teorema 2.15 (Teorema Fundamental da Aritme´tica). Seja n > 1 e supon-
hamos que
n = p1p2 · · · pr = q1q2 · · · qs,
onde p1, p2, . . . , pr, q1, q2, . . . , qs sa˜o primos. Enta˜o r = s e as duas factori-
zac¸o˜es de n sa˜o iguais, com a poss´ıvel excepc¸a˜o da ordem dos factores.
Demonstrac¸a˜o: Suponhamos que o teorema e´ falso e seja N o menor
inteiro para o qual o teorema e´ falso. Enta˜o o teorema e´ verdadeiro para
qualquer inteiro 1 < n < N . Suponhamos que
N = p1p2 · · · pr = q1q2 · · · qs,
onde p1, p2, . . . , pr, q1, q2, . . . , qs sa˜o primos. Como o teorema e´ certamente
verdadeiro para nu´meros primos, N e´ composto. Portanto, r, s ≥ 2. Como a
ordem dos factores na˜o e´ importante, podemos assumir que
pr ≥ pi, 1 ≤ i ≤ r − 1
e
qs ≥ qj, 1 ≤ j ≤ s− 1
22
Primeiro provamos que na˜o podemos ter pr > qs. Se pr > qs enta˜o pr > qj,
para qualquer 1 ≤ j ≤ s. Portanto, pr - qj, para qualquer 1 ≤ j ≤ s. Mas
pr|(q1q2 · · · qs),
pelo teorema anterior, temos uma contradic¸a˜o. Assim, pr ≤ qs. Se pr < qs,
obter´ıamos tambe´m uma contradic¸a˜o usando um processo ana´logo. Portanto,
pr = qs.
Agora
N
pr
= p1p2 · · · pr−1 = q1q2 · · · qs−1
e 1 <
N
pr
< N , porque r, s ≥ 2. Enta˜o o teorema e´ va´lido para N
pr
, i. e.
r − 1 = s− 1 e as factorizac¸o˜es p1p2 · · · pr−1 e q1q2 · · · qs−1 sa˜o iguais, com a
poss´ıvel excepc¸a˜o da ordem dos factores. Portanto, r = s e, como pr = qs, as
factorizac¸o˜es de N em primos sa˜o iguais, com a poss´ıvel excepc¸a˜o da ordem
dos factores. Assim, o teorema e´ va´lido para N , o que contradiz a definic¸a˜o
de N .
Portanto, o teorema e´ va´lido para todo o n > 1. 2
Note que o teorema seria falso se considera´ssemos 1 como primo. Por
exemplo, 2 = 1× 2 = 1× 1× 1× 2.
Como, por vezes, na factorizac¸a˜o de um inteiro, temos primos repetidos,
usaremos a notac¸a˜o
n = pa11 p
a2
2 · · · parr .
Teorema 2.16. Suponhamos que o primo p divide n e a factorizac¸a˜o de n
em primos e´ dada por
n = pa11 p
a2
2 · · · parr .
Enta˜o p = pj, para algum 1 ≤ j ≤ r.
Demonstrac¸a˜o: Pelo teorema 2.13, p|pj para algum 1 ≤ j ≤ r. Como
p > 1 e os u´nicos divisores de pj sa˜o 1 e pj, temos p = pj. 2
23
Teorema 2.17. Suponhamos que
n = p1p2 · · · pkq1q2 · · · qs
m = p1p2 · · · pkr1r2 · · · rt
onde p1, p2, . . . , pk, q1, q2, . . . , qs, r1, r2, . . . , rt sa˜o primos e nenhum dos q’s e´
igual a algum dos r’s (se k = 0 interpretamos o produto p1p2 · · · pk como
sendo igual a 1, analogamente para s = 0 e t = 0). Enta˜o
(n,m) = p1p2 · · · pk.
Demonstrac¸a˜o: Seja e = p1p2 · · · pk. Como e|m e e|n, temos e|(m,n).
Portanto, existe um inteiro a, tal que (m,n) = ea. Logo, ea|eq1q2 · · · qs, o
que implica que a|q1q2 · · · qs. Analogamente, a|r1r2 · · · rt. Queremos provar
que a = 1, com vista a obtermos uma contradic¸a˜o, suponhamos que a > 1.
Enta˜o existe um primo p que divide a, donde p|q1q2 · · · qs e p|r1r2 · · · rt. Pelo
teorema anterior, existem 1 ≤ i ≤ s e 1 ≤ j ≤ t, tais que p = qi e p = rj.
Contradic¸a˜o! Portanto, a = 1 e (n,m) = p1p2 · · · pk. 2
Terminamos esta secc¸a˜o com dois resultados que dependem da factori-
zac¸a˜o u´nica. Comec¸amos com um teorema que sera´ muito importante mais
tarde.
Teorema 2.18. Suponhamos que a e b sa˜o dois inteiros positivos tais que
(a, b) = 1 e ab = cn. Enta˜o existem inteiros positivos d e f tais que a = dn
e b = fn.
Demonstrac¸a˜o: Se a = 1 enta˜o basta tomar d = 1 e f = c. Se b = 1,
enta˜o d = c e f = 1. Portanto, podemos assumir que a > 1 e b > 1. Como
(a, b) = 1, podemos escrever
a = pa11 p
a2
2 · · · parr e b = par+1r+1 par+2r+2 · · · par+sr+s
onde pi e´ primo, para 1 ≤ i ≤ r + s, e pi 6= pj, para i 6= j. Suponhamos que
a decomposic¸a˜o de c em primos e´ dada por
c = qb11 q
b2
2 · · · qbkk .
Enta˜o
pa11 · · · parr par+1r+1 · · · par+sr+s = qnb11 · · · qnbkk .
24
Pelo teorema fundamental da aritme´tica, r + s = k e os primos pi sa˜o os
mesmos que os primos qj (talvez ordenados de maneira diferente), e os cor-
respondentes expoentes sa˜o os mesmos. Podemos, portanto, numerar os q’s
tal que qj = pj, para 1 ≤ j ≤ r + s. Enta˜o aj = nbj, para 1 ≤ j ≤ r + s.
Logo,
a =
(
pb11 p
b2
2 · · · pbrr
)n
b ==
(
p
br+1
r+1 p
br+2
r+2 · · · pbr+sr+s
)n
2
O pro´ximo teorema generaliza o famoso resultado, demonstrado por Pita´-
goras, de que
√
2 e´ irracional.
Teorema 2.19. Sejam a e n inteiros positivos. Se n
√
a e´ racional enta˜o n
√
a
e´ inteiro.
Demonstrac¸a˜o: Suponhamos que n
√
a e´ racional. Enta˜o existem inteiros
positivos r e s, tais que (r, s) = 1 e
n
√
a =
r
s
.
Suponhamos que s > 1. Enta˜o existe um primo p tal que p|s. Mas asn = rn,
o que implica que p|r. Contradic¸a˜o, pois (r, s) = 1. Portanto, s = 1 e
n
√
a = r, um inteiro. 2
Por exemplo, 1 <
√
2 < 2, logo
√
2 na˜o e´ inteiro. Portanto,
√
2 e´ irra-
cional. Como 2 < 3
√
10 < 3, temos que 3
√
10 e´ irracional.
Exerc´ıcios
1. Sejam p e q dois primos ı´mpares consecutivos. Mostre que qualquer
factorizac¸a˜o de p + q em primos necessita de pelo menos treˆs primos
na˜o necessariamente distintos. Por exemplo 5 + 7 = 2× 2× 3.
25
2. Suponha que
n = pa11 p
a2
2 · · · parr e m = pb11 pb22 · · · pbrr
onde expoentes nulos sa˜o permitidos. Mostre que
a) (n,m) = p
min(a1,b1)
1 p
min(a2,b2)
2 · · · pmin(ar,br)r ;
b) [n,m] = p
max(a1,b1)
1 p
max(a2,b2)
2 · · · pmax(ar,br)r ;
c) n|m se e so´ se ai ≤ bi, para qualquer 1 ≤ i ≤ r.
3. Considere a equac¸a˜o
anx
n + an−1xn−1 + · · ·+ a1x+ a0 = 0
onde ai e´ inteiro, para 0 ≤ i ≤ n. Mostre que, se a equac¸a˜o tem uma
soluc¸a˜o racional, digamos x =
r
s
com (r, s) = 1, enta˜o s|an e r|a0. Em
particular, se an = 1 e x e´ rational enta˜o x e´ um inteiro.
4. Mostre que, se p e´ primo e p|an, enta˜o pn|an.
5. Quantos zeros ha´ no fim de 100!?
6. * Mostre que so´ a primeira soma parcial da se´rie harmo´nica e´ inteira.
7. Mostre que
a)
3
√
3 e
5
√
5 sa˜o irracionais.
b) n
√
n e´ irracional, para qualquer n ≥ 2.
8. Mostre que
√
2 +
√
3 e´ irracional.
9. Mostre que log2 3 e´ irracional.
10. Mostre que ha´ infinitos primos da forma 4n+ 3.
11. Mostre que ha´ infinitos primos da forma 6n+ 5.
12. * Se a e b sa˜o inteiros, enta˜o a progressa˜o aritme´tica a, a+ b, a+2b, . . .
conte´m um nu´mero ta˜o grande quanto se queira de compostos consec-
utivos.
13. Factorize em primos cada um dos seguintes inteiros:
106 − 1, 108 − 1, 215 − 1, 224 − 1, 236 − 1.
26
2.5 Equac¸o˜es Diofantinas Lineares
O algoritmo de Euclides permite-nos encontrar uma soluc¸a˜o da equac¸a˜o
ax+ by = (a, b).
Nesta secc¸a˜o vamos mostrar como resolver completamente uma equac¸a˜o a
duas inco´gnitas, ax+ by = c e como generalizar para n inco´gnitas.
Teorema 2.20. Sejam a e b inteiros na˜o nulos e d = (a, b). Se d - c enta˜o
a equac¸a˜o
ax+ by = c (2.3)
na˜o tem soluc¸o˜es integrais. Se d|c, a equac¸a˜o tem uma infinidade de soluc¸o˜es
inteiras. Se x = x0, y = y0 e´ uma soluc¸a˜o de (2.3), enta˜o todas as soluc¸o˜es
de (2.3) sa˜o dadas por  x = x0 + t
b
d
y = y0 − tad
onde t e´ um inteiro.
Demonstrac¸a˜o: Como d|a e d|b, temos d|(ax + by) para quaisquer in-
teiros x e y. Portanto, se c = ax + by, enta˜o d|c. Donde, se d - c, (2.3) na˜o
tem soluc¸o˜es inteiras. Agora, se d|c, existe um inteiro e tal que c = de. Pelo
teorema 2.9, existem inteiros u e v, tais que
au+ bv = d.
Multiplicando por e,obtemos a(ue) + b(ve) = de = c. Portanto, a equac¸a˜o
(2.3) tem pelo menos uma soluc¸a˜o. Seja (x0, y0) uma soluc¸a˜o de (2.3) e t um
inteiro qualquer. Enta˜o
a
(
x0 + t
b
d
)
+ b
(
y0 − ta
d
)
= ax0 + by0 = c.
O que prova que a equac¸a˜o (2.3) tem uma infinidade de soluc¸o˜es.
Falta-nos ainda provar que qualquer soluc¸a˜o de ax + by = c e´ da forma
descrita no teorema. Suponhamos que (x1, y1) e´ outra soluc¸a˜o. Enta˜o
a(x1 − x0) + b(y1 − y0) = c− c = 0.
27
Donde
a
d
(x1 − x0) = − b
d
(y1 − y0), (2.4)
o que implica que
b
d
| a
d
(x1 − x0).
Como
(
a
d
,
b
d
)
= 1, temos
b
d
| (x1 − x0) (ver teoremas 2.11 e 2.14). Portanto,
existe um inteiro t, tal que
x1 = x0 + t
b
d
.
Substituindo em (2.4), obtemos
a
d
(
t
b
d
)
= − b
d
(y1 − y0),
donde
y1 = y0 − ta
d
.
Portanto, qualquer soluc¸a˜o de (2.3) e´ forma descrita acima. 2
Exemplo. Como exemplo, vamos resolver a equac¸a˜o 12x+25y = 331. Pelo
algoritmo de Euclides ou por tentativa, obtemos 12 × (−2) + 25 × 1 = 1.
Multiplicando por 331, obtemos 12 × (−662) + 25 × 331 = 331. Portanto,
(−662, 331) e´ uma soluc¸a˜o da equac¸a˜o. A soluc¸a˜o geral e´ dada por
x = −662 + 25t, y = 331− 12t, para t inteiro.
Suponhamos que deseja´vamos encontrar as soluc¸o˜es na˜o negativas. Enta˜o
x ≥ 0 e y ≥ 0, i. e. 25t ≥ 662 e 12t ≤ 331. Donde, t ∈ [26.48, 27.58(3)].
Como t e´ inteiro, t = 27. Assim, obtemos uma u´nica soluc¸a˜o na˜o negativa:
x = 13 e y = 7.
Este me´todo permite-nos resolver problemas como o seguinte:
Na ve´spera de fim de ano, o Hermenegildo foi comprar Cham-
pagne e vinho tinto e gastou 331 euros. Sabendo que cada garrafa
de Champagne custou 25 euros e cada garrafa de vinho custou 12
euros, quantas garrafas comprou o Hermenegildo?
28
Exerc´ıcios
1. Para cada uma das seguintes equac¸o˜es, encontre todas as soluc¸o˜es em
inteiros ou prove que na˜o ha´ nenhuma
a) 3x+ 2y = 1;
b) 3x− 2y = 1;
c) 17x+ 14y = 4;
d) 33x− 12y = 9;
e) 91x+ 221y = 15;
f) 401x+ 503y = 20.
2. Para cada uma das seguintes equac¸o˜es, encontre todas as soluc¸o˜es em
inteiros positivos ou prove que na˜o ha´ nenhuma
a) 23x− 7y = 1;
b) 9x+ 11y = 79;
c) 39x+ 47y = 4151.
3. Mostre que (a, b, c) = ((a, b), c).
4. Mostre que se ha´ soluc¸o˜es inteiras da equac¸a˜o ax+ by + cz = e, enta˜o
(a, b, c) | e. Suponha que (a, b, c) | e e mostre que ha´ inteiros w e z tais
que
(a, b)w + cz = e.
Finalmente, mostre que ha´ inteiros x e y tais que
ax+ by = (a, b)w.
Esta te´cnica pode ser generalizada para resolver uma equac¸a˜o com n
inco´gnitas.
5. Encontre todas as soluc¸o˜es em inteiros da equac¸a˜o
323x+ 391y + 437z = 10473.
6. Resolva as equac¸o˜es diofantinas
a) 2x+ 3y + 5z = 7;
29
b) 1521x+ 1955y + 455z = 221.
7. Determine duas fracc¸o˜es cujos denominadores sejam 12 e 16 e cuja soma
seja 10
48
.
8. Numa papelaria vendem-se dois tipos de canetas por 55 e 35 ceˆntimos
respectivamente. Ao fim de um dia a importaˆncia total recebida pela
venda dessas canetas foi 32 euros e 85 ceˆntimos. Qual e´ o menor nu´mero
poss´ıvel de canetas vendidas? E qual o maior?
2.6 Factorizac¸a˜o de Fermat
Suponhamos que n e´ o produto de dois primos p e q pro´ximos um do outro.
Enta˜o n e´ a diferenc¸a de dois quadrados, um dos quais e´ pequeno. Neste caso,
ha´ um processo eficiente de factorizar n chamado factorizac¸a˜o de Fermat.
Teorema 2.21. Seja n um inteiro positivo ı´mpar. Ha´ uma correspondeˆncia
bijectiva entre factorizac¸o˜es de n da forma n = ab, com a ≥ b > 0, e
representac¸o˜es de n na forma t2 − s2, onde t e s sa˜o inteiros na˜o negativos.
A correspondeˆncia e´ dada pelas equac¸o˜es
t =
a+ b
2
, s =
a− b
2
a = t+ s b = t− s
Demonstrac¸a˜o: Se n = ab enta˜o
n =
(
a+ b
2
)2
−
(
a− b
2
2)2
donde n pode ser escrito como a diferenc¸a de dois quadrados. Se n = t2− s2
enta˜o n = (t− s)(t+ s). Obtemos assim a correspondeˆncia bijectiva. 2
Se n = ab e a e b esta˜o pro´ximos um do outro, enta˜o s e´ pequeno e t e´
ligeiramente maior que
√
n. Neste caso, podemos factorizar n, experimen-
tando valores para t, comec¸ando por [
√
n] + 1, ate´ que se encontre um para
o qual t2 − n e´ um quadrado perfeito.
30
Exemplo. Seja n = 200819. Comec¸amos com [
√
n] + 1 = 449. Agora,
4492− 200819 = 782 que na˜o e´ um quadrado perfeito. Em seguida, tentamos
t = 450. Temos 4502 − 200819 = 1681 = 412, donde
n = (450 + 41)(450− 41) = 491 · 409.
Note que se a e b na˜o estiverem pro´ximos, este me´todo ainda serve para
factorizar n, mas so´ apo´s termos usado imensos valores para t, o que o pode
tornar ta˜o moroso. Ha´ uma generalizac¸a˜o do me´todo de Fermat que funciona
melhor nesta situac¸a˜o. Comec¸amos por escolher um multiplicador k pequeno
e tomamos
t = [
√
kn] + 1, t = [
√
kn] + 2, . . .
ate´ que obtenhamos um t para o qual t2 − kn = s2 e´ um quadrado perfeito.
Enta˜o d = (t+ s, n) e´ um factor na˜o trivial de n.
Exemplo. Seja n = 141467. Se usarmos a factorizac¸a˜o de Fermat directa-
mente, precisamos de experimentar 38 t’s ate´ encontrar um factor de n. Mas
se tomarmos k = 3 e comec¸armos com t = [
√
3n] + 1 = 652, rapidamente
vemos que 6552 − 3n = 682. Como (655 + 68, n) = 241, conclu´ımos que
n = 241 · 587. Portanto, com k = 3 so´ precisamos de experimentar 4 t’s.
Mas como sabemos que dev´ıamos usar k = 3 no exemplo anterior? Uma
maneira de resolver este problema e´ utilizando o me´todo de Lehman (que e´
uma generalizac¸a˜o do me´todo de Fermat).
Exerc´ıcios
1. Factorize os inteiros 11413, 8051, 11021, 3200399, 10897 e 24681023.
2. Me´todo de Euler: Seja n ı´mpar. Sejam a, c > 0 ı´mpares e b, d > 0
pares tais que n = a2 + b2 = c2 + d2.
a) Seja u = (a − c, b − d). Mostre que u e´ par e que se r = a−c
u
e
s = d−b
u
, enta˜o (r, s) = 1, r(a+ c) = s(d+ b) e s | (a+ c);
b) Seja v tal que sv = a+ c. Mostre que rv = d+ b, v = (a+ c, d+ b)
e v e´ par;
c) Mostre que n =
(
u2+v2
4
)
(r2 + s2).
31
d) Sabendo que 221 = 102+112 = 52+142, 2501 = 502+12 = 492+102 e
1000009 = 10002+32 = 9722+2352, factorize 221, 2501 e 1000009.
3. Mostre qualquer inteiro da forma 24n+2+1 pode ser factorizado usando
a identidade 4x4 + 1 = (2x2 + 2x+ 1)(2x2 − 2x+ 1). Factorize 218 + 1
e encontre factores na˜o triviais de 242 + 1.
32
Cap´ıtulo 3
Congrueˆncias
3.1 Introduc¸a˜o
Embora muitos resultados ja´ fossem conhecidos, a teoria sistema´tica das
congrueˆncias foi desenvolvida por Gauss. Neste cap´ıtulo, iremos estudar
diversos teoremas famosos, nomeadamente os de Fermat, Euler, Wilson e
Gauss, assim como a func¸a˜o de Euler e o s´ımbolo de Legendre.
Definic¸a˜o. Sejam a e b inteiros e n um inteiro positivo. Se n | (a − b),
dizemos que a e´ congruente com b e escrevemos
a ≡ b mod n
Pela definic¸a˜o de divisibilidade, se a ≡ b mod n enta˜o existe um inteiro
k tal que a = b+ kn. Por exemplo
37 ≡ 25 mod 12
−9 ≡ 31 mod 10
7216 ≡ 34216 mod 1000
Na vida dia´ria usamos congrueˆncias em imensas situac¸o˜es: Os relo´gios
de ponteiros medem as horas mod 12; os dias da semana medem os dias
mod 7; o odo´metro mede a kilometragem mod 106.
Teorema 3.1. Seja n um inteiro positivo. A relac¸a˜o congruente mod n e´
uma relac¸a˜o de equivaleˆncia.
33
Demonstrac¸a˜o: Exerc´ıcio 2
Teorema 3.2. Se a ≡ b mod n e c ≡ d mod n enta˜o
(a) a+ c ≡ b+ d mod n;
(b) a− c ≡ b− d mod n;
(c) ac ≡ bd mod n.
Demonstrac¸a˜o: Exerc´ıcio 2
Teorema 3.3. Se (a, n) = 1 e ab ≡ ac mod n, enta˜o b ≡ c mod n. Em
geral, se (a, n) = d e ab ≡ ac mod n enta˜o
b ≡ c mod n
d
.
Demonstrac¸a˜o: Suponhamos que (a, n) = d e ab ≡ ac mod n. Enta˜o
existe um inteiro k tal que ab = ac+ kn. Sejam
a1 =
a
d
, n1 =
n
d
.
Claramente, a1 e n1 sa˜o inteiros e (a1, n1) = 1. Dividindo ambos os membrosde ab = ac + kn por d, obte´m-se a1(b − c) = kn1. Donde, a1 | kn1. Como
(a1, n1) = 1, temos a1 | k. Portanto, k = a1k1, para algum inteiro k1. Assim,
b− c = k1n1, ou seja n1 | (b− c). Portanto, b ≡ c mod nd . 2
Definic¸a˜o. Um conjunto de inteiros a1, a2, . . . , an diz-se um sistema completo
de res´ıduos mod n, se qualquer inteiro e´ congruente, mod n com um e um
so´ aj.
Seja n um inteiro positivo. Vamos provar que os inteiros 0, 1, 2, . . . , n− 1
formam um sistema completo res´ıduos. Se a e´ um inteiro, pelo algoritmo de
Euclides, existem inteiros q e r, tais que 0 ≤ r < n e a = qn + r. Portanto,
34
a ≡ r mod n. Mais, o resto r e´ u´nico, porque se a ≡ r1 mod n e a ≡ r2
mod n com 0 ≤ r1 ≤ r2 < n, enta˜o r1 ≡ r2 mod n, donde n | (r2− r1). Mas
0 ≤ r2 − r1 ≤ n− 1 < n. Logo r1 = r2.
Portanto, 0, 1, 2, . . . , n− 1 formam um sistema completo res´ıduos.
Como qualquer inteiro e´ congruente mod n com algum dos nu´meros
0, 1, 2, . . . , n− 1, enta˜o para calcular ab mod n ou a+ b mod n e´ suficiente
saber as tabelas de multiplicac¸a˜o e adic¸a˜o de 0, 1, 2, . . . , n − 1. Por exem-
plo, como os nu´meros 0, 1, 2, 3, 4 formam um sistema completo de res´ıduos e
02, 12, 22, 32 e 42 sa˜o todos congruentes mod 5 com 0, 1 ou 4, enta˜o nenhum
quadrado perfeito dividido por 5 da´ resto 2 ou 3. Mais, se tomarmos os
quadrados dos nu´meros anteriores, verificamos que
14, 24, 34, 44 ≡ 1 mod 5.
Podemos enta˜o dizer que para qualquer inteiro n, temos 5 | n ou 5 | (n4− 1).
O pro´ximo teorema tem imensas aplicac¸o˜es:
Teorema 3.4. Seja f(x) um polino´mio com coeficientes inteiros. Se a ≡ b
mod n, enta˜o
f(a) ≡ f(b) mod n.
Demonstrac¸a˜o: Seja
f(x) = akx
k + ak−1xk−1 + · · ·+ a1x+ a0,
onde ai sa˜o inteiros para 0 ≤ i ≤ k. Enta˜o, pelo teorema 3.2
aka
k + ak−1ak−1 + · · ·+ a1a+ a0 ≡ akbk + ak−1bk−1 + · · ·+ a1b+ a0 mod n.
Portanto, f(a) ≡ f(b) mod n. 2
Como primeira aplicac¸a˜o do teorema anterior vamos mostrar que na˜o ha´
polino´mios (na˜o constantes) que deˆem sempre primos.
Corola´rio 3.5. Para qualquer polino´mio de grau maior ou igual a 1 existe
um inteiro a tal que |f(a)| e´ um nu´mero composto.
35
Demonstrac¸a˜o: Seja
f(x) = akx
k + ak−1xk−1 + · · ·+ a1x+ a0,
onde ai sa˜o inteiros para 0 ≤ i ≤ k. Sabemos que se ak > 0, enta˜o
lim
x→∞
f(x) =∞
e se ak < 0 enta˜o
lim
x→∞
f(x) = −∞.
Como, por definic¸a˜o, os primos sa˜o todos positivos, consideremos ak > 0.
Assim,
lim
x→∞
f(x) =∞,
o que implica que podemos tomar b suficientemente grande tal que f(b) > 1.
Seja n = f(b) e j um inteiro suficientemente grande tal que f(b + jn) > n.
Note-se que b+ jn ≡ b mod n, donde
f(b+ jn) ≡ f(b) = n ≡ 0 mod n,
i. e. n | f(b + jn). Como 1 < n < f(b + jn), temos que f(b + jn) e´ um
nu´mero composto. Para terminar a demonstrac¸a˜o basta tomar a = b+ jn.
Se ak < 0, uma demonstrac¸a˜o semelhante, prova que existe um inteiro a
tal que f(a) = −c para algum composto c. 2
Exerc´ıcios
1. Prove que qualquer conjunto de n inteiros consecutivos forma um sis-
tema completo res´ıduos.
2. Determine os menores res´ıduos positivos de 232, 247 e 2200 mod 47.
3. Mostre que se n e´ ı´mpar enta˜o 8 | n2 − 1.
4. Mostre que n3 ≡ n mod 3.
5. Sera´ que a ≡ b mod n implica ca ≡ cb mod n? Justifique indicando
uma demonstrac¸a˜o ou um contra-exemplo.
36
6. Mostre que se n e´ ı´mpar enta˜o 1 + 2 + · · · + (n − 1) ≡ 0 mod n.
Determine o que acontece se n for par.
7. Mostre que se n e´ ı´mpar ou divis´ıvel por 4, enta˜o 13+23+· · ·+(n−1)3 ≡
0 mod n. Este resultado e´ verdadeiro se n for par mas na˜o divis´ıvel
por 4?
8. Para que inteiros n temos 12 + 22 + · · ·+ (n− 1)2 ≡ 0 mod n?
9. Mostre que qualquer nu´mero da forma
4 · 14k + 1
com k ≥ 1, e´ composto. Sugesta˜o: Use congrueˆncias mod 3 para k
ı´mpar e congrueˆncias mod 5 para k par.
10. Mostre que se n2 + 2 for primo, enta˜o 3 | n.
11. No calenda´rio Gregoriano (calenda´rio actual) cada ano divis´ıvel por 4
anos e´ um ano bisexto, excepto para os anos centena´rios que so´ sa˜o
bissextos se forem divis´ıveis por 400. Por exemplo, 1800, 1900 e 2100
na˜o sa˜o bissextos mas 2000 e´. O dia 1 de Janeiro de 1900 calhou a
uma segunda-feira. Mostre que, embora qualquer semana comece a um
domingo, nenhum se´culo comec¸a a um domingo.
12. Mostre que qualquer pessoa nascida entre 1901 e 2071 celebra o seu
aniversa´rio de 28 anos no dia de semana igual ao dia de semana em que
nasceu.
13. Mostre que 43 | (n2 + n+ 41) para uma infinidade de inteiros n.
14. Sabendo que a10 ≡ 10 mod 26, encontre (a, 26).
15. Em 1825, Gauss fez a seguinte construc¸a˜o para escrever um primo
congruente com 1 mod 4 como a soma de dois quadrados perfeitos:
Seja p = 4k + 1 um primo. Primeiro determina-se x tal que
x ≡ (2k)!
2(k!)2
mod p, com |x| < p
2
depois determina-se y tal que
y ≡ x(2k)! mod p, com |y| < p
2
.
37
Gauss mostrou que x2+y2 = p. Verifique este resultado de Gauss, para
p = 5, p = 13 e p = 17.
16. Ha´ razo˜es para acreditar (embora nunca tenha sido provado) que ha´
infinitos primos que podem ser escritos como soma dos quadrados de 3
diferentes primos (o exemplo mais pequeno e´ 83 = 32+52+72. Suponha
que
p = p21 + p
2
2 + p
2
3
onde p, p1, p2 e p3 sa˜o primos. Use congrueˆncias mod 3 para mostrar
que um dos primos p1, p2 ou p3 e´ igual a 3.
17. Suponha que m ≥ 0. Mostre que 17 | (3 · 52m+1 + 23m+1). Sugesta˜o:
Use congrueˆncias mod 17.
18. Suponha que m ≥ 0. Mostre que 49 | (5 · 34m+2 + 53 · 25m).
19. Mostre que se k for ı´mpar, enta˜o 241 | (112k + 192k).
20. Suponha que p e´ primo.
a) Mostre que p e´ o ma´ximo divisor comum entre o coeficientes bino-
miais
(
p
i
)
, onde 1 ≤ i ≤ p− 1;
b) Seja p um primo. Mostre que
(a+ b)p ≡ ap + bp mod p
c) Mostre que para quaisquer inteiros a e b, (ap − bp, p) = 1 ou p2 |
(ap − bp).
3.2 Testes de Divisibilidade
O teorema anterior permite-nos obter diversos testes de divisibilidade, os
quais iremos descrever nesta secc¸a˜o.
Teorema 3.6. Qualquer inteiro positivo e´ congruente com a soma dos seus
algarismos mod 9 e mod 3.
38
Demonstrac¸a˜o: Seja n > 0 um inteiro cuja representac¸a˜o decimal e´
dada por
n = ak10
k + ak−110k−1 + · · ·+ 10a1 + a0,
onde 0 ≤ aj ≤ 9, para qualquer 0 ≤ j ≤ k. Os inteiros aj sa˜o, portanto, os
algarismos de n. Seja
f(x) = akx
k + ak−1xk−1 + · · ·+ a1x+ a0.
Como 10 ≡ 1 mod 9, temos f(10) ≡ f(1) mod 9. Portanto,
n ≡ ak + ak−1 + · · ·+ a1 + a0 mod 9.
Como 3 | 9,
n ≡ ak + ak−1 + · · ·+ a1 + a0 mod 3.
2
Este resultado e´ a base teo´rica da prova dos nove, ensinada na escola
prima´ria alguns anos atra´s. Esta prova serve para ”verificar”se um produto
esta´ certo ou na˜o. Suponhamos que queremos calcular 1472, e que o resultado
nos da´ 21509. Como
147 ≡ 1 + 4 + 7 ≡ 12 ≡ 1 + 2 ≡ 3 mod 9
temos 1472 ≡ 32 ≡ 0 mod 9, mas
21509 ≡ 2 + 1 + 5 + 9 ≡ 8 mod 9,
portanto, o resultado esta´ errado. Note que 21510 ≡ 0 mod 9, mas 1472 6=
21510, porque o u´ltimo algarismo de 1472 e´ um 9. A prova dos nove so´
descobre 8 em cada 9 erros, i. e. so´ resulta 88.8% das vezes. Nos exerc´ıcios,
sera´ descrita outra ”prova”que resulta mais de 90% das vezes.
Teorema 3.7. Seja n > 0 um inteiro cuja representac¸a˜o decimal e´ dada por
n = ak10
k + ak−110k−1 + · · ·+ 10a1 + a0,
onde 0 ≤ aj ≤ 9, para qualquer 0 ≤ j ≤ k. Seja r ≤ k um inteiro positivo.
Enta˜o
n ≡ (ar−1ar−2 · · · a1a0)10 mod 2r e n ≡ (ar−1ar−2 · · · a1a0)10 mod 5r
39
Demonstrac¸a˜o: Como 10 ≡ 0 mod 2 e 10 ≡ 0 mod 5 enta˜o 10r ≡
0 mod 2r e 10r ≡ 0 mod 5r, para qualquer inteiro positivo r. Portanto,
obtemos o resultado pretendido. 2
Exemplo. Seja n = 67537048. Enta˜o 2 | n porque 2 | 8, 4 | n porque 4 | 48,
8 | n porque 8 | 48, mas 16 - n porque 16 - 7048.
Exemplo. Seja n = 85645625. Enta˜o 5 | n porque 5 | 5, 25 | n porque
25 | 25, 125 | n porque 125 | 625, 625 | n porque 625 | 5625, mas3125 - n
porque 3125 - 45625.
Teorema 3.8. Seja n > 0 um inteiro cuja representac¸a˜o decimal e´ dada por
n = ak10
k + ak−110k−1 + · · ·+ 10a1 + a0,
onde 0 ≤ aj ≤ 9, para qualquer 0 ≤ j ≤ k. Enta˜o
n ≡
k∑
j=0
(−1)jaj mod 11
Demonstrac¸a˜o: Exerc´ıcio. 2
Exerc´ıcios
1. Divisibilidade por 7 Seja n = a210
2 + 10a1 + a0. Mostre que n ≡
2a2 + 3a1 + a0 mod 7.
2. Divisibilidade por 1001 E´ um facto que
4 176 204 105 ≡ 105− 204 + 176− 4 ≡ 73 mod 1001.
Prove o resultado que estas congrueˆncias sugerem.
3. Suponha que o me´todo descrito no exerc´ıcio anterior reduz o nu´mero
n ao nu´mero m que tem no ma´ximo treˆs algarismos. Mostre que
40
a) 7 | n se e so´ se 7 | m;
b) 13 | n se e so´ se 13 | m.
4. Encontre todos os inteiros positivos menores que 1000 que da˜o resto 1
quando sa˜o divididos por 2, 3, 5 e 7.
5. A seguinte multiplicac¸a˜o estava correcta, mas quando o resultado es-
tava a ser impresso um mosquito impediu que um dos algarismos fosse
correctamente impresso, obtendo-se
172195 · 572167 = 985242x6565.
Determine o algarismo perdido, x, sem refazer a multiplicac¸a˜o.
3.3 Congrueˆncias Lineares
Uma equac¸a˜o da forma
a1x1 + a2x2 + · · ·+ akxk ≡ b mod n (3.1)
com inco´gnitas x1, . . . , xk e´ uma congrueˆncia linear com k varia´veis. Uma
soluc¸a˜o desta congrueˆncia linear e´ um k-uplo de inteiros que satisfaz a con-
grueˆncia linear. A definic¸a˜o de congrueˆncia mostra que a equac¸a˜o (3.1) e´
equivalente a` equac¸a˜o diofantina
a1x1 + a2x2 + · · ·+ akxk + nxk+1 = b (3.2)
com k + 1 inco´gnitas. Ja´ vimos no cap´ıtulo anterior que a equac¸a˜o (3.2) ou
na˜o tem soluc¸o˜es ou tem uma infinidade de soluc¸o˜es. O mesmo e´ verdade
para a equac¸a˜o (3.1). No entanto, encontrar todas as soluc¸o˜es de (3.1), sig-
nifica encontrar todas as soluc¸o˜es diferentes mod n. Ou seja, duas soluc¸o˜es
diferentes de (3.1) sera˜o a mesma mod n se os diferentes valores de xj forem
congruentes mod n, para qualquer j. Por exemplo, a soluc¸a˜o (1, 2, 3) da
congrueˆncia
x+ y + z ≡ −1 mod 7
e´ a mesma mod 7 que a soluc¸a˜o (8,−5, 17), mas e´ diferente mod 7 da
soluc¸a˜o (1, 3, 2). Em particular, se so´ existir uma soluc¸a˜o mod n de (3.1),
dizemos que a soluc¸a˜o e´ u´nica mod n.
41
Teorema 3.9. A congrueˆncia
ax ≡ b mod n (3.3)
tem soluc¸o˜es se e so´ se d | b, onde d = (a, n). Se d | b enta˜o a soluc¸a˜o e´ u´nica
mod
n
d
. Se (a, n) = 1 enta˜o (3.3) tem uma soluc¸a˜o que e´ u´nica mod n.
Demonstrac¸a˜o: Se x0 e´ uma soluc¸a˜o da equac¸a˜o (3.3) enta˜o existe um
inteiro y0 tal que
ax0 = b+ ny0,
donde a equac¸a˜o
ax− ny = b (3.4)
tem soluc¸a˜o. Reciprocamente, se (x0, y0) e´ uma soluc¸a˜o de (3.4) enta˜o
ax0 ≡ ax0 − ny0 ≡ b mod n
e, portanto, (3.3) tem soluc¸a˜o. Acaba´mos de provar que (3.3) tem soluc¸o˜es
se e so´ se (3.4) tem soluc¸o˜es e a partir de uma soluc¸a˜o de (3.4) obtemos
uma soluc¸a˜o de (3.3). Pelo teorema 2.20, (3.4) tem soluc¸o˜es se e so´ se d | b.
Portanto, (3.3) tem soluc¸o˜es se e so´ se d | b.
Suponhamos agora que (3.4) tem soluc¸o˜es e seja (x0, y0) uma soluc¸a˜o.
Pelo teorema 2.20 qualquer soluc¸a˜o de (3.4) e´ da forma
x = x0 + t
n
d
, y = y0 − ta
d
,
onde t e´ um inteiro. Portanto, qualquer soluc¸a˜o de (3.3) e´ da forma
x = x0 + t
n
d
Como
x0 + t
n
d
≡ x0 mod n
d
,
enta˜o todas as soluc¸o˜es de (3.3) sa˜o congruentes com x0 mod
n
d
, e portanto,
a soluc¸a˜o de (3.3) e´ u´nica mod
n
d
.
A u´ltima parte do teorema resulta imediatamente das duas primeiras
partes. 2
42
Seguidamente vamos ver algumas aplicac¸o˜es deste teorema. A equac¸a˜o
14x ≡ 13 mod 21
na˜o tem soluc¸o˜es, porque (14, 21) = 7 e 7 - 13. Consideremos a equac¸a˜o
9x ≡ 15 mod 21
Aqui temos (9, 21) = 3 e 3 | 15. Portanto, a equac¸a˜o tem uma u´nica soluc¸a˜o
mod 7. Primeiro dividimos tudo por 3. Pelo teorema 3.3, ficamos com
3x ≡ 5 mod 7
Como 5 ≡ 12 mod 7, vemos que a soluc¸a˜o da equac¸a˜o e´ x = 4 e como
(3, 7) = 1, esta soluc¸a˜o e´ u´nica mod 7. Mas a equac¸a˜o original era mod 21,
portanto tem interesse determinar todas as soluc¸o˜es mod 21. Como
4 ≡ 11 ≡ 18 mod 7,
as soluc¸o˜es mod 21 sa˜o 4, 11 e 18.
Em geral, a congrueˆncia
x ≡ a mod n
tem m soluc¸o˜es mod mn, dadas por
x ≡ a, a+ n, a+ 2n, . . . , a+ (m− 1)n mod mn.
3.4 Sistemas de Congrueˆncias
Em seguida estudamos sistemas de congrueˆncias com uma inco´gnita. Supon-
hamos que queremos resolver{
x ≡ 2 mod 4
x ≡ 1 mod 6
Se x ≡ 2 mod 4 enta˜o x ≡ 2 mod 2. Analogamente, x ≡ 1 mod 6 implica
x ≡ 1 mod 2. Mas 2 6≡ 1 mod 2. Portanto, o sistema na˜o tem soluc¸o˜es.
Consideremos, agora, o sistema{
x ≡ 2 mod 4
x ≡ 3 mod 5
43
Facilmente se veˆ que x = −2 e´ uma soluc¸a˜o. Vamos determinar todas as
soluc¸o˜es. A primeira equac¸a˜o e´ satisfeita se e so´ se x = 2 + 4t, onde t e´ um
inteiro. Substituindo na segunda equac¸a˜o, obtemos
2 + 4t ≡ 3 mod 5
donde −t ≡ 1 mod 5 ou seja t ≡ 4 mod 5. Portanto, t = 4 + 5k, para
algum inteiro k. Substituindo no valor de x, obtemos
x = 4(4 + 5k) + 2 = 20k + 18.
Claramente, para cada inteiro k, 20k + 18 e´ soluc¸a˜o do sistema. O pro´ximo
teorema generaliza o processo anterior.
Teorema 3.10. Se (m,n) = 1, enta˜o o sistema{
x ≡ a mod m
x ≡ b mod n
Tem uma e uma so´ soluc¸a˜o mod mn.
Demonstrac¸a˜o: Um inteiro x satisfaz a primeira equac¸a˜o se e so´ se
existe um inteiro t tal que
x = a+mt (3.5)
Agora, a+mt satisfaz a segunda equac¸a˜o se e so´ se
mt ≡ b− a mod n. (3.6)
Como (m,n) = 1, esta u´ltima equac¸a˜o tem uma u´nica soluc¸a˜o, digamos c, i.
e.
t ≡ c mod n.
Portanto, t satisfaz (3.6) se e so´ se existe um inteiro k tal que t = c + nk.
Substituindo em (3.5), verificamos que x e´ soluc¸a˜o do sistema se e so´ se
x = a+m(c+ nk)
= (a+mc) +mnk
Logo, a+mc e´ soluc¸a˜o do sistema e e´ u´nica mod mn. 2
Este resultado e´ um caso especial de um resultado mais geral, que ja´ era
conhecido dos chineses ha´ mais de 2000 anos.
44
Teorema 3.11 (Teorema chineˆs do resto). Sejam m1, . . . ,mk inteiros posi-
tivos que sa˜o primos entre si dois a dois. Enta˜o o sistema
x ≡ a1 mod m1
x ≡ a2 mod m2
...
x ≡ ak mod mk
tem uma u´nica soluc¸a˜o mod (m1m2 · · ·mk).
Demonstrac¸a˜o: Iremos usar o teorema 3.10 (k−1) vezes. Pelo teorema
3.10 as duas primeiras equac¸o˜es teˆm uma u´nica soluc¸a˜o mod (m1m2). Seja
b2 esta soluc¸a˜o, i. e.
x ≡ b2 mod m1m2 (3.7)
A terceira equac¸a˜o e´
x ≡ a3 mod m3. (3.8)
Como, por hipo´tese (m1,m3) = (m2,m3) = 1, enta˜o temos (m1m2,m3) = 1
(porqueˆ?). Para resolver o sistema formado pelas equac¸o˜es (3.7) e (3.8),
podemos mais uma vez utilizar o teorema 3.10. Portanto, ha´ uma u´nica
soluc¸a˜o de (3.7) e (3.8) mod ((m1m2)m3), i. e., ha´ uma u´nica soluc¸a˜o
das treˆs primeiras equac¸o˜es mod (m1m2m3). Continuando desta maneira,
depois de (k − 1) aplicac¸o˜es do teorema 3.10, obtemos uma u´nica soluc¸a˜o
mod (m1m2 · · ·mk) do sistema{
x ≡ bk−1 mod (m1m2 · · ·mk−1)
x ≡ ak mod mk
Esta soluc¸a˜o, digamos x ≡ bk mod (m1m2 · · ·mk), e´ tambe´m a u´nica soluc¸a˜o
do sistema inicial mod (m1m2 · · ·mk). 2
O pro´ximo teorema permitir-nos-a´ encontrar uma soluc¸a˜o do sistema
x ≡ a1 mod m1
x ≡ a2 mod m2
...
x ≡ ak mod mk
sem ter que utilizar diversas vezes o teorema 3.10. Primeiro, precisamos de
definir inverso de um elemento mod n.
45
Definic¸a˜o. Sejam a e n inteiros tais que (a, n) = 1. Ao u´nico inteiro, que e´
soluc¸a˜o da equac¸a˜o
ax ≡ 1 mod n
chamamos inverso de a mod n e denota-mo-lo por a−1 mod n. Este inteiro
existe e e´ u´nico, pelo teorema 3.9
Teorema 3.12. Sejam m1, . . . ,mk inteiros positivos que sa˜o primos entre
si dois a dois. Sejam M = m1m2 · · ·mk, Mi = M
mi
e yi o inverso de Mi
mod mi, para qualquer 1 ≤ i ≤ k. Enta˜o
N = a1M1y1 + a2M2y2 + · · · akMkyk
e´ a u´nica soluc¸a˜o mod M do sistema
x≡ a1 mod m1
x ≡ a2 mod m2
...
x ≡ ak mod mk
Demonstrac¸a˜o: Pelo teorema do resto chineˆs, sabemos que ha´ uma
soluc¸a˜o u´nica mod M do sistema anterior. Portanto, basta-nos provar que
N e´ essa soluc¸a˜o. Seja 1 ≤ i ≤ k. Como (Mi,mi) = 1, enta˜o, pelo teorema
3.9, existe yi tal que Miyi ≡ 1 mod mi. Mais, Mi ≡ 0 mod mj, para
qualquer j 6= i. Enta˜o
N ≡ a1M1y1 + a2M2y2 + · · · akMkyk mod mi
≡ aiMiyi mod mi
≡ aiMi(Mi)−1 mod mi
≡ ai mod mi
Portanto, N e´ soluc¸a˜o da equac¸a˜o x ≡ ai mod mi, para qualquer 1 ≤ i ≤ k.
Donde, N e´ a u´nica soluc¸a˜o do sistema mod M . 2
Exemplo. A primeira menc¸a˜o conhecida do teorema chineˆs do resto e´ o
seguinte problema extra´ıdo do livro Sun Tzu Suan Ching (O Manual Matema´-
tico do Mestre Sun), escrito por Sun Zi, por volta do terceiro se´culo a.C.
46
Temos um certo nu´mero de coisas, mas na˜o sabemos exactamente
quantas sa˜o. Se formarmos grupos de treˆs, sobram duas. Se
formarmos grupos de cinco, sobram treˆs. Se formarmos grupos
de sete, sobram duas. Quantas coisas temos?
Resolver este problema equivale a resolver o sistema
x ≡ 2 mod 3
x ≡ 3 mod 5
x ≡ 2 mod 7
Primeiro iremos usar o processo descrito no teorema do resto chineˆs. Da
primeira equac¸a˜o obtemos x = 2 + 3t, para algum inteiro t. Substituindo na
segunda equac¸a˜o, obtemos 2 + 3t ≡ 3 mod 5, donde 3t ≡ 1 mod 5, i. e.
t ≡ 2 mod 5. Portanto, t = 2 + 5k, para algum inteiro k, e
x = 2 + 3(2 + 5k) = 8 + 15k.
Substituindo este valor na terceira equac¸a˜o, obtemos
8 + 15k ≡ 2 mod 7.
Como 8 ≡ 15 ≡ 1 mod 7, resulta que k ≡ 1 mod 7. Assim, k = 1 + 7s,
para algum inteiro s. Portanto
x = 8 + 15(1 + 7s) = 23 + 105s.
Prova´mos que qualquer soluc¸a˜o do sistema e´ da forma 23 + 105s, para s
inteiro, e a u´nica soluc¸a˜o mod (3 · 5 · 7) e´ 23.
Agora usamos o me´todo descrito no teorema anterior. Aqui M = 105,
M1 = 35, M2 = 21 e M3 = 15. O inverso de 35 mod 3 e´ y1 = −1, o inverso
de 21 mod 5 e´ y2 = 1 e o inverso de 15 mod 7 e´ y3 = 1. Portanto,
N = 2 · 35 · (−1) + 3 · 21 · 1 + 2 · 15 · 1 = 23
Exerc´ıcios
1. Mostre que qualquer inteiro satisfaz pelo menos uma das seguintes con-
grueˆncias:
x ≡ 0 mod 2, x ≡ 0 mod 3, x ≡ 1 mod 4,
x ≡ 1 mod 6, x ≡ 11 mod 12
47
2. Resolva as congrueˆncias
a) 5x ≡ 1 mod 7;
b) 14x ≡ 5 mod 45;
c) 14x ≡ 35 mod 87;
d) 6x ≡ 10 mod 14;
e) 9x ≡ 21 mod 12.
3. Determine os inversos de todos os inteiros invert´ıveis mod 18.
4. Determine os inversos de 1908, 1974, 1998 e 2004 mod 2005.
5. Resolva os sistemas de congrueˆncias
a)
{
x ≡ 2 mod 3
x ≡ 3 mod 4 b)

x ≡ 7 mod 9
x ≡ 13 mod 23
x ≡ 1 mod 2
c)
{
2x ≡ 3 mod 5
4x ≡ 3 mod 7 d)
{
6x ≡ 8 mod 10
15x ≡ 30 mod 55
6. Encontre todos os inteiros positivos menores que 1000 que da˜o resto 1
quando sa˜o divididos por 2, 3, 5 e 7.
7. Um Coronel, apo´s ter sido destacado para comandar um regimento do
exe´rcito, quis saber por quantos efectivos esse regimento era formado;
com esse objectivo mandou-os dispor sucessivamente em colunas de
37 pessoas, tendo ficado a u´ltima coluna com 10 pessoas;
32 pessoas, tendo ficado a u´ltima coluna com 14 pessoas;
27 pessoas, tendo ficado a u´ltima coluna com 5 pessoas.
Sabendo que um regimento tem menos de 10000 efectivos, determine
quantos indiv´ıduos constituem esse regimento.
8. Um casal resolveu ir fazer uma viagem a` volta do mundo. Sabendo que
partiram no dia 1 de Marc¸o de um ano bissexto, num domingo, que
chegaram no dia 6 de Marc¸o, segunda-feira e que demoraram menos de
4 anos, determine quantos dias demorou a viagem usando o teorema
chineˆs do resto.
48
3.5 Me´todo ro´ de Pollard
Nesta secc¸a˜o, vamos analisar outro me´todo de factorizac¸a˜o introduzido por
J. Pollard. Sejam l um inteiro e f uma func¸a˜o aleato´ria de S = {0, 1, . . . , l}
para S. Seja x0 um elemento aleato´rio e considere-se a sequeˆncia
x0, x1 = f(x0), x2 = f(x1), . . . .
Como S e´ finito, a sequeˆncia ira´ tornar-se ciclica ao fim de um certo nu´mero
de termos. Se fizermos um diagrama que mostre este comportamento, ele
assemelhar-se-a´ a ρ, da´ı a origem do nome do me´todo.
Seja n um inteiro composto. O primeiro passo do me´todo ro´, consiste em
escolher uma func¸a˜o f de Z/nZ para Z/nZ que seja facil determinar f(x).
Costuma-se usar polino´mios com coeficientes inteiros, e. g. f(x) = x2 + 1.
Em seguida, toma-se um inteiro positivo x0, e. g. x0 = 1 ou x0 = 2.
Calculam-se as sucessivas iterac¸o˜es xk = f(xk−1) mod n. Depois fazem-
se comparac¸o˜es entre diferentes xi’s, esperando encontrar dois que sejam
diferentes mod n mas que sejam iguais mod l para algum divisor pro´prio l
de n. Quando encontrarmos xj e xk nestas condic¸o˜es (i. e. xj ≡ xk mod l),
temos que (xj − xk, n) e´ um divisor pro´prio de n. Assim como esta´, este
me´todo ira´ tornar-se moroso, pois ao fim de k iterac¸o˜es temos de comparar
aproximadamente k2 pares de valores. Note que se xj ≡ xk mod l e sendo
m ≥ 0, temos
xj+m ≡ xk+m mod l
Portanto, em vez de efectuar todas as comparac¸o˜es poss´ıveis podemos apenas
fazer uma comparac¸a˜o em cada iterac¸a˜o. Por exemplo, podemos calcular
so´mente
(x2i − xi, n)
em cada iterac¸a˜o i. Podemos tambe´m calcular, na iterac¸a˜o k com 2r ≤ k <
2r+1, o ma´ximo divisor comum
(xk − xj, n)
onde j = 2r − 1.
Exemplo. Vamos factorizar 4087 usando f(x) = x2 + 1 e x0 = 3. Obtemos
49
sucessivamente
x1 = 10, x2 = 101 (101− 10, 4087) = 1
x2 = 101, x4 = 1263 (1263− 101, 4087) = 1
x3 = 2028, x6 = 889 (2028− 89, 4087) = 67
Portanto, 67 | 4087. Dividindo, obtem-se 4087 = 67 · 61.
Exemplo. Sejam n = 845651, f(x) = x2 + x + 1 e x0 = 2. Verifica-se que
(x10 − x7, n) = 571. Portanto, n = 571 · 1481.
Exerc´ıcios
1. Utilize o me´todo ro´ de Pollard para factorizar cada um dos inteiros
133, 1189, 1927, 8131, 36287 e 48227.
2. Utilize o me´todo ro´ de Pollard com as func¸o˜es e x0 indicados, para
factorizar os inteiros n indicados. Em cada caso compare xk com xj
onde 2r ≤ k < 2r+1 e j = 2r − 1.
a) x2 − 1, x0 = 5, n = 7031;
b) x2 + 1, x0 = 1, n = 8051;
c) x3 + x+ 1, x0 = 1, n = 2701;
3.6 Armazenamento de ficheiros
Uma repartic¸a˜o de financ¸as pretende armazenar num computador um ficheiro
para cada uma das pessoas registadas naquele domic´ılio fiscal. A identificac¸a˜o
(chave) utilizada para cada ficheiro e´ o nu´mero de contribuinte. Como o
nu´mero de contribuinte tem 9 algarismos, seria impractica´vel reservar lo-
calizac¸o˜es de memo´ria para cada um dos poss´ıveis nu´meros de contribuinte.
Nesta secc¸a˜o, iremos descrever um me´todo sistema´tico de armazenar ficheiros
usando um razoa´vel nu´mero de localizac¸o˜es. Va´rios me´todos para resolver
este problema foram desenvolvidos utilizando Func¸o˜es de mistura. Uma
func¸a˜o de mistura atribui a` chave de cada ficheiro uma localizac¸a˜o particu-
lar. Ha´ va´rios tipos de func¸o˜es de mistura, mas as mais utilizadas envolvem
aritme´tica modular, que iremos passar a descrever.
50
Definic¸a˜o. Seja k a chave do ficheiro a ser armazenado e seja m um inteiro
positivo. Definimos func¸a˜o de mistura h por
h(k) ≡ k mod m,
onde 0 ≤ h(k) < m.
De forma a que as chaves sejam distribu´ıdas de uma forma razoa´vel,
entre as poss´ıveis m localizac¸o˜es, devemos ter cuidado na escolha do inteiro
m. Por exemplo deve-se escolher m de modo a evitar na medida do poss´ıvel,
que duas diferentes chaves k1 e k2 sejam enviadas para a mesma localizac¸a˜o.
Por exemplo, se m = 111, como m | 103 − 1, os nu´meros de contribuinte
273321412 e 273425308 sa˜o enviados para o mesmo s´ıtio:
h(273321412) ≡ 412 + 321 + 273 ≡ 7 mod 111
e
h(273425308) ≡ 308 + 425 + 273 ≡ 7 mod 111.
Para evitar estas dificuldades, m deve ser um nu´mero primo pro´ximo do
nu´mero de localizac¸o˜es dispon´ıveis para o armazenamento dos ficheiros. Por
exemplo, se tivermos 5000 localizac¸o˜es dispon´ıveis e pretendermos armazenar
2000 chaves, pode-se utilizar m= 4969.
Mesmo sendo m um primo podemos ainda assim obter coliso˜es, i. e.
duas chaves diferentes serem enviadas para o mesmo s´ıtio. Um processo para
ultrapassar as coliso˜es que tambe´m evita que os ficheiros fiquem demasiado
pro´ximos e´ utilizar dupla mistura: Tal como antes, escolhemos a func¸a˜o de
mistura
h(k) ≡ k mod m,
onde 0 ≤ h(k) < m, m primo. Seja g a segunda func¸a˜o de mistura, definida
por
g(k) ≡ k + 1 mod m− 2,
onde 0 < g(k) ≤ m − 2. Como m e´ primo, (g(k),m) = 1. Seguidamente
consideramos a sequeˆncia
hj(k) ≡ h(k) + jg(k) mod m,
com 0 ≤ hj(k) < m. O facto de (g(k),m) = 1 garante-nos que todas as
poss´ıveis localizac¸o˜es sera˜o alcanc¸adas quando j toma os valores 0, 1, . . . , n−
1. Idealmente, m− 2 tambe´m deve ser primo.
51
Exemplo. Consideremos m = 4969 e assim m−2 = 4967. A seguinte tabela
indica-nos as localizac¸o˜es de va´rias chaves usando dupla mistura
Nu´mero de Contribuinte h0(k) h1(k) h2(k)
344 401 659 269
325 510 778 1526
212 228 844 2854
329 938 157 1526 1741
147 900 151 3960
372 500 191 4075
134 367 980 2376
546 332 190 578
509 496 993 578 2580
132 489 973 1526 1742 1958
Exerc´ıcios
1. Utilizando os dados do exemplo, determine as localizac¸o˜es das pes-
soas com os nu´meros contribuinte 137612044, 505576452, 157170996 e
131220418.
2. Um parque de estacionamento tem 101 lugares. Uma pessoa tem de
pagar semestralmente o parque comprando no in´ıcio do semestre um
passe. Sa˜o vendidos 500 passes, mas a cada momento so´ sa˜o esperados
de 50 a 75 automo´veis. Elabore uma func¸a˜o de mistura e uma pol´ıtica
para resoluc¸a˜o de coliso˜es de modo a atr´ıbuir um lugar a cada utilizador
baseado nos 4 algarismos da matr´ıcula.
3.7 Detecc¸a˜o de erros
As congrueˆncias tambe´m sa˜o usadas para identificar erros de introduc¸a˜o de
dados.
Exemplo. Os bilhetes de identidade teˆm um algarismo que detecta se ha´ um
erro no nu´mero de BI. Se um BI tem o nu´mero a8a7 · · · a2a1, o algarismo de
52
verificac¸a˜o a0 e´ dado pela congrueˆncia
8∑
i=0
(i+ 1)ai ≡ 0 mod 11.
Infelizmente, nos nossos Bilhetes de identidade, esta congrueˆncia pode falhar
devido a um erro matema´tico pate´tico na idealizac¸a˜o deste sistema de veri-
ficac¸a˜o de erros. Este erro ocorre quando a soluc¸a˜o da congrueˆncia e´ a0 = 10,
porque, neste caso, foi introduzido um 0 como algarismo de verificac¸a˜o. A
raza˜o deste erro pode ter a ver com o facto de so´ termos 10 algarismos e ne-
cessitarmos de representar a0 = 10 com um so´ algarismo. Se fosse utilizado
de X ou A para representar este algarismo, poderia criar confusa˜o entre as
pessoas.
Exemplo. Em va´rios pa´ıses europeus os nu´meros de passaporte teˆm um
algarismo de verificac¸a˜o, a0. Se o nu´mero e´ a9a8 . . . a2a1a0, que e´ obtido pela
congrueˆncia
a0 ≡ 7a1 + 3a2 + a3 + 7a4 + 3a5 + a6 + 7a7 + 3a8 + a9 mod 10.
Nos passaportes existem tambe´m algarismos de verificac¸a˜o para a data de
nascimento e data de validade.
Exemplo. O ISBN (International Standard Book Number) e´ um nu´mero que
consiste de 10 algarismos, e escreve-se da forma a9 − a8a7a6 − a5a4a3a2a1 −
a0. O primeiro algarismo identifica a l´ıngua, os treˆs algarismos seguintes
identificam a editora, os cinco algarismos seguintes e´ o nu´mero atribu´ıdo
pela editora a um livro particular, e o u´ltimo algarismo a0 e´ um algarismo
de verificac¸a˜o. Este algarismo e´ calculado utilizando a congrueˆncia
a0 ≡
9∑
i=1
(10− i)ai mod 11.
Se a congrueˆncia da´ 10 enta˜o escreve-se a0 = X.
Este sistema de detecc¸a˜o de erros, permite detectar se ha´ um erro num
u´nico algarismo ou se houve troca de dois algarismos. Seja a9a8 · · · a1a0 um
ISBN va´lido e que este nu´mero foi introduzido como b9b8 . . . b1b0. Sabemos
que
9∑
i=0
(10− i)ai ≡ 0 mod 11.
53
Se ha´ um erro num u´nico algarismo, temos, para algum j, ai = bi para i 6= j
e aj = bj + c para algum −10 ≤ c ≤ 10, com c 6= 0. Enta˜o
9∑
i=0
(10− i)bi =
9∑
i=0
(10− i)ai + jc ≡ jc 6≡ 0 mod 11,
porque 11 6= ja.
Exerc´ıcios
1. Mostre que o sistema de detecc¸a˜o de erros do ISBN detecta troca de
dois algarismos.
2. Mostre que o sistema de detecc¸a˜o de erros dos passaportes detecta a
troca dos algarismos ai e aj se e so´ se |ai − aj| 6= 5.
3. Verifique se o seu nu´mero de BI verifica o sistema de detecc¸a˜o men-
cionado.
4. Determine se os seguintes nu´meros de ISBN sa˜o va´lidos:
0− 394− 38049− 5, 1− 09− 231221− 3, 0− 404− 50874−X.
5. O governo da Noruega atribui um nu´mero de registo a cada cidada˜o
noruegueˆs com 11 algarismos, utilizando um processo criado pelo mate-
ma´tico noruegueˆs E. Selmer (da a´rea de Teoria dos Nu´meros). Os
primeiros seis algarismos x1, . . . x6 representam a data de nascimento,
os treˆs algarismos seguintes x7, x8 e x9 identificam cada pessoa nascida
naquele dia, os algarismos x10 e x11 sa˜o algarismos de verificac¸a˜o, de-
terminados pelas congrueˆncias
x10 ≡ 8x1 + 4x2 + 5x3 + 10x4 + 3x5 + 2x6 + 7x7 + 6x8 + 9x9 mod 11
e
x11 ≡ 6x1+7x2+8x3+9x4+4x5+5x6+6x7+7x8+8x9+9x10 mod 11
a) Determine os algarismos de verificac¸a˜o que completam o nu´mero
110491238;
b) Mostre que este processo detecta todos os erros num u´nico algar-
ismo.
54
Cap´ıtulo 4
Func¸a˜o de Euler
4.1 Sistema Reduzido de Res´ıduos
Na u´ltima secc¸a˜o vimos que a equac¸a˜o ax ≡ 1 mod n e´ solu´vel se e so´ se
(a, n) = 1. Os nu´meros que sa˜o primos com n teˆem outras propriedades
interessantes. Nesta secc¸a˜o iremos estudar estes nu´meros.
Definic¸a˜o. Seja S um sistema completo de res´ıduos mod n. Ao conjunto
T formado pelos membros de S que sa˜o primos com n chamamos sistema
reduzido de res´ıduos mod n.
Em seguida iremos definir a func¸a˜o de Euler, que conta o nu´mero de
elementos de um sistema reduzido de res´ıduos mod n.
Definic¸a˜o. Seja n ≥ 1. O nu´mero de inteiros positivos menores ou iguais a
n que sa˜o primos com n e´ denotado por φ(n). Esta func¸a˜o de n e´ chamada
func¸a˜o φ de Euler
Se a ≡ b mod n e a e´ primo com n enta˜o tambe´m b e´ primo com n.
Se p e´ primo enta˜o qualquer inteiro positivo menor que p e´ primo com p,
portanto, φ(p) = p− 1.
Teorema 4.1. Suponhamos que (a, n) = 1. Se a1, a2, . . . , an forma um sis-
tema completo de res´ıduos enta˜o aa1, aa2, . . . , aan tambe´m forma um sis-
tema completo de res´ıduos. Se a1, a2, . . . , aφ(n) forma um sistema reduzido
de res´ıduos enta˜o aa1, aa2, . . . , aaφ(n) tambe´m forma um sistema reduzido de
res´ıduos.
55
Demonstrac¸a˜o: Vamos comec¸ar por provar a primeira parte. Como
(a, n) = 1, enta˜o aai ≡ aaj mod n implica ai ≡ aj mod n, mas por definic¸a˜o
de sistema completo de res´ıduos, isto na˜o pode acontecer. Assim, aai 6≡ aaj
mod n para i 6= j. O facto de a ser primo com n tambe´m implica que existe
c tal que
ac ≡ 1 mod n.
Seja d um inteiro. Enta˜o cd ≡ ai mod n, para algum 1 ≤ i ≤ n. Donde,
d ≡ acd ≡ aai mod n.
Portanto, aa1, aa2, . . . , aan tambe´m forma um sistema completo de res´ıduos.
tambe´m forma um sistema reduzido de res´ıduos.
Agora, se (a, n) = 1 e (ai, n) = 1 enta˜o (aai, n) = 1. Portanto, os inteiros
aa1, aa2, . . . , aaφ(n) tambe´m formam um sistema reduzido de res´ıduos. 2
4.2 Pequeno teorema de Fermat e Teorema
de Euler
O u´ltimo resultado tem as seguintes consequeˆncias
Teorema 4.2 (Teorema de Euler). Se (a, n) = 1 enta˜o
aφ(n) ≡ 1 mod n
Demonstrac¸a˜o: Seja a1, a2, . . . , aφ(n) um sistema reduzido de res´ıduos.
Pelo teorema anterior, aa1, aa2, . . . , aaφ(n) tambe´m forma um sistema re-
duzido de res´ıduos. Mais, para cada 1 ≤ i ≤ φ(n), aai ≡ aj mod n, para
algum 1 ≤ j ≤ n. Portanto,
aa1aa2 · · · aaφ(n) ≡ a1a2 · · · aφ(n) mod n
Como (a1a2 · · · aφ(n), n) = 1 enta˜o, pelo teorema 3.3
aφ(n) ≡ 1 mod n
2
56
Teorema 4.3 (Pequeno Teorema de Fermat). Se p e´ primo enta˜o
ap ≡ a mod p
para qualquer inteiro a.
Demonstrac¸a˜o: Se p | a enta˜o ap ≡ 0 mod p e a