MATEMÁTICA DISCRETA

Notas de Aulas

Prof. George Ney

 2. Divisibilidade e Congruência

2.1 Divisibilidade
Definição 2.1.1 Dados os inteiros a e b, diz-se que "a divide b"e escreve-se a|b, se existe um inteiro c tal
que b = a · c.

a|b ⇐⇒ ∃ c ∈ Z; b = a · c

Alternativamente, a|b pode ser lido como "a é divisor de b", "a é um fator de b"ou "b é múltiplo de a".
Quando não se tem a|b, escreve-se a ̸ |b.

Proposição 2.1.1 — Propriedades. Para a, b, c, x e y, todos números inteiros:

• D1: a|a (reflexiva);
• D2: se a|b, então b = 0 ou |a| ≤ |b| (limitação);
• D3: se a|b e b|a, então |a| = |b| (anti-simétrica);
• D4: se a|b e b|c, então a|c (transitiva);
• D5: se a|b e a|c, então a|(bx + cy);
• D6: seja a = b + c e suponha que d|b, então d|a ⇔ d|c.

2.1.1 Exemplos e Problemas

x2 5
Problema 2.1 Quantos pares de números inteiros (x, y) satisfazem a relação + = 7?
2 y
Problema 2.2 Encontre todos os pares de inteiros positivos a e b tais que 79 = ab + 2a + 3b.

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

Solução: Desde que 7|7a e 7|3a + 2b, então 7|[7a − (3a + 2b)] = 4a − 2b. ■

Problema 2.3 Mostre que se 3|a + 7b, então 3|a + b.

Problema 2.4 Mostre que se 7|a + 3b, então 7|13a + 11b.
Problema 2.5 Mostre que se 19|3x + 7y, então 19|43x + 75y.
Problema 2.6 Mostre que se 17|3a + 2b, então 17|10a + b.
Problema 2.7 Mostre que se para algum n, m|(35n + 26), m|(7n + 3) e m > 1, então m = 11.
Problema 2.8 Prove que para a ̸= 0, d e n, todos números inteiros, d|n ⇔ ad|an.
24 Capítulo 2. Divisibilidade e Congruência

Exemplo 2.2 Encontre todos os inteiros positivos n tais que (2n2 + 1)|(n3 + 9n − 17).
Solução: Dado que (2n2 + 1)|(n3 + 9n − 17) e (2n2 + 1)|(2n2 + 1), tem-se

(2n2 + 1)|[(n3 + 9n − 17) · 2 + (2n2 + 1) · (−n)].

Isto acarreta,

(2n2 + 1)|(17n − 34).

Há duas hipóteses:

17n − 34 = 0 ⇔ n = 2

ou, utilizando a propriedade da limitação,

|2n2 + 1| ≤ |17n − 34| ⇔ n = 1, n = 4 ou n = 5.

Testando tais valores, n = 2 e n = 5 são soluções. ■

Problema 2.9 Encontre todos os números inteiros positivos n para os quais n + 1|n2 + 1.
Problema 2.10 Quantos números inteiros positivos n existem tais que n + 3 divide n2 + 7?
Problema 2.11 — Leningrado, 1991. Cada um dos naturais a, b, c e d é divisível por ab − cd, que também
é um número natural. Prove que ab − cd = 1.
Problema 2.12 Pode o número A = 111 . . . 1, formado por trezentos 1’s, ser um quadrado perfeito?

Exemplo 2.3 — Maio, 2006. Encontre todos os naturais a e b tais que a|(b + 1) e b|(a + 1).
Solução: Pela propriedade da limitação, temos a ≤ b + 1 e b ≤ a + 1. Assim, a − 1 ≤ b ≤ a + 1. Temos
os seguintes os casos:
(i) a = b. Como a|b + 1 e a|b (pois b = a) temos que a|[(b + 1) − b] = 1. Assim, a = 1, gerando a solução
única (a, b) = (1, 1);
(ii) a = b + 1. Como b|a + 1 e b|a − 1 (pois b = a − 1) temos que b|[(a + 1) − (a − 1)] = 2. Assim, b = 1
ou b = 2 e nesse caso, temos as soluções (3, 2) e (2, 1);
(iii) a = b − 1. De modo análogo a (ii) obtemos (1, 2) e (2, 3). ■

Exemplo 2.4 — AIME, 1986. Qual é o maior inteiro n para o qual n3 + 100 é divisível por n + 10?
Solução: Temos que

n3 + 103 = (n + 10)(n2 − 10n + 100).

Assim,

n3 + 100 = (n + 10)(n2 − 10n + 100) − 900.

Desde que (n + 10)|(n3 + 100), então (n + 10)|900. Assim, o maior inteiro n para o qual n + 10 divide
900 é 890. ■

Exemplo 2.5 — Leningrado, 1989. Seja A um número natural maior

√ que 1, e seja B um número natural
que é um divisor de A2 + 1. Prove que se B − A > 0, então B − A > A.
Solução: Seja B − A = q. Assim, (A + q)|(A2 + 1) e desde que (A − q) · (A + q) = A2 − q2 é divisível
por A + q, podemos concluir que A + q|[(A2 + 1) − (A2 − q2 )] = q2 + 1. Pela propriedade da limitação,
A + q ≤ q2 + 1. Nessa desigualdade,
√ não podemos ter q = 1 pois A > 1. Usando então que q > 1, temos
2 2
A ≤ q − q + 1 < q , ou seja, A < q. ■
2.1 Divisibilidade 25

Exemplo 2.6 — ARML, 2003. Encontre o maior divisor de 1001001001 que não exceda 10000.
Solução: Tem-se que

1001001001 = 1001 · 106 + 1001 = 1001 · 106 + 1 = 7 · 11 · 13 · 106 + 1 .

Observe que x6 + 1 = x2 + 1 x4 − x2 + 1 . Donde 106 + 1 = 101 · 9901 e assim 1001001001 =

7 · 11 · 13 · 101 · 9901. Não é difícil verificar que nenhuma combinação dos fatores 7, 11, 13 e 101 pode
gerar um produto maior que 9901 e menor que 10000. ■

n
Exemplo 2.7 Seja n um número inteiro positivo. Prove que 32 + 1 é divisível por 2, mas não por 4.
n n
Solução: Claramente, 32 é ímpar e 32 + 1 é par. Observe também que
n n−1 n−1 n−1
32 = (32 )2 = 92 = (8 + 1)2 .

Lembremos o Binômio de Newton,

(x + y)m = xm + m1 xm−1 y + m m


m−2 2
m−1
2 x y +...+ m−1 xy + ym .

Tomando x = 8, y = 1 e m = 2n−1 na equação acima, vemos que cada parcela, com exceção da última
(ou seja, ym = 1), é um múltiplo de 8 (que é um múltiplo de 4).
n n
Portanto, o resto de 32 ao dividir por 4 é igual a 1 e o resto de 32 + 1 ao dividir por 4 é igual a 2. ■

Exemplo 2.8 Encontre o maior n tal que 2n |31024 − 1.

Solução: Observe que 210 = 1024 e x2 − y2 = (x + y)(x − y). Assim,
10 9 9
32 − 1 = (32 + 1)(32 − 1)
9 8 8
= (32 + 1)(32 + 1)(32 − 1)
= ...
9 8 7 1 0
= (32 + 1)(32 + 1)(32 + 1) . . . (32 + 1)(32 + 1)(3 − 1).
k
Pelo exemplo anterior, 2|(32 + 1) para todo inteiro positivo k.
Portanto, a resposta é 9 + 2 + 1 = 12. ■

Exemplo 2.9 Para quais valores de a ∈ N a expressão a4 + 4 é um número primo?

Solução: Note que

a4 + 4 = (a2 + 2)2 − 4a2 = (a2 + 2)2 − (2a)2 = (a2 + 2 + 2a)(a2 + 2 − 2a).

Desse modo, a4 + 4 é sempre composto para a ̸= 1. ■

Exemplo 2.10 Prove que se a ∈ N, então 6|(2a3 + 3a2 + a).

Solução: Observe, de início, que

2a3 + 3a2 + a = a(2a2 + 3a + 1)

= a[2a2 + 2a + a + 1]
= a[2a(a + 1) + (a + 1)]
= a(a + 1)(2a + 1).

Assim,
 26 Capítulo 2. Divisibilidade e Congruência

2|a(a + 1)(2a + 1)
6|(2a3 + 3a2 + a) ⇔ 6|a(a + 1)(2a + 1) ⇔
3|a(a + 1)(2a + 1)
Isto de fato ocorre, uma vez que:
(i) Entre dois números consecutivos (a e a + 1) algum deles é par. Deste modo,

2|a(a + 1) ∴ 2|a(a + 1)(2a + 1)

(ii) Há 3 possibilidades para a (a = 3k ou a = 3k + 1 ou a = 3k + 2). De tal modo que,

a = 3k ⇒ 3|a ∴ 3|a(a + 1)(2a + 1)

a = 3k + 1 ⇒ 2a + 1 = 3(2k + 1) ⇒ 3|(2a + 1) ∴ 3|a(a + 1)(2a + 1)
a = 3k + 2 ⇒ a + 1 = 3(k + 1) ⇒ 3|(a + 1) ∴ 3|a(a + 1)(2a + 1)

De (i) e (ii) tem-se que 6|(2a3 + 3a2 + a). ■

Problema 2.13 Prove que se a é um número mutuamente primo com 6, então 24|(a3 − 1).
Problema 2.14 Prove que se a ∈ N, então 120|(a5 − 5a3 + 4a).
a a2 a3
Problema 2.15 Prove que se a é um número par, + + é um número inteiro.
12 8 24
a 5 a 4 7a 3 5a2 a
Problema 2.16 Prove que se a ∈ N, então + + + + é um número inteiro.
120 12 24 12 5

2.2 Algoritmo da Divisão

Teorema 2.2.1 — Algoritmo da Divisão. Dados dois inteiros a e b, b > 0, existe um único par de inteiros
q e r tais que

a = qb + r, com 0 ≤ r < b, (r = 0 ⇔ b|a)

onde q é chamado de quociente e r de resto da divisão de a por b.

Prova: Como b > 0, existe q satisfazendo:

qb ≤ a < (q + 1)b

o que implica 0 ≤ a − qb e a − qb < b. Desta forma, se definirmos r = a − qb, teremos, garantida, a

existência de q e r. A fim de mostrarmos a unicidade, vamos supor a existência de outro par q1 e r1
verificando:

a = q1 b + r1 , com 0 ≤ r1 < b.

Disto temos (qb + r) − (q1 b + r1 ) = 0 ⇒ b(q − q1 ) = r1 − r, o que implica b|(r1 − r). Mas, como
r1 < b e r < b, temos |r1 − r| < b e, portanto, como b|(r1 − r) devemos ter r1 − r = 0 o que implica r = r1 .
Logo q1 b = qb ⇒ q1 = q, uma vez que b ̸= 0.

2.3 Máximo Divisor Comum

Proposição 2.3.1 — Máximo Divisor Comum. Dados a, b ∈ Z existe um único d ∈ N tal que d|a, d|b e,
para todo c ∈ N, se c|a e c|b então c|d. Além disso existem x, y ∈ Z com d = ax + by.
Esse natural d é chamado o máximo divisor comum, ou mdc, entre a e b. Escrevemos d = mdc(a, b) ou se
não houver possibilidade de confusão, d = (a, b).
Prova: O caso a = b = 0 é trivial (temos d = 0). Nos outros casos, seja I(a, b) = {ax + by; x, y ∈ Z} e
seja d = ax0 + by0 o menor elemento positivo de I(a, b). Como d ∈ N∗ , existem q, r ∈ Z com a = dq + r e
0 ≤ r < d. Temos r = a − dq = a(1 − qx0 ) + b(−qy0 ) ∈ I(a, b); como r < d e d é o menor elemento positivo
de I(a, b), r = 0 e d|a. Analogamente, d|b. Suponha agora que c|a e c|b; temos c|ax + by para quaisquer
 2.4 Problemas Relacionados 27

valores de x e y donde, em particular, c|d.

Definição 2.3.1 Os inteiros a e b são relativamente primos quando (a, b) = 1.

Teorema 2.3.2 Se a e b são inteiros e a = qb + r onde q e r são inteiros, então (a, b) = (b, r).
Prova: Da relação a = qb + r podemos concluir que todo divisor de b e r é um divisor de a. Esta mesma
relação, escrita na forma r = a − qb, nos diz que todo divisor de a e b é um divisor de r. Logo o conjunto
dos divisores comuns de a e b é igual ao conjunto dos divisores comuns de b e r, o que nos garante o
resultado (a, b) = (b, r).

2.4 Problemas Relacionados

Exemplo 2.11 — Maio, N2. Quantos são os números de sete algarismos que são múltiplos de 388 e
terminam em 388?
Solução: O número se expressa como

n · 103 + 388,

em que n é um número de quatro algarismos. Ora,

n · 103 + 388 = k · 388 ⇒ n · 103 = (k − 1) · 388.

Mas 388 = 22 · 97, então n deve ser múltiplo de 97. Assim n = t · 97, com 11 ≤ t ≤ 103. São 93 números.
■

Problema 2.17 Encontre os inteiros que, na divisão por 7, deixam um quociente igual ao resto.
Problema 2.18 Determinar os números que divididos por 17 dão um resto igual ao quadrado do quociente
correspondente.
Problema 2.19 — OCM, 1994. Seja A = 777 . . . 77 um número onde o dígito 7 aparece 1001 vezes.
Determinar o quociente e o resto da divisão de A por 1001.
Problema 2.20 Encontre um inteiro que deixa resto 4 na divisão por 5 e resto 7 na divisão por 13.
Problema 2.21 Encontre o menor inteiro que, dividido por 29 deixa resto 5, e dividido por 31 dá resto 28.

Teorema 2.4.1 — Teorema dos Restos. Se b1 e b2 deixam restos r1 e r2 na divisão por a, respectivamente,
então:

b1 + b2 deixa o mesmo resto que r1 + r2 na divisão por a;

b1 · b2 deixa o mesmo resto que r1 · r2 na divisão por a.

Problema 2.22 Qual o resto que o número 1002 · 1003 · 1004 deixa quando dividido por 7?
Problema 2.23 Qual o resto que o número 45000 deixa quando dividido por 3?
Problema 2.24 — OBM. Mostre que se n é ímpar, então n2 − 1 é divisível por 8.
Problema 2.25 Qual o resto que o número 22k+1 deixa quando dividido por 3?
Problema 2.26 Qual o resto de n3 + 2n na divisão por 3?
Problema 2.27 Prove que:
a) 5 | (n5 + 4n), ∀n ∈ Z;
b) 3 ∤ (n2 + 1), ∀n ∈ Z;
c) 9 ∤ (n3 + 2), ∀n ∈ Z;
d) 24 | (n3 − n), ∀n(ímpar)∈ Z.
Problema 2.28 Prove que, para todo inteiro positivo n o número n5 − 5n3 + 4n é divisível por 120.
Problema 2.29 Qual é o último algarismo do número 777777 ?
Problema 2.30 Prove que existe um número natural n tal que os números n + 1, n + 2, . . . , n + 2016 são
todos compostos.
Problema 2.31 Se p > 3 é primo, prove que o resto da divisão de p2 por 12 é igual a 1.
 28 Capítulo 2. Divisibilidade e Congruência

Problema 2.32 — OBMEP, N2, 2017. Um número inteiro n é chamado de bilegal se n é maior do que 1 e
n2 é igual à soma de n inteiros positivos consecutivos. Por exemplo, 3 é bilegal, pois 32 = 9 = 2 + 3 + 4 (3
inteiros consecutivos).
a) Verifique que 5 é bilegal.
b) Verifique que 4 não é bilegal.
c) Explique por que nenhum número par é bilegal e todo número ímpar maior do que 1 é bilegal.
Problema 2.33 Sejam m e n naturais tais que mn + 1 é múltiplo de 24, mostre que m + n também é múltiplo
de 24.
Problema 2.34 Seja n um inteiro positivo tal que 3n + 7 é um quadrado perfeito. Prove que n + 3 é a soma
de três quadrados perfeitos, com possível repetição.
Problema 2.35 Prove que o produto de qualquer sequência de k inteiros consecutivos é divisível por k!.
n
Problema 2.36 Um número da forma Fn = 22 + 1 é chamado número de Fermat. Prove que quaisquer dois
números de Fermat, diferentes entre si, são relativamente primos.
Problema 2.37 Prove que existem infinitos primos da forma 6k + 5.
Problema 2.38 Para n ≥ 2 e k um inteiro positivo qualquer temos (n − 1)|(nk − 1).
Problema 2.39 Se a e b são ímpares, então a2 + b2 não pode ser um quadrado perfeito.
Problema 2.40 Mostre que se m e n são inteiros positivos com m > 1, então n < mn .

2.5 Congruência
Definição 2.5.1 Sejam a, b e m > 0 números inteiros. Dizemos que a é côngruo a b, módulo m, se
m|(a − b). Escreve-se:

a ≡ b (mod m) (2.1)

Dito de outro modo: a e b são côngruos, módulo m, se ambos deixam o mesmo resto quando divididos
por m.

Proposição 2.5.1 Se a e b são inteiros, temos que a ≡ b (mod m) se, e somente se, existir um inteiro c tal
que a = b + cm.
Prova: Se a ≡ b (mod m), então m|(a − b), o que implica na existência de um inteiro c tal que a − b = cm,
isto é, a = b + cm. A reciproca é trivial, pois da existência de um c satisfazendo a = b + cm, temos cm = a − b,
ou seja, que m|(a − b), isto é, a ≡ b (mod m).

Teorema 2.5.2 Se a, b, m e d são inteiros, m > 0, as seguintes sentenças são verdadeiras:

• C1: Para todo m > 0, a relação ≡ é reflexiva, simétrica e transitiva, ou seja, é uma relação de
equivalência;
• C2: Para quaisquer a, b ∈ Z: a ≡ b (mod m) se, e somente se, a e b fornecem o mesmo resto na
divisão euclidiana por m;
• C3: Se a ≡ b (mod m), então a ± c ≡ b ± c(mod m) e ac ≡ bc(mod m), para todo c ∈ Z;
• C4: Se a ≡ b (mod m) e c ≡ d (mod m), então a ± c ≡ b ± c (mod m) e ac ≡ bd (mod m);
• C5: Se a ≡ b (mod m), então ra ≡ rb (mod m) e ar ≡ br (mod
 m), m  todo inteiro r ≥ 1;
para
• C6: Se ca ≡ cb (mod m) e mdc(m, c) = d > 0, então a ≡ b mod .
d

Corolário 2.5.3 Se ca ≡ cb(mod m) e mdc(m, c) = 1, então a ≡ b (mod m).

Corolário 2.5.4 Se ca ≡ cb(mod p), onde p é primo e p ∤ c, então a ≡ b(mod p).

Definição 2.5.2 — Sistema Completo de Restos módulo m. Um conjunto de m > 0 inteiros forma
um Sistema Completo de Restos módulo m se dois quaisquer desses números, diferentes entre si, são
 2.5 Congruência 29

incôngruos módulo m.
Proposição 2.5.5 Se {r1 , r2 , . . . , rm } é um sistema completo de restos módulo m, então todo inteiro a é
côngruo a um e somente um dos ri .

2.5.1 Problemas
Problema 2.41 Ache os restos nas seguintes divisões:
a) 245 por 7;
b) 1110 por 100;
c) (310 · 425 + 68 ) por 5;
d) (52 · 4841 + 285 ) por 3;
e) 1169 por 3.
Problema 2.42 Encontre o resto de 22225555 + 55552222 na divisão por 7.
Problema 2.43 Prove que o número M = 111 + 2222 + 3333 + 4444 + 5555 − 12345 não é um quadrado
perfeito.
Problema 2.44 Quantos calendários anuais diferentes existem? Quantos anos consecutivos são necessários
para que todos estes calendários sejam usados?
Problema 2.45 Enuncie e demonstre Critérios de Divisibilidade por 2, 3, 4, 5, 7, 8, 9, 10 e 11.
Problema 2.46 a) Seja n um inteiro positivo, mostre que o número
(5n + 1)(5n + 2)(5n + 3)(5n + 4)
2
é inteiro e que o dígito das unidades é 2.
b) Se é verdade que
51 · 52 · 53 · . . . · 200 = (10m + n) · 10 p ,
onde m, n, p são números inteiros positivos e 0 < n < 10. Encontre o valor de n + p.

Exemplo 2.12 Mostrar que 47|(223 − 1).

Solução: Devemos mostrar que 223 − 1 ≡ 0 (mod 47), ou seja, 223 ≡ 1 (mod 47).
Note que 210 = 1024 = 37 + 47 · 21, o que significa que 210 ≡ 37 (mod 47).
Assim,

210 ≡ −10 (mod 47) ⇒ (210 )2 ≡ (−10)2 (mod 47) ⇒ 220 ≡ 6 (mod 47).

Desse modo,

220 · 23 ≡ 6 · 23 (mod 47) ∴ 223 ≡ 1 (mod 47).

Problema 2.47 Encontrar o resto da divisão de 734 por 51 e o resto da divisão de 563 por 29.
Problema 2.48 Qual o resto da divisão euclidiana de

s = 15 + 25 + 35 + . . . + 995 + 1005
por 4? Justifique.
Problema 2.49 Mostre que o resto da divisão euclidiana de

s(n) = 1! + 2! + 3! + . . . + n!
por 12 é 9, para todo n ≥ 4.
Problema 2.50 Se n é múltiplo de 4, qual o resto da divisão de

1n + 2n + 3n + . . . + 9n
por 10?
30 Capítulo 2. Divisibilidade e Congruência

Problema 2.51 Sabendo que 74 = 2401, ache os algarismos da dezena e da unidade do número 799999 .
Problema 2.52 Encontre o resto da divisão de 9 · 99 · 999 · . . . · 99 . . . 9} quando dividido por 1000.
| {z
999 9′ s
2
Problema 2.53 — EUA. Determine a soma dos dígitos na base 10 de (104n +8 + 1)2 , sendo n um inteiro
positivo.

Exemplo 2.13 Mostrar que para a e b inteiros temos que 3|(a2 + b2 ) ⇒ 3|a e 3|b.
Solução: Suponha por absurdo, e sem perda de generalidade, que 3 ∤ a.
Analisemos pela tabela abaixo as possíveis congruências de a2 + b2 , módulo 3.
a\b 0 1 2 (mod 3)
1 1 2 2
≡ a2 + b2
2 1 2 2

De todo modo, a2 + b2 ̸≡ 0 (mod 3). ■

Exemplo 2.14 Mostrar que 5n3 + 7n5 ≡ 0 (mod 12) para todo inteiro n.
Solução: Ora,

5n3 + 7n5 ≡ −7n3 + 7n5 ≡ 7n3 (n2 − 1) (mod 12).

Analisemos pela tabela abaixo as possíveis congruências de 7n3 (n2 − 1), módulo 12.

n≡ 0 ±1 ±2 ±3 ±4 ±5 6 (mod 12)
n3 ≡ 0 ±1 ±8 ±3 ±4 ±5 0 (mod 12)
n2 − 1 ≡ −1 0 3 8 3 0 −1 (mod 12)
7n (n2 − 1) ≡
3 0 0 0 0 0 0 0 (mod 12)

De todo modo, 5n3 + 7n5 ≡ 0 (mod 12). ■

Exemplo 2.15 — OBM. Sejam x, y, z inteiros tais que x3 + y3 − z3 é múltiplo de 7. Mostre que um desses
números é múltiplo de 7.
Solução: Suponha por absurdo que nenhum dos números é múltiplo de 7. Ademais, por hipótese,

x3 + y3 − z3 ≡ 0 (mod 7) ⇔ z3 ≡ x3 + y3 (mod 7).

Além disso, para todo n inteiro,

n≡ ±1 ±2 ±3 (mod 7)
n3 ≡ ±1 ±1 ∓1 (mod 7)

Usando a tabela acima, analisemos as possíveis congruências de x3 + y3 , módulo 7.

x3 \y3 −1 1 (mod 7)
−1 −2 0
z3 ≡ x 3 + y3
1 0 2

Note que z3 ̸≡ −2, 2 (mod 7) (pois n3 ≡ ±1 (mod 7)) e z3 ̸≡ 0 (mod 7) (suposição por absurdo).
Deste modo, x ou y ou z é múltiplo de 7. ■

Problema 2.54 — OBM. Dados 3 inteiros tais que x2 + y2 = z2 , mostre que x e y não são ambos ímpares e
que xy é múltiplo de 6.
Problema 2.55 — OBM. Demonstre que:
a) O quadrado de um inteiro é da forma 8n ou 8n + 1 ou 8n + 4.
2.5 Congruência 31

b) Um inteiro da forma 4a (8b + 7), com a e b inteiros não negativos, não pode ser uma soma de três quadrados
de inteiros.
Exemplo 2.16 — OBM. Prove que não existem números inteiros x, y satisfazendo a equação

15x2 − 7y2 = 9.

Solução: Apliquemos congruência módulo 5 na equação acima:

15x2 − 7y2 ≡ 9 (mod 5) ⇒ 3y2 ≡ 4 (mod 5).

Analisemos pela tabela abaixo as possíveis soluções de 3y2 ≡ 4 (mod 5).

y≡ 0 ±1 ±2 (mod 5)
y2 ≡ 0 1 4 (mod 5)
3y2 ≡ 0 3 2 (mod 5)

Em quaisquer dos casos, não há soluções para 3y2 ≡ 4 (mod 5). ■

Exemplo 2.17 — OBM. Mostre que nenhum número inteiro da forma 1 + 4n é divisível por 3.
Solução: Veja que,

4 ≡ 1 (mod 3) ⇒ 4n ≡ 1n (mod 3) ∴ 1 + 4n ≡ 2 (mod 3).

Exemplo 2.18 Seja n um inteiro maior que três. Prove que

1! + 2! + . . . + n!

não pode ser uma potência perfeita.

Solução: Para n = 4, temos 1! + 2! + 3! + 4! = 33, que não é uma potência perfeita. Para k ≥ 5,
k! ≡ 0(mod10). Segue-se que para n ≥ 5, 1! + 2! + 3! + 4! + . . . + n! ≡ 3(mod10), por isso, não pode ser
um quadrado perfeito, ou outra potência par.
Para potências ímpares, o argumento a seguir estabelece todos os casos:
• por verificação direta para todo n < 9;
• para k ≥ 9, k! é um múltiplo de 27, enquanto 1! + 2! + . . . + 8! é um múltiplo de 9, mas não de 27.
Daí 1! + 2! + . . . + n! não pode ser um cubo ou potência superior.
■

Problema 2.56 — AIME, 1996. Um aluno entediado caminha por um corredor que contém uma fileira de
armários fechados, numerados de 1 a 1024. Ele abre o armário com o número 1 e depois alterna entre pular e
abrir cada armário a partir de então. Quando ele chega ao final do corredor, o aluno se vira e começa a voltar.
Ele abre o primeiro armário fechado que encontra e depois alterna entre pular e abrir cada armário fechado a
partir de então. O aluno continua vagando dessa maneira até que todos os armários estejam abertos. Qual é o
número do último armário que ele abre?
r
Exemplo 2.19 Seja n > 1 um número inteiro. Prove que o número 11 . . . 1} 44
| {z . . . 4} não é racional.
| {z
n 2n
 32 Capítulo 2. Divisibilidade e Congruência

Solução: Veja que

. . . 1} 44
|11{z . . . 4} = (103n−1 + 103n−2 + . . . + 102n ) + 4 · (102n−1 + 102n−2 + . . . + 10 + 1)
| {z
n 2n
102n (10n − 1) (102n − 1)
= +4·
9 9
102n (10n − 1) (10n − 1) · (10n + 1)
= +4·
9 9
(10n − 1)
= · (102n + 4 · 10n + 4)
9
(102n + 2)2
= · (10n − 1).
9
Então, para que 11 . . . 1} 44
| {z . . . 4} seja um quadrado perfeito, (10n − 1) deve ser quadrado perfeito. Ou seja,
| {z
n 2n
(10n − 1) = k2 . Isto significa que k deve ser ímpar.
Note,
k≡ 1 3 (mod 4)
k2 ≡ 1 1 ≡ 10n − 1
Mas veja que para n > 1, tem-se sempre 10n − 1 ≡ 3.
Logo, para n > 1, |11{z
. . . 1} 44 . . . 4} não pode ser quadrado perfeito.
| {z ■

n 2n

2.5.2 Congruência Linear

Definição 2.5.3 Uma congruência algébrica do tipo

ax ≡ b (mod m) (2.2)

onde a, b, m ∈ Z, a ̸= 0 e m > 0, e x é uma variável em Z, recebe o nome de congruência linear ou

congruência de primeiro grau.

Proposição 2.5.6 Uma congruência linear ax ≡ b (mod m) admite soluções em Z se, e somente se, b é
divisível por d = mdc{a, m}. E, neste caso, se x0 é uma solução particular, então o conjunto de todas as
soluções tem d elementos, a saber:
m m m m
x0 , x0 + , x0 + 2 · , x0 + 3 · , . . . , x0 + (d − 1) · . (2.3)
d d d d
Problema 2.57 Resolva as seguintes congruências lineares:
a) 5x ≡ 2 (mod 26);
b) 3x ≡ 17 (mod 5);
c) 34x ≡ 60 (mod 98);
d) 6x ≡ 15 (mod 21);
e) 20x ≡ 7 (mod 15);
f) 14x ≡ 36 (mod 48);
g) 5x ≡ −38 (mod 7);
h) 20x ≡ 30 (mod 31).

2.5.3 Equações Diofantinas

Teorema 2.5.7 — Euclides. Sejam a, b e c números inteiros e defina d = mdc(b, c). Considere a equação
diofantina linear:
bx + cy = a
2.5 Congruência 33

Então temos:
1. Se d ∤ a, então a equação dada não tem solução inteira;
2. Se d | a, então a equação dada tem infinitas soluções inteiras e, além disso, o conjunto de pontos
inteiros pode ser parametrizado a partir de um ponto particular. Precisamente, fazendo a = dα,
b = dβ e c = dγ a equação fica da forma:

β x + γy = α

e dada uma solução particular (x0 , y0 ) nos inteiros, então todas as outras soluções inteiras da equação
são da forma: 
x = x0 + γk
k∈Z
y = y0 − β k

Problema 2.58 Resolva cada uma das seguintes equações diofantinas:

a) 3x + 4y = 20;
b) 5x − 2y = 2;
c) 24x + 138y = 18;
d) 18x − 20y = −8;
e) −26x + 39y = 65;
f) 12x − 27y = 33.
Problema 2.59 Dividir 100 em duas parcelas positivas tais que uma é múltipla de 7 e a outra de 11.
Problema 2.60 Ache todos os inteiros estritamente positivos com a seguinte propriedade: fornecem resto 6
quando divididos por 11 e resto 3 quando divididos por 7.
Problema 2.61 Se um macaco sobe uma escada de dois em dois degraus, sobra um degrau; se ele sobe
de três em três degraus, sobram dois degraus. Quantos degraus a escada possui, sabendo que o número de
degraus é múltiplo de sete e está compreendido entre 40 e 100.
Problema 2.62 Um grupo de homens, alguns dos quais acompanhados pelas esposas, gastaram 1000 dólares
num hotel. Cada homem gastou 19 dólares e cada mulher, 13 dólares. Determine quantas mulheres e quantos
homens estavam no hotel.
Problema 2.63 Dê uma interpretação geométrica, em termos de coordenadas cartesianas, para o fato de que
uma equação diofantina linear em duas incógnitas quando admite uma solução, admite infinitas.
Proposição 2.5.8 Um sistema de congruências lineares


x ≡ a1 (mod m1 )


x ≡ a2 (mod m2 )

.. (2.4)


 .

x ≡ ar (mod mr )


admite soluções se, e somente se, ai − a j é divisível por di j = mdc(mi , m j ), para qualquer par de índices
i, j(i ̸= j). Neste caso, se x0 , é uma solução particular, então a solução geral do sistema é dada por:

x ≡ x0 (mod m) (2.5)

onde m = mmc{m1 , m2 , . . . , mr }.
Proposição 2.5.9 — Teorema Chinês do Resto. Sejam m1 , m2 , . . . , mr números inteiros maiores que
zero e tais que mdc{mi , m j } = 1, sempre que i ̸= j. Façamos m = m1 · m2 · . . . · mr e sejam b1 , b2 , . . . , br ,
respectivamente, soluções das congruências lineares

m
y ≡ 1 (mod m j )( j = 1, 2, . . . , r). (2.6)
mj
 34 Capítulo 2. Divisibilidade e Congruência

Então o sistema

x ≡ a1 (mod m1 )


x ≡ a2 (mod m2 )

.. (2.7)


 .

x ≡ ar (mod mr )


é solúvel para quaisquer a1 , a2 , . . . , ar ∈ Z e sua solução geral é dada por:

m m m
x ≡ a1 b1 + a2 b2 + . . . + ar br (mod m). (2.8)
m1 m2 mr

2.5.4 Problemas
Problema 2.64 Determine todos os números naturais que, quando divididos por 18, deixam resto 6 e, quando
divididos por 14, deixam resto 4.
Problema 2.65 Ache o menor inteiro que fornece restos 1, 2, 5 e 5 quando dividido, respectivamente, por 2,
3, 6 e 12 (Yin-Hing - séc. VII).
Problema 2.66 Retirando-se os ovos contidos num cesto 2, 3, 4, 5 e 6 de cada vez restarão, respectivamente,
1, 2, 3, 4 e 5 ovos. Quando eles são retirados de 7 em 7, não sobra nenhum no cesto. Qual o menor número
de ovos que um cesto nessas condições pode conter? (Brahmagupta - séc. VII).
Problema 2.67 Dispomos de uma quantia de x reais menor do que 3000. Se distribuirmos essa quantia entre
11 pessoas, sobra um real; se a distribuirmos entre 12 pessoas, sobram dois reais, e se a distribuirmos entre
13 pessoas, sobram 3 reais. De quantos reais dispomos?
Problema 2.68 Ache todos os números que deixam resto 2, quando divididos por 7, deixam resto 3, quando
divididos por 11 e deixam resto 5, quando divididos por 13. Aponte a menor solução positiva.
Problema 2.69 Encontre três números inteiros consecutivos tais que o primeiro é divisível pelo quadrado de
um número primo, o segundo é divisível pelo cubo de um número primo e o terceiro é divisível pela quarta
potência de um número primo.
Problema 2.70 Descanse.

2.6 Problemas do Banco OBM

Problema 2.71 Quantos quadrados perfeitos existem entre 40.000 e 640.000 que são múltiplos simultanea-
mente de 3, 4 e 5?
Problema 2.72 Se subtrairmos de um número positivo x, de 2 algarismos, o número obtido de x por troca de
seus dígitos, obteremos um cubo perfeito. Ache os possíveis valores de x.
Problema 2.73 Sejam p, q inteiros positivos. Mostre que 2 p + 1 = q2 implica p = q = 3.
Problema 2.74 Dado um inteiro n, mostre que existem inteiros x e y tais que x2 − y2 = n, se, e somente se,
n = ab, com a e b inteiros de mesma paridade.
Problema 2.75 Seja n um inteiro maior que 1. Mostre que 4n + n4 não é primo.
Problema 2.76 Se n > 4 é um número não primo, prove que (n − 1)! é múltiplo de n.
Problema 2.77 Ache todas as soluções, no conjunto dos números naturais, para a equação (n + 1)k − 1 = n!.
Problema 2.78 Sejam a, b, c, d inteiros. Demonstre que

x2 + ax + b = y2 + cy + d
tem uma infinidade de soluções (x, y), com x e y inteiros, se, e somente se a2 − 4b = c2 − 4d.
1 1 1 1
Problema 2.79 Mostre que o número de soluções de + + = , com x, y e z naturais, é finito.
x y z 1983
Problema 2.80 Prove que, para cada número natural p, com p ≥ 3, existem p números naturais distintos
1 1 1
dois a dois: n1 , n2 , . . ., n p , tais que + +...+ = 1.
n1 n2 np
1 1 1
Problema 2.81 Mostre que, para todo natural n, n ≥ 2, 1 + + + . . . + não é inteiro.
2 3 n
 2.7 Problemas Finais 35

Problema 2.82 Seja n > 0 um número natural e an = n2 + n + 1. Demonstre que na sequência (an ) existem
infinitos termos ak iguais ao produto de dois termos da sequência.
Problema 2.83 Todo número inteiro positivo a pode ser fatorado na forma a = 2b (2c + 1) onde b e c são
inteiros não negativos. O número 2c + 1 é chamado fator ímpar de a. Por exemplo, o fator ímpar de 60 é
15. Seja n um número ímpar e positivo, a0 = 2n − 1 e ak+1 o fator ímpar de 3ak + 1 para k = 0, 1, . . . , n − 1.
Calcule an .
Problema 2.84 Sendo m inteiro positivo, mostre que existem sempre 3 ou 4 potências de 2 com m algarismos.
Ache os m para os quais existem 4.
Problema 2.85 Seja P(n) o número de fatores primos distintos de n. Prove que existe n0 tal que, se n > n0 ,
P(n) 1
então < 1983 .
n 10
Problema 2.86 Em quantos zeros termina 1000!?  
k
Problema 2.87 Seja p um número natural primo e k um número natural. Se p é divisor de para todo
i
1 ≤ i ≤ k − 1, então existe um natural m tal k = pm .
que 
n 
n + k −k
Problema 2.88 Calcule a somatória ∑ 2 para qualquer inteiro positivo n.
k=0
k
Problema 2.89 Dado um número inteiro n, mostre que existe um múltiplo de n que se escreve com os
algarismos 0 e 1 apenas. (Por exemplo, se n = 3, temos 111 ou 1011, etc...)
Problema 2.90 Obtenha todos os números de 10 dígitos, tais que o dígito que figura na posição k (para todo
k, com 0 ≤ k ≤ 9) seja igual ao número de vezes que o algarismo k figura no número.
Problema 2.91 Descanse.

2.7 Problemas Finais

Problema 2.92 Mostrar que se p é um ímpar e a2 + 2b2 = 2p, então a é par e b é ímpar.
Problema 2.93 Provar que para p primo (p − 1)! ≡ p − 1(mod 1 + 2 + 3 + . . . + (p − 1)).
Problema 2.94 Encontrar o máximo divisor comum de (p − 1)! − 1 e p! (p primo).
Problema 2.95 Mostrar que para n inteiro 3n2 − 1 nunca é um quadrado.
Problema 2.96 Resolver as seguintes congruências.
a) 5x ≡ 3 (mod 24).
b) 3x ≡ 1 (mod 10).
c) 23x ≡ 7 (mod 19).
d) 7x ≡ 5 (mod 18).
e) 25x ≡ 15 (mod 120).
Problema 2.97 Seja f (x) = a0 + a1 x + . . . + an xn um polinômio com coeficientes inteiros onde an > 0 e
n ≥ 1. Mostrar que f (x) é composto para infinitos valores da variável x.
Problema 2.98 Mostrar que se p1 e p2 são primos tais que p2 = p1 + 2 e p1 > 3, então p1 + p2 ≡ 0 (mod12).
Problema 2.99 Sejam p1 , p2 e p3 primos tais que p = p21 + p22 + p23 é primo. Mostrar que algum dos pi ’s é
igual a 3.
Problema 2.100 Mostrar que 3x2+ 4x 
2 ≡ 3 (mod 5) é equivalente a 3x2 − x2 + 2 ≡ 0 (mod 5).

pα
Problema 2.101 Mostrar que p| onde 0 < k < pα .
k
Problema 2.102 Mostrar que 310 ≡ 1 mod 112 .

Problema 2.103 Resolver os seguintes sistemas:

  
x ≡ 1 (mod 2)  2x ≡ 1 (mod 5)  x ≡ 7 (mod 11)
a) x ≡ 2 (mod 3) b) 3x ≡ 2 (mod 7) c) 3x ≡ 5 (mod 13)
x ≡ 5 (mod 7) 5x ≡ 7 (mod 11) 7x ≡ 4 (mod 5)
  

Problema 2.104 Encontrar todas as soluções de cada uma das seguintes congruências lineares.
a) 5x ≡ 3 (mod 7).
b) 13x ≡ 14 (mod 29).
36 Capítulo 2. Divisibilidade e Congruência

c) 15x ≡ 9 (mod 25).

d) 37x ≡ 16 (mod 19).
e) 5x ≡ 20 (mod 15).
Problema 2.105 Mostrar que a7 ≡ a (mod 21) para todo inteiro a.
Problema 2.106 Mostrar que para a e b inteiros, com (a, b) = 1 temos: aϕ(b) + bϕ(a) ≡ 1 (mod ab).
Problema 2.107 Provar ou dar contra-exemplo: "Se a e m são inteiros com (a, m) = 1, então m|(1 + a +
a2 + . . . + aϕ(m)−1 )”.
Problema 2.108 Mostrar que se p e q são primos, p ≥ q ≥ 5, então p2 − q2 ≡ 0 (mod 24).
Problema 2.109 Encontrar um sistema completo de resíduos módulo 11 formado somente por múltiplos de
6.
Problema 2.110 Encontrar um sistema completo de resíduos módulo 7 onde todos os elementos são números
primos.
Problema 2.111 Dado um primo p é sempre possível encontrar um sistema completo de resíduos módulo p
formado só por primos? Justificar.
Problema 2.112 Provar que, para todo número composto n, n ̸= 4, a congruência (n − 1)! ≡ 0 (mod n) é
verdadeira.
Problema 2.113 Descanse.