Mathematics">
Sumário: 1 Números Inteiros: Noções Fundamentais 5
Sumário: 1 Números Inteiros: Noções Fundamentais 5
Sumário: 1 Números Inteiros: Noções Fundamentais 5
2 INDUÇÃO MATEMÁTICA 17
2.1 ELEMENTO MÍNIMO DE UM CONJUNTO DE INTEIROS . . . . . . . . . . . . . . . . . . 17
2.2 PRINCÍPIO DA BOA ORDENAÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
2.3 PRINCÍPIO DE INDUÇÃO FINITA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.4 INDUÇÃO MATEMÁTICA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.5 EXEMPLOS DE DEMONSTRAÇÃO POR INDUÇÃO MATEMÁTICA . . . . . . . . . . . 19
2.6 OUTRAS FORMAS DA INDUÇÃO MATEMÁTICA . . . . . . . . . . . . . . . . . . . . . . 21
3 SOMATÓRIOS E PRODUTÓRIOS 25
3.1 SOMATÓRIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 PROPRIEDADES DOS SOMATÓRIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 SOMATÓRIOS DUPLOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.4 PRODUTÓRIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
3.5 PROPRIEDADES DOS PRODUTÓRIOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.6 TEOREMA DO BINÔMIO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.7 TRIÂNGULO DE PASCAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.8 PROPRIEDADES DO TRIÂNGULO DE PASCAL . . . . . . . . . . . . . . . . . . . . . . . 32
3.9 NÚMEROS TRIANGULARES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
4 DIVISIBILIDADE 39
4.1 RELAÇÃO DE DIVISIBILIDADE EM Z . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4.1.1 CONJUNTO DOS DIVISORES DE UM INTEIRO . . . . . . . . . . . . . . . . . . . 41
4.1.2 DIVISORES COMUNS DE DOIS INTEIROS . . . . . . . . . . . . . . . . . . . . . . 41
4.1.3 ALGORITIMO DA DIVISÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4.1.4 PARIDADE DE UM INTEIRO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
1
2 SUMÁRIO
7 CONGRUÊNCIAS 61
7.1 INTEIROS CONGRUENTES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
7.2 CARACTERIZAÇÃO DE INTEIROS CONGRUENTES . . . . . . . . . . . . . . . . . . . . 62
7.3 PROPRIEDADES DAS CONGRUÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
7.4 SISTEMAS COMPLETOS DE RESTOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
10 DIVISORES DE UM INTEIRO 87
10.1 DIVISORES DE UM INTEIRO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
10.2 NÚMERO DE DIVISORES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88
10.3 SOMA DE DIVISORES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
10.4 NOTAÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
10.5 PRODUTO DOS DIVISORES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
11 FUNÇÕES ARITMÉTICAS 95
11.1 CONCEITO DE FUNÇÃO ARITMÉTICA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
11.2 FUNÇÕES ARITMÉTICAS MULTIPLICATIVAS . . . . . . . . . . . . . . . . . . . . . . . . 95
11.3 FUNÇÃO DE MOBIUS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
11.4 FUNÇÃO MAIOR INTEIRO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
11.5 FÓRMULA DE INVERSÃO DE MOBIUS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
Z+ = {x ∈ Z | x , 0} = {0, 1, 2, 3, · · · }
Os inteiros positivos são também denominados inteiros naturais e por isso o conjunto dos inteiros positivos
é habitualmente designado pela letra N(N = Z∗+ ).
5
6 CAPÍTULO 1. NÚMEROS INTEIROS: NOÇÕES FUNDAMENTAIS
1) a + b = b + a e ab = ba
2) (a + b) + c = a + (b + c) e (ab) c = a (bc)
3) 0 + a = a e 1 · a = a
4) −a = (−1) a e a − a = a + (−a) = 0
5) a (b + c) = ab + ac
6) 0 · a = 0, e se (ab) = 0, então a = 0 ou b = 0.
Também existe uma "relação de ordem"entre os inteiros, representada pelo sinal "< ( menor que)", que
possui as seguintes propriedades:
Destas propriedades podem ser deduzidas muitas outras propriedades dos inteiros.
−(a + b) = (−1) (a + b)
= (−1) a + (−1) b
= (−a) + (−b)
Assim, p.ex.:
|3| = 3 e | − 5| = −(−5) = 5
Consoante a definição |a|, para todo inteiro a, temos:
Demonstração:
Com efeito:
p √ √ √
|ab| = (a · b)2 = a2 · b2 = a2 · b2 = |a| · |b|
|a + b| ≤ |a| + |b|
Demonstração:
Com efeito, pela definição de |a| temos:
|a + b| ≤ |a| + |b|
|a − b| ≤ |a| + |b|
Demonstração:
Com efeito:
1.4 FATORIAL
Definição 1.4.1 Chama-se fatorial de um inteiro não negativo n (n ≥ 0), o inteiro que se indica por n!, e tal que:
1 se n = 0 ou n = 1
(
n! =
n (n − 1) (n − 2) · · · 3 · 2 · 1 se n ≥ 2
Assim, p.ex.:
7! = 7 · 6 · 5 · 4 · 3 · 2 · 1 = 5040
Observe-se que, n! = n · (n − 1).!
Exemplo 1.4.1 Escrever, usando o símbolo de fatorial, o produto dos n primeiros inteiros positivos pares e o
produto dos n primeiros inteiros positivos ímpares.
2, 4, 6, · · · , 2n − 2, 2n
isto é:
2 · 1, 2 · 2, 2 · 3, · · · , 2 · (n − 1), 2 · n
Portanto:
2 · 4 · 6 · · · (2n − 2) · 2n = 2n (1 · 2 · 3 · · · (n − 1) · n) = 2n · nt .
1, 3, 5, · · · , 2n − 3, 2n − 1
Portanto:
1 · 2 · 3 · 4, · · · , (2n − 2) · (2n − 1) · 2n
1 · 3 · 5, · · · , (2n − 3) · (2n − 1) =
2 · 4 · 6, · · · , (2n − 2) · 2n
(2n)!
=
2n · n!
1 · 1! = 2! − 1
2 · 2! = 3! − 2!
3 · 3! = 4! − 3!
· · · · · · · · · · ··
n · n! = (n + 1)! − n!
Somando ordenadamente todas essas n igualdades e simplificando, obtemos:
1 · 1! + 2 · 2! + 3 · 3! + · · · + n · n! = (n + 1)! − 1
1.5. NÚMERO BINOMIAL 9
n(n − 1) · · · (k + 1) n(n − 1) · · · (n − k + 1)
!
n
= =
k (n − k)! k!
Assim, p.ex.: !
8 8! 8·7·6·5·4·3·2·1 8·7·6
= = = = 56
3 3! 5! 3 · 2 · 1 · 5 · 4 · 3 · 2 · 1 3 · 2 · 1
!
7 7·6·5 7·6·5
= = = 35
4 (7 − 4)! 3 · 2 · 1
Assim, p.ex.:
! ! !
18 18 19
+ =
9 10 10
! ! !
13 12 12
= +
8 8 7
Cololário 1.7.1 ! ! ! ! !
n n−1 n−2 k k−1
= + + ··· + +
k k−1 k−1 k−1 k−1
Substituindo, nesta relação, cada número binomial pelo seu complementar, obtemos:
! ! ! ! !
n n−1 n−2 k k−1
= + + ··· + +
n−k n−k n−k−1 1 0
Cololário 1.7.2 ! ! ! ! !
n n−1 n−2 n−k n−k−1
= + + ··· + +
k k k−1 1 0
Demonstração:
Consoante a relação de STIFEL, temos:
! ! !
n n−1 n−1
= +
k k−1 k
! ! !
n−1 n−2 n−2
= +
k−1 k−2 k−1
! ! !
n−2 n−3 n−3
= +
k−2 k−3 k−2
· · · · · · · · · · · · · · · · · · · · ··
n−k+1
! ! !
n−k n−k
= +
1 0 1
EXERCÍCIOS
1. Calcular a soma dos n primeiros inteiros positivos.
2. Calcular o inteiro positivo de n sabendo:
(mn)! = m! n! e (m + n) = m! + n!
6. Demonstrar:
(n − 1)! [(n + 1)! − n!] = (n!)2
12 CAPÍTULO 1. NÚMEROS INTEIROS: NOÇÕES FUNDAMENTAIS
(x + 1) (y + 2) = 2xy
10. Achar um inteiro positivo de dois algarismos que seja igual ao quadruplo da soma dos seus
algarismos.
14. Demonstrar:
n−k+1 n
! !
n
=
k k k−1
x2 − y2 = 88
19. O produto de um inteiro positivo de três algarismos por 7 termina à direita por 638. Achar esse
inteiro.
20. Determinar quantos algarismos se empregam para numerar todas as páginas de um livro que tem
2748 páginas.
22. Calcular a soma dos três maiores inteiros de, respectivamente, três, quatro e cinco algarismos.
23. Determinar a diferença entre o maior inteiro com seis algarismos diferentes e o maior inteiro com
cinco algarismos também diferentes.
24. Um livro tem 1235 páginas. Determinar o número de vezes que o algarismo 1 aparece na numeração
das páginas desse livro.
1.7. NÚMEROS BINOMIAIS CONSECUTIVOS 13
∗ ∗ 8 ∗ ∗ ∗
∗ 6 ∗ 1 ∗ ∗ ∗
(a) ∗ 9 1 3 2 (b)
5 9 6
4 ∗
26. Mostrar que o produto de quatro inteiros consecutivos, aumentado de 1, é um quadrado perfeito.
27. A soma dos quadrados de dois inteiros é 3332 e um deles é o quadruplo do outro. Achar os dois
inteiros.
(a + b + |a − b|)
max (a, b) =
2
(a + b − |a − b|)
min (a, b) =
2
29. Determinar o inteiro n > 1 de modo que a soma
1! + 2! + 3! + · · · + n!
30. A média aritmática de dois inteiros positivos é 5 e a média geométrica é 4. Achar os dois inteiros.
31. Achar os cinco inteiros positivos cuja soma dos quadrados é 2010.
32. O resto por falta da raiz quadrada de um inteiro positivo é 135 e o resto por excesso é 38. Achar esse
inteiro.
34. Achar o inteiro que deve ser somado a cada um dos inteiros 2, 6, e 14 para que, nesta ordem,
formem uma proporção contínua.
36. Achar o valor mínimo de uma soma de 10 inteiros positivos distintos, cada um dos quais se escreve
com três algarismos.
38. Um estudante ao efetuar a multiplicação de 7432 por um certo inteiro achou o produto 1731656,
tendo trocado, por engano, o algarismo das dezenas do multiplicador, tomando um 3 em vez de 8.
Achar o verdadeiro produto.
39. Achar o menor inteiro cujo produto por 21 é um inteiro formado apenas com algarismos 4.
40. Escreve-se a sequência natural dos inteiros positivos, sem separar os algarismos:
123456789101112131415 . . .
Determinar:
o 435o algarismo que se escreve;
o 1756o algarismo que se escreve;
o 12387o algarismo que se escreve.
14 CAPÍTULO 1. NÚMEROS INTEIROS: NOÇÕES FUNDAMENTAIS
41. Escreve-se a sequência natural dos inteiros positivos pares, sem separar os algarismos:
2461012141618 . . .
43. Mostrar que o produto de dois fatores entre 10 e 20 é o décuplo da soma do primeiro com as
unidades do segundo, mais o produto das unidades dos dois.
44. Achar o menor inteiro positivo que multiplicado por 33 dá um produto cujos algarismos são todos
7.
45. Os inteiros a e b são tais que 4 < a < 7 e 3 < b < 4. Mostrar que 0 < a − b < 4.
46. Os inteiros a e b são tais que −1 < a < 3 e −2 ≤ b ≤ 0. Mostrar que −1 < a − b < 5.
CAPÍTULO 1
n (n − 1)
1.
2
2. n = 2
3. n = 3
4. n = 4, 5, 7
9. x = 2, y = 6; x = 5, y = 3; x = 3, y = 4
12. x = 7
13. x = 1 ou x = 2
19. 234
1.7. NÚMEROS BINOMIAIS CONSECUTIVOS 15
20. 9885
21. a) 435 · 36
b) 2403 · 62
22. 110997
23. 888889
24. 690
25. a) 73 × 32 + 45
b)257 × 6 + 59
27. 14 e 56
16 CAPÍTULO 1. NÚMEROS INTEIROS: NOÇÕES FUNDAMENTAIS
Capítulo 2
INDUÇÃO MATEMÁTICA
Representa-se pela notação "minA", que se lê: "mínimo de A". Portanto, simbolicamente:
Exemplo 2.1.1 O conjunto N = {1, 2, 3,. . . } dos inteiros positivos tem o elemento mínimo, que é 1 (minN =
1), porque 1 ∈ N e 1 ≤ n para todo n ∈ N.
Exemplo 2.1.2 O conjunto A = {x ∈ Z|x > 12 } tem o elemento mínimo, que é 13 (minA = 13), porque 13 ∈ A
e 13 6 x para todo x ∈ A.
Exemplo 2.1.3 O conjunto Z− = {0, -1, -2, -3, . . . } dos inteiros não positivos não tem o elemento mínimo,
porque não existe a ∈ Z− tal que a 6 x para todo x ∈ Z− .
Exemplo 2.1.4 O conjunto A = {x ∈ N|3 divide x2 } tem o elemento mínimo 3 (minA = 3), porque 3 ∈ A (3
divide 9) e 3 6 x para todo x ∈ A (1 < A e 2 < A).
17
18 CAPÍTULO 2. INDUÇÃO MATEMÁTICA
Z+ = {0, 1, 2, 3,. . . }
dos inteiros não negativos (∅ , A ⊂ Z+ ) possui o elemento mínimo, isto é, simbolicamente:
(∀A ⊂ Z+ , A , ∅) ⇒ ∃ minA
Exemplo 2.2.1 O conjunto A = {1, 3, 5, 7,. . . } dos inteiros positivos ímpares é um subconjunto não vazio
de
Z+ (∅ , A ⊂ Z+ ).
Logo, pelo "Princípio da boa ordenação", A possui o elemento mínimo (minA = 1).
Exemplo 2.2.2 O conjunto P = {2, 3, 5, 7, 11, . . .} dos inteiros primos é um subconjunto não vazio de Z+ (∅ ,
P ⊂ Z+ ).
Logo, pelo "Princípio da boa ordenação", P possui o elemento mínimo (minP = 2).
Teorema 2.2.1 (de ARCHIMEDES) Se a e b são dois inteiros positivos quaisquer, então existe um inteiro n tal
que n.a ≥ b.
Demonstração Suponhamos que a e b são dois inteiros positivos para os quais n.a < b para todo
inteiro positivo n. Então, todos os elementos do conjunto:
S = {b − n.a | n ∈ N }
são inteiros positivos e, pelo "Princípio da boa ordenação", S possui o elemento mínimo, digamos
minS = b -k.a.
E como b - (k + 1)a pertence a S, porque S contém todos os inteiros positivos desta forma, temos:
isto é, b − ka não é o elemento mínimo de S, o que é uma contradição. Logo, a propriedade archime-
diana é verdadeira.
Assim, p.ex.:
X = {x|x ∈ N e x < S } = N - S
Então, X é um subconjunto não vazio de N(∅ , X ⊂ N)e, pelo "Princípio da boa ordenação", existe
o elemento mínimo xo de X(minX = xo ).
Pela condição (1), 1 ∈ S, de modo que xo > 1 e, portanto, xo − 1 é um inteiro positivo que não per-
tence a X. Logo, xo − 1 ∈ S e, pela condição (2), segue-se que (xo − 1) + 1 = xo ∈ S, o que é uma contradição,
pois, xo ∈ X = N − S, isto é, xo < S. Assim sendo, X = ∅ e S = N.
Conforme este "Princípio de indução finita", o único subconjunto de N que satisfaz às condições (1) e
(2) é o próprio N.
(2) para todo inteiro positivo k, se p(k) é verdadeira, então P(k + 1) também é verdaddeira.
Demonstração Seja S o conjunto de todos os inteiros positivos n para os quais a proposição P(n) é
verdadeira, isto é:
S = {n ∈ N | P(n) é verdadeira}
Pela condição (1), P(1) é verdadeira e, portanto, 1 ∈ S. Pela condição (2), para todo inteiro positivo
k, se k ∈ S, então K + 1 ∈ S. Logo, o conjunto S satisfaz as condições (1) e (2) do "Princípio de Indução
Finita" e, portanto, S = N, isto é, a proposição P(N) é verdadeira para todo inteiro positivo n.
Na "Demonstração por Indução Matemática" de uma dada proposição P(n) é obrigatório verificar
que as condições (1) e (2) são ambas satisfeitas. A verificação da condição (1) é geralmente muito fácil,
mas a verificação da condição (2) implica em demonstrar o teorema auxiliar cuja hipótese é:
P(n) : 1 + 3 + 5 + . . . + (2n − 1) = n2 , ∀ n ∈ N
Demonstração
P(n) : 1
1.2 + 1
2.3 + 1
3.4 + ... + 1
n(n+1) = n+1 ,
n
∀n ∈ N.
Demonstração
P(k) : 1
1.2 + 1
2.3 + 1
3.4 + ... + 1
k(k+1 = k+1 , k
k
∈ N é verdadeira.
1
Adicionando (k+1)(k+2) a ambos os membros desta igualdade, obtemos:
k2 +2k+1
1
1.2 + 1
2.3 + 1
3.4 +...+ 1
k(k+1) + 1
(k+1)(k+2) = k
k+1 + 1
(k+1)(k+2) = (k+1)(k+2) = k+1
k+2
Demonstração
é verdadeira. Portanto:
o que implica:
isto é, a proposição P(k + 1) é verdadeira. Logo, pelo "Teorema da Indução Matemática", a proposição
P(n) é verdadeira para todo inteiro positivo n.
P(n) : 2n > n, ∀n ∈ N
Demonstração
(1) P(1) é verdadeira, visto que 21 = 2 > 1;
(2) A hipótese de indução é que a proposição:
P(k): 2k > k, k ∈ N
é verdadeira. Portanto:
o que implica:
2k+1 > k + 1 isto é, a proposição P(k + 1) é verdadeira. Logo, pelo "Teorema da Indução Matemática",
a proposição P(n) é verdadeira para todo inteiro positivo n.
Demonstração Seja S o conjunto de todos os inteiros positivos n para os quais a proposição P(r + n − 1)
é verdadeira, isto é:
P((r + k − 1) + 1) = P(r + (k + 1) − 1)
também é verdadeira, isto é, se k ∈ S, então k + 1 ∈ S. Logo, pelo "Princípio de Indução Finita", S é o
conjunto dos inteiros positivos: S = N, isto é, a proposição P(r + n − 1) é verdadeira para todo n ∈ N, ou
seja, o que é a mesma coisa, a proposição P(n) é verdadeira para todo inteiro n ≥ r.
Demonstração
22 CAPÍTULO 2. INDUÇÃO MATEMÁTICA
isto é, a proposição P(k+1) é verdadeira. Logo, pelo teorema 2.5, a proposição P(n) é verdadeira para
todo inteiro n ≥ 4.
P(n) : n2 > 2n + 1, ∀n ≥ 3
Demonstração
P(k) : k2 > 2k + 1, k ≥ 3
Então, temos:
e, portanto:
isto é, a proposição P(k+1) é verdadeira. Logo, pelo teorema 2.5, a proposição P(n) é verdadeira
para todo inteiro n ≥ 3.
Observe-se que a proposição P(n) é falsa para n = 1 e n = 2, pois, temos:
Teorema 2.6.2 Seja P(n) uma proposição associada a cada inteiro positivo n e que satisfaz às duas seguintes
condições:
Demonstração Seja S o conjunto de todos os inteiros positivos n para os quais as proposição P(n) é
verdadeira, isto é:
S = {n ∈ N|P(n)é verdadeira}
Suponhamos, por absurdo, que S , N e seja X o conjunto de todos os inteiros positivos que não
pertencem a S, isto é:
X = { x | x ∈ N e x < S} = N − S
Então, X é um subconjunto não vazio de N e, pelo "Princípio da boa ordenação", existe o elemento
mínimo j de X (minX = j).
Pela condição (1), 1 ∈ S, de modo que j > 1, e como j é o menor inteiro positivo que não pertence
a S, segue-se que as proposições P(1), P(2), . . . , P( j − 1) são todas verdadeiras. Então, pela condição (2),
a proposição P(j) é verdadeira e j ∈ S, o que é uma contradição, pois, j ∈ X, isto é, j < S. Assim sendo,
S = N e a proposição P(n) é verdadeira para todo inteiro positivo n.
Teorema 2.6.3 Seja r um inteiro positivo fixo e seja P(n) uma proposição associada a cada inteiro n ≥ r e que
satisfaz às duas seguintes condições:
Pela condição(1), r < S, de modo que j > r, e por conseguinte P(m) é verdadeira para todo inteiro
m tal que r 6 m < j. Assim sendo, pela condição (2), P(j) é verdadeira e j < S, o que é uma contradição,
pois, j ∈ S. Logo, o conjunto S é vazio (S = ∅), e a proposição P(n) é verdadeira para todo inteiro n > r.
EXERCÍCIOS
1. Demonstrar por "Indução Matemática":
(a) 12 + 22 + 32 + . . . + n2 = n6 (n + 1)(2n + 1), ∀n ∈ N
n2
(b) 13 + 23 + 33 + . . . + n3 = 4 (n + 1)2 , ∀n ∈ N
(c) 12 + 32 + 52 + . . . + (2n − 1) = n3 .(4n2 − 1), ∀n ∈ N
2
24 CAPÍTULO 2. INDUÇÃO MATEMÁTICA
(a) 2n < 2n + 1, ∀n ∈ N
(b) 2n > n2 , ∀n > 5
(c) 2n > n3 , ∀n > 10
(d) 4n > n4 , ∀n > 5
(e) n! > n2 , ∀n > 4
(f) n! > n3 , ∀n > 6
3. Demonstrar por "Indução Matemática":
SOMATÓRIOS E PRODUTÓRIOS
3.1 SOMATÓRIOS
Sejam os n > 1 inteiros a1 , a2 , · · · , an . Para indicar, de modo abreviado, a soma a1 + a2 + · · · + an
desses n inteiros usa-se a notação:
n
X
ai
i=1
2
X 3
X
ai = a1 + a2 , ai = a1 + a2 + a3 , · · ·
i=1 i=1
A letra i chama-se o índice do somatório e pode ser substituida por qualquer outra diferente deP a e de n
- é um índice mudo. E os inteiros 1 e n que figuarm abaixo e a cima da letra grega maiúscula (sigma)
chama-se respectivamente limite inferior e limite superior do índice i. O número de parcelas de um
somatório é sempre igual a diferença entre os limites superior e inferior do seu índice mais uma unidade.
Se m e n são dois inteiros, com m ≤ n, então, por definição:
n
X
ai = am + am+1 + am+2 + · · · + an
i=m
7
X
5i = 5.1 + 5.2 + 5.3 + 5.4 + 5.5 + 5.6 + 5.7 =
i=1
= 5 + 10 + 15 + 20 + 25 + 30 + 35 = 140
4
X
(8j − 3) = (8.1 − 3) + (8.2 − 3) + (8.3 − 3) + (8.4 − 3) =
j=1
= 5 + 13 + 21 + 29+ = 68
8
X
k.2k = 3.23 + 4.24 + 5.25 + 6.26 + 7.27 + 8.28 =
k=3
= 24 + 64 + 160 + 384 + 896 + 2048 = 3576
25
26 CAPÍTULO 3. SOMATÓRIOS E PRODUTÓRIOS
Demontração:
n
X
(ai + bi ) = (a1 + b1 ) + (a2 + b2 ) + · · · + (an + bn ) =
i=1
= (a1 + a2 + · · · + an ) + (b1 + b2 + · · · + bn ) =
Xn Xn
= ai + bi
i=1 i=1
Teorema 3.2.2
n
X
a = na
i=1
Demonstração:
n
X n
X
a= ai = a1 + a2 + · · · + an = a + a + · · · + a = na
i=1 i=1
Teorema 3.2.3
n
X n
X
(ai + a) = ai + na
i=1 i=1
Demontração:
Teorema 3.2.4
n
X n
X
kai = k ai
i=1 i=1
3.3. SOMATÓRIOS DUPLOS 27
Demonstração:
20
X 20
X 20
X 20
X
(5i + 2) = 5i + 2=5 i + 20.2 =
i=1 i=1 i=1 i=1
= 5(1 + 2 + · · · + 20) + 40 =
1
= 5. (1 + 20) 20 + 40 = 5.210 + 40 = 1090
2
Demonstração:
n
X
ai j = a11 + a12 + · · · + a1n + a21 + a22 + · · · + a2n +
i, j=1
+ · · · + an1 + an2 + · · · + ann
ou seja,
Xn n
X n
X n
X n X
X n
ai j = a1 j + a2j + · · · + an j = ai j
i, j=1 j=1 j=1 j=1 i=1 j=1
Teorema 3.3.2
m X
X n n
X m
X
ai b j = ai . bj
j=1 i=1 i=1 j=1
Demonstração:
X 3
2 X 3
X 2
X
2i 3 j = 2i . 3 j = (2 + 22 + 23 )(3 + 32 ) =
j=1 i=1 i=1 j=1
= 14.12 = 168
3.4 PRODUTÓRIOS
Sejam os n > 1 inteiros a1 , a2 , · · · , an . Para indicar, de modo abreviado, o produto a1 a2 · · · an desses n
inteiros usa-se a notação:
n
Y
ai
i=1
A letra i chama-se o índice do produtório e pode ser substituida por qualquer outra diferente de Q
a e de
n - é um índice mudo. E os inteiros 1 e n que figuram abaixo e acima da letra grega maiúscula (pi)
chama-se respectivamente limite inferior e limite superior do índice i.
O número de fatores de um produtório é sempre igual à diferença entre os limites superior e inferior do
seu índice mais uma unidade.
Se m e n são dois inteiros, com m 6 n, então, por definição:
n
Y
ai = am .am+1 .am+2 · · · an
i=m
6
Y
3i = (3.1) (3.2) (3.3) (3.4) (3.5) (3.6) =
i=1
= 3 . 6 . 9 . 12 . 15 . 18 = 524880
4
Y
(5j − 3) = (5.1 − 3) (5.2 − 3) (5.3 − 3) (5.4 − 3) =
j=1
= 2 . 7 . 12 . 17 = 2856
16
Y
1.3.5.7. · · · .31 = (2j − 1)
j=1
3.5. PROPRIEDADES DOS PRODUTÓRIOS 29
n
Y
1.2.3 · · · (n − 1)n = n! = i
i=1
Demonstração:
Com efeito, desenvolvendo o primeiro membro, temos:
n
Y
ai bi = (a1 b1 )(a2 b2 ) · · · (an bn ) = (a1 a2 · · · an )(b1 b2 · · ·
i=1
n
Y n
Y
··· bn ) = ai . bi
i=1 i=1
Teorema 3.5.2
n
Y
a = an
i=1
Demonstração:
Teorema 3.5.3
n
Y n
Y
kai = kn ai
i=1 i=1
Demonstração:
4
Y
(2i + 1)2
i=1
Consoante ao teorema 5.1, temos :
4
4
Y Y
(2i + 1)2 = (2i + 1)2 = (3.5.7.9)2 = 9452 =
i=1 i=1
= 893025
30 CAPÍTULO 3. SOMATÓRIOS E PRODUTÓRIOS
n
Y n Y
Y n
ai j = ai j
i,j=1 i=1 j=1
! ! !
n n n n−1 n n−2 2
(a + b) n
= a + a b+ a b + ··· +
0 1 2
! !
n n n
+ abn−1 + b
n−1 n
(3.1)
Demonstração:
Suponhamos, agora, que a fórmula subsiste para o inteiro positivo m (hipótese de indução). Então,
teremos:
m ! m !
X m m−k+1 k X m m+1−kb k
a(a + b) = m
a b =am+1
+ a
k k
k=0 k=1
m ! m !
X m m−k k+1 X m m+1−k k
b(a + b) =
m
a b = a b + bm+1
k k−1
k=0 k=1
isto é, a fómula subsiste para o inteiro positivo m + 1 e, portanto, é verdadeira para todo inteiro positivo
m.
3.7. TRIÂNGULO DE PASCAL 31
n n n n n n
0 1 2 3 ··· n−1 n
———————————————————————————————————–
Substituindo os números binomiais pelos seus respectivos valores, o triângulo de PASCAL escreve-se:
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
———————————————————————————————————-
Observe-se que, no triângulo de PASCAL:
32 CAPÍTULO 3. SOMATÓRIOS E PRODUTÓRIOS
(I) Dois elementos de uma mesma linha, equidistantes dos extremos, são iguais.
É consequência da fórmula mk = m−k
m
: dois números binomiais complementares são iguais.
(III) Cada elemento de uma linha, a partir do segundo, é a soma do elemento que lhe fica acima com o
que está à esquerda deste último.
É consequência da relação de STIFEL:
n+1
! ! !
n n
+ =
k−1 k k
(IV) A soma de um número qualquer de elementos consecutivo de uma coluna, a partir do primeiro,
é igula ao elemento que se encontra na interseção da linha e da coluna imediatamente posteriores
aquelas a que pertence o último dos elementos considerados.
Esta propriedade resulta da fórmula:
! ! ! ! !
n n−1 n−2 k k−1
= + + ··· + +
k k−1 k−1 k−1 k−1
Assim, p.ex., a soma dos n primeiros elementos da segunda coluna:
! ! ! ! !
1 2 3 n−1 n
, , , ··· , ,
1 1 1 1 1
é igual a n+1
2 , isto é:
n(n + 1)
1 + 2 + 3 + · · · + (n − 1) + n =
2
(V) A soma de um número qualquer de elementos consecutivos de uma mesma diagonal, a partir de
um elemento da primeira coluna, é igual ao elemento que se encontra na mesma coluna do último
3.9. NÚMEROS TRIANGULARES 33
n+1
! ! ! ! !
1 2 3 n
+ + + ··· + =
0 1 2 n−1 n−1
1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3
10 = 1 + 2 + 3 + 4, 15 = 1 + 2 + 3 + 4 + 5, · · ·
cada um dos quais é a soma de inteiros consecutivos começando por 1, chama-se números triângulares,
porque cada um deles dá o número de pontos que podem ser dispostos em forma de triângulo equilátero,
conforme mostra as figuras abaixo:
Demonstração:
Com efeito:
(n − 1)n n(n + 1)
tn−1 + tn = + = n2
2 2
NOTA. Os pitagóricos relacionaram os inteiros com a Geometria, introduzindo os números poligo-
nais: números triangulares, números quadráticos, números pentagonais, etc. A razão desta nomencla-
tura geométrica resulta da representação dos números poligonais mediante pontos dispostos em forma
de triângulos, quadrados, pentágonos, etc., como mostram as figuras que se seguem:
34 CAPÍTULO 3. SOMATÓRIOS E PRODUTÓRIOS
Denotando o n-ésimo número quadrático por qn , é imediato que qn = n2 , e temos (Teorema 9.1):
qn = tn−1 + tn
isto é, o n-ésino número quadrático é a soma do n-ésimo número triangular e do seu antecessor.
Este resultado os pitagóricos conheciam, e o demonstraram separando os pontos e contando-os, no modo
indicado nas figuras.
A soma Sq dos n primeiros números quadráticos é dado pela fórmula:
EXERCÍCIOS
1. Calcular:
X5 7
X
(a) 3i (b) 6
i=1 i=3
4
X 3
X
(c) ( j + 1)( j + 2) (d) k2k
j=1 k=1
2. Calcular:
Y3 3
Y
(a) (3 + i2 ) (b) 5
i=1 k=1
6
Y 7
Y
(c) ( j − 1)( j + 1) (d) n/2n
j=2 n=3
n
n 2 5 5
Y Y X X
(c) a2i = ai (d) ai = ai
i=1 i=1 i=0 i=1
5. Demonstrar:
m Y
Y n n Y
Y m
ai j = ai j
i=1 j=1 j=1 i=1
8. Demonstrar:
n n
(a) 0 − 1 + n
2 + · · · + (−1)n n
n = 0, n > 1
n
(b) 1 +2 n
2 +3 n
3 + ··· + n n
n = n.2n−1 , n > 1
n
(c) 0 +2 n
1 + 22 n
2 + · · · + 2n n
n = 3n , n > 1
(d) 2
2 + 3
2 + 4
2 + ··· + n
2 = 3 ,
n+1
n>2
√ 9
2
x+
x
7.
(a) t6 = 21 e t5 = 15
(b) t3 = 6, t4 = 10 e t5 = 15
(c) t5 = 15, t6 = 21 e t7 = 28
9. 672
10. n = 9
38 CAPÍTULO 3. SOMATÓRIOS E PRODUTÓRIOS
Capítulo 4
DIVISIBILIDADE
Com a notação "a|b" indica-se que a , 0 divide b e, portanto, a notação "a - b" significa que a , 0 não
divide b.
Assim, p.ex.:
39
40 CAPÍTULO 4. DIVISIBILIDADE
Demonstração:
|b| ≥ |a|
Consoante as propriedades (1) e (4), a relação de divisibilidade Z é reflexiva e transitiva, mas não
é simétrica, porque, p.ex., 3|6 e 6 - 3.
4.1. RELAÇÃO DE DIVISIBILIDADE EM Z 41
D(a) = { x ∈ Z∗ | x|a }
onde Z∗ denota o conjunto dos inteiros não nulos (, 0).
Assim, p.ex.:
a = a.1 = (−a).(−1)
segue-se que 1, -1, a e −a são divisores de a, denominados divisores triviais de a. Em particular, o inteiro
1 (ou -1) só admite divisores triviais.
−a ≤ x ≤ a =⇒ D(a) ⊂ [−a, a]
Em outros termos, divisor comum de dois inteiros a e b é todo inteiro d , 0 que pertence simultane-
amente aos conjuntos D(a) e D(b).
O conjunto de todos os divisores comuns a dois inteiros a e b indica-se por D(a, b). Portanto,
simbolicamente:
A interseção (∩) é uma operação comutativa, de modo que D(a, b) não depende da ordem dos inteiros
dados a e b, isto é: D(a, b) = D(b, a).
Como -1 e 1 são divisores comuns de dois inteiros quaisquer a e b, segue-se que o conjunto D(a, b)
dos divisores comuns de a e b nunca é vazio: D(a, b) , ∅. Em particular, se a = b = 0, então todo inteiro
não nulo é um divisor comun de a e b, isto é: D(a, b) = Z∗ .
42 CAPÍTULO 4. DIVISIBILIDADE
Portanto:
a = bq + r e 0 ≤ r < b
Demonstração:
Seja S o conjunto de todos os inteiros não negativos (≥ 0) que são da forma a − bx, com x ∈ Z, isto é:
S = { a − bx | x ∈ Z, a − bx ≥ 0 }
Este conjunto S não é vazio (S , ∅), porque, b > 0, temos b ≥ 1 e, portanto, para x = −|a|, resulta:
a − bx = a + b|a| ≥ a + |a| ≥ 0
Assim sendo, pelo "Princípio da boa ordenação", exite o elemento minímo r de S tal que
r ≥ 0 e r = a − ba ou a = bq + r, com q ∈ Z
0 ≤ r − b = a − bq − b = a − b(q + 1) < r
Para demonstrar a unicidade de q e r, suponhamos que existem dois outros inteiros q1 e r1 tais que
a = bq1 + r1 e 0 ≤ r1 < b
Então, teremos:
bq1 + r1 = bq + r =⇒ r1 − r = (q − q1 )b =⇒ b|(r1 − r)
−b < −r ≤ 0 e 0 ≤ r1 < b
o que implica:
Cololário 4.1.1 Se a e b são dois inteiros, com b , 0, existem e são únicos os inteiros q e r que satisfazem as
condições:
a = bq + r e 0 ≤ r < |b|
Demonstração:
Com efeito, se b > 0, nada há que demonstrar, e se b < 0, então |b| > 0, e por conseguinte existem e
são únicos os inteiros q1 e r tais que
a = bq + r e 0 ≤ r < |b|
Exemplo 4.1.2 Achar o quociente q e o resto r na divisão de a = 59 por b = −14 que satisfazem às condições de
algoritmo da divisão.
59 = 14.4 + 3
o que implica:
Exemplo 4.1.3 Achar o quociente q e o resto r na divisão de a = −79 por b = 11 que satisfazem às condições do
algoritmo da divisão.
44 CAPÍTULO 4. DIVISIBILIDADE
79 = 11.7 + 2
o que implica:
−79 = 11(−7) − 2
Como o termo de r = −2 < 0 não satisfaz à condição 0 ≤ r < 11, somando e subtraindo o valor 11 de b ao
segundo membro da igualdade anterior, obtemos:
1 = (−7).0 + 1 e 0 ≤ 1 < | − 7| =⇒ q = 0 e r = 1
61 = (−7)(−8) + 5 e 0 ≤ 5 < | − 7| =⇒ q = −8 e r = 5
Observe-se que
Com efeito, pelo algoritmo da divisão, qualquer inteiro é de uma das seguintes formas:
4q, 4q + 1, 4q + 2, 4q + 3
Nesta classificação, somente os inteiros das formas 4q + 1 e 4q + 3 são ímpares e, portanto, os seus
quadrados são da forma:
4.1. RELAÇÃO DE DIVISIBILIDADE EM Z 45
72 = 49 = 8.6 + 1
132 = 169 = 8.21 + 1
EXERCÍCIOS
18. Mostrar que a diferença entre os cubos de dois inteiros consecutivos nunca é divisível por 2.
19. Na divisão do inteiro a = 427 por um inteiro positivo b o quociente é 12 e o resto é r. Achar o
divisor b e o resto r.
20. Na divisão do inteiro 525 por um inteiro positivo o resto é 27. Achar os inteiros que podem ser o
divisor e o quociente.
21. Na divisão de dois inteiros positivos o quociente é 16 e o resto é o maior possível. Achar os dois
inteiros, sabendo que a sua soma é 341.
22. Achar os inteiros positivos menores que 150 e que divididos por 39 deixam um resto igual ao
quociente.
24. Sejam n, r e s inteiros tais que 0 ≤ r < n e 0 ≤ s < n. Mostrar que, se n|(r − s), então r = s.
28. Mostrar que, para todo inteiro n, existem inteiros k e r tais que
n = 3k + r e r = −1, 0, 1
(a) o maior inteiro que se pode somar ao dividendo sem alterar o quociente ;
(b) o maior inteiro que se pode subtrair do dividendo sem alterar o quociente.
32. Numa divisão de dois inteiros, o quociente é 16 e o resto é 167. Determinar o maior inteiro que se
pode somar ao dividendo e ao divisor sem alterar o quociente.
33. Achar o maior inteiro de quatro algarismos divisível por 13 e o menor inteiro de cinco algarismos
divisível por 15.
34. Achar um inteiro de quatro algarismos, quadrado perfeito, divisível por 27 e terminado em 6.
15. a = 6, b = 10 e c = 21
Demonstração:
Se o mdc ( a, b)= d, então d|a e d|b o que implica d|(a-bq) ou d|r,isto é , d é um divisor comum de b e r (d|b
e d|r).
Por outro lado, se c é um divisor comum qualquer de b e r (c|b e c|r), então c|(bq + r)ou c|a, isto é, c é um
divisor comum de a e b, o que implica c6d.Assim sendo o mdc(b,r)=d.
É imediato:
Além disso, por ser mdc ( a, b) = mdc ( |a| , |b|), a determinação do mdc de (a, b) reduz-se ao acaso em
que a e b são inteiros positivos distintos, p. ex., com a> b, tais que b não divide a, isto é: a>b>0 e b-a.
Nestas condições; a aplicação repetida do algorítmo da divisão dá-nos as igualdades:
49
50 CAPÍTULO 5. ALGORÍTIMO DE EUCLIDES MÍNIMO MÚLTIPLO COMUM
E existem apenas b − 1 inteiros positivos menosres que b, necessariamente se chega auma divisão cujo
resto rn+1 =0, isto é finalmente teremos:
O últimos resto rn , 0, que aparece nesta sequência de divisões é o máximo divisor comumprocurado de a
e b,isto é , o mdc de (a, b) = rn , visto que pelo lema anterior temos:
q1 q2 q3 qn qn+1
Que se traduz na seguinte REGRA: Para se "achar"o MDC de dois inteiros positivos,divide-se o maior
pelo menor, este pelo primeiro resto obtido, o segundo resto pelo primeiro , e assim sucessivamente até
se encontrar um resto nulo. O último resto não nulo é o máximo divisor procurado.
O Algorítomo de EUCLIDES , também é usado para achar a expressão do MDC ( a, b )= rn como com-
binação linear de a e b, para o que basta eliminar sucessivamente os restos rn−1CLIDES , rn−2 ...,r3 , r2 , r1 ,
entre as n primeiras igualdades anteriores.
Exemplo 5.1.1 Achar o Mdc de (963 , 657) pelo Algorítmos de EUCLIDES e a sua expressão como combinação
linear de 963 e 657.
Temos sucessivamente:
Portanto, o MDC de ( 963 ,657 ) = 9 e a sua expressão como combinação linear de 963 e 657 se obtém alinhando
os restos de 36, 45 e 306 , entre as quatro primeiras igualdades anteriores do seguinte modo:
9 = 45 − 36 = 45 − (306 − 45.6)
= −306 + 7.45 = −306 + 7(657 − 306.2
= 7.657 − 15.306 = 7.657 − 15(963 − 657) =
963(−15) + 657.2
Isto é :
5.1. ALGORÍTMO DE EUCLIDES 51
Esta representação do inteiro 9 = mdc(963, 657) como combinação linear de 963 e 657 não é única, por exemplo:
Somando e subtraindo o produto 963.657 ao segundo membro da igualdade:
963(−15) + 657.22
Obtemos:
que é uma outra representação do inteiro 9 = mdc(963, 657) como combinação linear de 963 e 657.
Exemplo 5.1.2 Achar o mdc ( 252 , -180 )pelo Algorítmos de Euclides e a sua expressão como combinação linear
252 e -180.
Temos sucessivamente:
252 = 180.2 + 72
180 = 72.2 + 36
72 = 36.2
Portanto, o mdc ( 252 , -180 )= o mdc ( 252 , 180 )=35, e como 36 =180-72.2 = 180 - ( 252 -180)2 = 252(-2)
+ 180(-3).
temos:
Outra representação do inteiro 36 = mdc ( 252 , -180 ) como combinação linear de 252 e -180 é a seguinte:
36= 252 ( -2+180) + (-180) + ( -180)(-3+252)=
=252.178 + ( -180)249
Exemplo 5.1.3 O mdc de dois inteiros positivos a e b é 74 e na sua determinação pelo algorítmos de EUCLIDES
os quocientes obtidos foram 1,2,2,5,1 e 3. Calcular a e b.
1 2 2 5 1 3
a b r r1 r2 r3 74
r r1 r2 r3 74 0
Temos, sucessivamente:
a = b + r, b = 2r + r1 , r = 2r1 + r2
Portanto:
Multiplicando ambos os membros de cada umas das n + 1 igualdades que dão mdc(a, b) = rn pelo algoritmo de
EUCLIDES por k, obtemos:
ak = bk(q1 ) + r1 k, 0 < r1 < bk
bk = (r1 )q2 + r2 k, 0 < r2 k < r1 k
r1 k = (r2 k)q3 + r3 k, 0 < r3 k < r2 k
·················· ············
rn−2 k = (rn−1 k)qn + rn k, 0 < rn k < rn−1 k
rn−1 k = (rn k)qn+1 + 0
Obviamente, estas n + 1 outra coisa não são que o algoritmo de EUCLIDES aplicado aos inteiros ak e bk, e por
conseguinte o mdc(ak, bk) é o último resto rn , 0, isto é:
Assim, p.ex:
mdc(12, 30) = mdc(2 · 6, 5 · 6) = 6 · mdc(2, 5) = 6 · 1 = 6
Cololário 5.1.1 Para todo k , 0, o mdc(ka, kb) = |k| · mdc(a, b).
Demonstração:
Se k > 0 não há que demonstrar, e se k < 0, então −k = |k| > 0 e, pelo teorema anterior, temos:
M(a) = {x ∈ Z| a | x} = {aq |q ∈ Z}
Assim, p.ex:
M(−1) = M(1) = Z
M(5) = {5q |q ∈ Z} = {0, ±5, ±10, ±15, ±20, · · · }
Definição 5.2.1 Sejam a e b dois inteiros diferentes de zero (a , 0 e b ,=). Chama-se múltiplo comum e a e b
todo inteiro x tal que a | b e b | x.
Em outros termos, múltiplo comum de a e b é todo inteiro que pertence simultaneamente aos conjuntos M(a) e
M(b).
O conjunto de todos os múltiplos comuns de a e b indica-se por M(a, b). Portanto, simbolicamente:
M(a, b) = {x ∈ Z | a | x e b | x}
ou seja:
M(a, b) = {x ∈ Z | x ∈ M(a) e x ∈ M(b)}
5.3. MÍNIMO MÚLTIPLO COMUM DE DOIS INTEIROS 53
e, portanto:
M(a, b) = M(a) ∩ M(b)
A interseção (∩) é uma operação comutativa, de modo que M(a, b) não depende de ordem dos inteiros dados a
e b, isto é: M(a, b) = M(b, a).
Obviamente, 0 é um múltiplo comum de text e b: 0 ∈ M(a, b). E os produtos ab e (−ab) também são
múltiplos comuns de a e b.
Portanto:
(1) a | m e b | m
Observe-se que, pela definição (1) m é um múltiplo com de a e b, e pela definição (2), m é o menor dentre todos os
múltiplos comuns positivos de a e b.
O mínimo múltiplo comum de a e b indica-se pela notação mmc(a, b).
Pelo "Princípio da boa ordenação", o conjunto dos múltiplos comuns positivos de a e b possui o elemento
mínimo e, portanto, o mmc(a, b) existe sempre e é único. Além disso, por ser o produto ab um múltiplo comum
de a e b, segue-se que mmc(a, b) ≤ |ab|.
Exemplo 5.3.1 Sejam os inteiros a = −12 e b = 30. Os múltiplos comuns positivos de −12 e 30 são
60, 120, 180, . . . , e como o menor deles é 60, segue-se que o mmc(−12, 30) = 60.
mdc(a, c) · mmc(a, b) = ab
Demonstração:
!
b a ab
Seja mdc(a, b) = d e mmc(a, b) = m. Como a | a eb|b , segue-se que é um múltiplo comum
d d d
de a e b. Portanto, existe um inteiro positivo k tal que
ab
, k ∈N
d
o que implica:
a m b m
= k e = ( )k
d b d a
54 CAPÍTULO 5. ALGORÍTIMO DE EUCLIDES MÍNIMO MÚLTIPLO COMUM
! !
a b a b
isto é, k é um divisor comum dos inteiros e . Mas, e são primos entre si (Corolário 5.1),
d d d d
de modo que k = 1. Assim sendo, temos:
!
ab
= m ou ab = dm
d
isto é:
ab = mdc(a, b) · mmc(a, b)
Esta importante relação permite determinar o mmc de dois inteiros quando se conhece o seu mdc e,
vice-versa.
963 · 657
mmc = (963, 657) = = 70299
9
Cololário 5.4.1 Para todo par de inteiros positivos a e b, o mmc(a, b) = ab se, e somente se, o mdc(a, b) = 1.
Demonstração:
mdc(a, b) · ab = ab =⇒ mdc(a, b) = 1
(1) a | m, b | m e c | m
(2) Se a | e, se b | e e se c | e, com e > 0, então m ≤ e.
Assim, p.ex.:
mmc(39, 102, 75) = 33150
5.6 EXERCÍCIOS
Capítulo 6
EQUAÇÕES DIOFANTINAS
LINEARES
6.1 GENERALIDADES
O tipo mais simples de equações diofantinas é a equação diofantina linear com suas incógnitas x e y:
ax + by = c
3x + 6y = 18
Temos:
3 · 4 + 6 · 1 = 18
3(−6) + 6 · 6 = 18
3 · 10 + 6(−2) = 18
Logo, os pares de inteiros:
4 e 1, −6 e 6, 10 e − 2
são solições da equação 3x + 6y = 18.
Existem equaçõedefiniçãos diofantinas lineares copm duas incógnitas que não têm solução. Assim, p. ex.,
a equação diofantina linear:
2x + 4y = 7
não tem solução, por que 2x+4y é um inteiro para quaisquer que sejam os valores inteiros de x e y, enquanto
que 7 é um inteiro ímpar (observe-se que 2 = mdc(2, 4) não divide 7).
De modo geral, a equação diofantina linear ax + by = c não tem solução todas as vezes que d = mdc(a, b) não
divide c, como é óbvio.
55
56 CAPÍTULO 6. EQUAÇÕES DIOFANTINAS LINEARES
Demonstração:
(=⇒)Suponhamos que a equação ax + by = c tem uma solução, isto é, que existe um par de inteiros x0 , yo
tais que ax0 + by0 = c.
Por ser o mdc(a, b) = d, existem inteiros r e s tais que a = dr e b = ds, e temos:
c = ax0 + by0 = drx0 + dsy0 = d(rx0 + sy0 )
E como rx0 + sy0 é um inteiro, segue-se que d divide c (d/c).
(⇐=) Reciprocamente, suponhamos que d divide c (d | c), isto é, que c = dt, onde t é um inteiro.
Por ser o mdc(a, b) = d, existem inteiros x0 e y0 tais que
d = ax0 + by0
o que implica:
c = dt = (ax0 + by0 )t = a(tx0 ) + b(ty0 )
isto é, o par de inteiros:
x = tx0 = (c/d)x0 , y = ty0 = (c/d)y0
é uma solução da equação ax + by = c.
Cololário 6.3.1 Se o mdc (a, b) = 1 e se x0 e y0 é uma solução particular da equação diofantina linear ax+by = c,
então todas as outras soluções são dadas pelas fórmulas:
x = x0 + bt, y = y0 − at
NOTA. Uma solução particular da equação diofantina linear se obtém por tentativas ou pelo algoritmo de
EUCLIDES. E em ambos os casos a solução geral se pode obter usando o teorema 8.2, conforme se vai ver
nos exemplos a seguir:
172x + 2y = 1000
172 = 20 · 8 + 12
20 = 12 · 1 + 8
12 = 8·1+4
8 = 4·2
Portanto, o mdc(172, 20) = 4 e como 4 | 1000, segue-se que a equação dada tem solução.
Posto isso, cumpre obter a expressão do inteiro 4 como combinação linear de 172 e 20, para que o que basta
eliminar sucessivamente os restos 8 e 12 entre as três primeiras igualdades anteriores do seguinte modo:
4 = 12 − 8 = 12 − (20 − 12) = 2 · 12 − 20 =
= 2(172 − 20 · 8) − 20 = 172 · 2 + 20(−17)
Isto é:
4 = 172 · 2 + 20(−17)
Multiplicando ambos os membros desta igualdade por 1000/4 = 250, obtemos:
Portanto, o par de inteiros x0 = 500, y0 = −4250 é uma solução particular da equação proposta, e todas as
soluções são dadas pelas fórmulas:
Exemplo 6.3.2 Determinar todas as soluções inteiras e positivas da equação diofantina linear
18x + 5y = 48
18 = 5·3+3
5 = 3·1+2
3 = 2·1+1
2 = 1·2
58 CAPÍTULO 6. EQUAÇÕES DIOFANTINAS LINEARES
3 1 1 2
18 5 3 2 1
3 2 1 0
Portanto, o mdc(18, 5) = 1 e a equação dada tem solução. E para exprimir 1 como combinação linear de 18 e
5 basta eliminar os restos 2 e 3 entre as três primeiras igualdades anteriores do seguinte modo:
1 = 3 − 2 = 3 − (5 − 3) = 2 · 3 − 5 =
= 2(18 − 15 · 3) − 5 = 18 · 2 + 5(−7)
isto é:
1 = 18 · 2 + 5(−7)
e
48 = 18 · 96 + 5(−336)
Logo, o par de inteiros x0 = 96, y0 = 336 é uma solução particular da equação proposta, e todas as demais
soluções são dadas pelas fórmulas:
isto é:
1 2
t < −19 , e t < −18
5 3
o que implica que t = -19 e, portanto:
Assim, o par de inteiros x = 1, y = 6 é a única solução inteira e positiva da equação 18x + 5y = 48.
O mdc(39, 26) = 13 e como 13 não divide 105, segue-se que a equação dada não tem solução.
O mdc(14, 22) = 2 e como 2 | 50, a equação dada tem solução, e por simples inspeção logo se vê que
14 · 2 + 22 · 1 = 50,
de modo que o par de inteiros x0 = 2, y0 = 1 é uma solução particular, e por conseguinte todas as demais
soluções são dadas pelas fórmulas:
x = 2 + 11t, y = 1 − 7t
onde t é um inteiro arbitrário.
6.3. SOLUÇÕES DA EQUAÇÃO AX + BY = C. 59
EXERCÍCIOS
1. Determinar todas as soluções inteiras das seguintes equações diofantinas lineares:
(a) 56x + 72y = 40 (b) 24x + 138y = 18
(c) 221x + 91y = 117 (d) 84x − 438y = 156
(e) 48x + 7y = 5 (f) 57x − 99y = 77
(g) 11x + 30y = 31 (h) 27x − 13y = 54
(i) 13x − 7y = 21 (j) 44x + 66y = 11
(k) 21x − 12y = 72 (l) 17x + 54y = 8
2. Determinar todas as soluções inteiras e positivas das seguintes equações diofantinas lineares:
(a) 5x − 11y = 29 (b) 32x + 55y = 771
(c) 58x − 87y = 290 (d) 62x + 11y = 788
(e) 30x + 17y = 300 (f) 54x + 21y = 906
(g) 123x + 360y = 99 (h) 158x − 57y = 7
3. Determinar o menor inteiro positivo que dividido por 8 e por 15 deixa os restos 6 e 13 respectiva-
mente.
4. Exprimir 100 como soma de dois inteiros positivos de modo que o primeiro seja divisível por 7 e o
segundo seja divisível por 11.
5. Determinar as duas menores frações positivas que tenham 13 e 17 para denominadores e cuja soma
seja igual a 305/221.
6. Demonstrar que, se a e b são inteiros positivos primos entre si, então a equação diofantina ax − by = c
tem um número infinito de soluções inteiras e positivas.
CAPÍTULO 8
1. (a) x = 20 + 9t, y = −15 − 7t
(b) x = 18 + 23t, y = −3 − 4t
(c) x = −18 + 7t, y = 45 − 17t
(d) x = 54 + 73t, y = 10 − 14t
(e) x = −5 + 7t, y = 35 − 48t
(f) Não tem soluções inteiras
(g) x = 11 + 30t, y = −3 − 11t
(h) x = 2 + 2t, y = 3t
(i) x = 7t, y = −3 − 13t
(j) Não tem soluções inteiras
(k) x = 4t, y = −6 + 7t
(l) x = 1 + 54t, y = −3 − 17t
2. (a) x = 8 + 11t, y = 1 + 5t, onde t ≥ 0
(b) Não tem soluções inteiras e positivas
(c) x = 8 + 3t, y = 2 + 2t, onde t ≥ 0
(d) x = 1, y = 66; x = 12, y = 4
(e) Não tem soluções inteiras e positivas
(f) x = 2, y = 38; x = 9, y = 20; x = 16, y = 2
(g) Não tem soluções inteiras e positivas
(h) x = 17 − 57t, y = 47 − 158t, onde t ≤ 0
3. 118
4. 100 = 56 + 44
5. 8/13 e 13/17
60 CAPÍTULO 6. EQUAÇÕES DIOFANTINAS LINEARES
Capítulo 7
CONGRUÊNCIAS
Em outros termos, a é congruente a b módulo m se, e somente se, existe um inteiro k tal que a − b = km.
Com a notação
a ≡ b (mod.m)
a ≡ b (mod.m) ⇐⇒ m | (a − b)
ou seja:
a ≡ b (mod.m) ⇐⇒ ∃k ∈ Z | a − b = km
Assim, p.ex:
3 ≡ 24(mod.7), porque 7(3 − 24)
−31 ≡ 11(mod.6), porque 6(−31 − 11)
−15 ≡ −63(mod.8), porque 8(−15 − (−63))
Se m não divide a diferença a − b, então diz-se que a é incongruente a b módulo m, o que se indica pela notação:
a . b(mod.m)
Assim, p. ex.:
61
62 CAPÍTULO 7. CONGRUÊNCIAS
Note-se que dois inteiros quaisquer são congruentes módulo 1, enquanto que dois inteiros são congruentes módulo
2 se ambos são pares ou se ambos são ímpares.
Em particular,
a ≡ 0(mod.m)
se, e somente se, o módulo m divide a (m | a).
n ≡ 7 (mod.12) ⇒ n ≡ 3 (mod.4), ∀ n ∈ Z
Com efeito:
n2 ≡ 0 (mod.4) ou n2 ≡ 1 (mod.4), ∀ n ∈ Z
Com efeito:
Demonstração:
(⇒) Suponhamos que a ≡ b(mod.m). Então, por definição:
a − b = km, com k ∈ Z
b = mq + r, onde 0 ≤ r < m
.
Portanto:
a = km + b = km + mq + r = (k + q)m + r
e isto significa que r é o resto da divisão de a por m, isto é, os inteiros a e b divididos por m deixam o mesmo resto
r.
(⇐) Reciprocamente, suponhamos que a e b divididos por m deixam o mesmo resto r. Então, podemos escrever:
a − b = (q1 − q2 )m ⇒ m | (a − b) ⇒ a ≡ b(mod.m)
7.3. PROPRIEDADES DAS CONGRUÊNCIAS 63
−31 ≡ 11(mod.7)
de modo que pelo teorema anterior, −31 e 11 divididos por 7 deixam o mesmo resto. Realmente, é o que mostram
as igualdades:
−31 = 7(−5) + 4 e 11 = 7 · 1 + 4
m | 0 ou m | (a − a) ⇒ a ≡ a(mod.m)
(3) Com efeito, se a ≡ b(mod.m) e se b ≡ c(mod.m), então existem inteiros h e k tais que
a − b = hm e b − c = km
Portanto:
a − c = (a − b) + (b − c) = hm + km = (h + k)m
aRb ⇐⇒ a ≡ b(mod.m)
Teorema 7.3.2 Seja m um inteiro positivo fixo (m > 0) e sejam a e b dois inteiros quaisquer. Subsistem as
seguintes propriedades:
a b a b
a ≡ b (mod.m) ⇒ a − b = km ⇒ − ⇒ ≡ (mod.m)
d d d d
Assim, p. ex.:
Teorema 7.3.3 Seja m um inteiro positivo fixo (m > 0) e sejam a, b, c, d inteiros quaisquer. Subsistem as
seguintes propriedades:
Demonstração:
(1) Se a ≡ b(mod.m) e se c ≡ d(mod.m), então existem inteiros h e k tais que a − b = hm e c − d = km. Portanto:
(a + c) − (b + d) = (a − b) + (c − d) = hm + km = (h + k)m
e
(ac − bd) = (b + hm)(d + km) − bd = (bk + dh + hkm)m
o que implica:
a + c ≡ b + d (mod.m) e ac ≡ bd (mod.m)
(2) Com efeito, se a ≡ b(mod.m), como c ≡ c(mod.m), temos pela propriedade anterior:
a + c ≡ b + c(mod.m) e ac ≡ bc(mod.m)
7.3. PROPRIEDADES DAS CONGRUÊNCIAS 65
(3) Usando o "Teorema da indução", a proposição é verdadeira para n=1, e suposta verdadeira para um inteiro
positivo k, temos:
ak ≡ bk (mod.d) e a ≡ b (mod.m)
Portanto, pela propriedade (1):
isto é, a proposição é verdadeira para o inteiro positivo k+1. Logo, a proposição é verdadeira para todo inteiro
positivo n.
Assim, p. ex.:
12 + 8 ≡ 22 + 13(mod.5) ou 20 ≡ 35(mod.5)
12 · 8 ≡ 22 · 13(mod.5) ou 96 ≡ 286(mod.5)
12 + 6 ≡ 5 + 6 (mod.7)ou13 ≡ 11 (mod.7)
a ≡ b(mod.m) e − 1 ≡ −1(mod.m)
obtemos:
a + b ≡ c (mod.m) e − b ≡ −b (mod.m)
obtemos:
Portanto, numa congruência pode-se passar um termo de um membro para o outro trocando-lhe o sinal.
66 CAPÍTULO 7. CONGRUÊNCIAS
m
Teorema 7.3.4 Se ac ≡ bc (mod.m) e se mdc (c, m) = d, então a ≡ b mod. .
d
Demonstração:
E se o mdc(c, m) = d, existem r e s tais que c = dr e m = ds, onde r e s são primos entre si. Portanto:
o que implica que s | (a−b)r, com o mdc(r, s) = 1. Logo, pelo teorema 5.4(DE EUCLIDES): s | (a−b) e a ≡ b(mod.s)
m
ou, pode ser s = .
d
Esta propriedade mostra que é permitido cancelar fatores de ambos os membros de uma congruência que são
primos com o módulo.
Cololário 7.3.2 Se ac ≡ bc (mod.p), com p primo, se, e somente se, p não divide c (p - c), então a ≡ b (mod.p).
Demonstração:
33 ≡ 15 (mod.9) ou 3 · 11 ≡ 3 · 5 (mod.9)
11 ≡ 5 (mod.3).
Consideremos a congruência:
Como o mdc (5,8)=1, podemos cancelar o fator 5 de ambos os membros da congruência, o que dá a nova congruência:
−7 ≡ 9(mod.8).
Demonstração:
Seja a um inteiro qualquer e sejam q e r o quociente e o resto na divisão de a pelo inteiro positivo m, isto
é:
a = mq + r, onde 0 ≤ r < m
a ≡ r (mod.m)
e como r pode assumir os valores 0, 1, 2, ...m − 1, segue-se que o inteiro a é congruente módulo m a um único
elemento do conjunto S, e por conseguinte este conjunto é um sistema completo de restos módulo m.
Assim, p.ex., o conjunto S={0,1,2,3,4} é um sistema completo de restos módulo 5.
Cololário 7.4.1 Se S = {r1 , r2 , ..., rm } é um sistema completo de restos módulo m, então os elementos de S são
congruentes módulo m aos inteiros 0, 1, 2, ..., m − 1, tomados numa certa ordem.
Demonstração:
a ≡ ri (mod.m), com ri ∈ S
a ≡ k(mod.m), com 0 ≤ k ≤ m − 1
r1 ≡ k(mod.m)
91 ≡ 0(mod.7)
Exemplo 7.4.1 Mostrar que o conjunto S0 = {−2, −1, 0, 1, 2} é um sistema completo de restos módulo 5.
Pelo teorema 9.6, um inteiro qualquer a é congruente módulo 5 a um único elemento do conjunto {0,1,2,3,4},
isto é:
a ≡ (mod.5), com 0 ≤ k ≤ 4
Por outro lado, os elementos de S são congruentes módulo 5 aos inteiros 0, 1, 2, 3, 4, tomados numa certa ordem,
pois, temos:
Logo, o inteiro a é congruente módulo 5 a um único elemento do conjunto S, e por conseguinte este conjunto é um
sistema completo de restos módulo 5.
EXERCÍCIOS
1. Verdadeiro (V) ou falso (F):
(a) 5 + 3 + 2 + 1 + 8(mod.7)
(b) 2 + 3 − 1 + 7 − 2(mod.4)
4. Sabendo que 1066 ≡ 1776 (mod.m), achar todos os possíveis valores do módulo m
5. Exprimir que "n é ímpar"de três outras maneiras.
6. Achar todos os valores de "x"tais que 0 6 x 6 15 e 3x ≡ 6(mod.15).
7. Achar todos os valores de "x" tais que 1 6 x 6 100 e x ≡ 7(mod.17).
8. Sabendo que k ≡ 1 (mod.4) mostrar que 6k + 5 ≡ 3 (mod.4) .
9. Mostrar, mediante um exemplo, que a2 ≡ b2 (mod.m) não implica a ≡ b (mod.m).
10. Mostrar que todo primo (exceto 2) é congruente módulo 4 a 1 ou 3.
11. Mostrar que todo primo (exceto 2 e 3) é congruente módulo 6 a 1 ou 5.
12. Mostrar que 1110 ≡ 1 (mod.100).
13. Mostrar que 41 divide 220 − 1.
14. Achar os restos das divisões 250 e 4165 por 7.
15. Mostrar:
(a) 89 | (244 − 1);
7.4. SISTEMAS COMPLETOS DE RESTOS 69
(b) 97 | (248 − 1)
19. Determinar quais dos seguintes conjuntos são sistemas completos de restos módulo 4:
(a) {-2,-1,0,1} (b) {0,4,8,12}
20. Determinar quais dos seguintes conjuntos são sistemas completos de restos módulo 6:
(a) {1,2,3,4,5,} (b) {0,5,10,15,20,25}
21. Achar um sistema completo de restos {p1 , p2 , ..., p7 } módulo 7 tal que todo pi é primo.
22. Achar um sistema completo de restos módulo 7 formado só de múltiplos não negativos de 4.
RESPOSTAS CAPÍTULO 9
1. (a) V (b) V (c) F (d) V (e) F (f) F
2. (a) V (b) V
3. (a) 5 (b) 1
9. 72 ≡ 52 (mod.8) e 72 . 52 (mod.8)
14. 4 e 6
19 (a) e (c)
SISTEMAS DE CONGRUÊNCIAS
LINEARES
8.1 GENERALIDADES
Um sistema de duas ou mais congruências lineares não tem necessariamente solução, mesmo que cada
uma das congruências do sistema, isoladamente, tenha solução. Assim, p.ex., não existe inteiro algum x
que verifique simultaneamente as congruências lineares:
x ≡ 1 (mod.2) e x ≡ 0 (mod.4)
Obviamente, um sistema de congruências lineares não tem solução se alguma das congruências do
sistema não tem solução.
Exemplo 8.1.1 Mostrar que todo inteiro x ≡ 52 (mod.105) satisfaz cada uma das três seguintes congruências
lineares:
x ≡ 1 (mod.33)
x ≡ 2 (mod.5)
x ≡ 3 (mod.7)
1 + 3a ≡ 2 (mod.5)
3a ≡ 1 (mod.5)
a ≡ 2 (mod.5)
Portanto:
7 + 15b ≡ 3 (mod.7)
15b ≡ −4 (mod.7)
b ≡ 3 (mod.7)
Portanto:
71
72 CAPÍTULO 8. SISTEMAS DE CONGRUÊNCIAS LINEARES
x ≡ 52 (mod.105)
Note-se que os módulos 3, 5 e 7 são primos entre si dois a dois e que o mmc(3, 5, 7) = 105.
Demonstração:
isto é, Mk é o produto de todos os inteiros mi com o fator mk omitido. Por hipótese, os mi são primos
entre si dois a dois, de modo que o mdc(Mk , mk ) = 1 e, portanto, a congruência linear:
Mk x ≡ 1 (mod.mk ) (1)
X = a1 M1 x1 + a2 M2 x2 + ... + ar Mr xr
satisfaz cada uma das congruências do sistema considerado, ou seja, que X é uma solução deste
sistema.
X = a1 M1 x1 + a2 M2 x2 + ... + ar Mr xr ≡ ak Mk xk (mod.mk )
Mk xk ≡ 1 (mod. mk )
o que implica:
X ≡ ak .1 ≡ ak (mod. mk )
8.1. GENERALIDADES 73
Para demonstrar a unicidade desta solução, suponhamos que X1 é uma outra solução qualquer do
sistema de congruências considerado. Então:
X ≡ ak ≡ X1 (mod. mk ), k = 1, 2, ..., r
de modo que mk | (X − X1 ) para cada valor de k. E como o mdc(mi , m j ) = 1, segue-se que m1 m2 ...mr |
(X − X1 ), isto é:
m | (X − X1 ) e X ≡ X1 (mod. m)
Os módulos 3, 5 e 7 das congruências do sistema dado são primos entre si dois a dois:
de modo que, pelo teorema anterior, o sistema tem uma única solução módulo m = 3.5.7 = 105. Temos aqui:
As congruências lineares:
Portanto, o inteiro:
Como 233 ≡ 23 (mod. 105), segue-se que X ≡ 23 (mod.105) é a única solução do sistema de congruências
lineares dado.
Note-se que o sistema corresponde ao seguinte problema: achar um inteiro que deixa os restos 2, 3 e 2 quando
dividido por 3, 5 e 7, respectivamente.
Os módulos 5, 3, 7 e 4 das congruências do sistema dado são primos entre si dois a dois, de modo que o sistema
tem uma única solução módulo m = 5.3.7.4 = 420. Temos:
As congruências lineares:
X ≡ 158 (mod.420)
Teorema 8.1.1 Sejam m1 , m2 , ...mr inteiros positivos primos entre si dois a dois, isto é, o mdc(m1 , m j ) = 1 se i , j,
e sejam a1 , a2 , ..., ar inteiros tais que o
Demonstração:
ak x ≡ 1 (mod.mk )
ak a∗k ≡ 1 (mod.mk )
x ≡ bk a∗k (mod.mk )
x ≡ b1 a∗1 (mod.m1 )
x ≡ b2 a∗ (mod.m2 )
2
................................
x ≡ br a∗ (mod.mr )
r
o qual tem, pelo "Teorema do resto chinez", uma única soluçao módulo m = m1 m2 ...mr .
Os módulos 5, 7 e 11 das congruências do sistema dado são primos entre si dois a dois e, além disso:
de modo que, pelo teorema 11.1, o sistema tem uma única solução módulo m = 5.7.11 = 385.
As congruências lineares:
tem como soluções respectivas: a∗1 = 3, a∗2 = 5, a∗3 = 3, e por conseguinte o sistema dado é equivalente ao
sistema:
x ≡ 3 (mod.5)
x ≡ 10 (mod.7)
x ≡ 9 (mod.11)
13x ≡ 17 (mod.42)
Por ser 42 = 2.3.7, a congruência linear dada é equivalente ao sistema de congruências lineares:
13x ≡ 17 (mod.2)
13x ≡ 17 (mod.3)
13x ≡ 17 (mod.7)
ou
x≡1 (mod.2)
x≡2 (mod.3)
x ≡ 4
(mod.7)
A primeira congruências dá-nos x = 1 + 2a, onde a é um inteiro. Substituindo este valor de x na segunda
congruência obtemos:
1 + 2a ≡ 2 (mod.3) ⇒ a ≡ 2 (mod.3)
Portanto:
a = 2 + 3b e x = 1 + 2(2 + 3b) = 5 + 6b
5 + 6b ≡ 4 (mod.7) ⇒ b ≡ 1 (mod.7)
Portanto:
x ≡ 11 (mod.42)
13x ≡ 17 (mod.42).
76 CAPÍTULO 8. SISTEMAS DE CONGRUÊNCIAS LINEARES
EXERCÍCIOS
1. Resolver os seguintes sistemas de congruências lineares:
(a) 5x ≡ 11 (mod.17)
3x ≡ 19 (mod.32)
11x ≡ 6 (mod.37)
(b) 2x ≡ 1 (mod.5)
3x ≡ 9 (mod.6)
4x ≡ 1 (mod.7)
5x ≡ 9 (mod.11)
(a) x ≡ 8 (mod.9)
x ≡ 2 (mod.3)
x ≡ 5 (mod.7)
(b) x ≡ 4 (mod.6)
x ≡ 13 (mod.15)
x ≡ 8 (mod.14)
x ≡ 1 (mod.7)
(c) x ≡ 0 (mod.3)
x ≡ 1 (mod.4)
17x ≡ 9 (mod.23)
(b) x ≡ 52 (mod.105)
(c) x ≡ 785 (mod.1122)
(d) x ≡ 4944 (mod.9889)
(e) x ≡ 106 (mod.252)
(f) x ≡ −1 (mod.9889)
(g) x ≡ 40a − 24b − 15c (mod.120)
Teorema 9.0.2 TEOREMA DE FERMAT Se p é um primo e se p não divide o inteiro a (p - a), então:
ap−1 ≡ 1 (mod.p)
Nenhum desses inteiros é congruente a 0 (mod.p), além disso, dois quaisquer deles são incongruentes
(mod.p) , pois, se fosse:
ra ≡ sa (mod.p), 1 6 r < s 6 p − 1
então, o fator comum a poderia ser cancelado, por que o mdc(a, p) = 1, e teríamos:
r ≡ s (mod.p)
Assim sendo, cada um dos inteiros a, 2a, 3a, · · · , (p − 1)a é congruente (mod.p) a um único dos intei-
ros 1, 2, 3, ..., p − 1, considerados numa certa ordem, e por conseguinte multiplicando ordenadamente
todas essas p − 1 congruências, teremos:
ou seja:
Como p é primo e p não divide (p − 1)!, podemos cancelar o fator comum (p − 1)!, o que dá a congruência
DE FERMAT:
ap−1 ≡ 1 (mod.p)
79
80 CAPÍTULO 9. TEOREMAS DE FERMAT E WILSON
Demonstração:
a ≡ 0 (mod.p) e ap ≡ 0 (mod.p)
O que implica:
ap ≡ a (mod.p)
Se, ao invés, p não divide a (p - a), então, pelo teorema de FERMAT: ap−1 ≡ 1 (mod.p) e, portanto:
37−1 = 36 = 729
37−1 ≡ 1 (mod.7)
1717−1 = 1716
mas não é necessário calcular o número muito grande 316 , pois, temos:
33 = 27 ≡ 10 (mod.17)
o que implica:
Portanto:
510 ≡ 1 (mod.11)
o que implica:
3 4
538 = 510·3 + 8 = (510 ) (52 )
≡ 13 · 34 ≡ 81 ≡ 4 (mod.11)
a117 . a (mod.117)
Com a = 2, temos:
16
2117 = 27·16 + 5 = (27 ) · 25
3
Mas, 221 = (27 ) , o que implica:
Portanto:
2117 ≡ 44 . 2 (mod.117)
ap ≡ a (mod.q) e aq ≡ a (mod.p)
então:
apq ≡ a (mod.pq)
Demonstração:
e, pela hipótese:
aq ≡ a (mod.p) e ap ≡ a (mod.q)
O que implica:
ou seja:
p | (apq − a) e q | (apq − a)
Portanto:
2340 ≡ 1 (mod.341)
83
Nota-se que esta congruência, onde o módulo 341 é composto, mostra que o recíproco do teorema de FERMAT, isto é:
(2 − 1)! = 1! = 1 ≡ −1 (mod.2)
(3 − 1)! = 2! = 2 ≡ −1 (mod.3)
ax ≡ 1 (mod.p)
1, 2, 3, · · · , p − 1
Então, o mdc(a, p) = 1 e, pelo corolário 10.1, esta congruência admite uma única solução módulo p, isto é, existe
um único inteiro a1 , com 1 ≤ a1 ≤ p − 1, tal que aa1 ≡ (mod.p).
a2 ≡ 1 (mod.p)
é equivalente à seguinte:
(a − 1)(a + 1) ≡ 0 (mod.p)
de modo que p|(a − 1)(a + 1) e, portanto:
p|(a − 1) ou p|(a + 1)
,
o que implica:
a − 1 ≡ (mod.p) e a = 1
a + 1 ≡ (mod.p) e a = p − 1
a 1 2 3 4 5 6 7 8 9 10 11 12
a1 1 7 9 10 8 11 2 5 3 4 6 12
Omitindo os inteiros 1 e p − 1, com os p − 3 inteiros restantes: 2, 3, · · · , p − 2, podemos formar (p − 3)/2
84 CAPÍTULO 9. TEOREMAS DE FERMAT E WILSON
aa1 ≡ 1 (mod.p)
2. 3 · · · (p − 2) ≡ 1 (mod.p)
(p − 2)! ≡ 1 (mod.p)
(p − 1)! ≡ p − 1 ≡ −1 (mod.p)
Note-se que, com p = 13, os 10 inteiros 2, 3, ..., 11 dão lugar a 5 pares tais que o produto dos inteiros de cada par
é congruente a 1 (mod.13):
2.7 ≡ 1 (mod.13)
3.9 ≡ 1 (mod.13)
4.10 ≡ 1 (mod.13)
5.8 ≡ 1 (mod.13)
6.11 ≡ 1 (mod.13)
e portanto:
12! ≡ 12 ≡ −1 (mod.13)
isto é:
(p − 1)! ≡ −1 (mod.p), com p = 13
Demonstração:
Suponhamos que o inteiro n é composto. Então, n tem um divisor d tal que 1 < d < n. Além disso,
como d 6 n − 1, segue-se d é um dos fatores de (n − 1)! = 1. 2. 3. ... (n − 1) e, portanto, d | (n − 1)!. Mas, por
9.1. EXERCÍCIOS 85
hipótese, n | (n − 1)! + 1, de modo que d | (n − 1)! + 1. Logo d | 1, o que é absurdo. Portanto, n é primo.
NOTA. O teorema de WILSON e o seu recíproco dão um critério para se reconhecer se um inteiro dado é primo:
um inteiro n > 1 é primo se e somente se
(n − 1)! ≡ −1 (mod.n)
.
Entretanto, para inteiros grandes este critério é impraticável, e por isso de interesse apenas teórico.
Portanto:
(7 − 1)! + 1 ≡ 0 (mod.7)
ou
(7 − 1)! ≡ −1 (mod.7)
temos:
e portanto:
Logo, 11 é primo.
9.1 EXERCÍCIOS
1. Verificar o teorema de FERMAT com a = 2 e p = 13.
6. Verificar:
a12 ≡ 1 (mod.35)
.
12. Mostrar:
(a) 561 | (2561 − 2)
(b) 561 | (3561 − 3)
13. Formar com os inteiros 2, 3, 4, ..., 21 todos os pares a, b tais que ab ≡ 1 (mod. 23).
Capítulo 10
DIVISORES DE UM INTEIRO
onde 0 ≤ hi ≤ ki (i = 1, 2, . . . r)
h1 = h2 = . . . = hr = 0
e
h1 = k1 , h2 = k2 . . . = hr = kr
d = q1 q2 . . . qs , d1 = t1 t2 . . . tu
obtemos:
n = pk11 pk22 . . . pkr r = q1 q2 . . . qs t1 t2 . . . tu
Que são duas decomposições do inteiro positivo n num produto de primos, e como é a única uma decomposição
de n de tal natureza, então cada primo qi coincide com um p j de modo que, substituindo os produtos de primos por
potência de expoente inteiro, teremos:
d = q1 q2 ...qs = ph11 ph22 ...phr r
n = pk11 pk22 . . . pkr r = (ph11 ph22 . . . phr r )(pk11 −h1 pk22 −h2 . . . pkr r −hr ) = d(pk11 −h1 pk22 −h2 . . . pkr r −hr )
87
88 CAPÍTULO 10. DIVISORES DE UM INTEIRO
n = 1350 = 2 · 33 · 52
são precisamente os inteiros d da forma:
d = 2h1 · 3h2 · 5h3
onde
0 ≤ h1 ≤ 1, 0 ≤ h2 ≤ 3, 0 ≤ h3 ≤ 2
isto é:
h1 = 0, 1, h2 = 0, 1, 2, 3, h3 = 0, 1, 2
Assim, com h1 = 1, h2 = 2eh3 = 0, obtemos o divisor:
d = 2 · 32 · 50 = 2 · 9 · 1 = 18
do inteiro 1350. Realmente: 1350 = 18 · 75.
Com h1 = h2 = h3 = 0 e h1 = 1, h2 = 3, h3 = 2 acham-se os divisores triviais d=1 e d=1350 do inteiro dado
1350.
Se p é um primo, então d(p) = 2, porque os únicos divisores positivos de p são 1 e p. E como os divisores
positivos de p2 são 1, p e p2 , temos d(p2 ) = 3. De modo geral, d(pn ) = n + 1, porque os divisores positivos de
pn são 1, p, p2 , . . . ,pn . A tabela abaixo dá o número de divisores positivos dos inteiros de 1 até 10:
n 1 2 3 4 5 6 7 8 9 0
d(n) 1 2 2 3 2 4 2 4 3 2
Teorema 10.2.1 Se n = pk11 pk22 . . . pkr r é a decomposição canônica do inteiro positivo n > 1, então:
Demonstração:
Consoante o teorema 13.1, os divisores positivos de n são precisamente os inteiros d da forma:
n = 756 = 22 · 33 · 7
é:
d(756) = (2 + 1)(3 + 1)(1 + 1) = 3 · 4 · 2 = 24
Estes 24 divisores positivos de 756 são os inteiros d da forma:
onde h1 = 0, 1, 2, h2 = 0, 1, 2, 3 e h3 = 0, 1.
O cálculo para a determinação efetiva destes 24 divisores positivos de 756 pode dispor-se do seguinte modo:
1 2 4
3 3 6 12
9 9 18 36
27 27 54 108
7 7 14 28
21 42 84
63 126 252
189 373 756
Na primeira linha, de lado direito, escrevem-se as potências do primeiro fator primo 2, isto é, 1,2 e 4. Na segunda,
terceira e quarta linhas, do lado esquerdo, escrevem-se, por baixo uma das outras, as diversas potências do segundo
fator primo 3, a partir da primeira potência, no caso presente 3,9 e 27, e à direita de cada uma delas escrevem-se os
produtos dessa potência por todos os inteiros da primeira linha. A seguir, do lado esquerdo, escrevem-se as potências
do terceiro fator primo 7, a partir da primeira (no caso 7), e à direita escrevem-se os produtos dessas potências por
todos os inteiros que do lado direito figuram nas linha anteriores. Se houvesse mais fatores primos procedia-se com
eles como para o caso do terceiro fator primo.
Exemplo 10.2.2 Achar o menor inteiro positivo n que tem 10 divisores positivos. Como 10 = 10 · 1 = 5 · 2, temos:
ou
d(n) = (k1 + 1)(k2 + 2) = 5 · 2
Portanto, os expoentes, k1 e k2 dos fatores primos de n são 9 e 0, ou 4 e 1. E como 24 · 3 é menor que 29 , o menor
inteiro positivo com 10 divisores positivos é 24 · 3 = 48.
Exemplo 10.2.3 Achar o inteiro positivo de forma 9 · 10m e que admite 27 divisores positivos.
Por ser 9 · 10m = 32 · 2m · 5m , devemos ter:
(2 + 1)(m + 1)(m + 1) = 27
ou
(m + 1)2 = 9 =⇒ m + 1 = 3 e m = 2
Logo, o inteiro positivo procurado é 9 · 102 = 900.
s(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28
90 CAPÍTULO 10. DIVISORES DE UM INTEIRO
n 1 2 3 4 5 6 7 8 9 10
s(n) 1 3 4 7 6 12 8 15 13 18
Teorema 10.3.1 Se pk11 pk22 . . . pkr r é a decomposição canônica do inteiro positivo n > 1, então
Demonstração:
Consideremos o produto:
k )
(1 + p1 + p21 + . . . + p11 (1 + p2 + p22 + . . . + pk22 ) . . . (1 + pr + p2r + . . . + pkr r )
. Pelo Teorema 13.1, cada divisor positivo de n é um termo do desenvolvimento deste produto e vice-versa, de modo
que
s(n)(1 + p1 + p21 + . . . + pk11 )(1 + p2 + p22 + . . . + pk22 ) . . . (1 + pr + p2r + . . . + pkr r )
. Aplicando a cada parêntese do segundo membro desta igualdade a fórmula que dá a soma dos termos de uma
progressão geométrica finita, temos:
pk11 +1 − 1 pk22 +1 − 1 pkr r +1 − 1
s(n) = · ...
p1 − 1 p2 − 1 pr − 1
ou seja:
r
Y pk1 +1 − 1
1
s(n) =
p1 − 1
i=1
Note-se que
s(n) = s(pk11 ) s(pk22 ) . . . s(pkr r )
Exemplo 10.3.1 A soma dos divisores positivos do inteiro
n = 180 = 22 · 32 · 5
é:
23 − 1 33 − 1 52 − 1
s(180) = · · = 7 · 13 · 6 = 546
2−1 3−1 5−1
Realmente, os divisores positivos de 180 são:
1, 2, 3, 4, 5, 6, 9, 10, 12, 15, 18, 20, 30, 36, 45, 60, 90, 180
e a soma destes 18 divisores é 546.
10.4. NOTAÇÃO 91
10.4 NOTAÇÃO
Seja n um inteiro positivo. Com o símbolo
X
f (d)
d|n
indica-se a soma dos valores de f(d) quando d é sucessivamente igual a cada um dos divisores positivos
de n. Assim, p.ex.: X
f (d) = f (1) + f (2) + f (4) + f (5) + f (10) + f (20)
d|20
X
d2 = 12 + 22 + 52 + 102 = 1 + 4 + 25 + 100 = 130
d|10
Assim, p.ex.: X
d(10) = 1=1+1+1+1=4
d|10
X
s(10) = d = 1 + 2 + 5 + 10 = 18
d|10
Analogamente, o produto dos valores de f(d) quando d é sucessivamente igual a cada um dos divisores
positivos de n indica-se pelo símbolo: Y
f (d)
d|n
Assim, p.ex.: Y
f (d) = f (1) f (2) f (3) f (4) f (6) f (12)
d|12
Y
d + 1 · 2 · 4 · 5 · 10 · 20 = 8000
d|20
Demonstração:
Sejam d1 , d2 , . . . dk todos os divisores positivos de n, de modo que existem os inteiros q1 , q2 , . . . , qk tais que
n = d1 q1 , n = d2 q2 , . . . , n = dk qk
nk = (d1 d2 . . . dk )(q1 q2 . . . qk )
nd(n) = (d1 d2 . . . dk )2
donde
d1 d2 . . . dk = nd(n)|2
ou seja: Y
d = nd(n)|2
d|n
92 CAPÍTULO 10. DIVISORES DE UM INTEIRO
Realmente, os divisores positivos de 16 são 1,2,4,8,16 e o produto destes 5 divisores é igual a 1024.
EXERCíCIOS
1. Sendo p e q primos, calcular: d(pq), d(p2 q)
(a) 144
(b) 360
(c) 1009
(d) 6534
11. Achar a soma dos divisores positivos de cada um dos seguintes inteiros:
(a) 144
(b) 360
(c) 1009
(d) 6534
17. verificar que d(n) = d(n+1) = d(n+2) = d(n+3) para n=3655 e n=4503.
10.5. PRODUTO DOS DIVISORES 93
18. Achar os inteiros positivos menores que 10000 e com 60 divisores positivos.
RESPOSTAS
1. 4, 6 e 8
2. 8, 20, 24 e 12
3. (a)15 (b)24 (c)2 (d)24
4. 50
5. 12
6. 24
7. 6300
8. 3150
9. 1 + p + q + pq , 1 + p + p2 + p3 + 1 + p + q + p2 + pq + p2 q
10. 744, 1344, 3224, 14736
11. (a)403 (b)1170 (c)1010 (d)15960
12. 24 e 39
21. n = 432
22. n = 1400
23. (a) x = 22; (b)x = 38, 24, 59
94 CAPÍTULO 10. DIVISORES DE UM INTEIRO
Capítulo 11
FUNÇÕES ARITMÉTICAS
Assim, p.ex., são funções aritméticas multiplicativas as funções f e g definidas por f(n) = 1 (função
constante) e g(n) = n para todo inteiro positivo n, pois, quaisquer que sejam os inteiros positivos r e s,
temos:
f (rs) = 1 = 1.1 = f (r) f (s)
g(rs) = rs = g(r)g(s)
Note-se que, para estas duas funções, f e g, se verifica a igualdade f (rs) = f (r) f (s) mesmo sem a condição
de o mdc(r,s)= 1. Se f é uma função aritmética multiplicativa e se n1 , n2 , · · · , nk são inteiros positivos
primos entre si dois a dois , então, usando o "Teorema da indução matemática"conclui-se:
Portanto, se n = pk11 pk22 · · · pkr r é a decomposição canônica de um inteiro positivo n>1 como os fatores
pki i
95
96 CAPÍTULO 11. FUNÇÕES ARITMÉTICAS
Esta igualdade mostra que uma função aritmética multiplicativa fica completamente determinada
quando os seus valores para potências de primos são cohecidos.
Importa ainda notar que, para toda função aritmética multiplicativa não identicamente nula se tem
f(1)= 1, pois existe necessariamente um inteiro positivo r tal que f (r) , 0 e como o mdc(r,1) = 1, temos:
f (r) = f (r · 1) = f (r) f (1) =⇒ f (1) = 1
Teorema 11.2.1 As funções d(n) e s(n) são ambas funções aritméticas multiplicativas.
Demonstração:
Se u e v dois inteiros positivos tais que o mdc(u,v)= 1.
Se u= 1 ou v= 1, então, obviamente:
d(uv) = d(u)d(v)
e
s(uv) = s(u)s(v)
Suponhamos, pois, u > 1 e v > 1, sejam
h
u = pk11 pk22 · · · pki i , v = qh11 qh22 · · · q j j
as decomposições canônicas de u e v.
e, portanto: h i
d(uv) = [(k1 + 1) · · · (ki + i)] (hi + 1) · · · (h j + 1) = d(u)d(v)
e
h +1 h +1
ki +1
k +1
p11 − 1 p − 1 q 1 − 1 q j j − 1
s(uv) = ··· i 1 ··· = s(u)s(v)
p1 − 1 pi − 1 q1 − 1 q j − 1
isto é:
s(63) = s(9)s(7)
Teorema 11.2.2 Se f é uma função aritmética multiplicativa e se g é a função aritmética assim definida:
X
g(n) = f (d)
d|n
Demonstração:
Sejam r e s dois inteiros positivos tais que o mdc(r,s)= 1. Como o conjunto dos divisores positivos de rs consiste de
todos os produtos xy, onde x | r, y | s e o mdc(x,y)= 1, temos:
X X
g(rs) = f (d) = f (xy)
d|rs x|r,y|s
e, portanto:
X X X
g(rs) = f (x) f (y) = f (x) f (y) = g(r)g(s)
x|r, y|s x|r y|s
Exemplo 11.2.3 Verificar que a função aritmética g(n) é multiplicativa para n = 24.
ou seja:
g(3 · 8) = f (1 · 1) + f (1 · 2) + f (1 · 3) + f (1 · 4) + f (2 · 3) + f (1 · 8) + f (3 · 4) + f (3 · 8) =
f (1) f (1) + f (1) f (2) + f (1) f (3) + f (1) f (4) + f (2) f (3) + f (1) f (8) + f (3) f (4) + f (3) f (8)
isto é:
X X
f (3 · 8) = f (1) + f (3) f (1) + f (2) + f (4) + f (8) = f (d) = g(3)g(8)
f (d) ·
d|3 d|8
1 se n = 1
2
u(n) =
0 se p | n, sendo p um primo
(−1)r se n = p p . . . p onde os p são primos distintos
1 2 r i
Assim, p.ex.:
n 1 2 3 4 5 6 7 8 9 10
u(n) 1 -1 -1 0 -1 1 -1 0 0 1
Demonstração:
Sejam r e s dois inteiros positivos tais que o mdc(r,s)= 1. Cumpre demonstrar que u(rs) = u(r)u(s).
Se r = 1, então:
r = p1 p2 . . . pm e s = q1 q2 . . . qn
1 se n = 1
X (
u(d) =
0 se n > 1
d|n
Demonstração:
Consideremos a função aritmética g assim definida:
X
g(n) = u(d)
d|n
Se n = 1, então: X
g(1) = u(d) = u(1) = 1
d|1
Suponhamos, agora, n > 1. Se n = pk , sendo p um primo e k > 1 um inteiro, então os divisores positivos de pk
são os k + 1 inteiros: 1, p, p2 , . . . , pk , e temos:
X
g(pk ) = u(d) = u(1) + u(p) + u(p2 ) + . . . + u(pk )
d|pk
ou seja: X
g(pk ) = u(d) = u(1) + u(p) = 1 + (−1) = 0
d|pk
Definição 11.3.2 Uma função aritmética f : N → Z diz-se uma funçaõ aritmética multiplicativa completa
se f(rs) = f(r)f(s) para todo par de inteiros positivos r e s.
Assim, p.ex., a função aritmética f definida por f (n) = n3 é uma função aritmética multiplicativa completa,
pois, quaisquer que sejam os inteiros positivos r e s temos;
As funções aritméticas d(n), s(n) e u(n) não são funções aritméticas multiplicativas completas, pois, temos:
A função f : R → R definida por f(x) = [x] chama-se "função maior inteiro". Não é uma função aritmética,
porque o seu domínio é o conjunto R , N dos número reais, mas desempenha papel importante no tratamento
dos problemas de divisibilidade.
Observe que:
1
X
u(d) =
n
d|n
A "função maior inteiro" também é denominada "função colchete" ou "função escada" (por virtude do
seu gráfico cartesiano).
Também se costuma considerar a função x = x − [x], denominada parte fracionária de x.
Assim, p.ex.:
{7} = 0; {2, 6} = 0, 6; {−4, 75} = 0, 25
Então: X n
g(n) = u(d) f (
d
d|n
100 CAPÍTULO 11. FUNÇÕES ARITMÉTICAS
Demonstração:
Obviamente, temos:
X n X X X X
u(d) f ( ) = u(d) g(c) = u(d)g(c)
d
n
n
d|n d|n c|( d ) d|n c|( d )
n n
A última soma dupla é sobre todos os pares de inteiros positivos (c,d) tais que d | n e c | . E como d | n e c |
d d
n
se e somente se d | n e c | , temos:
d
X X X X X X
u(d)g(c) = u(d)g(c) = g(c) u(d)
n n n
d|n c|( d ) c|n d|( c ) c|n d|( c )
n n
tem o valor 0 se > 1 e tem o valor 1 se = 1 ou n = c. Assim sendo, temos, finalmente:
c c
n
X X
u(d) f = g(c) · 1 = g(n)
d c=n
d|n
Note-se que
n n
X X
u(d) f = u f (d) = g(n)
d d
d|n d|n
Assim, p.ex., no caso das funções aritméticas d(n) e s(n) temos, por definição:
X X
d(n) = 1 e s(n) = d
e|n d|n
EXERCÍCIOS
1. Mostrar que é multiplicativa a função aritmética f (n) = nk , onde k é um inteiro fixo positivo.
2. Mostrar que, se f (n) e g(n) são funções aritméticas multiplicativas, então a função aritmética
h(n) = f (n)g(n)
também é multiplicativa.
3. Mostrar que, se f (n) e g(n) são funções aritméticas multiplicativas tais que f (pk ) = g(pk ) para todo
primo e k ≥ 1, então f = g.
Números Perfeitos
Definição 12.1.1 Um inteiro positivo n diz-se perfeito se e somente se é igual à soma de todos os seus divisores
positivos, exceto o divisor trivial n.
A soma de todos os divisores positivos de n, com exceção do divisor n, é igual a s(n) − n e, portanto, n é
um perfeito se e somente se a seguinte condição se verifica:
n = s(n) − n, ou : s(n) = 2n
isto é, um inteiro positivo n é um perfeito se e somente se a soma de todos os seus divisores positivos é
igual ao seu dobro 2n.
Assim, p.ex., para n = 6 e n = 28, temos:
s(6) = 1 + 2 + 3 + 6 = 12 = 2.6
s(28) = 1 + 2 + 4 + 7 + 14 + 28 = 56 = 2.28
de modo que os inteiros positivos 6 e 28 são ambos perfeitos.
Os números perfeitos são muito raros e até hoje (1980) são conhecidos apenas 24, todos pares, e os seis
primeiros são:
P1 = 6, P2 = 28, P3 = 496
P4 = 8128, P5 = 33550336, P6 = 8589869056
os quais terminam em 6 ou em 8 e, com exceção de 6, são da forma 9k + 1.
Não se conhece nenhum número perfeito ímpar, e nem mesmo se sabe se existem, mas, se existem, são
muito grandes - maiores que 1050 .
Teorema 12.1.1 (de EUCLIDES) Se 2k − 1 é primo (k > 1), então o inteiro positivo n = 2k−1 (2k − 1) é um
número perfeito.
Demonstração:
Seja 2k − 1 = p (k > 1) um primo. Consideremos o inteiro positivo n = 2k−1 p. Como o mdc 2k−1 , p = 1 e s(n)
é uma função aritmética multiplicativa, temos:
s(n) = s(2k−1 )s(p) = (2k − 1)(p + 1) =
(2k − 1)2k = 2n
103
104 CAPÍTULO 12. NÚMEROS PERFEITOS
Seja 2k − 1 = p (k > 1) um primo. Consideremos o inteiro positivo n = 2k−1 p. Como o mdc 2k−1 , p = 1 e s(n)
é uma função aritmética multiplicativa, temos:
s(n) = s(2k−1 )s(p) = (2k − 1)(p + 1) =
(2k − 1)2k = 2n
Logo, por definição, n é um número perfeito.
Assim, todas as vezes que se conhece um inteiro k > 1 tal que 2k − 1 é primo pode-se construir um número
perfeito. Para k = 13 p.e.x., temos 21 3 − 1 = 8191, um primo, o que dá o 5 número perfeito.
NOTA. Os quatro primeiros números perfeitos se obtem pela fórmula de EUCLIDES atribuindo a k os
valores 2,3,5 e 7, isso é:
P1 = 2(22 − 1) = 6, P2 = 22 (23 − 1) = 28
P3 = 2 (2 − 1) = 496, P4 = 26 (27 − 1) = 8128
4 5
os quais foram determinados, pela primeira vez, pelo matemático italiano PIETRO CATALDI em 1603.
31, 61, 89, 107, 127, 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213 e 19937
n = 2k−1 (2k − 1)
onde 2k − 1 é primo.
Demonstração:
Suponhamos que n é um número perfeito par. Então, n pode escrever-se sob a forma: n = 2k−1 m, onde m
é um inteiro ímpar e k >= 2.
s(n) = 2n = 2k m
Portanto:
s(m) = 2k M
2k M = s(m) >= m + M = 2k M
o que implica:
s(m) = m + M
Assim sendo, m e m são os únicos divisores positivos de m, e isto significa que m é primo e M=1. Então:
m = (2k − 1)M = 2k − 1
Este teorema é o recíproco do teorema 16.1 (EUCLIDES) e foi demonstrado por EULER cerca de 2000 anos
depois de EUCLIDES.
O teorema que se segue estabelece uma condição necessária, mas não su f iciente, para que um inteiro da
forma
2k − 1 (k > 2)
seja primo.
Demonstração:
106 CAPÍTULO 12. NÚMEROS PERFEITOS
Suponhamos o inteiro 2k − 1 (k > 2) primo. Se o inteiro k fosse composto, então teríamos k = rs, com r > 1
e s > 1, o que implica:
2k − 1 = 2rs − 1 = (2r )s − 1
ou seja:
Como r > 1, os dois fatores do segundo membro são ambos maiores que 1, isto é, 2k − 1 é um inteiro
composto, o que contraria a hipótese. Logo, k é primo.
NOTA. O recíproco do teorema 16.3 é f also,isto é, k primo não implica 2k − 1 também primo. Assim, p.ex.,
11 é primo e no entanto 211 − 1 é composto, pois, temos:
Demonstração:
Seja n um número perfeito par. Pelo teorema 16.2 (de EULER), temos:
Por ser 16t ≡ 6 (mod. 10), qualquer que seja o inteiro positivo t, segue-se que
e, portanto, n termina em 6.
Analogamente, se k é da forma 4m + 3, então:
Por ser 16t ≡ 6 (mod. 10), qualquer que seja o inteiro positivo t, segue-se que
isto é:
n = 10h∗ + 8
e, portanto, n termina em 8.
Cololário 12.1.1 Todo número perfeito par n é congruente a 6 módulo 10 ou congruente a 8 módulo 10, isto é:
Demonstração:
Seja p um primo qualquer. Então, s(p) = p + 1. Se p é um número perfeito, então s(p) = 2p. Portanto:
p + 1 = 2p e p = 1
Definição 12.1.2 Um inteiro positivo n diz-se que um número multiperfeito de ordem k ou um k-número
perfeito se e somente se s(n) = kn, onde k > 3 é um inteiro.
Assim, p.ex., o inteiro positivo 30240 = 55 .33 .5.7 é um número multiperfeito de ordem 4,pois, temos:
Definição 12.1.3 Dois inteiros positivos m e n dizem-se números amigos se e somente se a soma dos divisores
positivos de m, exceto o divisor m, é igual a n, e a soma dos divisores positivos de n, exceto o divisor n, é igual a
m.
s(m) − m = n e s(n) − n = m
s(m) = m + n = s(n)
Exemplo 12.1.1 Mostrar que os inteiros 220 e 284 são números amigos.
Por ser
temos:
isto é:
Mn = 2n − 1 (n > 2)
p=2,3,5,7,13,17,19,31,67,127,257
e que para todos os demais valores de p 6 257 os inteiros Mp são compostos, exceto possivelmente para
p=157,167,193,199,227,229
M2 = 3, M5 = 5, M5 = 7, M7 = 127
e que
12.1. NÚMEROS PERFEITOS 109
também são primos de MERSENNE. Entretanto, o quinto primo de MERSENNE é M13 = 8191, mas
não é um primo de MERSENNE, pois, é um número composto com 2446 algarismos. Assim, é falsa a
conjectura: Se Mn é um primo de MERSENNE, então MMn também é um primo de MERSENNE.
q|Mp ou q|Mp + 2
Demonstração:
Como q é primo e o mdc(2, p) = 1, temos, pelo teorema de FERMAT:
2q−1 − 1 ≡ 0 (mod.q)
ou seja:
Mp (Mp + 2) ≡ (mod.q)
Assim, q é um número primo que divide o produto Mp (Mp + 2) e, portanto, q|Mp ou q|Mp + 2 (Corolário
7.1). Mas, q não divide conjuntamente Mp e Mp + 2, porque, então, q|2, o que é impossível.
47|M23 ou 47|M23 + 2
Portanto:
n
Fn = 22 + 1 (n > 0)
F5 = 23 2 + 1 = 4294967297 = (641)(6700417)
Até hoje não se conseguiu encontrar um primo de FERMAT distinto dos cinco primeiros. Realmente,
5 6 n 6 16 cada número de FERMAT Fn é composto, e também é sabido que é composto para os 34
seguintes valores isolados de n:
n = 18, 19, 21, 23, 25, 26, 27, 30, 32, 36, 38, 39, 42, 52, 55,
58, 63, 73, 77, 81, 117, 125, 144, 150, 207, 226, 228,
260, 267, 268, 284, 316, 452, 1945.
Teorema 12.1.7 Se Fn e Fm são dois números de FERMAT, com m > n > 0, então o mdc(Fn , Fm ) = 1
Demonstração:
Seja d = mdc(Fn , Fm ). Como os números de FERMAT são inteiros ímpares, segue-se que d é um inteiro
ímpar. Temos:
Fm − 2 m n
=(22 − 1)/(22 + 1) =
Fn n n
= [(22 )2m−n − 1]/(22 + 1)
n
Denotando, para simplicidade da notação, 22 por x e 2m−n por k, temos:
Fm − 2 (xk − 1)
= = xk−1 − xk−2 + ... − 1
Fm (x + 1)
de modo que Fn |(Fm − 2). Como d|Fn , segue-se que d|(Fm − 2).
Mas, d|Fm e, portanto, d|2. E como d é um inteiro ímpar, temos d = 1.
12.1. NÚMEROS PERFEITOS 111
EXERCÍCIOS
1/2 = 2.
P
d|n
n = 2k−1 (2k − 1)
então:
7. Mostrar que, se n > 6 é um número perfeito par, então a soma dos seus algarismos é congruente
a 1. (mod. 9)
8. Mostrar que nenhum divisor de um número perfeito pode ser um número perfeito.
n = 219936 (219937 − 1)
14. Mostrar que 120 e 672 são os únicos 3-números perfeitos da forma n = 2k .3.p, onde p é um primo
ímpar.
15. Demonstrar que, se n > 6 é um número perfeito par, então n é congruente a 1 (módulo 6).
112 CAPÍTULO 12. NÚMEROS PERFEITOS
27. Mostrar que 5 e 7 são os únicos primos gêmeos cuja semissoma é um número perfeito.
28. Seja n = 2k−1 (2k − 1) um número perfeito par. Demonstrar que o produto dos divisores positivos
de n é igual a nk .
Capítulo 16
1. 130816 = 28 (29 − 1), e como 29 − 1 = 7.73 não é um primo, segue-se que 130816 não é um número
perfeito.
2. 211 − 1 = 23.89 não é um primo. Logo, n não é um número perfeito.
9. 56
11. s(120) = 3.120 e s(672) = 3.672
17. 12, 18 e 20 são abundantes, 6 é perfeito e os demais inteiros são deficientes.
18. 25575 = 36 .5.7
24. M19 = 524287
25. 23|M11 e 233|M29
Capítulo 13
NUMÉROS DE FIBONACCI
É óbvio que se pode construir arbritariamente um número infinito de sequências de inteiros satisfazendo
à condição (2), tais como, p. ex.:
Como se vê, a condição (2) não basta para determinar univocamente a sequência (1), sendo necessário
conhecer os seus dois primeiros termos para poder calcular todos os outros, isto é, conhecer ou fixar os
termos u1 e u2 .
F1 = F2 = 1
e
Fn = Fn−1 + Fn−2 (n > 3)
isto é, a sequência:
113
114 CAPÍTULO 13. NUMÉROS DE FIBONACCI
Demonstração:
F1 = F3 − F2
F2 = F4 − F3
F3 = F5 − F4
...................
Fn−1= Fn+1 − Fn
Fn = Fn+2 − Fn+1
Assim, p.ex.:
1 + 1 + 2 + 3 + 5 + 6 + 8 + 13 + 21 = F10 − 1 + 55 − 1 = 54
Teorema 17.2 A soma dos n primeiros números de FIBONACCI com índices ímpares é igual a F2n .
F1 = F2
F3 = F4 − F2
F5 = F6 − F4
.......................
F2n−3 = F2n−2 − F2n−4
F2n−1 = F2n − F2n−2
13.4. SOMA DOS QUADRADOS DE NÚMEROS DE FIBONACCI 115
Assim, p.ex.:
Teorema 17.4 A soma dos n primeiros números de FIBONACCI tomados alternadamente com os sinais
+ e − é igual a (−1)n+1 Fn−1 + 1.
Demonstração:
Com efeito, subtraindo ordenamente as igualdades correspondentes aos teoremas 17.2 e 17.3, temos:
1 − 1 + 2 − 3 + 5 − 8 + 13 − 21 =
= (−1)9 F7 + 1 = −13 + 1 = 12
1 − 1 + 2 − 3 + 5 − 8 + 13 − 21 + 34 =
= (−1)10 F8 + 1 = 21 + 1 = 22
Demonstração:
(F)2 = F1 F2
(F)2 = F2 F3 − F1 F2
(F)2 = F3 F4 − F2 F3
......................................
(Fn−1 )2 = Fn−1 Fn−2 Fn−1
(Fn )2 = Fn Fn+1 − Fn−1 Fn
Assim, p.ex.:
12 + 12 + 22 + 32 + 52 + 82 + 132 =
= F7 F8 = 13.21 = 273
Realmente:
1 + 1 + 4 + 9 + 25 + 64 + 169 = 273
Demosntração:
Para cada valor de m usaremos o "Teorema da indução matemática"sobre n. A identidade subsiste para
n = 1, pois temos:
Suponhamos, agora, que a identidade subsiste para n = 1, 2, ..., k, e demonstremos que também sub-
sistepara n = k + 1.
Então, temos (hipótese de indução)
ou seja:
que é precisamente a identidade (I) PARA n = k + 1. Logo, a identidade (I) subsiste para todos os
valores inteiros e positivos de m e n.
Demonstração:
Suponhamos, agora, que a identidade subsiste para o inteiro positivo k (hipótese de indução), isto é:
Somando aos dois membros o inteiro positivo Fk+1 FK+2 , teremos, sucessivamente:
isto é, a identidade (II) subsiste para o inteiro positivo K+1 e, portanto, subsiste para todo inteiro positivo n.
Assim, p.ex.:
Demonstração:
temos:
Portanto:
mdc(Fn , Fn+1 = F2 ) = 1
são todos primos, e por conseguinte é natural conjecturar que Fn é primo para todo índice n > 2 que é
primo. Mas esta conjectura é falsa, porque F19 é um inteiro composto:
Demosntração:
Para cada valor de m usaremos o "Teorema da indução matemática"sobre n. Como a proposição é verdadeira
para n = 1, suponhamos que Fmn é divisível por Fm para n = 1, 2, ..., K (hipótese de indução), e demonstremos
que Fm (k + 1) é divisível por Fm . Temos, pela identidade (I):
Como Fm divide Fmk−1 e Fmk (hipótese de indução), segue-se que a Fm divide o último membro das
igualdades acima e, portanto, Fm divide Fm (k = 1). Logo, Fmn é divisível por Fm para os valores positivos
13.6. PROPRIEDADES DOS NÚMEROS DE FIBONACCI 119
de m e n.
LEMA. Se m = nq + r, então o
mdc(Fm , Fn ) = mdc(n , Fr )
.
Demonstração:
de modo que d é um divisor positivo comum dos npumeros consecutivos Fnq−1 e Fnq de FIBONACCI.
Logo, pelo teorema 17.6, d = 1, isto é, o mdc(Fnq−1 , Fn ) = d = 1.
Demonstração:
suponhamos m > n. Determine o mdc(m, n) pelo algarismo de EUCLIDES, obtemos as seguintes igual-
dades:
mdc(Fm , Fn ) = mdc(Fn , Fr1 ) = mdc(Fr1 , Fr2 ) = ... = mdc(Frn−1 ) como rn | rn−1 , segue-se que Frn | Frn−1
(Teorema 17.7) e, portanto o
mas, sendo rn o último resto diferente de zero no algoritmo de EUCLIDES, o mdc(m, n) = rn , o que
implica:
mdc(Fm , Fn ) = Fmdc(m,n)
Assim, p.ex.:
Realmente:
Demonstração:
Com efeito, se Fm | Fn , então o mdc(Fm , Fn ) = Fm . Mas, pelo teorema 17.8, o mdc(Fm , Fn ) = Fmdc(m,n) .
Assim sendo, o mdc(m, n) = m e, portanto, m | n.
Note-se que este teorema é o recíproco do teorema 17.7, de modo que na sequência de FIBONACCI,
Fm | Fn se somente se m | n.
EXERCÍCIOS
5. Calcular a soma dos 17 primeiros números de FIBONACCI tomados alternadamente com os sinais
+ e −.
10. Foi conjecturado que há somente cinco números de FIBONACCI que tamém são números triangulares.
Achar esses cinco números de FIBONACCI.
11. Representar os inteiros 50, 75 e 100 como somas de distintos números de FIBONACCI.
12. Verificar que 5(Fn )2 + 4(−1)n é sempre um quadrado perfeito para n = 1, 2, ..., 10.
13. Demosntrar:
14. Demonstrar:
(b) Fn+5 ≡ 3Fn (mod.5), isto é, F5 , F10 , F15 , ... são todos inteiros divisíveis por 5.
(a) 2 | Fn se e somente se 3 | n;
(b) 3 | Fn se e somente se 4 | n;
(c) 4 | Fn se e somente se 6 | n;
(d) 5 | Fn se e somente se 5 | n;
18. Demosntrar:
19. demonstrar:
√
Fn = (an − bn )/ 5
22. Demonstrar que, se r é o resto da divisão de Fn por Fm (n > m), então r ou Fm − r é umm número de
FIBONACCI. Exemplificar ambos os casos.
! ! ! !
n n n n
1F1 + F2 + F3 + ... + Fn = F2n , ∀n > 1
] 2 3 n
RESPOSTA
2. F17 − 1 = 1596
3. F24 = 46368
13.6. PROPRIEDADES DOS NÚMEROS DE FIBONACCI 123
4. F21 − 1 = 10945
9. F1 , F2 , F3 , F4 , F6 , F12
10. F1 , F2 , F4 , F8 , F10
11. 50 = F4 + F7 +9
75 = F3 + F5 + F7 + F10
100 = F1 + F3 + F6 + F11
TERMOS PITAGÓRICOS
a2 + b2 = c2
Em outros termos, terno pitagórico é toda solução inteira e positiva da equação diofantina:
x2 + y2 = z2
(3, 4, 5), (6, 8, 10), (5, 12, 13), (12, 35, 37)
pois,temos:
32 + 42 = 52 , 62 + 82 = 102
52 + 122 = 132 , 122 + 352 = 372
Se (a, b, c) é um terno pitagórico, então (ka, kb, kc), onde k > 1 é um inteiro positivo qualquer, também é
um terno pitagórico, pois, temos:
onde K é um inteiro positivo qualquer, atribuidas a PITAGÓRAS, dão uma infinidade de ternos pitagó-
ricos, pois, temos:
a2 + b2 = (2k + 1)2 + (2k2 + 2k)2 =
= 4k2 + 8k3 + 8k2 + 8k + 1 =
= (2k2 + 2k + 1)2 = c2
Assim, p.ex., para k = 7, temos:
125
126 CAPÍTULO 14. TERMOS PITAGÓRICOS
a == 2pq, b = p 2 − q2 , c = p 2 + q2
onde p e q(p > q) são dois inteiros positivos quaisquer, atribuidas a PLATÃO, também dão uma infinidade
de ternos pitagóricos, pois, temos:
= (p2 + q2 )2 = c2
Assim, p.ex., para p = 5eq = 3, temos:
a = 2.5.3, b = 52 − 32 = 16
c = 52 + 32 = 34
de modo que (30, 16, 34) é um terno pitagórico.
As fórmulas:
1 1
a = (n2 − 1), b = n, c = (n2 + 1)
2 2
fornecem ternos pitagórico mediante a substituição de n por inteiro positivo ímpar maior do que 1.
Assim, p.ex., fazendo n = 7, temos:
1 2 1 2
a= (7 − 1) = 24, b = 7, c= (7 + 1) = 25
2 2
de modo que (24,7,25) é um terno pitagórico. É imediato que a todo terno pitagórico (a, b, c) está
associado um triângulo retângulo cujas medidas respectivas dos catetos e da hipotenusa são a, bec,
denominado triânuglo pitagórico.
Em outros termos, pitagórico primitivo é todo terno pitagórico (a, b, c) em que os inteiros positivos a
e b são primos entre si.
Assim, p. ex., são ternos pitagóricos primitivos:
a2 + b2 = c2 eomdc(a, b) = 1
então, se tem:
mdc(a, c) = mdc(b, c) = mdc(a, b, c) = 1.
porque todo divisor d de dois quais dos três inteiros positivos a, b, c divide também o terceiro.
Se (a, b, c) é um terno pitagórico não primitivo, isto é, tal que o mdc(a, b) = d , 1, então d|c, e os
quocientes:
a b c
a1 = , b1 = , c1 =
d d d
formam o terno pitagórico primitivo (a1 , b1 , c1 ), pois, temos:
a b a2 + b2 c2 c
a21 + b21 = ( )2 + ( )2 = 2
= 2 = ( )2 = c21
d d d d d
14.4. PROPRIEDADES DOS TERNOS PITAGÓRICOS 127
e o mdc(a1 , b1 ) = 1.
Portanto, qualquer terno pitagótico não primitivo se pode obter de um terno pitagórico primitivo
multiplicando-se os seus elementos por um textbfconveniente inteiro positivo maior do que 1, isto é,
todas as soluções de x2 + y2 = z2 resultam daqueles de x21 + y21 = z21 , onde o mdc(x1 , y1 ) = 1.
Assim, p. ex., os ternos pitagóricos não primitivos:
resutam ambos do terno pitagórico primitivo (5, 12, 13) multiplicando-se os elementos deste respectiva-
mente pelos inteiros 3 e 5.
NOTA. Com todos os elementos menores quem 1000 são conhecidos 158 ternos pitagóricos primi-
tivos, e aquele que tem os maiores elementos é (372, 925, 997).
Demonstração: Suponhamos, primeiro, que o inteiro a > 2 é par. Então, 2|ae4|a2 , de modo que
(a2 − 4) (a2 + 4)
b= e c=
4 4
são dois inteiros positivos. E como
a4 − 8a2 + 16 a2 + 4 2
a2 + b2 = a2 + =( ) = c2
16 4
segue-se que (a, b, c) é um terno pitagórico.
Suponhamos, agora, que o inteiro a > 2 é ímpar. Então, a = 2k + 1 e as fórmulas de PITÁGORAS:
Teorema 14.4.2 Um terno (a, b, c) é um terno pitagórico se e somente se existem inteiros u e v que verificam as
seguintes condições:
(i) u > v > 0
(ii) u ≡ v(mod.2)
(iii) uv é um quadrado perfeito
√ (u − v) (u + v)
(iv) a = uv, b = , c=
2 2
Demonstração:
(=⇒) Suponhamos, primeiro, que u e v são dois inteiros que verificam as quatro condições enumeradas
no enunciado do teorema. Então, por (i) e (iv), a, b e c são positivos, por (iii) e (iv), a é um inteiro, e por
(ii) e (iv), b e c também são inteiros (a condição (ii) é um modo abreviado de dizer que os inteiros u e v
são ambos pares ou ambos ímpares). finalmente, pela (iv), temos:
u2 − 2uv + v2 u+v 2
a2 + b2 = uv + =( ) = c2
4 2
e, portanto, (a, b, c) é um terno pitagórico.
(⇐=) Reciprocamente, suponhamos, agora, que (a, b, c) é um terno pitagórico. Cumpre achar inteiros u
e v que verifiquem as quatro condições enumeradas no enunciado do teorema. Seja
u = c + bev = c − b
128 CAPÍTULO 14. TERMOS PITAGÓRICOS
Como b e c são inteiros positivos e c > b, temos u > v > 0, de modo que (i) é satisfeita. Por ser u − v = 2b,
segue-se que 2|(u − v), isto é:
u ≡ v(mod.2)
e a condição (ii) é satisfeita. A condição (iii) é satisfeita, pois, temos:
uv = (c + b)(c − b) = c2 − b2 = a2
Os inteiros:
u = 481 + 319 = 800, v = 481 − 319 = 162
satisfazem as quatro condições enumeradas no enunciado do teorema 18.2:
Se a ≡ b (mod.2), então a e b são ambos pares ou são ambos ímpares. Se a e b são ambos pares, então
2|mdc(a, b), o que é impossível, porque o mdc(a, b) = 1. E se, ao invés, a e b são ambos ímpares, então
c2 = a2 + b2 é par e, portanto, c é par, isto é, se a = 2h + +1 e b = 2k + 1, então c = 2n, e temos:
a2 = 4h2 + 4h + 1 ≡ 1(mod.4)
b2 = 4k2 + 4k + 1 ≡ 1(mod.4)
c2 = 4n2 ≡ 0
o que implica:
a2 + b2 ≡ 2(mod.4)
ou seja:
c2 = a2 + b2 ≡ 2(mod.4)
e, portanto, 2 ≡ 0 (mod.4), o que é absurdo. Assim sendo só pode ser a . b (mod.2), de modo que a e b
são de paridade diferente, e como a2 + b2 = c2 , segue-se que c2 é ímpar, o que implica c também ímpar.
NOTA. De conformidade com este teorema, num terno pitagórico primitivo qualquer (a, b, c), há
exatamente um elemento que é par (a ou b) e dois elementos que são ímpares (a e c ou b e c, de modo
que a soma a + b + c é sempre um inteiro positivo par.
EXERCÍCIOS
4. O termo pitagórico (20, b, c) é dado pelas fórmulas de PLATÃO. Determine fórmulas de PLATÃOb
e fórmulas de PLATÃOc.
5. Construir três termos pitagóricos (a, b, c) tais que os elementos b e c sejam inteiros consecutivos.
10. Mostrar que (3, 4, 5) é o único termo pitagórico primitivo formado por inteiros positivos consecu-
tivos.
11. Demonstrar que um termo pitagórico primitivo (a, b, c) o produto ab é diviśivel por 12 e o produto
abc é divisível por 60.
12. Demonstrar que, se n @ (mod.4), então existe um termo pitagórico primitivo (x, y, z) no qual
x = n ou y = n.
13. Mostrar que (3n, 4n, 5n), onde n = 1, 2, 3, ..., são os únicos termos pitagóricos cujos elementos estão
em progressão aritmética.
14. Demonstrar que, se (a, b, c) é um termo pitagórico primitivo, então a ou b é divísivel por 3.
15. Mostrar que, a é um número inteiro positivo ímpar, então existe um termo pitagórico (a, b, c) tal
que c = b + 1.
17. Seja (a, b, c) um termo pitagórico primitivo no qual b é ímpar. Mostrar que 4|a.
CAPÍTULO 18
3. b = 180 e c = 181
4. b = 21 e c = 29
7. (16, 30, 34), (72, 30, 78), (40, 30, 50), (224, 30, 226)
8. (40, 9, 41), (40, 339, 401)
9. (60, 11, 61), (60, 91, 109), (60, 221, 229), (60, 899, 901)
Capítulo 15
CLASSES RESIDUAIS
am = {x ∈ Z | x ≡ a (mod · m)} =
= {x ∈ Z | m | (x − a)}
ou seja:
am = {x | x = a + km, k ∈ Z}
a1 = {x ∈ Z | 1 | (x − a)} = Z
23 = {2 | x = 2 + 3k, k ∈ Z } =
= { . . . , −7, −4, −1, 2, 5, 8, 11, . . . }
Observa-se que
131
132 CAPÍTULO 15. CLASSES RESIDUAIS
(−4)5 = {x | x = −4 + 5k, k ∈ Z } =
= { . . . , −19, −14, −9, −4, 1, 9, 11, . . . }
Observa-se que
(−4)5 = 15 = 65 = 115 = . . .
Teorema 15.2.3 Se as classes residuias am e bm são distintas (am , bm ), então são disjuntas: am ∩ bm = ∅.
Demontração:
Com efeito, se am e bm não são disjuntos, então existe um inteiro c tal que c ∈ am e c ∈ bm , isto é, tal que
Logo, pelo Teorema 15.2.1: am = bm , o que é impossível, visto que, por hipótese am , bm .
15.3. CONJUNTO DAS CLASSES RESIDUAIS 133
NOTA: A classe residual am diz-se determinada ou definida pelo inteiro a, o qual, por sua vez, chama-se
um representante de am .
Dois inteiros são representantes de uma mesma classe residual módulo m se e somente se são con-
gruentes módulo m.
Zm = {am | a ∈ Z}
(i) As classes residuais módulo m dos inteiros x que satisfazem à condição x ∈ [0, m − 1] são todas
distintas, porque se a e b são dois inteiros tais que a e b ∈ [0, m − 1], então:
|a − b| < m ⇒ a . b (mod · m) ⇒ am , bm
y ∈ [0, m − 1],
temos, pelo algoritmo da divisão:
(iii) Como existem apenas m inteiros x ∈ [0, m − 1], que são: 0, 1, 2, . . . , m − 1, seque-se que o conjunto
Zm encerra m classses residuais módulo m distintas:
Zm = {0m , 1m , 2m , . . . , (m − 1)m }
75 ≡ 3 (mod · m) =⇒ 758 = 38 =
= {x|x = 3 + 8k, k ∈ Z} =
134 CAPÍTULO 15. CLASSES RESIDUAIS
02 = {x | x = 0 + 2k, k ∈ Z} =
= {. . . , −6, −4, −2, 0, 2, 4, 6, . . .}
= (−4)2 = 42 = 82 = . . .
12 = {x | x = 1 + 2k, k ∈ Z} =
= {. . . , −5, −3, −1, 1, 3, 5, . . .} =
= (−3)2 = 52 = 72 = . . .
A classe residual 02 é formada por todos os inteiros pares e a classe residual 12 é formada por todos os inteiros
ímpares. Portanto:
Z2 = {02 , 12 }
Note-se que 02 ∩ 12 = ∅ e 02 ∪ 12 = Z.
Exemplo 15.3.2 Se o módulo m = 5, temos cinco classes residuais módulo 5 distintas:
05 = {x | x = 0 + 5k, k ∈ Z} =
= {. . . , −15, −10, −5, 0, 5, 10, 15, . . .} =
= (−10)5 = 55 = 155 = . . .
15 = {x | x = 1 + 5k, k ∈ Z} =
= {. . . , −14, −9, −4, 1, 6, 11, 16, . . .} =
= (−9)5 = 65 = 215 = . . .
25 = {x | x = 2 + 5k, k ∈ Z} =
= {. . . , −13, −8, −3, 2, 7, 12, 17, . . .} =
= (−3)5 = 25 = 175 = . . .
35 = {x | x = 3 + 5k, k ∈ Z} =
= {. . . , −12, −7, −2, 3, 8, 13, 18, . . .} =
= (−7)5 = 85 = 235 = . . .
45 = {x | x = 4 + 5k, k ∈ Z} =
= {. . . , −11, −6, −1, 4, 9, 14, 19, . . .} =
= (−11)5 = 45 = 195 = . . .
Portanto:
Z5 = {05 , 15 , 25 , 35 , 45 }
Esta representação de Z5 não é a única, pois, temos:
Z5 = {55 , (−4)5 , 75 , (−2)5 , 95 }
Note-se:
05 ∩ 15 ∩ 25 ∩ 35 ∩ 45 = ∅ e 05 ∪ 15 ∪ 25 ∪ 35 ∪ 45 = Z
15.3. CONJUNTO DAS CLASSES RESIDUAIS 135
NOTA. Em cada um desses dois exemplos observa-se que as classes residuais obtidas possuem as três
seguintes propriedades: (1) não são vazias; (2) são disjuntas duas a duas; (3) sua reunião é o conjunto
Z dos inteiros. Exprime-se esse fato dizendo que os conjuntos Z2 e Z5 são partições do conjunto Z dos
inteiros.
Importa ainda notar que um conjunto m representantes de cada uma das classes residuais 0m , 1m , 2m , . . . , (m−
1)m , é um sistema complexo de restos módulo m.
Assim, p.ex., o conjunto:
{−5, 11, −8, 13, −6}
EXERCÍCIOS
1. Achar a classe residual módulo 8 de −5.
4. m = 1, 2, 3, 4, 6, 12
136 CAPÍTULO 15. CLASSES RESIDUAIS
EXERCÍCIOS SUPLEMENTARES
1. Demonstrar que , se a e b são inteiros, com b > 0, então existem e são únicos os inteiros q e r tais
que a = bq + r, onde 2b ≤ r < 3b.
2. Verificar que , se um inteiro n é ao mesmo tempo um quadrado perfeito e um cubo perfeito (como
64 = 82 = 43 ), então n é da forma 7k ou 7k + 1.
3. Demonstrar que , se a e b são inteiros , com b , 0, então existem e são únicos os inteiros q e r tais
−|b| |b|
que a = bq + q , onde <r6 .
2 2
4. Demonstrar que nenhum inteiro da sequência:
é um quadrado perfeito.
8. Demonstrar que a soma dos quadrados de dois inteiros ímpares não pode ser um quadrado
perfeito.
9. Demonstrar que o produto de três inteiros consecutivos é divisível por 6 e que o produto de quatro
inteiros consecutivos é divisível por 24.
10. Demonstrar que 360 | a2 (a2 − 1)(a2 − 4), qualquer que seja o inteiro a.
11. Demonstrar que o produto de cinco inteiros consecutivos é divisível por 120.
13. Sejam p e p + 2 primos gêmeos. Demonstrar que p(p + 2) + 1 é um quadrado perfeito e que p(p + 2)
com p > 3, é divisível por 12.
16. Verificar que o conjunto {0, 1, 2, 22 , 23 , . . . , 29 } é um sistema completo de restos módulo 11, mas que
o conjunto {0, 1, 22 , 32 , . . . , 102 } não o é.
137
138 CAPÍTULO 15. CLASSES RESIDUAIS
s(n + 2) = s(n) + 2
34. Demonstrar que s(n) é um inteiro ímpar se e somente se n é um quadrado perfeito ou o dobro de
um quadrado perfeito.
15.3. CONJUNTO DAS CLASSES RESIDUAIS 139
√
35. Demonstrar que, se n > 1 é um inteiro composto, então s(n) > n + n.
36. Sejam m e n inteiros positivos. Demonstrar:
(a)Φ(m)φ(n) = φ(mn)φ(d)/d, onde d = mdc(m, n)
(b)φ(m)φ(n) = φ(mdc(m, n))φ(mmc(m, n))
37. Mostrar que a equação φ(n) = 14 não tem solução.
38. Usando o teorema de EULER, demonstrar:
(a) a37 ≡ a(mod · 1729 ≡ 7 · 13 · 19), qualquer que seja o inteiro a.
(b) a13 ≡ a(mod · 2730 = 2 · 3 · 5 · 7 · 13), qualquer que seja o inteiro a.
(c) a33 ≡ a(mod · 4080 = 15 · 16 · 17), qualquer que seja o inteiro ímpar a.
39. Sejam m e n inteiros positivos primos entre si. Demonstrar:
2n2 +1 = m2 ,
então (mn)2 é um número triangular. Dar três exemplos de quadrados perfeitos que também são
números triangulares.
54. Achar um divisor primo do inteiro n = 4(3 · 7 · 11) − 1 da forma 4k + 3.
55. Achar a forma de todos os inteiros positivos n tais que d(n) = 10 e o menor inteiro positivo que
verifica esta igualdade.
56. Resolver as seguintes equações:
(a) φ(n) = 16
(b) φ(n) = 24
(c) φ(n) = 30
140 CAPÍTULO 15. CLASSES RESIDUAIS
57. Demonstrar que a equação φ(n) = 2p não tem solução quando p é um primo e 2p + 1 é composto.
58. Chama-se sistema reduzido de restos módulo m todo conjunto de φ(m) inteiros, incongruentes
módulo m, cada um dos quais é primo com m. Verificar:
(a) o conjunto de inteiros {−31, −16, −8, 13, 25, 80} é um sistema reduzido de restos módulo 9;
(b) o conjunto de inteiros {3, 32 , 33 , 34 , 35 , 36 } é um sistema reduzido de restos módulo 14;
(c) o conjunto de inteiros {2, 22 , 23 , . . . , 218 } é um sistema reduzido de restos módulo 27.
59. Determinar quais dos seguintes conjuntos são sistemas reduzidos de restos módulo 5:
(a) {0, 1, 2, 3, 4}
(b) {1, −2, 3, −4}
(c) {16, 9, −2, 7}
(d) {6, 11, 16, 21}
64. Um inteiro composto n tal que n | (2n − 2) chama-se pseudo-primo. Verificar que 341, 561, 645 e
1105 são pseudos-primos.
66. Mostrar que φ(n) = n/3 se e somente se n = 2k 3 j , onde k e j são inteiros positivos.
n/d
φ(d) para os seguintes valores de n:
P
67. Calcular d|n (−1)
(a) n = 12, 13, 14, 15, 16.
(b) n = p, sendo p um primo ímpar.
(c) n = 2k , sendo k > 1.
(d) n = pk , sendo k > 1 e p um primo ímpar
69. Demonstrar que, se 210m + n é primo, onde 0 6 n < 121, então n é primo.
70. Mostrar que todo divisor próprio de um número perfeito par é um número deficiente.
71. Mostrar que, se n = (6m + 1)(12m + 1)(18m + 1), então n − 1 é divisível por 36m.
72. Demonstrar que a soma 2p + 2 de primos gêmeos p e p + 2, onde p > 3, é divisível por 12.
73. Seja p um primo ímpar. Determinar o número de elementos em cada uma das sequências:
74. Mostrar que a média harmônica dos divisores de um número perfeito par é um inteiro.
75. Mostrar que 2n2 − 3 nunca é um quadrado perfeito, onde n = 2, 3, 4, . . . .
76. Demonstrar por indução matemática que
3n+2 | 103n − 1, n = 0, 1, 2, . . .
77. Seja n um número perfeito par. Demonstrar que πd|n d é uma potência de n.
78. Mostrar que a sequência 5, 12, 19, 26, . . . não contém termo algum da forma 2n ou 2n − 1.
79. Mostrar que o inteiro 111 . . . 111 com n algarismos 1 é composto se n é composto.
80. Mostrar que, se n é a soma de dois números triangulares, então 4n + 1 é uma soma de dois
quadrados.
81. Mostrar que a5 ≡ a(mod · 10), qualquer que seja o inteiro a.
82. Demonstrar que todo inteiro compreendido entre dois primos gêmeos, exceto, 3, 5 e 5, 7, é abun-
dante.
83. Sejam m e n números amigos. Demonstrar:
X X
( 1/d)−1 + ( 1/d)−1 = 1
d| m d| n
84. Um inteiro diz-se sem quadrados se não é divisível pelo quadrado de qualquer inteiro maior que
1. Demonstrar:
cada um dos quais é formado por um número par de algarismos 1, são todos compostos.
88. Calcular a soma: 1 + 11 + 111 + . . . + 111 . . . 1, onde a última parcela é formada de n algarismos 1.
89. Demonstrar que o produto P = (n+1)(n+2) . . . 2n de n inteiros consecutivos é divisível pelo produto
P1 = 1 · 3 · 5 . . . (2n − 1) dos n primeiros inteiros ímpares e achar o quociente.
90. Um inteiro positivo dividido por 5 dá resto 3 e dividido por 9 dá resto 4. Determinar o resto da
divisão desse inteiro por 45 = 5 x 9
91. Calcular o resto da divisão por 8 de 436543 x 793767 .
92. Mostrar que são falsas as preposições (a) e (b), dando um contra-exemplo para cada uma delas:
(a) Se a2 |b3 , então a|b.
(b) Se b|(a2 + 1), então b|(a4 + 1)
93. Demonstrar que, se o mdc(a, b) = 1, então o mdc(a+b, ab) = 1.
142 CAPÍTULO 15. CLASSES RESIDUAIS
√3
115. Mostrar que, se p - n para todos os primos p ≤ n, entao n é primo ou é o produto de dois primos.
117. Um inteiro compreendido entre 1 e 1200 deixa os restos 1, 2 e 6 quando dividido por 9, 11 e 13,
respectivamente. Achar esse inteiro.
121. Mostrar que, se n é um inteiro composto, então (n − 1)! ≡ 0 (mod.n), exceto quando n = 4.
L1 , L2 , L3 , . . . , Ln−1 , Ln , . . .
no caso em que
L1 = 1, L2 = 3 e Ln = Ln−1 + Ln−2 (n > 3)
isto é a sequência:
123. Determinar a mais elevada potência de 7 que divide o produto dos 1000 primeiros inteiros positivos.
124. Demosntrar que 60 divide o produto (n2 − 1)n2 (n2 + 1), qualquer seja o inteiro positivo n.
125. O inteiro n = 2x .3 y .5z . Calcular os expoentes x, y e z sabendo que o quociente n/2 tem 252 divisores
e que os quocientes n/3 e n/5 tem, respectivamente 45 divisores a menos que n.
126. Achar o menor inteiro positivo que tem 20 divisores positivos, sendo primos apenas 3, 5, 7.
131. Demonstrar que o inteiro n = 111...12888...896, que tem n algarismos iguais a 1 e n − 1 algarismos
iguais a 8, é um quadrado perfeito.
134. Determinar o inteiro cujo produto de todos os seus divisores é igual a 330 $x 540 .
na qual cada termo resulta de intercalar 48 no centro do anterior. Mostrar que todos os termos
desta sequência são quadrados perfeitos e determinar a raiz quadrada de n-ésimo termo.
136. Determinar a base do sistema de numeração no qual o inteiro 16000 se escreve 1003000.
138. Achar um inteiro de três algarismos que seja quadrado perfeito e divisível por 3 e por 5.
139. Demonstrar que, se os inteiros a e b são ímpares, então a2 + b2 não pode ser um quadrado perfeito.
140. Demonstrar que, se os inteiros a e b são primos com 3, então a2 + b2 não pode ser um quadrado
perfeito.
143. Demonstrar que, se os inteiros a e b são ímpares, então a2 + b2 é par, mas não divisível por 4.
13|(n2 + 1)
15.3. CONJUNTO DAS CLASSES RESIDUAIS 145
152. Mostrar que todo inteiro composto menor que 1000 tem um fator primo menor que 37.