N3 Teoria de Números 210325

.
Material Didático
Teoria de Números
Nível 3
Última Atualização: 25 de março de 2021
2
Sumário
1 Divisibilidade e Algoritmo de Divisão 5
2 Máxim Divisor Comum, Mínimo Múltiplo Comum 13
3 Teorema Fundamental da Aritmética 23
4 Resultados de Números Primos 31
5 Equações Diofantinas 39
6 Congruências 49
7 Teorema Chinês do Resto 57
8 Pequeno Teorema de Fermat 65
Referências Bibliográficas 73
3
4 POTI/TOPMAT
Aula 1
Divisibilidade e
Algoritmo de Divisão
Leonardo Gonçalves Fischer
Priscilla Pereira de Souza
No conjunto dos números inteiros, a equação bx = a nem sem-

pre admite solução. Isso significa simplesmente que nem sempre a
divisão é exata. Se existir uma solução nessas condições, recaímos
no caso em que b divide a, ou, mais formalmente:
Definição 1.1. Divisibilidade:
Dados dois números inteiros a, b, dizemos que b divide a se existe c
inteiro tal que a = bc. Neste caso, b é dito divisor de a, e denotare-
mos simplesmente b|a
A divisibilade apresenta algumas propriedades que merecem ser
mencionadas, as quais enunciaremos agora:
Proposição 1.1. Sejam a, b, c, d números inteiros, e cada divisor
um número diferente de zero. Então valem:
1. Limitação: Se a|b, então, ou b = 0 ou |a| ≤ |b|;
2. Transitividade: Se a|b e b|c, então a|c;
3. Se a|b e a|c, então, para quaisquer m, n ∈ Z, a|(mb + nc).
5
6 POTI/TOPMAT
Um importante resultado de divisibilidade que merece ser men-

cionado é apresentado no exemplo a seguir:
Exemplo 1.1. Para quaisquer x, y, vale que:
xn −y n = (x−y)(xn−1 +xn−2 y+xn−3 y 2 +. . .+x2 y n−3 +xy n−2 +y n−1 )
Portanto, para quaisquer x, y ∈ Z, se x 6= y, segue que x − y|xn − y n .

Apresentamos a seguir dois casos particulares da igualdade acima
• Se n é impar, vale que:
xn + y n = (x + y)(xn−1 − xn−2 y + . . . − xy n−2 + y n−1 )
De fato, basta tomar xn + y n = xn − (−y)n
• Se n = 2k é par, vale que:
x2k − y 2k = (x2 − y 2 )(x2k−2 + x2k−4 y 2 + . . . + x2 y 2k−4 + y 2k−2 )
Tomando ainda x2 − y 2 = (x − y)(x + y), podemos fazer mais

uma decomposição no número acima:
x2k −y 2k = (x−y)(x+y)(x2k−2 +x2k−4 y 2 +. . .+x2 y 2k−4 +y 2k−2 )
Nos casos em que não existe um inteiro satisfazendo tal condição,

isto é, se b não divide a, ainda assim, em geral, podemos efetuar um
processo de divisão com resto. Por exemplo, se a = 123, b = 5,
fazemos simplesmente:
123| 5
−10 24
23
−20
3
Neste exemplo, temos que 5 "cabe"24 vezes em 123, deixando

um resto 3 no processo de divisão.
Aula 1 - Divisibilidade e Algoritmo de Divisão 7
Certamente, para aplicar tal processo de divisão, precisamos que b 6=

0. Com essa condição, para qualquer inteiro a conseguimos garantir
sempre que a divisão com resto de a por b está bem definida. Tal
resultado é conhecido como Algoritmo da Divisão, que enunciamos
a seguir:
Teorema 1.1. Algoritmo da Divisão
Sejam a e b inteiros, com b 6= 0. Então existe um único par de
inteiros não negativos (q,r) tal que:
a = bq + r, 0 ≤ r < |b|
Neste par, o número q é chamado quociente e r o resto da divisão

de a por b.
Apresentamos a seguir uma aplicação do algoritmo de divisão na
resolução de problemas:
Exemplo 1.2. Seja a um inteiro. Mostre que se a é da forma
3k + 2, k ∈ Z então a não é o quadrado de outro inteiro.
Solução:
Seja b, q ∈ Z. Analisemos o quadrado de b com base no resto de b
na divisão por 3:
• se b = 3q : b2 = (3q)2 = 3(3q 2 ) + 0
• se b = 3q + 1 : b2 = (3q + 1)2 = 3(3q 2 ) + 3(2q) + 1 =

3(3q 2 + 2q) + 1
• se b = 3q + 2 : b2 = (3q + 2)2 = 3(3q 2 ) + 3(4q) + 3 · 1 + 1 =

3(3q 2 + 4q + 1) + 1
Com isso concluímos que os únicos restos possíveis para o quadrado
de um inteiro na divisão por 3 são 0 e 1. Ou seja, se a é da forma
3k + 2, k ∈ Z, então a não é o quadrado de outro inteiro.
Como o leitor pode observar, da maneira como definimos divi-
sibilidade, temos que b|a precisamente quando o resto do algoritmo
da divisão de a por b é zero.
8 POTI/TOPMAT
Para avaliar se um certo número inteiro diferente de zero divide

outro inteiro, sempre podemos efetuar o processo de divisão e verifi-
car se o resto é zero. Contudo, alguns números admitem estratégias
alternativas, em geral mais econômicas, para avaliarmos se eles divi-
dem algum número inteiro dado. Essas estratégias são chamadas de
Critérios de divisibilidade. Enunciaremos a seguir alguns critérios
de divisibilidade pelos números de 2 a 11:
• Critério de Divisibilidade por 2: Um número é divisível

por 2 se e somente se seu algarismo das unidades for par;
E.g.: 1234 é divisível por 2, pois seu último dígito, 4, é par.

por 3 se e somente se a soma de seus dígitos também for;
E.g.: 543 é divisível por 3, pois 5 + 4 + 3 = 12 é múltiplo de 3.

por 4 se e somente se seus dois últimos algarismos, das dezenas
e das unidades, formam um número divisível por 4;
E.g.: 432116 é divisível por 4, pois seus dois últimos dígitos
são 16, um múltiplo de 4.

por 5 se seu algarismo das unidades for 0 ou 5;
E.g. : 3115 é divisível por 5, pois seu dígito das unidades é 5

por 6 se e somente se satisfaz simultaneamente os critérios
para 2 e 3;
E.g. : 3132 é múltiplo de 6, pois é par e 3 + 1 + 3 + 2 = 9.

por 7 se e somente se, ao apagarmos o último dígito e subtrair-
mos seu dobro do número resultante, obtivermos um número
múltiplo de 7.
E.g. : 434 é divisível por 7, pois 43 − (4.2) = 43 − 8 = 35 é
múltiplo de 7.
• Critério de Divisibilidade por 8: Um número é divisí-

vel por 8 se seus três últimos algarismos formam um número
divisível por 8

por 9 se e somente se a soma de seus algarismos é um número
múltiplo de 9;

por 10 se simplesmente seu último algarismo é nulo;

por 11 se e somente se a diferença entra a soma dos algarismos
de posição ímpar e a soma dos algarismos de posição par for
múltipla de 11.
Problemas Propostos
Os problemas estão classificados por nível de dificuldade:
N F
Fácil Médio Difícil Desafio
1. Para todo inteiro a, prove que 4 não divide (a2 + 2).
2. Mostre que 3|7n − 4n , para todo n ≥ 1.
3. Prove que se a e b são ímpares, então 8|(a2 − b2 ).
4. Mostre que se 7|3a + 2b então 7|4a − 2b.
5. N Mostre que 9 divide n · 4n+1 − (n + 1) · 4n + 1
6. N Prove o critério de divisibilidade por 7.
7. N Prove o critério de divisibilidade por 9.
8. N Mostre que se 19|3x + 7y então 19|43x + 75y.
9. N Sejam a = bq+r = (b+1)q 0 +r0 , com a, b positivos, 0 ≤ r < b,

e 0 ≤ r0 < (b + 1). Provar que q = q 0 se, e somente se, r ≥ q
10 POTI/TOPMAT
10. N Prove que se f (x) é um polinômio de coeficientes inteiros e

a e b são inteiros quaisquer, então a − b|f (a) − f (b).
11. Prove que nenhum inteiro da sequência 11, 111, 1111, . . . é

um quadrado perfeito.
12. Encontre todos os inteiros positivos n tais que 2n2 + 1|n3 +

9n − 17.
13. Seja n > 1 e k um inteiro positivo. Prove que (n−1)2 |(nk −1)
se, e somente se, (n − 1)|k.
14. (OBM 2011) Qual é o maior inteiro positivo n tal que

(2011!)! é divisível por ((n!)!)! ?
15. Defina uma função dos inteiros neles mesmos por f (x) =
xn + c, com ∈ {−1, 1} e c um inteiro qualquer. Mostre que
f (x) − f (y)|xm − y m sempre que n|m.
16. (CONE SUL, Prova de Seleção, 2015) Para cada número

natural n, denotamos g(n) o maior divisor ímpar de n. Calcule
a soma dos 22015 termos:
g(1) + g(2) + g(3) + . . . + g(22015 )
17. (OBM 2000) É possível encontrar duas potências de 2, dis-

tintas e com o mesmo número de algarismos, tais que uma
possa ser obtida através de uma reordenação dos dígitos da
outra?
18. (OBM 2005) Prove que a soma 1k + 2k + . . . + nk , onde n é

um inteiro positivo e k é ímpar, é divisível por 1 + 2 + . . . + n.
19. (IMO 2011) Seja f uma função do conjunto dos inteiros no

conjunto dos inteiros positivos. Sumponha que, para quaisquer
dois inteiros m e n, a diferença f (m) − f (n) é divisível por
f (m − n). Prove que, para todos os inteiros m, n com f (m) ≤
f (n), o número f (n) é divisível por f (m).
20. F (IMO 2007) Sejam a e b inteiros positivos. Mostre que, se

4ab − 1 divide (4a2 − 1)2 , então a = b.
12 POTI/TOPMAT
Aula 2
Máxim Divisor Comum,

Mínimo Múltiplo Comum
Aqui, prosseguiremos com o estudo de divisibilidade a partir de

outros conceitos elementares da teoria de números. Salvo menção
em contrário, assumiremos nesta aula sempre a, b inteiros não simul-
taneamente nulos.
Máximo Divisor Comum
Primeiramente, dizemos que um inteiro d é um divisor comum

de a e b se c|a e c|b. Podemos recolher todos esses divisores comuns
de a e b em um conjunto que denotaremos D(a, b). Pelas propri-
edades de divisibilidade, sabemos que, se a 6= 0, c|a implica que
|c| ≤ |a|, logo D(a, b) é limitado. Ainda, para quaisquer a, b não
simultaneamente nulos, temos que pelo menos 1 divide ambos, logo
1 ∈ D(a, b), e o conjunto dos divisores comuns é não vazio. Por
conta dessas propriedades, faz sentido falar de um maior elemento
do conjunto D(a, b), o que motiva a seguinte definição:
Definição 2.1. Denominamos máximo divisor comum (mdc) de a
13
14 POTI/TOPMAT
e b o maior de seus divisores comuns. Assim:
mdc(a, b) = maxD(a, b)
Diante deste conceito, uma dúvida natural é o modo de calculá-

lo para um dado par de inteiros. O algoritmo da divisão apresentado
anteriormente permite a elaboração de um método capaz de deter-
minar o mdc de dois inteiros dados. Este método é denominado
Algoritmo de Euclides
Primeiro, verifiquemos brevemente o seguinte resultado:
Lema 2.1. Sejam a, b inteiros, com b 6= 0, e q e r os respectivos
quociente e resto da divisão de a por b. Então mdc(a, b) = mdc(b, r).
Demonstração. A divisão de a por b resulta na expressão:
a = bq + r
Basta verificar que todo divisor comum de a e b divide r, e, recipro-

camente, todo divisor comum de b e r divide a. Seja m ∈ D(a, b).
Então, pelas propriedades de divisibilidade, temos que m|a, m|b im-
plica m|a − bq, mas como a − bq = r, resulta que m também divide
o resto. A recíproca se prova de modo análogo.
Como todos divisores comuns D(a, b) e D(b, r) coincidem, seus
máximos também devem coincidir, verificando o resultado.

O Algoritmo de Euclides, também por vezes denominado Algo-

ritmo das divisões sucessivas, se baseia em aplicações reiteradas da
divisão euclidiana. Assim, começamos dividindo a por b, e obtendo
um resto r1 . Na sequência, se r1 6= 0, efetuamos a divisão euclidiana
de b por r1 , resultando em um resto r2 . Como os restos da sequência
são inteiros não-negativos, dispostos em ordem decrescente, eventu-
almente o algoritmo alcança o resto 0. Pelo lema, o menor resto rn
maior que 0 será justamente o mdc(a, b).
Aula 2 - Máxim Divisor Comum, Mínimo Múltiplo Comum 15
Exemplo 2.1. Calculando o mdc(1001, 109), obtemos as seguintes

divisões:
1001 = 109 · 9 + 20
109 = 20 · 5 + 9
20 = 9 · 2 + 2
9=2·4+1
2=1·2
O último resto não-nulo é 1, logo mdc(1001, 109) = 1.
Mínimo Múltiplo Comum
Assim como, dados dois inteiros não-nulos, é possível tratar dos

números que dividem ambos, é natural uma definição que abranja
os números que são divididos por dois inteiros não-nulos quaisquer.
Um número c é dito múltiplo comum de dois inteiros não-nulos a e
b se temos que a|c e b|c.
Denotaremos o conjunto de múltiplos comuns de a e b por M (a, b).
Note que este conjunto não é vazio, pois pelo menos a · b ∈ M (a, b).
Porém, ao contrário do caso dos divisores comuns, o conjunto de
múltiplos comuns é infinito. Ainda assim, se forem considerados
apenas os elementos positivos de M (a, b), pelo Princípio da Boa
Ordem se segue que entre estes existe um menor elemento, o que
motiva a seguinte definição:
Definição 2.2. Denominamos mínimo múltiplo comum (mmc) de
a e b o menor de seus múltiplos comuns positivos, isto é:
mmc(a, b) = minM + (a, b)
em que M + (a, b) é o conjunto de múltiplos comuns c de a e b tais

que c > 0.
Teorema de Bachet-Bézout
16 POTI/TOPMAT
Dizemos que um número inteiro c é combinação inteira de dois

inteiros a,b, se existem x, y ∈ Z tais que se verifique a equação:
c = ax + by
O Teorema de Bachet-Bézout, que enunciamos a seguir, garante
que sempre é possível escrever o mdc de dois números inteiros como
uma combinação inteira desses, isto é:
Teorema 2.1. Sejam a e b inteiros. Então existem x e y inteiros
tais que:
ax + by = mdc(a, b)
Duas consequências importantes desse teorema são:
Corolário 2.1. Dados a, b ∈ Z, a equação:
ax + by = c
admite solução inteira se, e somente se, mdc(a, b)|c
Corolário 2.2. Sejam a, b, c ∈ Z tais que a|bc. Se mdc(a, b) = 1,
então a|c.
Como vimos, equação ax+by = mdc(a, b) sempre admite solução
inteira. Contudo, essa solução não é única. No exemplo a seguir,
apresentamos um algoritmo para encontrar o conjunto de todas as
soluções inteiras desse tipo de problema.
Exemplo 2.2. Encontre todos os x, y ∈ Z tais que 1001x + 109y =
mdc(1001, 109).
Solução:
Fazemos as divisões sucessivas para o cálculo de mdc(1001, 109) = 1
utilizando o Algoritmo de Euclides. Em seguida, isolamos os restos:
1001 = 109 · 9 + 20
109 = 20 · 5 + 9
20 = 9 · 2 + 2
9=2·4+1
2=1·2
Se isolarmos os restos nas equações acima, obteremos as seguin-

tes igualdades:
20 = 1001 − 109 · 9
9 = 109 − 20 · 5
2 = 20 − 9 · 2
1=9−2·4
Note que podemos efetuar sucessivas substituições na equação 1 =
9 − 2 · 4 e expressar 1 como combinação linear de 1001 e 109. Isso
pode ser feito da seguinte forma:
Substituindo o 2:
1 = 9 − (20 − 9 · 2) · 4 = 9 · 9 − 4 · 20
Substituindo o 9:
1 = 9 · (109 − 20 · 5) − 4 · 20 = 9 · 109 − 49 · 20
Substituindo o 20:
1 = 9 · 109 − 49 · (1001 − 109 · 9) = 1001(−49) + 109(450)

Logo, uma solução da equação 1001x + 109y = 1 é (x0 , y0 ) =
(−49, 450).
Para encontrar as demais, escrevemos o lado direito desta equação
utilizando a solução particular que acabamos de encontrar:
1001x + 109y = 1001x0 + 109y0 ⇔ 1001(x − x0 ) = −109(y − y0 )

Como mdc(1001, 109) = 1 temos, pelo Teorema de Euclides,
que 1001|y − y0 , ou seja, y − y0 = 1001t, para algum t ∈ Z.
Substituindo temos:
1001(x − x0 ) = −109.1001t ⇔ 1001(x − x0 ) = 1001.(−109t)

⇔ x − x0 = −109t ⇔ x = x0 − 109t
18 POTI/TOPMAT
De maneira análoga podemos obter que y = y0 + 1001t

Assim, as soluções da equação dada são todos os pontos da reta
1001x + 109y = 1 da forma (x, y) = (x0 − 109t, y0 + 1001t) =
(−49, 450) + (−109, 1001)t com t ∈ Z.
Para concluir, apresentamos um resultado que caracteriza a re-
lação entre o máximo divisor comum e o mínimo múltiplo comum
de dois números dados. Por simplicidade, enunciaremos o resultado
para números naturais, podendo ser facilmente generalizado para os
inteiros tomando os valores absolutos adequados.
Teorema 2.2. Sejam a, b ∈ N∗ , então:
mdc(a, b).mmc(a, b) = ab
Demonstração. Seja d = mdc(a, b). Então podemos escrever a =

a1 d, b = b1 d, com a1 , b1 inteiros tais que mdc(a1 , b1 ) = 1. Agora
considere o número:
ab
x=
d
Temos, por um lado, que x = a1 b, por outro, que x = ab1 . Portanto
a|x, b|x e x é múltiplo comum de a, b. Verifiquemos agora que x é o
menor inteiro positivo nessas condições. Seja m ∈ N∗ um múltiplo
comum qualquer de a e b. Então, de a|m segue que existe q ∈ N
com m = aq = a1 dq. Por sua vez, como b|m, temos que b1 d|a1 dq,
e portanto, b1 |a1 d. Dado que a1 , b1 sãp coprimos, temos que b1 |q.
Escrevemos então q = b1 c. Logo m = aq = (a1 d)(b1 c) = (a1 db1 )c =
xc. Logo x divide qualquer outro múltiplo comum positivo de a e b.
Assim, por limitação, x deve ser o menor múltiplo comum.
Problemas Propostos
N F
1. Usar o Algoritmo de Euclides para obter números r e s

satisfazendo:
• mdc(56, 72) = 56r + 72s

• mdc(24, 138) = 24r + 138s
2. Mostre que 215 − 1 e 210 + 1 são primos entre si.
3. Mostre que quaisquer dois termos consecutivos da sequência

de Fibonacci são coprimos.
4. Sejam a, b, c inteiros. Prove que:
(a) mdc(−a, b) = mdc(a, −b)
(b) mdc(a, b) = mdc(a, a + b)
5. N Prove a seguinte proposição:

A equação ax + by = c admite solução inteira em x e y se, e
somente se, mdc(a, b)|c.
6. N Prove que se mdc(a, b) = 1 e a|bc, então a|c.
7. N Prove que se mdc(a, b) = 1, então mdc(ac, b) = mdc(c, b).
8. N Para todo n ∈ Z, n 6= 0, −1, calcular:
• mmc(n, n + 1);
• mmc(2n − 1, 2n + 1)
• mmc(nc, (n + 1)c), c ∈ Z∗
9. N (OBM 2011) Qual é o maior valor possível do mdc de dois

números distintos pertencentes ao conjunto {1, 2, 3, . . . , 2011}?
10. N (OBM 2011) Os inteiros positivos 30, 72 e N possuem a

propriedade de que o produto de quaisquer dois é divisível
pelo terceiro. Qual o menor valor possível de N ?
11. (OBMEP - Banco de Questões 2015) Em uma lousa são

escritos os 2014 inteiros positivos de 1 até 2014. A operação
permitida é escolher dois números a e b, apagá-los e escrever
20 POTI/TOPMAT
em seus lugares os números mdc(a, b) e mmc(a, b). Essa ope-

ração pode ser feita com quaisquer dois números que estão na
lousa, incluindo os números que resultaram de operações ante-
riores. Determine qual a maior quantidade de números 1 que
podemos deixar na lousa.
12. Sejam an = 100 + n2 e dn = mdc(an , an+1 ). Calcular dn

para todo n.
13. Demonstrar que se mdc(a, 2n+1 ) = 2n e mdc(b, 2n+1 ) = 2n ,

então mdc(a + b, 2n+1 ) = 2n+1 .
14. Demonstrar que, se a, b, c, d, m, n são inteiros tais que ad −

bc = 1, mn 6= 0, então:
mdc(am + bn, cm + dn) = mdc(m, n)
15. Demonstrar que mdc(2a − 1, 2b − 1) = 2mdc(a,b) − 1 para todo

a, b ∈ N.
16. (OBM 2011) Existem 2011 inteiros positivos a1 < a2 <

. . . < a2011 tais que, para todo 1 ≤ i < j ≤ 2011, mdc(ai , aj ) =
aj − ai ?
17. (OBM 2012) Esmeralda desenhou uma tabela com 100 linhas
e 100 colunas, e escreveu, na linha i e coluna j da tabela,
mdc(i, j) se i < j e mmc(i, j) se i ≥ j. Por exemplo, na linha
4, coluna 6 ela escreveu mdc(4,6) = 2, e na linha 15, coluna
10 ela escreveu mmc(15,10) = 30. Qual é o produto de todos
os 1002 números da tabela?
18. (OBM 2013) Seja A = {1, 2, 3, . . . , 20} o conjunto dos 20

primeiros inteiros positivos. Para cada subconjunto X de 15
elementos de A, calculamos o produto p(X) de seus elementos.
Por exemplo p({1, 2, 3, . . . , 15}) = 1.2 . . . .15 = 15! Qual é o
máximo divisor comum dos 20 15 produtos p(X) obtidos com
todos os subconjuntos com 15 elementos de A?
19. (IMO 1992) Encontrar todos os inteiros a, b, c, com 1 < a <

b < c, tais que (a − 1)(b − 1)(c − 1)|abc − 1.
20. F Encontrar todas as funções f : N∗ × N∗ → Z satisfazendo

simultaneamente as propriedades:
• f (a, a) = a;
• f (a, b) = f (b, a);
• Se a > b, então f (a, b) = a−b f (a
a
− b, b).
22 POTI/TOPMAT
Aula 3
Teorema Fundamental da
Aritmética
O objetivo desta aula é identificarmos o papel importante que

os números primos desempenham na Teoria de Números. Isso se
dá pelo fato de todo número inteiro diferente de 0, 1 e −1 poder
ser escrito de maneira única como o produto de números primos, a
menos da ordem dos seus fatores.
Primos
Definição 3.1. Dizemos que p é um número primo se possui

exatamente dois divisores positivos, 1 e |p|.
Observe que pela definição o número 0 não é um número primo,
pois possui infinitos divisores positivos. Da mesma forma, vemos
que 1 e −1 também não são primos.
Definição 3.2. Dizemos que um inteiro a é um número composto
quando possuir mais de dois divisores inteiros distindo.
Dado um inteiro a não nulo que seja composto, ele admite um
divisor b tal que |b| =
6 1 e |b| =
6 a, tal que 1 ≤ |b| ≤ |a|. Um divisor
23
24 POTI/TOPMAT
nessas condições será chamado de divisor próprio de a.

Proposição 3.1. Seja p um número primo, e sejam a, b inteiros.
1. Se p - a, então mdc(p, a) = 1.
2. Se p|ab, então p|a ou p|b.
Demonstração.
1. Como p é primo e p - a, então o único divisor comum positivo
entre a e p é 1. Daí, segue o resultado.
2. Por hipótese, temos que p|ab. Se tivermos p|a, segue o resul-
tado, caso contrário mdc(p, a) = 1 o que implica pelo Teorema
de Euclides que p|b.

Exercício Resolvido
1. Mostre que se p é primo e p divide um produto a1 a2 · · · an ,
então p|aj para algum j, 1 ≤ j ≤ n. Conlcua, em particular,
que se p|ak , k ≥ 2, então p|a.
Solução:
Primeiramente vamos separar o produto em duas partes:

(a1 · a2 · · · an−1 ) · an
Agora analisemos os casos:
• Se p|ai para algum i, 1 ≤ i ≤ n − 1, então está provado que

p|aj para algum j.
• Se p - ai , para todo i, 1 ≤ i ≤ n − 1, então p - (a1 · a2 · · ·
an−1 ) =⇒ mdc(p, a1 · a2 · · · an−1 ) = 1, pois p é primo.
Com isso, temos que p|(a1 · a2 · · · an−1 ) · an e mdc(p, a1 · a2 ·

· · an−1 ) = 1 e, pelo Teorema de Euclides, p|an . Ou seja, p|aj
para algum j.
Aula 3 - Teorema Fundamental da Aritmética 25
Observe que esse exercício resolvido é uma generalização do item

(ii) da última proposição.
É muito importante conseguirmos caracterizar a noção dos nú-

meros primos e fazemos isso extendendo a Proposição 1 para o se-
guinte Teorema:
Teorema 3.1. Seja p um inteiro diferente de 0,1 e −1. Então, p é

primo se e somente se, toda vez que p divide um produto de dois
números, p divide pelo menos um dos fatores.
Demonstração.
( =⇒ ) Essencialmente, a ida já foi provada no exercício pro-
posto.
( ⇐= ) Vejamos por absurdo que a volta é verificada. Para isso,

suponha que p não seja primo e que satisfaz as propriedades do
enunciado.
Como p é um número composto, segue que |p| pode ser escrito

da seguinte maneira |p| = a·b, onde a e b são seus divisores próprios,
ou seja,
1 < a < |p|
1 < b < |p|
Dessas desigualdades, decorre que p - a e p - b o que acaba im-
plicando p - a · b.
Um absurdo. A nossa contradição ocorreu ao supormos que p

não era um número primo.
Os próximos resultados serão desenvolvidos com o interesse de

chegarmos no Teorema Fundamental da Aritmética, tema dessa
aula.
Lema 3.1. Todo inteiro a > 1 pode ser escrito como produto de
números primos.
26 POTI/TOPMAT
Demonstração. Problema 5.
Teorema 3.2. Seja a > 1 um inteiro. Então, existem primos posi-

tivos p1 ≤ p2 ≤ ... ≤ pt , tais que a = p1 p2 · · · pt , e essa decomposição
é única.
Teorema Fundamental da Aritmética. Seja a um inteiro
diferente de 0,1 e −1. Então, existem primos positivos p1 < p2 <
... < pr e inteiros positivos n1 , n2 ,...,nr tais que a admite uma de-
composição única na forma a = E · pn1 1 ·n2 2 · · ·pnr r , onde E = ±1.
Obs. O número E caracteriza se a é um número positivo ou

negativo.
Demonstração.
Observe que a = E|a|, onde E = 1 ou E = −1.
Pela definição de módulo, temos que |a| é um inteiro positivo e

além disso, pelas condições do enunciado, é estritamente maior que
1. Com isso, decorre pelo Lema 1 que existem primos p1 ≤ p2 ≤ ···pt
tais que:
|a| = p1 · p2 · · · pt (3.1)
Dependendo do sinal de a, têm-se que:
a = E · p1 · p2 · · · pt
Agrupando os fatores primos repetidos, obtemos a seguinte de-

composição:
a = E · pn1 1 ·n2 2 · · ·pnr r (3.2)
Note que a decomposição (1) é única, pelo Lema 1. Decorre
imediatamente a unicidade da decomposição (2), pois ela foi obtida
a partir da (1).

Problemas Propostos
N F
1. Considere um inteiro a e suponha que ele não seja divisí-

vel por 5. É possível que o número 2a seja divisível por 5?
Justifique usando o Teorema Fundamental da Aritmética.
2. Seja a um inteiro. Temos que o número 2a é divisível por

6. É possível que a seja divisível por 6? Novamente, justifque
pelo Teorema Fundamental da Aritmética.
3. Sejam a um número inteiro e p um número primo. Mostre,

por indução em n, que se p divide an então p divide a.
4. Demonstre o Lema 1.
√
5. N Mostre que 2 · 3 · 5 é irracional.
6. N Seja a um inteiro positivo e suponha que a = pr11 · pr22 · · · prnn

é sua fatoração em produto de primos.
Mostre que todo divisor de a é da forma d = u · pr11 · pr22 · · · prnn ,

com u = ±1 e 0 ≤ ki ≤ ri para i = 1,2,· · · ,n.
7. N Usando o item anterior, mostre que o número de divisores

positivos de a é (r1 + 1) · (r2 + 1) · · · (rn + 1).
8. N Mostre que um número inteiro positivo a possui exatamente

três divisores positivos se e somente se a é o quadrado de um
número primo. Observe os casos com 4 e 5 divisores.
9. N Mostre o caso geral do Problema 8, ou seja, quando possuir

um número primo p de divisores positivos.
10. N Sejam k = pr11 · ... · prnn e l = q1s1 · ... · qm

sm as fatorações em
primos de k e l, respectivamente. Então k = l ⇔ n = m e

pri i = qisi para todo i, 0 ≤ i ≤ n = m.
28 POTI/TOPMAT
√
11. N Mostre que se p é um primo positivo então p é um número
irracional.
12. N Mostre que, dados um inteiro n e um primo p, n pode ser

escrito na forma n = pk · m, em que k ≥ 0 e m é um inteiro
não divisível por p.
13. N Seja a um inteiro positivo e suponha que a = pr11 · ... · prnn

é sua fatoração em produto de primos. Mostre que a é um
quadrado perfeito se e somente se todos os expoentes ri são
pares.
14. N Use o item anterior para decidir se os números abaixo são

quadrados perfeitos.
(a) 693
(b) 11 · 025
(c) 2 · 475
15. Sejam p, q e r três números primos maiores que 3. Sabe-se

que o número p + q + r também é primo . Mostre que p + q,
p + r ou q + r é um múltiplo de 6.
16. Sejam p,q primos tais que p ≥ q ≥ 5. Prove que 24|(p2 − q 2 ).
17. Seja n um inteiro positivo. Prove que:
(a) Se n > 4 não é primo, emtão n|(n − 1)!

(b) Nenhum inteiro da forma 8n + 1 é primo.
18. (OBM 2016) As raízes de um polinômio P , de coeficientes

inteiros e grau 10, são todas inteiras e distintas. Então todo
valor não nulo de P (n), n inteiro, tem, no mínimo, quantos
divisores positivos?
19. F (OlbM1987) A sequência pn é definida da seguinte maneira:
(a) p1 = 2
(b) Para todo n ≥ 2, pn é o maior divisor primo da expressão
p1 · p2 · p3 · · · pn−1 + 1
Demonstre que pn é diferente de 5.
20. F (Teorema de Euclides) Existem infinitos primos.

30 POTI/TOPMAT
Aula 4
Resultados de Números
Primos
O objetivo desta aula é trabalharmos com números que nos for-

neçam números primos, e além disso ser possível respoder a seguinte
pergunta: existem infinitos números primos?
Números de Fermat
O primeiro número que iremos estudar são os conhecidos núme-

ros de Fermat, que são definidos a seguir:
n
Fn = 22 + 1
Em 1640 Fermat afirmou que para todo n tinha-se Fn primo.

Mas em 1740, Euler provou que F (5) = 4294967297 era um número
composto, assim encontrando um contra-exemplo para a afirmação
de Fermat. É fácil obervar que para 0 ≤ n ≤ 4 têm-se Fn primo e
esses são chamados de primos de Fermat. Note que a fórmula de
Fn é uma função duas vezes exponecial e assim podemos concluir
que ela cresce muito rápido, então para valores de n maiores que
31
32 POTI/TOPMAT
4 obtemos um valor Fn cada vez maior e com mais casas decimais

dos números anteriores. Dessa forma fica difícil estudar esses núme-
ros sem um apoio computacional. E mesmo com esse apoio ainda
não sabemos se existem outros primos de Fermat, além desses cinco.
Propriedades dos Números de Fermat

Proposição 4.1. Todo número de Fermat verifica as seguintes re-
lações de recorrência:
1. Fn = (Fn−1 − 1)2 + 1
2. Fn = Fn−1 + 2n−1 F0 · · · Fn−2
3. Fn = Fn−1
2 − 2(Fn−2 − 1)2
k
4. Fn+k − 1 = (Fn − 1)2
Como vimos anterioriormente, os quatro primeiros números de

Fermat são co-primos, pois não são compostos; será que isso ocorre
para os números de Fermat seguintes? Ou seja, se todos os números
de Fermat são co-primos entre si? E a resposta é sim, com isso
enunciamos o próximo resultado da aula:
Teorema 4.1. Sejam Fn e Fm números de Fermat tais que n 6= m.
Então, Fn e Fm são co-primos.
Agora, deixamos para o leitor perguntas que estão abertas na
matemática sobre os números de Fermat. Esses números formam
um conjunto infinito? Existem infinitos números primos de Fermat?
E infinitos números compostos?
Aula 4 - Resultados de Números Primos 33
Números de Mersenne
Agora, discutiremos os chamados números de Mersenne. Es-

ses números são da forma:
Mn = 2n − 1
para cada n inteiro não negativo. Pode-se provar que, se n é

composto Mn também é (exercício). Assim, se um dado número de
Mersenne é primo, então é necessariamente da forma Mp = 2p − 1,
em que o próprio p é primo. Note, contudo, que a recíproca não é
verdadeira. Como contraexemplo, podemos tomar p = 11. De fato:
M11 = 2047 = 23.89

Uma das questões bastante vinculadas aos primos de Mersenne
é a dos números perfeitos. Um número natural é dito perfeito se
ele é a soma de todos os seus divisores positivos próprios, i.e., todos
seus divisores positivos menores do que ele. Assim, por exemplo, 6
é perfeito, pois seus divisores próprios são 1, 2, 3, e 1 + 2 + 3 = 6. É
possível provar que 2n−1 (2n −1) é perfeito sempre que Mn = 2n −1 é
primo (exercício). De fato, todo número perfeito par é dessa forma.
A existência ou não de números perfeitos ímpares permanece em
aberto até hoje.
Muitos métodos foram desenvolvidos historicamente para avaliar
a primalidade de um número de Mersenne dado. Dada a eficiência de
alguns desses algoritmos para números grandes, os maiores números
primos conhecidos são justamente primos de Mersenne.
Infinidade de Primos
Um dos fatos mais conhecidos sobre o conjunto dos números

primos diz respeito à sua infinidade. A demonstração de que exis-
tem infinitos primos que apresentamos a seguir é conhecida desde a
Antiguidade, constando já nos Elementos de Euclides.
Teorema 4.2. Existem infinitos números primos.
34 POTI/TOPMAT
Demonstração. Suponhamos, por absurdo, que o conjunto dos nú-

meros primos seja finito. Assim, sejam p1 , p2 . . . , pn todos os núme-
ros primos existentes. Então, podemos considerar o número:
P = p1 p2 . . . pn + 1
Sabemos que P admite um divisor primo pi . No entanto, temos
que pi |p1 p2 . . . pn , logo segue que pi |P − p1 p2 . . . pn = 1, mas pi > 1,
e com isso obtemos uma contradição.

Entre outras demonstrações deste fato fundamental sobre núme-

ros primos, cabe mencionar a prova formulada por Euler. A ideia
do matemático suíço consistiu em considerar o produto:
 
1 1 1 1 
! ! !
P = ... ...
1− 1
2 1− 1
3 1− 1
5 1 − p1
onde cada número primo p aparece em exatamente uma parcela.

Se assumirmos, por absurdo novamente, que a quantidade de nú-
meros primos é finita, o produto acima deve ser um número real
(positivo). Euler verificou que a igualdade acima é equivalente à
seguinte:
1 1 1 1 1
P =1+ + + + + + ...
2 3 4 5 6
A soma acima é conhecida como série harmônica, e é possível
provar que tal soma é maior que qualquer número real. Portanto, P
não pode ser nenhum número real positivo, contradizendo a hipó-
tese de que a quantidade de números primos é finita.
Assim, sabemos dizer que existem infinitos números primos, no en-
tanto pouco temos a dizer ainda sobre sua distribuição. Várias con-
jecturas relativamente simples sobre números primos permanecem
em aberto até hoje.
Um resultado relativamente fácil de se provar diz respeito a poder-
mos encontrar primos consecutivos "tão distantes entre si quanto se
desejar".
Proposição 4.2. Dado um inteiro positivo n, existem n inteiros

positivos consecutivos que são todos compostos.
Demonstração. Fixemos a sequência de números inteiros dada por:
(n + 1)! + 2, (n + 1)! + 3, . . . (n + 1)! + (n + 1)

Para todo m inteiro com 2 ≤ m ≤ n + 1, temos que m|(n +
1)!. Logo m|(n + 1)! + m. Como existem n números na sequência
considerada, obtemos pelo menos n inteiros consecutivos que são
todos compostos.

Problemas Propostos
N F
Definição 1. Dado n ∈ N, denotaremos por σ(n) a soma de

todos os divisores de n. Denotaremos também por σ0 (n) a soma de
todos os divisores próprios de n.
Definição 2. Diremos que n ∈ N é um número perfeito se sa-

tisfaz a seguinte igualdade σ(n) = 2n.
Obs. Se n é perfeito, então σ0 (n) = n. Como σ0 (n) = σ(n) − n

isto implica que σ(n) = 2n.
Afirmação 1. Seja n ∈ N, com n ≥ 2, cuja fatoração prima é

dada por n = pα1 1 · · · pαmm . Então
pα1 1 +1 − 1 pαr +1 − 1
σ(n) = ··· r
p1 − 1 pr − 1
36 POTI/TOPMAT
1. O número Mn = 2n − 1, com n ≥ 1 é chamado de n-ésimo

número de Mersenne.
Mostre que se Mn = 2n − 1 é primo, então n é primo.
2. Prove por Indução os itens da Proposição 1.
3. Seja n ∈ Z, n > 1. Mostre que se n|(n − 1)!, então n é

composto.
4. Provar que, se a 6= b, existem infinitos positivos n tais que

a + n e b + n sejam relativamente primos.
5. N Mostre que três ímpares positivos consecutivos não podem

ser todos primos, com exceção de 3, 5 e 7.
6. N Demonstrar que existem infinitos primos da forma 4n +

3, n ∈ N.
7. N Seja {p1 , . . . , pn } um conjunto de primos positivos distin-

tos. Seja A o produto de quaisquer r destes primos, e B o
quociente:
p1 . . . pn
B=
A
• Provar que pk divide A ou B, mas não ambos
• Provar que A + B tem um divisor primo p 6∈ {p1 . . . pn }
• Deduzir, desse argumento, a existência de infinitos nú-
meros primos.
8. N Para cada inteiro n ≥ 1 seja pn o n-ésimo número primo

positivo. Prove que o inteiro p1 p2 . . . pn +1 não é um quadrado
perfeito.
9. Prove que, se 2m + 1 é primo para algum m > 0, então m é

uma potência de 2.
10. Mostre que todo número de Fermat é igual ao produto de

seus anteriores somado a 2, ou seja, que Fn = F0 · ... · Fn−1 + 2.
11. Mostre a seguinte equivalência na prova formulada por Euler

para a existência de infinitos números primos:
 
1 1 1  1 1 1 1 1
! !
... . . . = 1+ + + + + +. . .
1− 1
2 1− 1
3 1− p
1 2 3 4 5 6
12. Seja M um conjunto de 1537 inteiros positivos sem divisores

primos maiores que 27. Mostre que:
• Qualquer subconjunto de 513 números contém dois cujo

produto é um quadrado perfeito.
• M contém um subconjunto de quatro números cujo pro-
duto é uma quarta potência.
13. (IMO 2011) Considere um polinômio P (x) = (x + d1 )(x +

d2 ) . . . (x + d9 ), com d1 , d2 , . . . d9 números inteiros distintos.
Prove que existe um inteiro N tal que, para todos os inteiros
x > N , o número P (x) é divisível por um número primo maior
que 20.
14. FSeja n ∈ N. Então, n é primo se, e somente se, σ(n) = n + 1.
15. F Dado n ∈ N natural, denotaremos por σ(N ) a soma de to-

dos os divisores de n. Denotaremos tambem por σ0 (n) a soma
de todos os divisores próprios de n.
Seja n ∈ N composto tal que n = ab, com (a, b) = 1. Então,

σ(n) = σ(a)σ(b).
16. F Um natural da forma n = 2p−1 (2p − 1) é perfeito quando

2p − 1 é um primo de Mersenne.
38 POTI/TOPMAT
Aula 5
Equações Diofantinas
Recebem o nome de equações diofantinas quaisquer equações po-

linomiais (tipicamente com duas ou mais incógnitas) com coeficien-
tes inteiros, tendo em vista encontrar apenas suas soluções inteiras.
Historicamente, o nome é uma referência a Diofanto de Alexandria,
matemático grego do século III d.C., cuja principal obra, Arithme-
tica, é uma coletânea de equações determinadas e indeterminadas
para as quais são encontradas as soluções numéricas. Dos treze li-
vros originais dessa obra, apenas seis foram preservados em grego
e presumivelmente outros quatro em tradução árabe. Mais pro-
priamente, Diofanto de Alexandria se ocupou de estudar soluções
racionais positivas em suas equações, no entanto, pelas estratégias
algébricas que desenvolveu, tradicionalmente se vincula seu nome
aos problemas relacionados com números inteiros.
Entre as equações diofantinas mais elementares estão as equações
lineares a duas variáveis, que serão o objeto central de estudo dessa
aula.
Equações diofantinas lineares a duas variáveis
Denominamos equações diofantinas lineares a duas variáveis as
39
40 POTI/TOPMAT
equações do tipo:
ax + by = c
em que x, y são as incógnitas e a, b ∈ Z não são simultaneamente
nulos. Consideramos uma solução particular da equação um par da
forma (x0 , y0 ) ∈ Z × Z tal que torne verdadeira a igualdade:
ax0 + by0 = c
Primeiro, precisamos considerar as condições de existência de
alguma solução. Pelo Teorema de Bachet-Bézout que estudamos
anteriormente, sabemos que, se d = mdc(a, b), então existe solução
inteira para a equação:
ax + by = d
De fato, podemos depreender disso as condições necessárias e
suficientes para a existência de soluções de uma equação diofantina.
Proposição 5.1. Uma equação diofantina linear da forma ax+by =
c admite solução se, e somente se, d = mdc(a, b) divide c.
Demonstração. Seja (x0 , y0 ) uma solução de ax + by = c. Nesse

caso, temos que d|a =⇒ d|ax0 e d|b =⇒ d|by0 , e, portanto,
d|ax0 + by0 = c.
Reciprocamente, suponhamos que d|c. Logo, existe c0 ∈ Z tal
que c = dc0 . Pelo Teorema de Bachet-Bézout, sabemos que existem
inteiros r, s tais que ar + bs = d. Multiplicando ambos os lados da
equação por c0 , obtemos:
a(c0 r) + b(c0 s) = (ar + bs)c0 = dc0 = c

Logo, o par (c0 r, c0 s) é uma solução para a equação diofantina
inicial.
Caso a equação diofantina linear tenha solução, podemos obter

uma solução particular simplesmente a partir da solução de ax+by =
mdc(a, b). Porém, essa solução não é única para a nossa equação
Aula 5 - Equações Diofantinas 41
diofantina. De fato, quando tal equação admite alguma solução, as

soluções são infinitas. O próximo resultado que apresentamos é uma
descrição dessa família de soluções.
Proposição 5.2. Seja ax + by = c uma equação diofantina linear,
com d = mdc(a, b) dividindo c. Se (x0 , y0 ) é uma solução particular,
então toda outra solução é da forma:
!
b a
x0 + · t, y0 − · t , t ∈ Z
d d
Além disso, para todo t ∈ Z, os pares da forma acima são solu-
ções.
Demonstração. Seja (x0 , y 0 ) uma solução qualquer. Então:

ax0 + by0 = c = ax0 + by 0
Rearranjando os termos dos dois extremos da equação, obtemos:
a(x0 − x0 ) = −b(y0 − y 0 ) (5.1)

Como d é máximo divisor comum de a e b, existem a0 e b0 inteiros
tais que a = da0 , b = db0 . Além disso, temos que mdc(a0 , b0 ) = 1.
Assim podemos reescrever (1) como:
a0 d(x0 − x0 ) = −b0 d(y0 − y 0 )

Então, cancelando d em ambos os lados da equação, temos que:
a0 (x0 − x0 ) = −b0 (y0 − y 0 ) (5.2)

Como a0 , b0 são coprimos, se segue que a0 |(y0 − y 0 ) e b0 |(x0 − x0 ).
Portanto, existem inteiros u, t tais que (x0 −x0 ) = b0 u, (y0 −y 0 ) = a0 t.
Fazendo as devidas substituições em (2):
a0 b0 u = −b0 a0 t (5.3)
Cancelando a0 b0 em ambos os lados, concluímos que u = −t, e,
consequentemente x0 = x0 + b0 t, y 0 = y0 − a0 t. Como b0 = b/d, a0 =
a/d, a solução é exatamente da forma enunciada.
42 POTI/TOPMAT
A prova de que para qualquer t ∈ Z o par (x0 +(b/d)t, y0 −(a/d)t)

é solução será deixada como exercício.
Exemplo 5.1. Encontre as soluções de 56x + 72y = 40.

Inicialmente, calculando o máximo divisor comum dos coeficien-
tes acompanhando as incógnitas, obtemos mdc(56, 72) = 8, e 8|40,
portanto existem soluções.
Resolvendo 56r + 72s = 8 pelo Algoritmo de Euclides, obtemos
r = 4, s = −3. Como c0 = 40/8 = 5, nossa solução particular é dada
por x0 = rc0 = 4 · 5 = 20 e y0 = sc0 = (−3) · 5 = −15. Por fim,
temos que a/d = 56/8 = 7, b/d = 72/8 = 9, o que nos leva à forma
geral:
x = 20 + 9t, y = −15 − 7t, t ∈ Z
A Proposição 2 garante que quando ax + by = c admite uma

solução inteira, existe uma quantidade infinita de soluções para a
equação. Porém, em algumas situações, como alguns contextos de
mundo real, queremos considerar apenas soluções não-negativas, isto
é, soluções (x, y) em que simultaneamente x ≥ 0, y ≥ 0. Tais so-
luções nem sempre existem (como você pode verificar no Exemplo
1).
Exemplo 5.2. Suponha que um certo produto é vendido apenas em
sacos de 7kg ou 15kg. É possível fazer uma compra de exatamente
125kg?
Nosso problema pode ser expresso na forma da equação diofan-
tina:
15x + 7y = 125
No entanto, pela natureza do problema, somos forçados a con-

siderar apenas as soluções não-negativas da equação. Começamos
resolvendo de modo usal, verificando que mdc(7, 15) = 1 obviamente
divide 125. Também é fácil verificar que r = 1, s = −2 é solução de
15r + 7s = 1, o que nos fornece a solução particular:
x0 = 1 · 125 = 125
y0 = (−2) · 125 = −250
Por sua vez a solução geral é da forma:
x = 125 + 7t
y = −250 − 15t, t ∈ Z
Assim, para obter uma solução não-negativa, precisamos encon-

trar t ∈ Z satisfazendo simultaneamente as duas inequações:

125 + 7t ≥ 0
−250 − 15t ≥ 0
Da primeira inequação, resulta que t ≥ −17, da segunda, que t ≤

−17. Considerando essas condições, t = −17 fornece a única solução
não-negativa, da qual obtemos x = 6, y = 5. Portanto, o único
modo de comprar 125kg do produto nas condições do problema é
comprando 6 pacotes de 15kg e 5 pacotes de 7kg.
Como vimos no último exemplo, algumas aplicações de equações
diofantinas lineares a situações cotidianas exigem uma restrição das
soluções aos inteiros não-negativos. Isso nos leva naturalmente à
questão: como determinar quando existe pelo menos uma solução
não-negativa para a equação?
Em geral, dados a, b > 0 tais que mdc(a, b) = 1, sabemos que
a equação diofantina ax + by = c tem solução para todo c ∈ Z.
Sejam r, s tais que ar + bs = 1. Sabemos que a solução geral de
ax + by = c é da forma x = rc + bt, y = sc − at. Para avaliar se existe
uma solução não-negativa, precisamos satisfazer simultaneamente as
seguintes equações:

rc + bt ≥ 0
sc − at ≥ 0
44 POTI/TOPMAT
Destas inequações, obtemos: (sc)/a ≥ t ≥ (−rc)/b. Isto significa

que uma solução não-negativa existe se, e somente se, existe algum
inteiro entre (sc)/a e (−rc)/b. Note que para c suficientemente
grande, sempre conseguimos garantir a existência de algum inteiro
nesse intervalo, e, consequentemente, de uma solução não-negativa.
Vamos definir a função g(a, b) = N como o maior inteiro positivo
para o qual a equação ax + by = N não tem solução não-negativa.
O problema de determinar g(a, b) é conhecido como o Problema do
Troco de Frobenius (ou Problema das Moedas de Frobenius) para
duas incógnitas. De modo geral, supondo que tenhamos moedas
que valem a1 , . . . , an centavos, com mdc(a1 , . . . , an ) = 1, o pro-
blema consiste em determinar o maior valor que não pode ser pago
exatamente utilizando apenas essas moedas.
Para o caso de duas incógnitas, é conhecida uma solução ex-
plícita, expressa na seguinte fórmula, descoberta por James Joseph
Sylvester em 1882:
g(a, b) = ab − a − b
Para o caso n = 3 também se conhece uma solução explícita,
porém inviável para o cálculo manual. Para n ≥ 4, ainda não se co-
nhecem soluções explícitas do problema de Frobenius, embora sejam
conhecidas algumas estimativas de limite superior.
Equações Diofantinas não Lineares
Em algumas equações diofantinas, encontramos potências das

incógnitas e eventualmente produto entre incógnitas diferentes. Es-
tes casos em geral exigem variadas estratégias de resolução. Uma
das mais comuns consiste conseguir isolar uma constante k que possa
ser escrita como produto de parcelas inteiras dadas pelas incógnitas,
como no exemplo a seguir:
Exemplo 5.3. Sejam p e q dois números primos distintos. Encontre
as soluções inteiras positivas da equação:
1 1 1
+ =
x y pq
Neste caso, o problema equivale a determinar as soluções estri-

tamente positivas de:
xpq + ypq = xy
Note que a equação diofantina acima é não-linear, uma vez que
temos o produto entre as duas incógnitas na equação. Porém, neste
caso, podemos reescrever a equação das seguintes maneiras:
0 = xy − xpq − ypq
p2 q 2 = xy − xpq − ypq + (p2 q 2 )
p2 q 2 = (x − pq)(y − pq)
Note que agora nós conseguimos escrever p2 q 2 como produto

constante das parcelas inteiras (x − pq) e (y − pq). Como p2 q 2 tem
exatamente 9 divisores positivos, basta encontrarmos as soluções do
sistema: 
x − pq = d
2 2
y − pq = p q
d
em que d ∈ {1, p, q, p2 , pq, q 2 , p2 q, pq 2 , p2 q 2 }, o que nos dá as solu-

ções:
(pq + 1, pq(pq + 1)) (p(q + 1), pq(q + 1)) (q(p + 1), pq(p + 1))
(p(p + q), q(p + q)) (2pq, 2pq) (q(p + q), p(p + q))
(pq(p + 1), q(p + 1)) (pq(q + 1), p(q + 1)) (pq(pq + 1), pq + 1)
Problemas Propostos
N F
1. Encontre a solução geral das seguintes equações diofantinas:

46 POTI/TOPMAT
• 2x + 3y = 9
• 8x + 7y = 3
• -26x + 39y = 65
• 12x + 27y = 33
2. Determinar, quando existem, as soluções não-negativas das

equações diofantinas:
• 123x + 360y = 99
• 30x + 17y = 300
3. Para cada c ∈ {12, 13, . . . , 18} calcule uma solução não-

negativa da equação diofantina 7x + 3y = c. Conclua que para
todo N ≥ 12, a equação diofantina 7x + 3y = N admite uma
solução não-negativa
4. Encontre frações de denominadores 11 e 13 respectivamente,

cuja soma seja 143
67
.
5. Determine todas as maneiras de escrever 270 como soma

entre um múltiplo positivo de 9 e um múltiplo positivo de 11.
6. Escreva o número 100 como soma de dois números positivos

tais que um deles seja múltiplo de 7 e o outro múltiplo de 11.
7. N Conclua a demonstração da Proposição 2.
8. N Determine o menor inteiro positivo que tem resto 9 na di-

visão por 37 e resto 15 na divisão por 52.
9. N Uma loja de discos compra exemplares de um determinado

CD e exemplares de um determinado DVD. Se cada CD sai
por R$12,00 e cada DVD por R$20,00, qual o maior número
de unidades que a loja pode comprar com R$860,00? Quantos
DVDs e quantos CDs?
10. N Uma certa quantidade de maçãs é dividida em 37 montes

de igual número. Após serem retiradas 17 frutas, as restantes
são acondicionadas em 79 caixas, cada uma com a mesma

quantidade. Quantas maçãs foram colocadas em cada caixa?
Quantas havia em cada monte?
11. N Encontre todos os inteiros estritamente positivos com a se-

guinte propriedade: fornecem resto 6 quando divididos por 11
e resto 3 quando divididos por 7.
12. N Somando-se um certo númeor 6x com um certo numero 9y,

obtém-se 126. Se x e y forem trocados, obtém-se a soma 114.
Determine os valores de x e y.
13. Prove que a equação diofantina linear a três incógnitas, dada

por a1 x + a2 y + a3 z = b, onde a1 , a2 , a3 são inteiros não-nulos,
tem solução se, e somente se, d = mdc(a1 , a2 , a3 ) divide b
14. Encontre uma solução para equação diofantina abaixo:
21x + 33y + 77z = 1
15. Sejam a, b > 0 tais que mdc(a, b) = 1. Prove que ax−by = c

tem infinitas soluções positivas.
16. Um pescador tenta pescar um cardume jogando diversas

redes na água. Se cair exatamente um peixe em cada rede,
salvam-se ainda n peixes. Se caírem n peixes em cada rede,
sobram n redes vazias. Quantas são as redes? Quantos são os
peixes?
17. Qual o menor valor de c para o qual a equação 9x + 13y = c

tem pelo menos duas soluções estritamente positivas, isto é
x > 0 e y > 0?
18. (KöMaL) Sejam p, q números primos distintos. Determine

os pares de inteiros positivos (x, y) que satisfazem a equação:
p q
+ =1
x y
48 POTI/TOPMAT
19. F Sejam a e b inteiros positivos tais que mdc(a, b) = 1.
• Prove que, para todo N > ab−a−b, a equação diofantina

ax + by = N tem solução não negativa.
• Prove que não existe solução não negativa para ax + by =
ab − a − b.
Deduza dos itens acima a fórmula de Sylvester.
20. F Seja k um primo. Prove que a equação x4 + 4y 4 = k tem

solução inteira se, e somente se, k = 5. Nesse caso, determinar
suas soluções.
Aula 6
Congruências
Congruências
Definição 6.1. Seja R uma relação no conjunto X. Diremos que

R é uma relação de equivalência se:
(i) (Propriedade reflexiva) xRx, para todo x ∈ X;
(ii) (Propriedade simétrica) Se xRy, então yRx;
(iii) (Propriedade transitiva) Se xRy e yRz, então xRz.

No nosso contexto, iremos escrever a relação de equivalência R
por ≡. Observe que a classe de equivalência de um certo elemento x
em X é um subconjunto de X. E iremos defini-lo do seguinte modo:
x = {y ∈ X|x ≡ y}
Ou seja, no conjunto x teremos todos os elementos de X que se

relacionam com x.
Proposição 6.1. Seja X um conjunto e considere ≡ uma relação
de equivalência em X. Se x,y ∈ X, então as afirmações abaixo são
49
50 POTI/TOPMAT
equivalentes:
(i) x ≡ y
(ii) x = y
(iii) x ∈ y
Demonstração. (i) =⇒ (ii)
Hipótese: x ≡ y
Desejamos mostrar que x = y, para isso basta verificarmos que

x ⊂ y.
De fato, dado z ∈ x =⇒ z ≡ x. Por hipótese, temos que x ≡ y.

E pela propriedade transitiva, segue que z ≡ y, o que implica z ∈ y.
Ou seja, x ⊂ y.
De maneira análoga, decorre que y ⊂ x.
(ii) =⇒ (iii)
Hipótese: x = y
Pela propriedade reflexiva temos que x ∈ x, como x = y decorre

imediatamente que x ∈ y.
(iii) =⇒ (i)
Hipótese: x ∈ y
Segue da definição de equivalência.
As demais implicações são imediatas e deixaremos como exercí-

cio para o leitor.
Aula 6 - Congruências 51
Definição 6.2. Dado um inteiro m positivo fixo. Dizemos que os

inteiros a e b são congruentes módulo m, se m|(a − b).
Denotamos a ≡ b (mod m).

Obs. A congruência é uma classe de equivalência e, portanto,
assume as propriedades vistas na Definição 1: reflexiva, simétrica e
transitiva.
Por exemplo 191 ≡ 58 (mod 7) pois 191 − 58 = 133 = 7 · 19,

porém 8 e 3 não são congruentes módulo 2 pois 8 − 3 = 5 e 2 não
divide 5.
Proposição 6.2. A relação de congruência módulo m é uma relação

de equivalência em Z.
Demonstração. É imediato que a ≡ a (mod m) e que, se a ≡ b (mod m),

então b ≡ a (mod m).
Resta provar que, se a ≡ b (mod m) e b ≡ c (mod m), então
a ≡ c (mod m). De fato, temos que m|(a − b) e m|(b − c), logo, pelas
propriedades de divisibilidade, m|((a − b) + (b − c)), o que equivale
a afirmar m|(a − c), e, portanto a ≡ c (mod m).
A relação de congruência possui muitas propriedades boas com

relação a somas, produtos e potências. Tais propriedades são dadas
pelo seguinte teorema.
Teorema 6.1. Se x ≡ y (mod m) e z ≡ w (mod m). Então:
(i) x + z ≡ y + w (mod m)
(ii) x − z ≡ y − w (mod m)
(iii) kx ≡ ky (mod m), ∀k ∈ Z
(iv) xz ≡ yw (mod m)
52 POTI/TOPMAT
(v) xk ≡ y k (mod m), ∀k ∈ N
Demonstração. (i) Por hipótese, temos que x ≡ y (mod m) ⇔ m|x−

y e z ≡ w (mod m) ⇔ m|z −w. Pelas propriedades de divisibilidade,
segue que m|(x − y) + (z − w) = (x + z) − (y + w). Por definição de
congruência módulo m, segue que x + z ≡ y + w (mod m).
(ii) Observe que z ≡ w (mod m) ⇔ m|z − w =⇒ m|(−1)(z −

w) = w − z
Como m|x−y, decorre que m|(x−y)+(w−z) = (x−z)+(w−y) =

(x − z) + (−1)(y − w) = (x − z) − (y − w) ⇔ x − z ≡ y − w (mod m)
(iii) Note que x ≡ y (mod m) ⇔ m|x − y =⇒ m|k(x − y), com

k ∈ Z =⇒ m|kx − ky ⇔ kx ≡ ky (mod m).
(iv) Como x ≡ y (mod m) ⇔ m|x − y ⇔ ∃q1 ∈ Z, tal que

x − y = mq1 =⇒ x = mq1 + y. Da mesma forma, temos que
z = mq2 + w, com q2 ∈ Z.
Logo, xz = (mq1 +y)(mq2 +w) = m2 q1 q2 +mq1 w +ymq2 +yw =

yw + m(mq1 q2 + q1 w + yq2 )
=⇒ xz = yw+m(mq1 q2 +q1 w+yq2 ), com (mq1 q2 +q1 w+yq2 ) ∈

Z.
E, portanto, m|xz − yw ⇔ xz ≡ yw (mod m).
(v) A prova deste item será feita por indução em k.
Para k = 2, basta usar o item (iv) tomando z = x e w = y.

Dessa forma temos que x2 ≡ y 2 (mod m), verificando assim o pri-
meiro passo da indução.
Agora, suponha que vale para algum n ∈ N e vejamos que vale

também para n + 1.
De fato, pela hipótese de indução temos que xn ≡ y n (mod m) e

além disso sabemos que x ≡ y (mod m). Usando novamente o item
(iv) nessas duas últimas congruências, decorre que:
xn x ≡ y n y (mod m) ⇔ xn+1 ≡ y n+1 (mod m)
Este último teorema essencialmente nos diz que a congruência

módulo m é compatível com as operaçãoes em Z.
Uma outra caracterização para a noção de congruências é dado

pela seguinte propriedade:
Proposição 6.3. Dado m um inteiro fixo. Dois inteiros x,y são
congruente módulo m se, e somente se, eles possuem como resto o
mesmo inteiro quando dividmos por m.
Demonstração. Dados
x = mq1 + r1 , com 0 ≤ r1 < m
y = mq2 + r2 , com 0 ≤ r2 < m
Então, x−y = m(q1 −q2 )+(r1 −r2 ). Assim, m|x−y ⇔ m|r1 −r2 .
Como 0 ≤ r1 < m e 0 ≤ r2 < m, segue que 0 ≤ |r1 − r2 | < m. E,

portanto, m|r1 − r2 se, e somente se, r1 − r2 = 0. Ou seja, apenas
se r1 = r2 .
Calcular dígitos e restos de divisão, em geral, é facilitado pe-

las propriedades de congruência, como ilustramos com os próximos
exemplos.
54 POTI/TOPMAT
Exemplo 6.1. Calcule os restos de 4100 por 3 e 4100 por 5.
Como 4 ≡ 1 (mod 3) segue que 4100 ≡ 1100 = 1 (mod 3).
Logo, 4100 − 1 = 3k e portanto 4100 = 3k + 1 e o resto é 1.
Do mesmo modo 4 ≡ −1 (mod 5), ou seja 4100 ≡ (−1)100 =

1 (mod 5) e o resto também é 1.
Exemplo 6.2. Encontre o último algarismo de 370 + 770 .
Sabemos que 34 = 81 ≡ 1 (mod 10) e 70 = 4 · 17 + 2. Assim,
370 = 34·17 · 32 ≡ 1 · 32 = 9 (mod 10).
Além disso 72 = 49 ≡ −1 (mod 10), logo como 70 = 2 · 35 temos
770 = (72 )35 ≡ (−1)35 = −1 (mod 10).
Assim 370 + 770 ≡ 9 − 1 = 8(mod 10) e portanto o último algarismo

de 370 + 770 é 8.
Um teorema muito útil para resolver exercicios é o seguinte:
Teorema 6.2. Seja n um número inteiro e denote por d(n) a soma
dos algarismos de n. Então
n ≡ d(n)(mod 9)
Problemas Propostos
N F
1. Prove o critério de divisibilidade por 3.
2. Mostre que:
x ≡ y(mod m) ⇔ x + k ≡ y + k(mod m),∀k ∈ Z

3. Mostre que a relação de congruência módulo m é uma rela-

ção de equivalência em Z.
4. Prove que 2015 − 1 é divisível por 11.31.61
5. Sejam x,y ∈ Z com a relação de equivalência módulo m,

mostre que:
x 6= y =⇒ x ∩ y = {}
6. N Sejam x,y e z inteiros arbitrários e m um inteiro fixo.
Mostre que: se mdc(z, m) = 1, então xz ≡ yz(mod m) =⇒

x ≡ y(mod m)
7. N Calcule o resto de 34 · 35 · 36 · 37 + 5! − 423 por 6.
8. N Calcule o resto de 560 por 26.
9. N Calcule o resto de 4100 por 7.
10. N Prove que 22225555 + 55552222 é divisível por 7.
11. N Prove que n5 + 4n é divisível por 5 para todo inteiro n.
12. N Prove que 11n+2 + 122n+1 é divísivel por 133 para qualquer
n natural.
13. Prove o critério de divisibilidade por 11.
14. Prove que não existem inteiros x1 , . . . , x14 tais que:
x41 + . . . + x414 = 1599
15. Escreva uma única congruência que é equivalente à um par

de congruências x ≡ 1(mod 4) e x ≡ 2(mod 3).
16. Mostre que se n divide um número de Fibonacci, então

divide uma infinidade.
56 POTI/TOPMAT
17. Mostre que o quadrado de um inteiro é da forma 3k ou

3k + 1.
18. Prove que 3x2 + 2 = y 2 não tem solução em Z.
19. F Afirmação de Fermat: Todo número na forma Fn =

n
22 + 1 é primo.
Prove que a afirmação é falsa para n = 5.
Dica: Euler provou que F5 é divisível por 641.
20. F Seja d(n) a soma dos dígitos de n. Suponha que n + d(n) +

d(d(n)) = 1995. Quais os possíveis restos da divisão de n por
9?
Aula 7
Teorema Chinês do Resto

Teorema Chinês do Resto Sejam n1 ,n2 ,n3 ,· · · ,nk números

inteiros positivos tais que mdc(ni , nj ) = 1, para i 6= j, e sejam
a1 .a2 ,a3 ,· · · ,ak inteiros arbitrários. Então, o sistema de congruên-
cias lineares




 x ≡ a1 (mod n1 )
x ≡ a2 (mod n2 )






x ≡ a3 (mod n3 )
 ..
.






x ≡ ak (mod nk )


admite solução, que é única módulo n = n1 n2 n3 · · · nk .
Demonstração. Considerando n = n1 n2 n3 · · · nk , tome Ni = ni .

n
Observe que Ni = n1 n2 n3 · · · ni−1 ni+1 · · · nk , ou seja, Ni é o pro-

duto de todos os inteiros n1 ,n2 ,n3 ,· · · ,nk , omitindo o próprio ni .
57
58 POTI/TOPMAT
Pela hipótese do teorema, temos que os esses nj são relativa-

mente primos com ni . E, portanto, têm-se que mdc(Ni , ni ) = 1.
Dessa forma, conseguimos determinar os inteiros ri ,si tais que
ri Ni + si ni = 1 (7.1)
com 1 ≤ i ≤ k.
Iremos mostrar que
x0 = a1 r1 N1 + a2 r2 N2 + · · · + ak rk Nk
é uma solução para o sistema dado.
De fato, observe primeiramente que se i 6= j, temos que
Nj = n1 n2 n3 · · · ni · · · nj−1 nj+1 · · · nk ≡ 0 (mod ni )
pois ni é um dos fatores de Nj .
Segue imediatamente pelas propriedades de congruência que
aj rj Nj ≡ 0 (mod ni )
O que acaba implicando
x0 = a1 r1 N1 +a2 r2 N2 +· · ·+ai ri Ni +· · ·+ak rk Nk ≡ ai ri Ni (mod ni )
=⇒ x0 ≡ ai ri Ni (mod ni ) (7.2)
Voltando na equação (1), note que
si ni = 1 − ri Ni =⇒ ni |1 − ri Ni =⇒ ni |(−1)(1 − ri Ni ) ⇔
ni |ri Ni − 1.
Aula 7 - Teorema Chinês do Resto 59
Pela definição de congruência, segue que
ri Ni ≡ 1 (mod ni ) (7.3)
Substituindo a congruência (3) em (2), decorre que
x0 ≡ ai (mod ni )
E, portanto, x0 é solução da equação x ≡ ai (mod ni ) para cada

i, consequentemente, é uma solução do sistema.
Agora, basta verificarmos que essa solução é única.
Para isso, considere x solução do sistema. Ou seja, x ≡ ai (mod ni ),

para cada 1 ≤ i ≤ k. Também temos x0 solução, ou seja, x0 ≡
ai (mod ni ).
Da propriedade transitiva de congruências, segue que x ≡ x0 (mod ni ),

isto é, ni |x−x0 , para cada 1 ≤ i ≤ k. Comos os inteiros n1 ,n2 ,n3 ,· · · ,nk
são relativamente primos entre si, temos que n1 n2 · · · nk |(x − x0 ), o
que implica
x ≡ x0 (mod n).

Exemplo 7.1. Resolva o seguinte sistema de congruências lineares:

x ≡ 2 (mod 3)



x ≡ 3 (mod 5)

x ≡ 2 (mod 7)


Solução:
Na forma como esta distribuída no Teorema Chinês do Restos,

temos que:
60 POTI/TOPMAT
n = 3 · 5 · 7 = 105
a1 = 2, a2 = 3 e a3 = 2
n1 = 3, n2 = 5 e n3 = 7
=⇒ N1 = n
n1 = 3·5·7
3 = 5 · 7 = 35
=⇒ N2 = n
n2 = 3·5·7
5 = 3 · 7 = 21
=⇒ N3 = n
n3 = 3·5·7
7 = 3 · 5 = 15
Na demonstração do teorema, em algum momento nos depara-

mos com a seguinte congruência:
ri Ni ≡ 1 (mod ni )
.
No caso i = 1, devemos encontrar r1 ,s1 tais que:

r1 · N1 + s1 · n1 = 1 ⇔ r1 · 35 + s1 · 3 = 1
Para determinar os valores r1 e s1 iremos usar o método visto na
aula 2. Primeiro, fazemos divisões sucessivas usando o Algoritmo
de Euclides:
35 = 3 · 11 + 2
3=2·1+1
Em seguida isolamos os restos:
2 = 35 − 3 · 11 (7.4)
1=3−2 (7.5)
Substituindo a equação (4) em (5), decorre que:
1 = 3−2
= 3 − (35 − 3 · 11)
= 3 + (−1) · 35 + 3 · 11
= (−1) · 35 + 12 · 3
=⇒ (−1) · 35 + 12 · 3 = 1
E, portanto, r1 = −1 e s1 = 12.
Agora observando a congruência r2 N2 ≡ 1(mod n2 ), desejamos

encontrar inteiros r2 e s2 tais que
r2 · 21 + s2 · 5 = 1
Note que, 21 = 5 · 4 + 1 =⇒ 1 · 21 + (−4) · 5 = 1
Assim, r2 = 1 e s2 = 4.
Enfim, considerando a congruência r3 N3 ≡ 1(mod n3 ), temos

que:
r3 · 15 + s3 · 7 = 1
Onde, 15 = 7 · 2 + 1 =⇒ 1 · 15 + (−2) · 7 = 1.
Logo, r3 = 1 e s3 = −2.
Como vimos na demonstração do teorema, x0 é solução do sis-
tema dado, onde
x0 = a1 r1 N1 +a2 r2 N2 +a3 r3 N3 = 2·(−1)·35+3·1·21+2·1·15 = 23
=⇒ x0 = 23.
De fato x0 é solução do sistema dado, pois:
x0 = 23 = 21 + 2 ≡ 0 + 2 ≡ 2 (mod 3)
62 POTI/TOPMAT
x0 = 23 = 20 + 3 ≡ 0 + 3 ≡ 3 (mod 5)
x0 = 23 = 21 + 2 ≡ 0 + 2 ≡ 2 (mod 7)
É fácil verificar que x = 233 também é uma solução do sistema,

logo
x ≡ x0 (mod 105).
Problemas Propostos
N F
1. Resolva o sistema de congruências lineares dado a seguir:

x ≡ 2 (mod 2)



x ≡ 3 (mod 5)

x ≡ 2 (mod 7)


2. Resolva o seguinte sistema de congruências lineares:

x ≡ −1 (mod 4)
x ≡ 2 (mod 6).
3. Verifique que o seguinte sistema não possui solução:

x ≡ 8 (mod 12)
x ≡ 6 (mod 9)
Por que isso não contradiz o Teorema Chinês do Resto?

4. Mostre que o seguinte sistema não possui solução.

x ≡ −1 (mod 4)
x ≡ 2 (mod 6)
5. N Resolva o seguinte sistema linear e determine a sua menor

solução positiva:

x ≡ 1 (mod 3)



x ≡ 2 (mod 5)

x ≡ 3 (mod 7)


6. N Resolva de maneira análoga ao último exercício com o se-

guinte sistema linear:

x ≡ 5 (mod 6)



x ≡ 4 (mod 11)

x ≡ 3 (mod 7)


7. N Usando congruências, resolva as seguintes equações diofan-

tinas:
• 4x + 51y = 9
• 12x + 25y = 331
8. N Determine todos os números naturais menores que 1000 que

possuem como restos 9, na divisão por 37, e 15, na divisão por
52.
64 POTI/TOPMAT
9. N Ache x inteiro que satisfaça simultaneamente as congruên-

cias:

x ≡ 2 (mod 5)
3x ≡ 1 (mod 8)
10. N Encontre uma solução geral do seguinte sistema de con-

gruências lineares:

6x ≡ 2 (mod 4)



2x ≡ 1 (mod 3)

4x ≡ 2 (mod 7)


11. Encontre o menor a > 100 tal que 2|a, 3|(a + 1), 4|(a + 2),
5|(a + 3) e 6|(a + 4).
12. Um certo inteiro n é tal que tem restos 1 e 7 na divisão por

15 e 21 respectivamente. Qual seu resto na divisão por 35?
13. Determine todas as soluções da congruência linear 3x − 7y ≡

11 (mod 11).
14. Resolva a congruência linear 17x ≡ 3 (mod 2 · 3 · 5 · 7).
15. F Prove que as congruências x ≡ a (mod n) e x ≡ b (mod m)

possuem uma solução em comum se, e somente se, mdc(m, n)|(a−
b).
16. F Suponha que mdc(m, n) = 1 e prove que a solução do item

anterior é única módulo mmc(m, n).
Aula 8
Pequeno Teorema de
Fermat
No ano de 1640, Pierre de Fermat afirmou em correspondência

que, se um número a não divisível por um primo p, então p divide
ap−1 − 1. Como aconteceu com várias afirmações de Fermat, não
se conhece uma prova apresentada por ele próprio. Esse resultado,
que posteriormente ficou conhecido como o Pequeno Teorema de
Fermat, pode ser formulado em linguagem de aritmética modular
da seguinte maneira:
Teorema 8.1 (Pequeno Teorema de Fermat). Sejam p um número
primo e a um inteiro não divisível por p. Então:
ap−1 ≡ 1(mod p)
Demonstração. Inicialmente, vamos observar o seguinte conjunto:
A = {a, 2a, 3a, . . . , (p − 1)a}.
Se tomamos quaisquer dois elementos desse conjunto, temos que

eles não são congruentes entre si módulo p. Se tivermos xa ≡
65
66 POTI/TOPMAT
ya(mod p), para 1 ≤ x, y ≤ p − 1, como mdc(a, p) = 1, podemos

cancelar a os dois lados da congruência , e obtemos x ≡ y(mod p).
Como x, y são possíveis restos distintos da divisão por p, suas clas-
ses de congruência são necessariamente iguais, logo x = y. Também
temos que nenhum elemento de A é congruente a 0 módulo p, pois
para xa ∈ A, tanto x quanto a são relativamente primos a p.
Assim sendo, para alguma reordenação x1 , x2 , . . . , xp−1 dos in-
teiros 1, 2, . . . , p − 1, encontramos as seguintes congruências:
a ≡ x1 (mod p)
2a ≡ x2 (mod p)
..
.
(p − 1)a ≡ xp−1 (mod p).
A partir disso, podemos simplesmente multiplicar todos os ele-

mentos de cada lado, e a congruência se mantém. Como todos os
números entre 1 e p − 1 ocorrem em cada lado, o resultado da nossa
multiplicação será:
(p − 1)!ap−1 ≡ (p − 1)!(mod p).

Por fim, como (p−1)! é um produto de números coprimos com p,
esse fatorial pode ser cancelado em ambos os lados da congruência.
Isso nos dá o resultado:
ap−1 ≡ 1(mod p).
Como consequência imediata desse teorema, é fácil verificar o

seguinte resultado.
Corolário 8.1. Sejam p um número primo e a um inteiro qualquer.
Então:
ap ≡ a(mod p)
Aula 8 - Pequeno Teorema de Fermat 67
O Pequeno Teorema de Fermat é bastante útil para provar alguns

resultados envolvendo divisibilidade, como nos exemplos a seguir:
Exemplo 8.1. Seja a um número inteiro qualquer. Então an+4 tem
o mesmo algarismo das unidades que an .
De fato, basta mostrar que a5 tem o mesmo algarismo das uni-
dades que a, ou, na forma de congruências a5 ≡ a(mod 10). Mos-
traremos que a congruência vale para cada um dos fatores primos
de 10.
A congruência a5 ≡ a(mod 5) se segue imediatamente do Corolá-
rio. Por sua vez, como a5 e a são ou ambos ímpares ou ambos pares,
sua diferença é par, e portanto a5 ≡ a(mod 2). Como mdc(2, 5) = 1,
segue-se que a5 ≡ a(mod 10).
Exemplo 8.2. Sejam a e b inteiros, e p um número primo. Então,
tem-se que:
(a + b)p ≡ ap + bp (mod p)
De fato, aplicando o Pequeno Teorema de Fermat primeiro em
(a + b) e depois em a e b individualmente, obtemos:
(a + b)p ≡ a + b ≡ ap + bp (mod p)
A primeira prova publicada do Pequeno Teorema de Fermat se
deve a Euler, que posteriormente generalizou o resultado para qual-
quer número natural. Contudo, antes de apresentar tal generaliza-
ção, será necessário definir uma função sobre os números naturais,
chamada função totiente de Euler ou ainda função phi de Euler.
Definição 8.1 (Função Totiente de Euler). A função φ : N∗ → N∗
que associa cada inteiro positivo n à quantidade de números meno-
res ou iguais a n que são coprimos com ele é denominada Função
Totiente de Euler
Assim, por exemplo, φ(8) = 4, pois ao listarmos os números de
1 a 8, encontramos precisamente 4 números coprimos com relação a
8: 1, 3, 5 e 7.
Para qualquer número primo p, podemos constatar facilmente
que φ(p) = p − 1, pois de 1 a p, temos que apenas precisamente p
68 POTI/TOPMAT
não é coprimo consigo próprio. Também podemos calcular o valor de

φ(pk ) para qualquer potência k. De fato, como mdc(p, n) 6= 1 ⇐⇒
p|n, basta contar a quantidade de múltiplos de p entre 1 e pk , que
é dada por exatamente pk−1 números. Logo φ(pk ) = pk − pk−1 =
pk−1 (p − 1).
A proposição seguinte, que enunciaremos aqui sem demonstrar,
permite generalizar φ(n) para qualquer inteiro positivo n
Proposição 8.1. Se m e n são inteiros positivos e mdc(m, n) = 1,
então:
φ(m · n) = φ(m) · φ(n)

Exemplo 8.3. Vamos supor m = 4, n = 5. Queremos calcular
φ(20). Podemos verificar que φ(4) = 2, φ(5) = 4, logo φ(20) =
φ(4) · φ(5) = 8. De fato, podemos verificar o resultado dispondo os
números em uma tabela m × n:
1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
Retirando os números sublinhados, que não são coprimos com
20, obtemos exatamente 8 números: 1, 3, 7, 9, 11, 13, 17 e 19.
Definida a função totiente de Euler, estamos prontos para enun-
ciar o Teorema de Euler, que é a generalização do Pequeno Teorema
de Fermat para os números naturais:
Teorema 8.2 (Teorema de Euler). Sejam m > 1 e a ∈ Z tal que
mdc(a, m) = 1. Então:
aφ(m) ≡ 1(mod m)
.
Demonstração. Sejam s1 , . . . , sφ(m) os inteiros de 1 a m que são

relativamente primos a m. Dividindo cada a · si por m, podemos
escrever:
a · si = m · qi + ri , 0 ≤ 1ri < m
Se existisse algum primo p divisor comum de m e ri , teríamos
que p|a · si . Então teríamos p|a ou p|si , o que contradiz a hipótese
mdc(a, m) = 1 bem como mdc(si , m) = 1. Logo, para cada i, 1 ≤
i ≤ φ(m) temos que mdc(ri , m) = 1.
Mostremos agora que, para cada i 6= j, ri 6= rj . Supondo i 6= j e
ri = rj , teríamos a·si −m·qi = a·sj −m·qj , o que implica a(si −sj ) =
m(qi − qj ). Como mdc(a, m) = 1 temos que m|(si − sj ), mas como
1 ≤ si , sj ≤ m, a única possibilidade seria si = sj , contradição.
Portanto, a menos reordenação, os conjuntos {s1 , . . . , sφ(m) } e
{r1 , . . . , rφ(m) } são iguais. Assim, se multiplicarmos todas as con-
gruências a · si ≡ ri (mod m), obtemos:
aφ(m) · si · . . . · sφ(m) ≡ r1 · . . . · rφ(m) (mod m)

Como os produtos si · . . . · sφ(m) e r1 · . . . · rφ(m) são iguais, e m é
relativamente primo a cada ri , temos que mdc(m, r1 · . . . · rφ(m) ) = 1.
Assim sendo, podemos cancelar este produto em ambos os lados da
congruência, e disso obtemos o resultado:
aφ(m) ≡ 1(mod m)
.

Exemplo 8.4. Encontre os últimos 2 dígitos de 31000 .

Neste exemplo, como φ(100) = φ(52 )·φ(22 ) = 20·2 = 40, pelo Te-
orema de Euler
340 ≡ 1(mod 100). Logo:
31000 ≡ (340 )25 ≡ 125 ≡ 1(mod 100)

Logo, os últimos dígitos são 01.
Problemas Propostos
70 POTI/TOPMAT
N F
1. Calcule x em cada congruência abaixo usando o Teorema

de Euler:
• 31000 ≡ x(mod 7)
• 71000 ≡ x(mod 54)
2. Seja a um inteiro. Prove que:

Se mdc(a, 35) = 1, então a12 ≡ 1(mod 35).
3. Calcule φ(200), φ(860), φ(1001).
4. Sejam a e b inteiros e p um primo tal que mdc(a, p) = 1.

Verifique que uma solução da congruência ax ≡ b(mod p) é
dada por x = ap−2 b.
5. N Seja p > 2 um número primo. Prove que 1p + 2p + . . . + (p −

1)p ≡ 0(mod p).
6. N Sejam a e n inteiros tais que mdc(a, n) = mdc(a − 1, n) = 1.

Prove que 1 + a + . . . + aφ(n)−1 ≡ 0(mod n).
7. N Seja p um primo diferente de 2 e 5. Prove que p divide

infinitos inteiros da sequência 1, 11, 111, 1111, . . ..
8. N Se p é um primo ímpar, prove que np ≡ n(mod 2p) para

todo inteiro n.
9. N Se p é um primo ímpar e p|mp + np , prove que p2 |mp + np .
10. N Seja n um inteiro positivo ímpar em cuja decomposição

canônica figuram r fatores primos distintos. Prove que 2r |φ(n).
11. Prove que, se d|n, então φ(d)|φ(n).

12. Seja m > 1 e sejam p1 , p2 . . . pr os divisores primos distintos

de m. Prove que:
1 1 1
! ! !
φ(m) = m 1 − 1− ... 1 −
p1 p2 pr
13. Seja n > 1 e considere o número N = (n!)2 + 1. Prove que

existe algum número primo p da forma 4k + 1 tal que p|N .
Conclua disso que existem infinitos primos da forma 4k + 1.
1000
14. Encontre os últimos dois dígitos de 77 .
15. Encontre o resto de
2 10
1010 + 1010 + . . . + 1010
na divisão por 7.
16. (Putnam, 1972) Mostre que, dado um primo ímpar p, exis-
tem infinitos inteiros n tais que p|n · 2n + 1.
17. (Olimpíada Polonesa de Matemática, 2003) Encontre todos
os polinômios W com coeficientes inteiros satisfazendo a se-
gunte condição: para todo natural n, 2n − 1 é divisível por
W (n).
18. (IMO shortlist, 2006) Para certo x ∈ (0, 1), seja y ∈ (0, 1)
um número cujo n-ésimo dígito após a vírgula é o 2n -ésimo
dígito de x após a vírgula. Mostre que, se x é racional, então
y também é.
19. F (IMO, 1984) Encontre um par de inteiros positivos a e b
tais que:
• ab(a + b) não é divisível por 7.
• (a + b)7 − a7 − b7 é divisível por 77 .
20. F (USAMO, 1982) Prove que existe algum inteiro k tal que,
para todo n, k · 2n + 1 é composto.
72 POTI/TOPMAT
Referências Bibliográficas
Teoria de Números
Aula 1
1. MILIES, C. P.; COELHO, S. P. Números, Uma Introdução à

Matemática. 3a Edição. São Paulo: Editora da Universidade
de São Paulo, 2013.
2. COUTINHO, S. C. Números Inteiros e Criptografia RSA. Rio

de Janeiro: IMPA, 2013.
Aula 2


Aula 3

74 POTI/TOPMAT
2. TEOREMA FUNDAMENTAL DA ARITMÉTICA. Disponí-

vel em:
<http://www.dma.uem.br/kit/arquivos/arquivos_pdf/
teoremafundamentalaritmetica.pdf>.
Acesso em: 15 fev. 2020.
3. CLUBES DE MATEMÁTICA DA OBMEP. Disponível em:

<http://clubes.obmep.org.br/blog/tfa-problemas/>. Acesso
em: 10 fev. 2020.
Aula 4


3. PRIMOS DE FERMAT, PRIMOS DE MERSENNE, NÚME-

ROS PERFEITOS E O FATORIAL. Disponível em:
<https://www.ime.unicamp.br/ ftorres/ENSINO/
MONOGRAFIAS/Maicon_TN17M2.pdf>. Acesso em: 20
fev. 2020.
Aula 5

2. DOMINGUES, H. H. Fundamentos de Aritmética. 2a Edição

revista. Florianópolis: Editora da UFSC, 2017.
3. ANDRESCU, T.; ANDRICA, D. An Introduction to Diophan-

tine Equations. Zalau: GIL Publishing House, 2002.
Aula 6

2. GONÇALVES, A. Introdução à álgebra. Rio de Janeiro: Edi-

tora do IMPA, 2017.
Aula 7

2. GONÇALVES, A. Introdução à álgebra. Rio de Janeiro: Edi-

tora do IMPA, 2017.
Aula 8

2. DOMINGUES, H. H. Fundamentos de Aritmética. 2a Edição

revista. Florianópolis: Editora da UFSC, 2017.

N3 Teoria de Números 210325

Enviado por

Direitos autorais:

Formatos disponíveis

N3 Teoria de Números 210325

Enviado por

Dados do documento

Descrição original:

Título original

Direitos autorais

Formatos disponíveis

Compartilhar este documento

Compartilhar ou incorporar documento

Opções de compartilhamento

Você considera este documento útil?

Este conteúdo é inapropriado?

Direitos autorais:

Formatos disponíveis

N3 Teoria de Números 210325

Enviado por

Direitos autorais:

Formatos disponíveis

.

1 Divisibilidade e Algoritmo de Divisão 5

2 Máxim Divisor Comum, Mínimo Múltiplo Comum 13

3 Teorema Fundamental da Aritmética 23

4 Resultados de Números Primos 31

7 Teorema Chinês do Resto 57

8 Pequeno Teorema de Fermat 65

No conjunto dos números inteiros, a equação bx = a nem sem-

2. Transitividade: Se a|b e b|c, então a|c;

3. Se a|b e a|c, então, para quaisquer m, n ∈ Z, a|(mb + nc).

Um importante resultado de divisibilidade que merece ser men-

xn −y n = (x−y)(xn−1 +xn−2 y+xn−3 y 2 +. . .+x2 y n−3 +xy n−2 +y n−1 )

Portanto, para quaisquer x, y ∈ Z, se x 6= y, segue que x − y|xn − y n .

• Se n é impar, vale que:

xn + y n = (x + y)(xn−1 − xn−2 y + . . . − xy n−2 + y n−1 )

De fato, basta tomar xn + y n = xn − (−y)n

• Se n = 2k é par, vale que:

x2k − y 2k = (x2 − y 2 )(x2k−2 + x2k−4 y 2 + . . . + x2 y 2k−4 + y 2k−2 )

Tomando ainda x2 − y 2 = (x − y)(x + y), podemos fazer mais

x2k −y 2k = (x−y)(x+y)(x2k−2 +x2k−4 y 2 +. . .+x2 y 2k−4 +y 2k−2 )

Nos casos em que não existe um inteiro satisfazendo tal condição,

Neste exemplo, temos que 5 "cabe"24 vezes em 123, deixando

Certamente, para aplicar tal processo de divisão, precisamos que b 6=

Neste par, o número q é chamado quociente e r o resto da divisão

• se b = 3q + 1 : b2 = (3q + 1)2 = 3(3q 2 ) + 3(2q) + 1 =

• se b = 3q + 2 : b2 = (3q + 2)2 = 3(3q 2 ) + 3(4q) + 3 · 1 + 1 =

Para avaliar se um certo número inteiro diferente de zero divide

• Critério de Divisibilidade por 2: Um número é divisível

• Critério de Divisibilidade por 3: Um número é divisível

• Critério de Divisibilidade por 4: Um número é divisível

• Critério de Divisibilidade por 5: Um número é divisível

• Critério de Divisibilidade por 6: Um número é divisível

• Critério de Divisibilidade por 7: Um número é divisível

• Critério de Divisibilidade por 8: Um número é divisí-

• Critério de Divisibilidade por 9: Um número é divisível

• Critério de Divisibilidade por 10: Um número é divisível

• Critério de Divisibilidade por 11: Um número é divisível

Os problemas estão classificados por nível de dificuldade:

1. Para todo inteiro a, prove que 4 não divide (a2 + 2).

2. Mostre que 3|7n − 4n , para todo n ≥ 1.

3. Prove que se a e b são ímpares, então 8|(a2 − b2 ).

4. Mostre que se 7|3a + 2b então 7|4a − 2b.

5. N Mostre que 9 divide n · 4n+1 − (n + 1) · 4n + 1

6. N Prove o critério de divisibilidade por 7.

7. N Prove o critério de divisibilidade por 9.

8. N Mostre que se 19|3x + 7y então 19|43x + 75y.

9. N Sejam a = bq+r = (b+1)q 0 +r0 , com a, b positivos, 0 ≤ r < b,

10. N Prove que se f (x) é um polinômio de coeficientes inteiros e

11.  Prove que nenhum inteiro da sequência 11, 111, 1111, . . . é

12.  Encontre todos os inteiros positivos n tais que 2n2 + 1|n3 +

14.  (OBM 2011) Qual é o maior inteiro positivo n tal que

16.  (CONE SUL, Prova de Seleção, 2015) Para cada número

g(1) + g(2) + g(3) + . . . + g(22015 )

17.  (OBM 2000) É possível encontrar duas potências de 2, dis-

18.  (OBM 2005) Prove que a soma 1k + 2k + . . . + nk , onde n é

19.  (IMO 2011) Seja f uma função do conjunto dos inteiros no

20. F (IMO 2007) Sejam a e b inteiros positivos. Mostre que, se

Máxim Divisor Comum,

11. Prove que nenhum inteiro da sequência 11, 111, 1111, . . . é

12. Encontre todos os inteiros positivos n tais que 2n2 + 1|n3 +

14. (OBM 2011) Qual é o maior inteiro positivo n tal que

16. (CONE SUL, Prova de Seleção, 2015) Para cada número

17. (OBM 2000) É possível encontrar duas potências de 2, dis-

18. (OBM 2005) Prove que a soma 1k + 2k + . . . + nk , onde n é

19. (IMO 2011) Seja f uma função do conjunto dos inteiros no

11. (OBMEP - Banco de Questões 2015) Em uma lousa são

12. Sejam an = 100 + n2 e dn = mdc(an , an+1 ). Calcular dn

13. Demonstrar que se mdc(a, 2n+1 ) = 2n e mdc(b, 2n+1 ) = 2n ,

14. Demonstrar que, se a, b, c, d, m, n são inteiros tais que ad −

15. Demonstrar que mdc(2a − 1, 2b − 1) = 2mdc(a,b) − 1 para todo

16. (OBM 2011) Existem 2011 inteiros positivos a1 < a2 <

18. (OBM 2013) Seja A = {1, 2, 3, . . . , 20} o conjunto dos 20

19. (IMO 1992) Encontrar todos os inteiros a, b, c, com 1 < a <