docsity-aritmetica-solucao-de-todas-as-listas

Prévia do material em texto

Aritmética - solução de todas as
listas
Matemática Discreta
Universidade Federal Rural de Pernambuco (UFRPE)
197 pag.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
SUMÁRIO
MA-14 - Aula 01 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Divisibilidade: Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Divisão Euclidiana: Problemas . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Unidades 1 e 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
MA-14 - Aula 02 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.1 Sistemas de Numeração: Problemas . . . . . . . . . . . . . . . . . . . . . . 23
4.2 Jogo de Nim: Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
MA-14 - Aula 03 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 Máximo Divisor Comum: Problemas . . . . . . . . . . . . . . . . . . . . . 29
6.2 Propriedades do mdc: Problemas . . . . . . . . . . . . . . . . . . . . . . . 35
MA-14 - Aula 04 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
7.2 Mínimo Múltiplo Comum: Problemas . . . . . . . . . . . . . . . . . . . . . 45
8.2 Equações Diofantinas Lineares: Problemas . . . . . . . . . . . . . . . . . . 51
8.3 Exercícios Suplementares . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
MA-14 - Aula Revisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
9.2 Revisão . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
MA-14 - Aula 05 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
10.2 Expressões Binômias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
11.1 Números de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78
MA-14 - Aula 06 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
12.2 Teorema Fundamental Da Aritmética . . . . . . . . . . . . . . . . . . . . . 81
12.3 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
13.1 Pequeno Teorema de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . 90
13.2 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
13.3 Exercícios suplementares . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
13.4 O Renascimento da Aritmética . . . . . . . . . . . . . . . . . . . . . . . . 96
MA-14 - Aula 07 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
15.2 Primos de Fermat e de Mersenne . . . . . . . . . . . . . . . . . . . . . . . 99
MA-14 - Aula 08 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
Primos de Fermat e de Mersenne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
i
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
ii
17.1 Primos de Fermat . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
17.2 Primos de Mersenne . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109
17.3 Teorema da Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
17.4 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110
Números Perfeitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
18.1 Números Perfeitos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114
18.2 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
MA-14 - Aula 08 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
Fatoração do Fatorial em Primos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
17.1 O Teorema de Legendre . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
17.2 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
17.3 Exercícios suplementares . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
Congruências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
18.1 Congruências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
18.1.1 O Pequeno Teorema de Fermat . . . . . . . . . . . . . . . . . . . . 126
18.2 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
18.3 Exercícios suplementares . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133
MA-14 - Aula 09 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
Aplicações de Congruências . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
19.1 Aplicações de Congruências . . . . . . . . . . . . . . . . . . . . . . . . . . 141
19.1.1 Regra dos nove fora . . . . . . . . . . . . . . . . . . . . . . . . . . . 142
19.1.2 Representação decimal de número perfeito par . . . . . . . . . . . . 144
19.2 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
Os Teoremas de Euler e Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
20.1 A Função ϕ Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
20.1.1 O Cálculo de ϕ(m) . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
20.1.2 Teorema de Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151
20.1.3 Teorema de Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
20.2 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152
20.3 Teorema de Wilson . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
20.4 Problemas suplementares . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165
MA-14 - Aula 10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
Congruências Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
21.1 Congruências Lineares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123
21.1.1 Redução de Congruências . . . . . . . . . . . . . . . . . . . . . . . 124
21.2 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
21.3 Teorema Chinês dos Restos . . . . . . . . . . . . . . . . . . . . . . . . . . 128
21.3.1 O Problema de Sun-Tsu . . . . . . . . . . . . . . . . . . . . . . . . 128
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
iii
21.4 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
21.5 Exercícios complementares . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Aritmética das Classes Residuais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
22.1 Classes Residuais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
22.1.1 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138
22.1.2 Propriedades da adição . . . . . . . . . . . . . . . . . . . . . . . . . 139
22.1.3 Propriedades da multiplicação . . . . . . . . . . . . . . . . . . . .. 139
22.1.4 Exemplo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
22.2 Problemas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141
22.3 Exercícios complementares . . . . . . . . . . . . . . . . . . . . . . . . . . . 144
MA-14 - Aula 13 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Introdução à Criptografia I . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
23.1 Criptografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147
Introdução à Criptografia II. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
24.1 Criptografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
MA-14 - Aula 01
Semana 05/08 a 11/08
Unidade 1
Divisibilidade
1.2 Divisibilidade: Problemas
Exercício 1.2.1.
Mostre, por indução matemática, que, para todo n ∈ N,
a) 8|32n + 7 b) 9|10n + 3× 4n+2 + 5
c) 9|n4n+1 − (n+ 1)4n + 1 d) 169|33n+3 − 26n− 27
Demonstração.
a) Aplicar indução matemática.
b) Aplicar indução matemática.
Para n = 0 e n = 1 é imediato, a propriedade é verdadeira.
Suponhamos que, para n ≤ h seja verdade que 9|10h + 3 × 4h+2 + 5, logo existe
α ∈ N tal que 10h + 3× 4h+2 + 5 = 9α
Para h+ 1 temos 10h+1 + 3× 4h+3 + 5 = 10h(9 + 1) + 3× 4× 4h+2 + 5 =
= 9× 10h + [10h + 3× 4h+2 + 5] + 3× 3× 4h+2 = 9β
para algum β ∈ N
Portanto, 9|10n + 3× 4n+2 + 5 para todo n ∈ N
1
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
2
c) Aplicando indução sobre n
d) Aplicando indução sobre n
Exercício 1.2.2.
Mostre que, para todo n ∈ N:
a) 9|10n − 1 d) 3|10n − 7n g) 19|32n+1 + 44n+2
b) 8|32n − 1 e) 13|92n − 24n h) 17|102n+1 + 72n+1
c) 53|74n − 24n f) 6|52n+1 + 1 i) 14|34n+2 + 52n+1
Solução.
a) Temos para todo n ∈ N
10n − 1 = (m(9) + 1)n − 1 = m(9) + 110 − 1 = m(9)
b) Temos para todo n ∈ N
c) Temos para todo n ∈ N que
74n = 492n = (m(53)− 4)2n = m(53) + (−4)2n = m(53) + 24n
Logo 74n − 24n = m(53). Portanto, 53|74n − 24n
d) Temos para todo n ∈ N que
10n − 7n = (m(3) + 1)n − (m(3) + 1)n = m(3) + (1)n − (1)n = m(3)
Portanto, 53|74n − 24n.
e)
f)
g)
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
3
h)
1)
x
Exercício 1.2.3.
Sejam a, b ∈ Z.
a) Se a ̸= b, mostre que, para todo n ∈ N, n ≥ 2,
an − bn
a− b
= an−1 + an−2b+ an−3b2 + · · ·+ abn−2 + bn−1
b) Se a+ b ̸= 0, mostre que, para todo n ∈ N∗,
a2n+1 + b2n+1
a+ b
= a2n − a2n−1b+ a2n−2b2 + · · · − ab2n−1 + b2n
c) Mostre que, para todo n ∈ N,
a2n − b2n
a+ b
= a2n−1 − a2n−2b+ a2n−3b2 + · · ·+ ab2n−2 − b2n−1
Demonstração. a)
Por indução sobre n ≥ 2 quando b ̸= a
Se n = 2 temos a2 − b2 = (a− b)(a+ b) ⇒
a2 − b2
a− b
= a+ b é verdadeira
Suponhamos para h ∈ N seja verdade que
ah − bh
a− b
= ah−1 + ah−2b+ ah−3b2 + · · ·+ abh−2 + bh−1
Para h+ 1 e aplicando a hipótese auxiliar
ah+1 − bh+1 = a(ah − bh) + bh(a− b) =
ah+1 − bh+1 = a[(a− b)(ah−1 + ah−2b+ ah−3b2 + · · ·+ abh−2 + bh−1)] + bh(a− b) =
ah+1 − bh+1 = (a− b)[a(ah−1 + ah−2b+ ah−3b2 + · · ·+ abh−2 + bh−1) + bh] =
ah+1 − bh+1
a− b
= ah + ah−1 + ah−2b+ ah−3b2 + · · ·+ abh−2 + bh−1 + bh
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
4
Portanto, a igualdade é verdadeira para todo n ∈ N, n ≥ 2
Demonstração. b)
Exercício 1.2.4.
Para quais valores de a ∈ N:
a) (a− 2)|a3 + 4 ? b) (a+ 3)|a3 − 3 ?
c) (a+ 2)|a4 + 2 ? d) (a+ 2)|a4 + 2a3 + a2 + 1 ?
Demonstração.
a) Suponhamos que (a− 2)|a3 + 4 então existe β ∈ N tal que a3 + 4 = β(a− 2) isto é
a3 − 8 + 12 = β(a− 2), assim
(a− 2)[β − (a2 + 2a+ 4)] = 12 ⇒ β − (a2 + 2a+ 4) =
12
a− 2
Como, β − (a2 + 2a+ 4) ∈ N, temos a = 8, 6, 5, 4, 3
Portanto, a ∈ N que satisfaz (a+2)|a4+2a3+a2+1 são os números a = 8, 6, 5, 4, 3.
b)
c)
d) Suponhamos que (a+2)|a4+2a3+a2+1 então existe β ∈ N tal que a4+2a3+a2+1 =
β(a+ 2) isto é a3(a+ 2) + (a2 − 4) + 5 = β(a+ 2), assim
(a+ 2)[β − (a3 + a− 2)] = 5 ⇒ β − (a3 + a− 2) =
5
a+ 2
Como, β − (a3 + a− 2) ∈ N, temos a = 3, −1, −3, −7
Portanto, o único a ∈ N que satisfaz (a+ 2)|a4 + 2a3 + a2 + 1 é a = 3.
Exercício 1.2.5.
Mostre que, para todos a,m, n ∈ N, m > n > 0 ⇒ (a2
n
+ 1)|(a2
m
− 1)
Demonstração.
Se m > n, então existe p ∈ N tal que m = n+ p, assim a2
m
= a2
n+p
observe que 2n+p
é par
a2
m
− 1 = a2
n+p
− 12
n+p
= (a2
n+p−1
+ 12
n+p−1
)(a2
n+p−1
− 12
n+p−1
)
a2
m
− 1 = β1 × (a2
n+p−1
− 12
n+p−1
) = β1 × (a2
n+p−2
+ 12
n+p−2
)(a2
n+p−2
− 12
n+p−2
)
a2
m
− 1 = β2 × (a2
n+p−2
− 12
n+p−2
) = β2 × (a2
n+p−3
+ 12
n+p−3
)(a2
n+p−3
− 12
n+p−3
)
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
5
...
...
...
a2
m
− 1 = βp−2 × (a2
n+2
− 12
n+2
) = βp−2 × (a2
n+1
+ 12
n+1
)(a2
n+1
− 12
n+1
)
a2
m
− 1 = βp−1 × (a2
n+1
− 12
n+1
) = βp−1 × (a2
n
+ 12
n
)(a2
n
− 12
n
)
Logo, a2
m
− 1 = βp−1 × (a2
n+1
− 12
n+1
) = K × (a2
n
+ 1) para algum K ∈ N.
Portanto, para todos a,m, n ∈ N, m > n ⇒ (a2
n
+ 1)|(a2
m
− 1.
Exercício 1.2.6.
Mostre, para todo n ∈ N, que n2|(n+ 1)n − 1.
Demonstração.
Para todo n ∈ N sabemos pelo binômio de Newton que
(n+ 1)n =
n∑
k=0
Cn−k
n nn−k × 1k = nn + n× nn−1 +
n−1∑
k=2
Cn−k
n nn−k × 1k + 1
= n2[nn−2 + nn−2 + n2
n−1∑
k=2
Cn−k
n nn−k−2] + 1 = m(n2) + 1
Portanto, para todo n ∈ N, temos que n2|(n+ 1)n − 1.
Exercício 1.2.7.
Mostre, para todo a ∈ N, que:
a) 2|a2 − a b) 3|a3 − a c) 5|a5 − a d) 7|a7 − a
Demonstração.
a) Seja N = a2 − a = a(a− 1), Se a ∈ N é par, logo a = 2k, então N = (2k)(2k − 1) =
2(2k2 − k), assim, 2|a2 − a.
Se a = 2α + 1, então N = (2α + 1)[(2α + 1)− 1] = 2α(2α + 1), logo 2|a2 − a.
Assim, o produto de dois números inteiros consecutivos é múltiplo de 2.
b) Se a|3 o resultado é imediato. Suponhamos que a ∤ 3 e seja o conjunto M = {a, 2a}
então cada um dos elementos de M , diferença con elementos do conjunto P = {1, 2}
em alguma ordem, são divisíveis por 3.
Suponhamos a = 1 +m(3) e 2a = 2 +m(3) então multiplicando estas igualdades
temos 2!a2 = 2! +m(3).
Logo, como 2! não é múltiplo de 3 segue
2!a2 − 2! = m(3) ⇒ a(a2 − 1) = a×m(3) ⇒ a3 − a = m(3)
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
6
Portanto, 3|a3 − a
Assim, o produto de três números inteiros consecutivos é múltiplo de 3.
c) Se a|5 o resultado é imediato. Suponhamos que a ∤ 5 e seja o conjunto M =
{a, 2a, 3a 4a} então cada um dos elementos de M , diferença con elementos do
conjunto P = {1, 2, 3, 4} em alguma ordem, são divisíveis por 5.
Suponhamos a − 1 = m(5) ⇒ a =1 + m(5), 2a − 2 = m(5) ⇒ 2a =
2+m(5), 3a−3 = m(5) ⇒ 3a = 3+m(5), 4a−4 = m(5) ⇒ 4a = 4+m(5)
de onde 4!a4 = 4! +m(5). Logo, como 4! não é múltiplo de 5 segue
4!a4 − 4! = m(5) ⇒ a(a4 − 1) = a×m(5) ⇒ a5 − a = m(5)
Portanto, 5|a5 − a
d) Suponhamos que a ∤ 7 e seja o conjunto M = {a, 2a, 3a 4a, 5a, 6a} então cada um
dos elementos de M , diferença con elementos do conjunto P = {1, 2, 3, 4, 5, 6} em
alguma ordem, são divisíveis por 7. Logo
6!a6 − 6! = m(7) ⇒ a7 − a = m(7)
Portanto, 7|a7 − a
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&utm_medium=document&utm_campaign=watermark
7
Unidade 2
Divisão Euclidiana
1.2 Divisão Euclidiana: Problemas
Exercício 1.2.1.
Ache .
Solução.
Exercício 1.2.2.
Quais são os números que, quando divididos por 5, deixam resto igual a) à metade do
quociente? b) ao quociente? c) ao dobro do quociente? d) ao triplo do quociente?
Demonstração.
a) Seja D o número procurado, das condições do problema temos
D = 5q +
q
2
⇒ 2D = 11q ⇒ D = 11β, q = 2β β ∈ N
Os números são: 11, 22, 33, 44
b) Em geral temos D = 5q + r, 0 ≤ r < q
Supor r = q está errado pela definição do algoritmo da divisão. Quando r = 0
temos 0 = 5× 0 + 0.
Portanto, o zero é o único número.
c)
Exercício 1.2.3.
Seja n um número natural. Mostre que um, e apenas um, número de cada terna abaixo
é divisível por 3. a) n, n + 1, n + 2 b) n, n + 2, n + 4 c) n, n + 10, n + 23 d)
n, n+ 1, 2n+ 1.
Demonstração.
O conjunto de todos números naturais podemos representar mediante o conjunto
A = { 3k, 3k + 1, 3k + 2, k ∈ N }. Se n = 3k então para todos os 4 exercícios
um, e apenas um, número de cada terna é divisível por 3
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
8
a) Se n = 3k + 1 então a terna dada podemos escrever na forma 3k + 1, 3k + 2, 3k + 3
logo um, e apenas um, número da terna é divisível por 3.
Se n = 3k+2 então a terna dada podemos escrever na forma 3k+2, 3k+3, 3k+4
logo um, e apenas um, número da terna é divisível por 3.
Com qualquer das três hipóteses na terna um, e apenas um, número da é divisível
por 3.
b) Se n = 3k + 1 então a terna dada podemos escrever na forma 3k + 1, 3k + 3, 3k + 5
logo um, e apenas um, número da terna é divisível por 3.
Se n = 3k+2 então a terna dada podemos escrever na forma 3k+2, 3k+4, 3k+7
logo um, e apenas um, número da terna é divisível por 3.
Com qualquer das três hipóteses na terna um, e apenas um, número da é divisível
por 3.
c) Se n = 3k+1 então a terna dada podemos escrever na forma 3k+1, 3k+11, 3k+24
logo um, e apenas um, número da terna é divisível por 3.
Se n = 3k+2 então a terna dada podemos escrever na forma 3k+2, 3k+12, 3k+25
logo um, e apenas um, número da terna é divisível por 3.
Com qualquer das três hipóteses na terna um, e apenas um, número da é divisível
por 3.
d) Se n = 3k + 1 então a terna dada podemos escrever na forma 3k + 1, 3k + 2, 6k + 3
logo um, e apenas um, número da terna é divisível por 3.
Se n = 3k+2 então a terna dada podemos escrever na forma 3k+2, 3k+3, 6k+5
logo um, e apenas um, número da terna é divisível por 3.
Com qualquer das três hipóteses na terna um, e apenas um, número da é divisível
por 3.
Exercício 1.2.4.
a) Mostre que, se um número a não é divisível por 3, então a2 deixa resto 1 na divisão
por 3. b) A partir desse fato, prove que, se a e b são inteiros tais que 3 divide a2 + b2,
então a e b são divisíveis por 3.
Demonstração. a)
Se o número não é divisível por três então é da forma a = 3k+1 ou a = 3k+2, k ∈ Z,
logo
a2 = 3k(3k + 2) + 1 ou a2 = 3k(3k + 4) + 4 = 3[3k(3k + 4) + 1] + 1
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
9
Exercício 1.2.5.
O resto da divisão do inteiro N por 20 é 8. Qual é o resto da divisão de N por 5?
Solução.
Temos N = 20q + 8, isto é N = 5(4q) + 5 + 3 = 5(4q + 1) + 3.
O resto, é 3.
Exercício 1.2.6.
Ache o menor múltiplo de 5 que deixa resto 2 quando dividido por 3 e por 4.
Demonstração.
Seja x o número pedido, então x = 3a + 2 ou x = 4b + 2 para algum a, b ∈ N∗, logo
3a+ 2 = 4b+ 2 de onde 3a = 4b assim, a = 4 + 4t e b = 3 + 3t para todo t ∈ N∗
t 0 1 2 3 4 5 6 7 8 9
a 4 8 12 16 20 24 28 32 36 40
b 3 6 9 12 15 18 21 24 27 30
x 14 26 38 50 62 74 86 98 110 122
Logo, o menor número é 50.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
10
Problemas Suplementares
2.3 Unidades 1 e 2
Exercício 2.3.1.
Sejam a, b, c ∈ Z e c ̸= 0. Mostre que: ac|bc ⇔ a|b.
Demonstração.
(⇒) Condição necessária.
Seja ac|bc então existe m ∈ N tal que bc = m · ac, logo bc − m · ac = 0 assim,
c(b−ma) = 0.
Se c = 0 nada a concluir. Suponhamos que b−ma = 0 então b = ma e portanto a|b.
(⇐) Condição suficiente.
Suponhamos que a|b então existe β ∈ Z tal que b = βa. Para c ∈ Z temos que bc = βca
de onde ac|bc.
Portanto, ac|bc ⇔ a|b.
Exercício 2.3.2.
(ENC-98)1 A soma de todos os múltiplos de 6 que se escrevem (no sistema decimal)
com dois algarismos é:
(a) 612 (b) 648 (c) 756 (d) 810 (e) 864
Solução.
Os múltiplos de 6 com dois algarismos são: 12, 18, . . . , 96. A soma pedida é
12 + 18 + . . .+ 96 = 6(1 + 2 + 3 + 4 + . . .+ 16− 1) =
= 6
[
16× 17
2
− 1
]
= 810
Resposta d) 810.
Exercício 2.3.3.
Com quanto zeros termina o número 100!?
Solução.: (Primeira)
Da definição de fatorial temos:
100! = 1× 2× 3× 4× . . .× 98× 99× 100
100! = 250[1× 3× 5× 7× . . . 97× 99][1× 2× 3× 4× . . .× 50]
1Exame Nacional de Cursos, MEC/INEP.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
11
100! = 250[1×3×5×7× . . . 97×99][225(1×2×3×4× . . .×25)(1×3×5×7× . . .×47×49)]
100! = 275[5× 15× 25× 35× . . .× 85× 95× α1][(25!)(5× 15× 25× 35× 45× β1]
100! = 275[510(1× 3× 5× 7× . . . 17× 19)α2][(25!)][5
5(1× 3× 5× 7× 9)β2]
100! = 275 · 515[(1× 3× 5× 7× . . . 17× 19)α2][(25!)][(1× 3× 5× 7× 9)β2]
100! = 275 · 515[(5× 15α3][(25!)][(5× β3] = 275 · 518γ1 × 25! (2.1)
Por outro lado:
25! = 1×2×3×4× . . .×24×25 = [1×3×5×7× . . . 23×25][212(1×2×3×4× . . .×12)]
25! = 212[5× 15× 25× α3][(2× 4× 5× 6× 8× 10× 12)β3]
25! = 212[54 × α4][(2
10 × 52)β4] = 222 × 56 × γ2
En (2.1)
100! = 275 · 515[(5× 15α3][(25!)][(5× β3] = 275 · 518γ1 × (222 × 56 × γ2)]
Portanto 100! = 297 × 524 × γ, termina em 24 zeros.
Recomendo o site http : //2000clicks.com/MathHelp/BasicFactorialTable.aspx
Solução.: (Segunda)
Seja N = (1)(2) · · · (9)(10)(11) · · · (20) · · · (80) · · · (90)(91) · · · (99)(100) = 100!
Como 10 = 2× 5 e temos muito mais potências de 2, nossa preocupação será obter ao
máximo as potências de 5 então
N = (1) · · · (5) · · · (10) · · · (15) · · · (20) · · · (80) · · · (85) · · · (90) · · · (95) · · · (100) = 100!
N = · · · (5) · · · [2(5)] · · · [3(5)] · · · [4(5)] · · · [16(5)] · · · [17(5)] · · · (90) · · · (95) · · · [20(5)] = 100!
N = 520[(1) · · · (5) · · · (10) · · · (15) · (16) · (17) · · · (19) · · · (20)]α = 100!, α ∈ N
N = 520[(1) ·· · (5) · · · [2(5)] · · · [3(5)] · (16) · (17) · · · (19) · · · [4(5)]]α = 100!, α ∈ N
N = 524[(1) · · · (1) · · · [2] · · · [3] · (16) · (17) · · · (19) · · · [4]α = 100!, α ∈ N
N = 5242242kβ = 100!, β, k ∈ N
Portanto 100! = 5242242kβ, termina em 24 zeros.
Exercício 2.3.4.
a) Mostre que o produto de i números naturais consecutivos é divisível por i!.
b) Mostre que 6|n(n+ 1)(2n+ 1), para todo n ∈ N.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
12
Demonstração.
a) Seja n ∈ N tal que n > i e os números consecutivos n, n− 1, n− 2, · · · , n− (i− 1)
na forma decrescente. Seu produto é dado por
N = n(n− 1)(n− 2) · · · (n− i+ 1) (2.2)
Sabemos que
C i
n =
n!
i!(n− i)!
=
n(n− 1)(n− 2) · · · (n− i+ 1)
i!
=
N
i!
= α ∈ N
logo em (2.2) segue N = α× i!
Portanto, o produto de i números naturais consecutivos é divisível por i!
b) Primeira solução: Seja N = n(n+ 1)(2n+ 1) então temos
N = n(n+ 1)[(n− 1) + (n+ 2)] = (n− 1)n(n+ 1) + n(n+ 1)(n+ 2)
Temos três números n−1, n, n+1 consecutivos, logo (n−1)n(n+1) = 6α, α ∈ N.
Também os três números n, n + 1, n + 2 são consecutivos, logo n(n + 1)(n + 2) =
6β, β ∈ N. Isto implica que N = 6(α + β), α, β ∈ N.
Portanto, 6|n(n+ 1)(2n+ 1), para todo n ∈ N.
b) Segunda solução: Aplicando indução sobre n
Se n = 1, temos (1)(2)(3) = 6 é imediato que 6|n(n+ 1)(2n+ 1).
Suponhamos que para algum h ∈ N onde h ≤ n cumpra que 6|h(h+1)(2h+1), isto
é existe α ∈ N tal que h(h+ 1)(2h+ 1) = 6α.
Para h+ 1 temos
(h+ 1)[(h+ 1) + 1][2(h+ 1) + 1] = (h+ 1)(h+ 2)[(2h+ 1) + 2] ⇔
h(h+1)(2h+3)+2(h+1)(2h+3) = h(h+1)(2h+1)+2h(h+1)+2(h+1)(2h+3)
aplicando a hipótese auxiliar
= 6α + 2(h+ 1)[h+ (2h+ 3)] = 6α + 6(h+ 1)2 = 6β
onde β ∈ N.
Portanto, 6|n(n+ 1)(2n+ 1), para todo n ∈ N.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
13
Exercício 2.3.5.
Mostre que 13|270 + 370.
Demonstração.
Temos: 24 = 13 + 3, 25 = m(13) + 6, 26 = m(13) + 4 = m(13)− 1. Logo,
270 = 24 × (26)11 = 24[m(13)− 1]11 = m(13)− 24 = m(13)− 3
Por outro lado, 32 = 13− 4, 33 = m(13) + 1. então
370 = 3 · (33)23 = 3 · (m(13) + 1)23 = 3(m(13) + 123) = m(13) + 3
Assim, 270 + 370 = [m(13)− 3] +m(13) + 3 = m(13).
Portanto, 13|270 + 370.
Exercício 2.3.6.
Mostre que existem infinitos valores de n em N para os quais 8n2 + 5 é divisível por 7
e por 11.
Demonstração.
Se o número 8n2 + 5 é divisível por 7 e por 11, logo ele é divisível por 77 (7 e 11 são
coprimos). Suponhamos que 8n2 + 5 é divisível por 77, logo existe β ∈ N tal que
8n2 + 5 = 77β ⇒ 8n2 + 5− 77 = 77(β − 1) ⇒ 8(n2 − 9) = 77(β − 1)
Como 8 ∤ 77, segue que 8|(β − 1) e 77|(n2 − 9).
Assim, para todo α ∈ N temos β − 1 = 8α e n2 − 9 = 77α, α ∈ N, logo
β = 1 + 8α.
Portanto, 8n2 + 5 = 77(1 + 8α) para todo α ∈ N, assim existem infinitos valores de
n em N para os quais 8n2 + 5 é divisível por 7 e por 11
Exercício 2.3.7.
Ache o quociente e o resto da divisão a) de 27 por 5. b) de 38 por 7.
Solução.
a) 27 = 5(5) + 2 quociente q = 5 e o resto r = 2.
b) 38 = 5(7) + 3 quociente q = 5 e o resto r = 3.
Exercício 2.3.8.
Mostre como, usando uma calculadora que só realiza as quatro operações, pode-se
efetuar a divisão euclidiana de dois números naturais em apenas três passos. Aplique o
seu método para calcular o quociente e o resto da divisão de 3721056 por 18735.
Demonstração.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
14
Exercício 2.3.9.
Discuta a paridade a) da soma de dois números. b) da diferença de dois números.
c) do produto de dois números. d) da potência de um número. e) da soma de n números
ímpares.
Solução.
a) A soma de dois números pares ou ímpares sempre é par. A soma de um número par
com outro ímpar sempre é ímpar.
b) A diferença de dois números pares ou ímpares sempre é par. A diferença de um número
par com outro ímpar sempre é ímpar.
c) O produto de dois números sendo um deles par, sempre é par. O produto de dois
números ímpares sempre é ímpar.
d) A potência de um número par é par. A potência de um número ímpar sempre é ímpar.
e) A soma de n números ímpares será par se n é par, e será ímpar se n é ímpar.
Exercício 2.3.10.
a) Mostre que um número natural a é par se, e somente se, an é par, qualquer que
seja n ∈ N∗. b) Mostre que an ± am é sempre par, quaisquer que sejam n,m ∈ N∗. c)
Mostre que, se a e b são ímpares, então a2 + b2 é divisível por 2 mas não divisível por 4.
Demonstração.
a) Suponhamos a seja par, então a = 2k, k ∈ Z logo an = (2k)n = 2(2n−1kn) é par.
Inversamente
A mostrar que, se an é par, então a é par.
Por contradição
Suponhamos a não seja par, logo a = 2k + 1, k ∈ Z de onde
an = (2k + 1)n =
n∑
j=0
Cj
n(2k)
n−j1j =
n−1∑
j=0
Cj
n(2k)
n−j + 1 = 2α + 1, α ∈ Z
logo an é ímpar.
Isto mostra que sean é par, então a é par.
Portanto, um número natural a é par se, e somente se, an é par, qualquer que seja
n ∈ N∗
b)
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
15
c)
Exercício 2.3.11.
Mostre que a) se n é ímpar, então n2− 1 é divisível por 8. b) se n não é divisível por
2, nem por 3, então n2 − 1 é divisível por 24. c) ∀ n ∈ N, 4 ∤ n2 + 2.
Demonstração.
a) Se n é ímpar, então é da forma 2k+1, k ∈ N. Logo, como o produto de dois números
naturais consecutivos sempre é par, temos
n2 − 1 = (2k + 1)2 − 1 = 4k2 + 4k = 4k(k + 1) = 8β, β ∈ N
Portanto, n2 − 1 é divisível por 8
b)
c) Todo natural n ∈ N podemos escrever em alguma das formas dos elementos do conjunto
{ 5k, 5k + 1, 5k + 2, 5k + 3, 5k + 4 } onde k ∈ N. Logo
• Se n = 5k, então n2 = (5k)2 = m(5)
• Se n = 5k + 1, então n2 = (5k + 1)2 = m(5) + 1
• Se n = 5k + 2, então n2 = (5k + 2)2 = m(5) + 4
• Se n = 5k + 3, então n2 = (5k + 3)2 = m(5) + 32 = m(5) + 4
• Se n = 5k + 4, então n2 = (5k + 4)2 = m(5) + 42 = m(5) + 1
Assim o quadrado de qualquer número natural é da forma 5k ou 5k + 1 ou 5k + 4
De onde n2+4 = 5h+4 ou n2+4 = (5k+1)+4 = 5(k+1) ou n2+4 = (5k+4)+4 =
5(k + 1) + 3
Portanto, ∀ n ∈ N, 4 ∤ n2 + 2
Exercício 2.3.12.
Sejam dados os números naturais a, m e n tais que 1 < a < m < n. a) Quantos
múltiplos de a existem entre m e n? b) Quantos múltiplos de 7 existem entre 123 e
2551? c) Quantos múltiplos de 7 existem entre 343 e 2551?
Demonstração.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
16
Exercício 2.3.13.
(ENC-2000) Mostre que, se um inteiro é, ao mesmo tempo, um cubo e um quadrado,
então ele é da forma 5n, 5n+ 1, ou 5n+ 4.
Demonstração.
Seja n ∈ N, consideremos os números n2 e n3, pelos dados do problema temos N =
(n2)3 = (n3)2 = n6, isto é o número procurado é potência sexta de n.
Pela parte c) do exercício (1.2.7) sabemos que 5|n5−n ⇒ n5−n = m(5), de onde
n(n5 − n) = m(5) ⇒ n6 = n2 +m(5)
Mostramos na parte c) do exercicio (12.3.7) que o quadrado de qualquer número
natural é da forma 5k ou 5k + 1 ou 5k + 4.
Assimtemos que n6 = n2 +m(5), logo N = n6 = 5k +m(5) = m(5) ou
N = n6 = 5k + 1 +m(5) = m(5) + 1, ou N = n6 = (5k + 4) +m(5) = m(5) + 4
Portanto, se um inteiro é, ao mesmo tempo, um cubo e um quadrado, então ele é da
forma 5n, 5n+ 1, ou 5n+ 4.
Exercício 2.3.14.
(ENC-2001) Seja N um número natural; prove que a divisão de N2 por 6 nunca deixa
resto 2.
Demonstração.
O conjunto dos números naturais podemos identificar com elementos do conjunto
A = { 6m, 6m+ 1, 6m+ 2, 6m+ 3, 6m+ 4, 6m+ 5, m ∈ N } ≡ N
logo qualquer número natural tem uma dessas formasm assim,
• Se N = 6m ⇒ N3 = 6(6m2) + 0 o resto r = 0.
• Se N = 6m+ 1 ⇒ N2 = 6(6m2 + 2m) + 1 o resto r = 1.
• Se N = 6m+ 2 ⇒ N2 = 6(6m2 + 4m) + 4 o resto r = 4.
• Se N = 6m+ 3 ⇒ N2 = 6(6m2 + 6m+ 1) + 3 o resto r = 3.
• Se N = 6m+ 4 ⇒ N2 = 6(6m2 + 8m+ 2) + 4 o resto r = 4.
• Se N = 6m+ 5 ⇒ N2 = 6(6m2 + 10m+ 4) + 1 o resto r = 1.
Portanto, a divisão de N2 por 6 nunca deixa resto 2.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
17
Exercício 2.3.15.
Mostre que, se n é ímpar, então a soma de n termos consecutivos de uma PA é sempre
divisível por n.
Solução.
Exercício 2.3.16.
Mostre, para todo n ∈ N, que
a) 6|n3 + 11n b) 9|4n + 15n− 1 c) 3n+2|103n − 1
d) 7|23n − 1 e) 8|32n + 7 f) 7|32n+1 + 2n+2
g) a2 − a+ 1|a2n+1 + (a− 1)n+2 ∀ a ∈ N
Solução.
a) Por indução sobre n.
Se n = 1 temos 13 + 11(1) = m(6)
Suponhamos para h ∈ N cumpra h3 + 11h = m(6).
Para h+ 1 ∈ N e pela hipótese indutiva
(h+ 1)3 + 11(h+ 1) = (h3 + 11h) + 3h2 + 3h+ 12 = m(6) + 3h(h+ 1) (2.3)
Se h = 2k-par, em 3h(h+ 1) = 6k(2k + 1) = m(6)
Se h = 2k + 1-ímpar, em 3h(h+ 1) = 6(2k + 1)(k + 1) = m(6)
Logo (h+ 1)3 + 11(h+ 1) = m(6)
Portanto, 6|n3 + 11n.
b)
c)
d) Para todo n ∈ N temos
23n − 1 = (23)n − 1 = (m(7) + 1)n − 1 = m(7) + 1n − 1 = m(7)
Portanto, 7|23n − 1.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
18
e) Para todo n ∈ N temos
32n + 7 = (32)n + 7 = (m(8) + 1)n + 7 = m(8) + 1n + 7 = m(8)
Portanto, 8|32n + 7.
f) Para todo n ∈ N temos
32n+1 + 2n+2 = 3(32)n + 4 · 2n = 3(m(7) + 2)n + 4 · 2n =
= 3[m(7) + 2n] + 4 · 2n = m(7) + (3 + 4)2n = m(7)
Portanto, 7|32n+1 + 2n+2.
g)
Exercício 2.3.17.
Mostre que, se um inteiro é um quadrado e um cubo, então é da forma 7k ou 7k + 1.
Solução.
Seja a ∈ Z, e N um inteiro que é um quadrado e um cubo, logo podemos escrever na
forma N = (a3)2 ou N = (a2)3 assim temos que N = a6.
• Se a = m(7) então N = a6 = m(7)
• Suponhamos que a ∤ 7 e seja o conjunto M = {a, 2a, 3a 4a, 5a, 6a} então cada um
dos elementos de M , diferença con elementos do conjunto P = {1, 2, 3, 4, 5, 6} em
alguma ordem, são divisíveis por 7. Logo
6!a6 − 6! = m(7) ⇒ a6 − 1 = m(7) ⇒ N = a6 = 1 +m(7)
Portanto, se um inteiro é um quadrado e um cubo, então é da forma 7k ou 7k + 1.
Exercício 2.3.18.
a) Mostre que um quadrado perfeito ímpar é da forma 4n+ 1.
b) Mostre que nenhum elemento da sequência 11, 111, 1111, . . . , é um quadrado perfeito.
Demonstração.
a) Só iremos considerar números ímpares, para o caso dos pares, seu quadrado sempre
será número par,
Seja 2k + 1, k ∈ Z qualquer número ímpar, seu quadrado é da forma N = 4k2 +
4k + 1 = 4n+ 1, isto é um quadrado perfeito ímpar é da forma 4n+ 1.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
19
b) Seja N = 1111 . . . 11 número com n > 1 algarismos, e suponhamos que N seja um
quadrado perfeito, isto é, existe K ∈ N tal que N = K2. Temos
N = 1111 . . . 11 = 10n−1 + 10n−2 + 10n−3 + · · ·+ 102 + 10 + 1 ⇒
N =
10n − 1
10− 1
= K2 ⇒ 10n − 1 = 9K2 ⇒
10n − 1 = 9K2 ⇒ 10n − 1 = (10− 1)K2 ⇒ 10(10n−1 −K2) = 1−K2
Como K ∈ N, temos que 1−K2 é múltiplo de 10, isto acontece somente se K = 1
e conse1uentemente n = 1 sendo um absurdo! Isto do fato supor que N seja um
quadrado perfeito.
Portanto, nenhum elemento da sequência 11, 111, 1111, . . . , é um quadrado perfeito.
Exercício 2.3.19.
a) Mostre que todo quadrado perfeito é da forma 5k ou 5k ± 1.
b) Com que algarismo pode terminar um quadrado perfeito?
c) Se três inteiros positivos verificam a2 = b2 + c2, então entre eles há um múltiplo de 2
e um múltiplo de 5.
d) A soma dos quadrados de dois inteiros ímpares não pode ser um quadrado perfeito.
Demonstração.
a) Seja n = . . . a2a1a0, isto podemos escrever na forma n = 10(. . . + 10a2 + a1) + a0 o
quadrado deste número é
n2 = 102(. . .+ 10a2 + a1)
2 + 20a0(. . .+ 10a2 + a1) + a20 = m(5) + a20
onde m(5) indica múltiplo de 5
n2 = m(5) + a20 (2.4)
Na igualdade (2.4) se a0 = 0 ou a0 = 5 então a20 = m(5) logo n2 = m(5).
Na igualdade (2.4) se a0 = 1, 4, 6 ou a0 = 9 então a20 = m(5)+1, logo n2 = m(5)+1.
Na igualdade (2.4) se a0 = 2, 3, 7 ou a0 = 8 então a20 = m(5)+4 = m(5)− 1, logo
n2 = m(5)− 1.
Portanto, todo quadrado perfeito é da forma 5k ou 5k ± 1.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
20
b) Pela parte a) um quadrado perfeito pode terminar em 0, 1, 4. 6 ou 9.
c) Se três inteiros positivos verificam a2 = b2 + c2, então para b ∈ Z, b > 0 temos
c = b− 1 e a = b+ 1, logo
a2 = b2 + c2 ⇔ (b+ 1)2 = b2 + (b− 1)2 ⇔ b(b− 4) = 0
logo, b = 4, c = 3 e a = 5.
Portanto, entre eles há um múltiplo de 2 e um múltiplo de 5.
d) Sejam α, β ∈ Z, α ̸= β e consideremos os números 2α + 1 e 2β + 1 então
N = (2α + 1)2 + (2β + 1)2 = 4(α2 + α + β2 + β) + 2
N = (5− 1)(α2 + α + β2 + β) + 2 = m(5) + 2− (α2 + α + β2 + β)
pela parte a) do Exercício (1.2.7) temos α2 = m(2) + α e β2 = m(2) + β
N = m(5) + 2− [m(2) + 2α +m(2) + 2β] = m(5) +m(2)
Pela parte a) deste Exercício N não pode ser um quadrado perfeito.
Portanto, a soma dos quadrados de dois inteiros ímpares não pode ser um quadrado
perfeito.
Exercício 2.3.20.
Mostre que, de n inteiros consecutivos, um, e apenas um, deles é divisível por n.
Demonstração.
Exercício 2.3.21.
Um número é dito livre de quadrados se não for divisível pelo quadrado de nenhum
número diferente de 1.
a) Determine qual é o maior número de números naturais consecutivos livres de quadra-
dos.
b) Defina números livres de cubos e resolva o problema correspondente.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
21
Solução.
Exercício 2.3.22.
Seja m ∈ N. Pode o número m(m+ 1) ser a sétima potência de um número natural?
(generalize).
Solução.
Exercício 2.3.23.
Dados a; b ∈ N, quantos números naturais divisíveis por b existem na sequência
a; 2a; . . . ba?
Solução.
Exercício 2.3.24.
Sejam a; d ∈ N. Mostre que, na sequência a+0d; a+d; a+2d; a+3d; . . . ou não existe
nenhum quadrado ou existem infinitos quadrados.
Solução.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark22
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
MA-14 - Aula 02
Semana 12/08 a 18/08
Unidade 3
3.1 Sistemas de Numeração: Problemas
Exercício 3.1.1.
Um certo número de três algarismos na base 10 aumenta de 36 se permutarmos os dois
algarismos da direita, e diminui de 270 se permutarmos os dois algarismos da esquerda.
O que acontece ao número se permutarmos os dois algarismos extremos?
Demonstração.
Seja N = abc o número, pelas hipóteses abc = acb− 36 e abc = bac+ 270, logo
102a+ 10b+ c = 102a+ 10c+ b− 36 ⇒ c− b = 4 (3.5)
102a+ 10b+ c = 102b+ 10a+ c+ 270 ⇒ a− b = 3 (3.6)
Das igualdades (3.5) e (3.6) segue que c = a+ 1.
Ao permutar os dois algarismos extremos
cba = 100c+ 10b+ a = 100(a+ 1) + 10b+ (c− 1) = 102a+ 10b+ c+ 99
Resulta cba = abc+ 99, o número aumenta em 99 unidades.
Exercício 3.1.2. Critério de divisibilidade por uma potência de 2
Seja dado um número a, representado na base 10 por a = anan−1 . . . a0. Usando o fato
de que 2k|10k, mostre que 2k divide a se, e somente se, o número ak−1 . . . a1a0 é divisível
por 2k. Em particular, a é divisível por 2 se, e somente se, a0 é 0, 2, 4, ∥ : 6 ou 8; também,
a é divisível por 4 se, e somente se, a1a0 é divisível por 4.
Demonstração.
23
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
24
Como 2k|10k então existe β ∈ N tal que 10k = β · 2k, e de a = anan−1 . . . a0, então
a = 10nan + 10n−1an−1 + . . .+ 102a2 + 10a1 + 100a0
Suponhamos que o número ak−1 . . . a1a0 seja divisível por 2k, logo
10k−1ak−1 + . . .+ 102a2 + 10a1 + a0 = γ2k
então
10kak + (10k−1ak−1 + . . .+ 102a2 + 10a1 + a0) = γ2k + 10kak = 2k(γ + 5kak)
Portanto, 2k divide a.
Inversamente
Se 2k divide a, então a = α2k, assim
10kak + 10k−1ak−1 + . . .+ 102a2 + 10a1 + a0 = α · 2k
então
10k−1ak−1 + . . .+ 102a2 + 10a1 + a0 = α · 2k − 10kak = 2k(α− 5kak)
Portanto, o número ak−1 . . . a1a0 é divisível por 2k
Em particular, quando k = 1 temos que a é divisível por 21, isto é a0 = γ · 2, logo a0
é 0, 2, 4, 6 ou 8.
Em particular, quando k = 2 temos que a = a1a0 é divisível por 22, isto é a1a0 =
γ · 22 = 4γ, logo o número a1a0 tem que ser divisível por 4.
Exercício 3.1.3.
Escolha um número abc de três algarismos no sistema decimal, de modo que os algaris-
mos das centenas a e o das unidades c difiram de, pelo menos, duas unidades. Considere
os números abc e cba e subtraia o menor do maior, obtendo o número xyz. A soma de
xyz com zyx vale 1089. Justifique este fato.
Solução.
Seja N = abc o número e suponhamos que N seja maior do que M = cba, logo a > c.
Assim, a = c+K onde k = 2, 3, 4, 5, 6 ou 7. Logo, P = N −M = xyz
xyz = N−M = abc−cba = (102a+10b+c)−(102c+10b+a) = 102(a−c)+0×10+(c−a)
assim, xyz = 102 ·K −K, de onde xyz = [102(K − 1) + 100−K = 102(K − 1) + 10×
9 + (10−K) consequentemente zyx = 102(10−K) + 10× 9 + (K − 1)
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
25
Somando, xyz + zyx = [102(K − 1) + 10× 9 + (10−K)] + [102(10−K) + 10× 9 +
(K − 1)] = 9× 102 + 180 + 9 = 1089.
Este fato acontece, porque o resultado é independente do valor dado para k = 2, 3, 4, 5, 6
ou 7.
Exercício 3.1.4.
Seja dado o número 4783 na base 10; escreva-o nas seguintes bases: 2, 3, 4, 7, 12 e
15.
Solução.
Exercício 3.1.5.
O número 3416 está na base 7; escreva-o nas bases 5 e 12.
Solução.
34167 = 3× 73 + 4× 72 + 1× 7 + 6 = 123810 = 144235 = 87212
Exercício 3.1.6.
Um número na base 10 escreve-se 37; em que base escrever-se-á 52?
Solução.
Suponhamos se escreva na base a, então
3710 = 52a ⇒ 37 = 5a+ 2 ⇒ a = 7
Na base sete.
Exercício 3.1.7.
Considere 73 na base 10; em que base ele se escreverá 243?
Solução.
Suponhamos se escreva na base a, então
7310 = 243a ⇒ 73 = 2a2 + 4a+ 3 ⇒ a = 5
Na base cinco.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
26
Exercício 3.1.8.
Escreva a tabuada na base 5. Use-a para calcular 132 + 413 e 23× 342.
Solução.
1× 1 = 1
1× 2 = 2
1× 3 = 3
1× 4 = 4
2× 1 = 2
2× 2 = 4
2× 3 = 11
2× 4 = 13
3× 1 = 3
3× 2 = 11
3× 3 = 14
3× 4 = 22
4× 1 = 4
4× 2 = 13
4× 3 = 22
4× 4 = 31
Assim temos
1 3 2 +
4 1 1
1 0 4 3
3 4 2 ×
2 3
2 1 3 1
1 2 3 4
2 0 0 2 1
Exercício 3.1.9.
Utilize o método dos antigos egípcios para calcular 527× 72.
Solução.
1 −→ 527
2 −→ 1054
4 −→ 1581
8 −→ 2108
16 −→ 2635
32 −→ 3164
64 −→ 3689
64 + 8 = 72 −→ 3689 + 2108 = 5797
Assim, 527× 72 = 5797
Exercício 3.1.10.
Escreva:
a) O número 2n − 1 na base 2.
b) O número O número
bn − 1
b− 1
na base b.
Demonstração.
Exercício 3.1.11.
Sendo a = [an . . . a1a0]b, mostre que o número a− (a0 + . . .+ an) é divisível por b− 1.
Demonstração.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
27
Exercício 3.1.12.
Mostre que, na base 10, o algarismo das unidades de um quadrado perfeito só pode ser
0, 1, 4, 5, 6 ou 9.
Demonstração.
Seja n ∈ N um número na base 10, e denotemos m(5) o múltiplo de 5, então
n = an . . . a1a0 = 10nan + · · ·+ 10a1 + a0 = m(5) + a0
ao quadrado n2 = [m(5) + a0]
2 = m(5) + a20 como a0 é o algarismo das unidades, temos
a0 = 1 ou 4 ou 6 ou 9 ⇒ a20 = m(5) + 1; a0 = 5 ⇒ a20 = m(5)
a0 = 2 ou 3 ou 7 ou 8 ⇒ a20 = m(5) + 4
Como a20 = m(5), m(5) + 1, m(5) + 4 segue que o algarismo das unidades de um
quadrado perfeito só pode ser 0, 1, 4, 5, 6 ou 9.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
28
Unidade 4
Jogo de Nim
4.2 Jogo de Nim: Problemas
Exercício 4.1.1.
Determine, em cada caso apresentado abaixo, se a posição é segura ou insegura.
Demonstração.
a) | | | |
b) | | | | | | |
c) | | | |
d) | |
Exercício 4.1.2.
Determine qual das seguintes situações iniciais no Jogo de Nim permite ao primeiro
jogador traçar uma estratégia vencedora.
a) (12; 14; 15), b) (7; 9; 14), c) (7; 9; 15; 17).
Demonstração.
Exercício 4.1.3.
Demonstre que as afirmações feitas na variante 3 do jogo de Nim são verdadeiras.
Demonstração.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
MA-14 - Aula 03
Semana 19/08 a 25/08
Unidade 5
5.2 Máximo Divisor Comum: Problemas
Exercício 5.2.1.
Para cada par de números naturais a e b dados abaixo, ache (a, b) e determine números
inteiros m e n tais que (a, b) = na+mb.
a) 637 e 3887 b) 648 e 1218 c) 551 e 874
d) 7325 e 8485 e) 987654321 e 123456789
Solução.
a) 3887 = 6× 637 + 52, 637 = 9× 65+ 53, 65 = 1× 52 + 13, logo
13 = 65− 1× 52 = 65− 1(637− 9× 65)
13 = 10× 65− 637 = 10(3887− 6× 637)− 635 = 10× 3887− 61× 637
Portanto, (637, 3887) = 13, m = −61 e n = 10.
b) 1218 = 648× 1 + 570
Logo, 648× 47− 1218× 25 = 6
Portanto, (648, 1218) = 13, m = 47 e n = −25.
c) Aplicando o Lema 1 de Euclides temos
(874, 551) = (874− 551, 551) = (323, 551) = (323, 551− 323) = (323, 228) =
= (323, 228) = (323− 228, 228) = (95, 228) = (95, 228− 2× 95) = (95, 38) =
= (95−38, 38) = (57, 38) = (57−38, 38) = (19, 38) = (19, 38−2×19) = (19, 0) = 19
29
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
30
assim, (874, 551) = 19
Isto é 19 = 19(46, 29) ⇒ 1 = (46, 29) ⇒ 1 = 29 × 8 − 46 × 5, logo
concluímos que 19 = 551× 8− 874× 5
Portanto, (874, 551) = 19, m = 8 e n = −5.
d) 7325 e 8485
e) 987654321 e 123456789
Exercício 5.2.2.
Seja n ∈ N. Mostre que:
a) (n, 2n+ 1) = 1 b) (n+ 1, n2 + n+ 1) = 1
c) (2n+ 1, 9n+ 4) = 1 d) (n! + 1, (n+ 1)! + 1) = 1
Demonstração.
a) Primeira solução: Observe que 2n + 1 > 2n, pelo algoritmo de Euclides segue que
2n+1 = 1× 2n+1, logo 1 = 1× (2n+1)− (1)× 2n. Então o mdc{2n+1, 2n} = 1
são coprimos.
Portanto (n, 2n+ 1) = 1
a) Segunda solução: Suponhamos que (n, 2n+ 1) = d ⇒ d|n e d|2n+ 1
Como d|n ⇒ d|2n, assim temos que 2n = αd e como também d|2n + 1 logo
2n+ 1 = βd para α, β ∈ N.
Logo αd = βd+ 1 ⇒ 1 = d(α− β) de onde d = 1.
Portanto (n, 2n+ 1) = 1
b) Pelo Lema 1 (Lema de Euclides) segue
(n+ 1, n2 + n+ 1) = (n+ 1, n(n+ 1) + 1) = (n+ 1, 1)
O máximo divisor comum de dois naturais consecutivos (n+ 1, 1) = 1
Portanto (n, 2n+ 1) = 1.
Portanto (n, 2n+ 1) = 1.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
31
c) Primeira solução: Observe que 9n + 4 > 2n + 1, pelo algoritmo de Euclides segue
que 9n + 4 = 4 × (2n + 1) + (n + 0) então 2n + 1 = 2 × n + 1, logo 1 = 1 ×
(2n + 1) + (−2) × n ⇒ 1 = 1 × (2n + 1) + (−2)[9n + 4 − 4 × (2n + 1)], isto é
1 = (−2)× (9n+ 4) + 9× (2N + 1).
Portanto, mdc{2n+ 1, 9n+ 4} = 1.
c) Segunda solução: Suponhamos (2n+ 1, 9n+ 4) = d então d|2n+ 1 e d|9n+ 4 logo
d|(9n+ 4)− 4(2n+ 1), assim d|n
Temos d|2n+ 1 e d|n pela parte a) segue que d = 1.
Portanto, mdc{2n+ 1, 9n+ 4} = 1.
d) (n! + 1, (n+ 1)! + 1) = 1
Pelo Lema 1 (Lema de Euclides) segue
(n! + 1, (n+ 1)! + 1) = (n! + 1, n× n!)
A mostrar que (n! + 1, n× n!) = 1
Pelo Lema 1 (Lema de Euclides) segue
(n! + 1, n× n!) = (n! + 1, n(n! + 1)− n) = (n! + 1, −n) = 1
Exercício 5.2.3.
Mostre que (a, a2 + na+ b)|b, quaisquer que sejam a, b, n ∈ N.
Demonstração.
Para qualquer a, b, n ∈ N, suponhamos que
d = (a, a2 + na+ b) ⇒ d|a e d|a2 + na+ b
além disso existem números inteiros x, y ∈ Z tais que d = a · x+ y(a2 + na+ b).
Como d|a então existe c ∈ N tal que a = d · c. Também d|a2 + na + b então existe
β ∈ N tal que a2 + na+ b = β · d de onde
b = β · d− a2 − na = βd− d2c2 − ndc = d(β − dc2 − nc) ⇒ d|b
isto é (a, a2 + na+ b) = d|b
Portanto, (a, a+ b)|b, quaisquer que sejam a, b ∈ N
Exercício 5.2.4.
Dados a ∈ Z r {−1}, mostre que
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
32
a) Se m ∈ N, mostre que:
(
a2m − 1
a+ 1
, a+ 1
)
= (a+ 1, 2m)
b) Se m ∈ N ∪ {0}, mostre que:
(
a2m+1 + 1
a+ 1
, a+ 1
)
= (a+ 1, 2m+ 1)
Demonstração. a)
Como a+ 1|a2m − 1 então a2m − 1 = (a+ 1)[a2m−1 − a2m−2 + . . .− a2 + a− 1]
a2m − 1 = (a+ 1)[(a2m−1 + 1)− (a2m−2 − 1) + . . .− (a2 − 1) + (a+ 1) + 2m]
a2m − 1
a+ 1
= n(a+ 1) + 2m para algúm n ∈ N
Assim,
(
a2m − 1
a+ 1
, a+ 1
)
= (n(a+ 1) + 2m, a+ 1)
Pelo Lema 1 (Lema de Euclides)
(
a2m − 1
a+ 1
, a+ 1
)
= (2m, a+ 1)
Demonstração. b)
Como a+ 1|a2m+1 + 1 então a2m + 1 = (a+ 1)[a2m − a2m−1 + . . .+ a3 − a2 − a+ 1]
a2m+1 +1 = (a+1)[(a2m − 1)− (a2m−1 +1)+ . . .− (a3 +1)+ (a2 − 1)− (a+1)+ 2m+1]
a2m+1 − 1
a+ 1
= n(a+ 1) + 2m+ 1 para algúm n ∈ N
Assim,
(
a2m+1 + 1
a+ 1
, a+ 1
)
= (n(a+ 1) + 2m+ 1, a+ 1)
Pelo Lema 1 (Lema de Euclides)
(
a2m+1 + 1
a+ 1
, a+ 1
)
= (2m+ 1, a+ 1)
Exercício 5.2.5.
Calcule a)
(
340 − 1
35 − 1
, 35 − 1
)
b)
(
510 − 1
6
, 6
)
c)
(
240 + 1
28 + 1
, 28 + 1
)
d)
(
250 + 1
210 + 1
, 210 + 1
)
Solução. a)
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
33
Temos,
(
340 − 1
35 − 1
, 35 − 1
)
=
(
(35)8 − 1
35 − 1
, 35 − 1
)
, por outro lado
(35)8 − 1 = (35 − 1)((35)7 + (35)6 + (35)5 + (35)4 + (35)3 + (35)2 + (35) + 1)
(35)8−1 = (35−1)((35)7−1+(35)6−1+(35)5−1+(35)4−1+(35)3−1+(35)2−1+(35)−1+8)
(35)8 − 1 = (35 − 1)[β(35 − 1) + 8] β ∈ N
(
340 − 1
35 − 1
, 35 − 1
)
=
(
β(35 − 1) + 8, 35 − 1
)
=
(
8, 35 − 1
)
Solução. b)
Temos,
(
510 − 1
6
, 6
)
=
(
510 − 1
5 + 1
, 5 + 1
)
, aplicando o Lema de Euclides segue que
segue que m = 5 e
(
510 − 1
5 + 1
, 5 + 1
)
= (2× 5, 5 + 1) = 2
Solução. c)
Temos,
(
240 + 1
28 + 1
, 28 + 1
)
=
(
(28)5 + 1
28 + 1
, 28 + 1
)
, aplicando a parte b) do exercício
anterior segue que m = 2
(
240 + 1
28 + 1
, 28 + 1
)
=
(
(28)5 + 1
28 + 1
, 28 + 1
)
= (2× 2 + 1, 28 + 1) = (5, 257) = 1
Solução. d)
Temos,
(
250 + 1
210 + 1
, 210 + 1
)
=
(
(210)5 + 1
210 + 1
, 210 + 1
)
, aplicando a parte b) do exer-
cício anterior segue que m = 2
(
250 + 1
210 + 1
, 210 + 1
)
=
(
(210)5 + 1
210 + 1
, 210 + 1
)
= (2× 2 + 1, 210 + 1) = (5, 1025) = 5
Exercício 5.2.6.
Sejam a e n números naturais com a ̸= 1. Mostre que.
(a− 1)2|an − 1 ⇔ a− 1|n
Solução.
Temos (a− 1)2|an − 1 então an − 1 = α(a− 1)2, α ∈ N, por outro lado
an − 1 = (a− 1)(an−1 + · · ·+ a+ 1) = (a− 1)[(a− 1)β + n], β ∈ N
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
34
Logo, α(a− 1)2 = (a− 1)[(a− 1)β + n] ⇒ (a− 1)2[α− β) = (a− 1)n ⇒
(a− 1)[α− β) = n ⇒ (a− 1)|n
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
35
Unidade 6
Propriedades do mdc
6.2 Propriedades do mdc: Problemas
Exercício 6.2.1.
Sejam a; b; d ∈ Z com d ≥ 0. Mostre que se I(a; b) = dZ, então d = (a; b).
Solução.
Exercício 6.2.2.
Mostre que:
a) Se (a, b) = 1, a|c e b|c, então ab|c.
b) Mostre que, se (a, b) = 1, então (a · c, b) = (c, b).
c) Mostre que (a · c, b) = 1 se, e somente se, (a, b) = (c, b) = 1
d) (a, b) = (a, d) = (c, b) = (c, d) = 1 se e somente se (a · c, b · d) = 1
e) Se (c, d) = 1, então (an, bm) = 1, ∀ n,m ∈ N.
Demonstração.
a) Como (a, b) = 1, a|c e b|c então existem x, y, α, β ∈ Z tais que
a · x+ b · y = 1, c = β · a, c = α · b
Multiplicando a primeira igualdade por c e, logo substituindo os valores de c corres-
pondentes, segue
a · x · c+ b · y · c = c ⇒ a · x · (α · b) + b · y · (β · a) = c
isto é ab(xα + yβ) = c.
Portanto, ab|c.
b)Da hipótese (a, b) = 1, logo existem x, y ∈ Z tais que 1 = ax+ by.
Suponhamos d1 = (a · c, b) e d2 = (c, b)
Como d1 = (a · c, b) então existem α, β ∈ N tais que a · c = αd1 e b = βd1.
Como d2 = (c, b) então existem γ, ρ ∈ N tais que c = γd2 e b = ρd2.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
36
Como 1 = ax + by, logo c = acx + bcy. Substituindo as relações acima, segue que
c = (αd1)x− (βd1)cy ⇒ d1|c
Sendo que d1|c e d1|b então d1|(c, b) = d2.
Por outro lado,
Como d2|c e d2|b então d2|ac e d2|b, logo d2|(ac, b) = d1
Assim, como d1, d2 ∈ N e d1|d2 e d2|d1 ⇒ d1 = d2
Portanto, se (a, b) = 1, então (a · c, b) = (c, b)
c) Seja (a · c, b) = 1, então existem β, ρ ∈ Z tais que 1 = β(a · c) + µb
Suponhamos que d1 = (a, b) e d2 = (c, b), então d1|a, d1|b e d2|c, d2|b e existem
γ, ρ, η, ω ∈ N tais que a = γd1, b = ρd1 e c = ηd2, b = ωd2
Como 1 = β(a · c) + µb ⇒ 1 = β(γd1 · c) + µρd1 ⇒ d1|1
Como 1 = β(a ·c)+µb ⇒ 1 = β(a ·ηd2)+µωd2 ⇒ d2|1. De d1|1, d2|1 ⇒
d1 = d1 = 1.
Portanto, se (a · c, b) = 1, então (a, b) = (c, b) = 1
Inversamente.
Seja (a, b) = (c, b) = 1 e suponhamos que (a · c, b) = d, então d|(a · c) e d|b, logo
(a · c) = αd e b = βd, para algum α, β ∈ N.
Como (a, b) = (c, b) = 1 então existem x, y,m, n ∈ N tais que
1 = ax+ by ⇒ c = acx+ bcy ⇒ c = (αd)x+ (βd)cy ⇒ d|c
1 = mc+ nb ⇒ a = acm+ ban ⇒ a = (αd)m+ (βd)an ⇒ d|a
Como d|a, d|b e d|c então d|ax+ by = 1 e d|mc+ nb = 1 assim, d = 1 = (ac, b)
Portanto, (a · c, b) = 1 se, e somente se, (a, b) = (c, b) = 1
d) Pela parte c) deste Exercício temos de:
(a, b) = (c, b) = 1 ⇒ (a · c, b) = 1, e de (a, d) = (c, d) = 1 ⇒ (a · c, d) = 1
Como (b, a · c) = 1 e (d, a · c) = 1, então (b · d, a · c) = 1
Portanto, (a · c, b · d) = 1.
e) Aplicar indução, primeiro sobre n, logo sobre m, usando o resultado da parte a)
Portanto, (an, bm) = 1, ∀ n,m ∈ N.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
37
Exercício 6.2.3.
Para todos a; b ∈ Z e todo n ∈ N, mostre que.
(an, bn) = (a, b)n
Solução.
Exercício 6.2.4.
a) Mostre que, se n é ímpar, n(n2 − 1) é divisível por 24
b) Mostre que 24 divide n(n2 − 1)(3n+ 2) para todo n ∈ N.
Demonstração.
a) Primeira solução
Se n é ímpar então n = 2k + 1 para todo k ∈ Z, logo
n(n2 − 1) = (n− 1)n(n+ 1) = (2k)(2k + 1)(2k + 2) = 4k(2k + 1)(k + 1) (6.7)
A igualdade em (6.7) vale para todo k ∈ Z. Todo número inteiro podemos escrever
como algum elemento do conjunto
A = { 6m, 6m+ 1, 6m+ 2, 6m+ 3, 6m+ 4, 6m+ 5, ∀m ∈ Z } ≡ Z
Em (6.7), se k = 6m ⇒ n(n2 − 1) = 24m(12m+ 1)(6m+ 1)
Em (6.7), se k = 6m+ 1 ⇒ n(n2 − 1) = 24(6m+ 1)(4m+ 1)(3m+ 1)
Em (6.7), se k = 6m+ 2 ⇒ n(n2 − 1) = 24(3m+ 1)(12m+ 5)(2m+ 1)
Em (6.7), se k = 6m+ 3 ⇒ n(n2 − 1) = 24(2m+ 1)(12m+ 7)(3m+ 2)
Em (6.7), se k = 6m+ 4 ⇒ n(n2 − 1) = 24(3m+ 2)(4m+ 3)(6m+ 5)
Em (6.7), se k = 6m+ 5 ⇒ n(n2 − 1) = 24(6m+ 5)(12m+ 11)(m+ 1)
Portanto, n(n2 − 1) é divisível por 24.
a) Segunda solução
Sabemos que a soma 12 + 22 + 32 + · · ·+ k2 =
k(k + 1)(2k + 1)
6
∈ N
Na igualdade (6.7) temos
n(n2 − 1) = 4k(2k + 1)(k + 1) = 24 ·
k(k + 1)(2k + 1)
6
∈ N
Portanto, n(n2 − 1) é divisível por 24.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
38
b) Seja P = n(n2 − 1)(3n + 2). Todo número natural podemos expressar como algum
elemento do conjunto
A = { 6m, 6m+ 1, 6m+ 2, 6m+ 3, 6m+ 4, 6m+ 5, ∀m ∈ N } ≡ N
Como os números naturais da forma 6m + 1, 6m + 3, 6m + 5 ∀ m ∈ N são
ímpares, então pela parte a), é imediato que n(n2 − 1)(3n+2) seja divisível por 24,
logo temos
P = n(n2 − 1)(3n+ 2) (6.8)
Em (6.8), se k = 6m então
P = 6m(36m2 − 1)(18m+ 2) = 12m(6m+ 1)(6m− 1)(9m+ 1)
Se m-par, o fator m é par, logo temos P = 24β para algum β ∈ N.
Se m-ímpar, o fator 9m+ 1 é par, logo temos P = 24α para algum α ∈ N.
Em (6.8), se k = 6m+ 2 então
P = 12(3m+ 1)(2m+ 1)(6m+ 1)(9m+ 4)
Se m-par, o fator 9m+ 4 é par, logo temos P = 24β para algum β ∈ N.
Se m-ímpar, o fator 3m+ 1 é par, logo temos P = 24α para algum α ∈ N.
Em (6.8), se k = 6m+ 4 então
P = 12(3m+ 2)(6m+ 5)(2m+ 1)(9m+ 7)
Se m-par, o fator 3m+ 2 é par, logo temos P = 24β para algum β ∈ N.
Se m-ímpar, o fator 3m+ 1 é par, logo temos P = 24α para algum α ∈ N.
Portanto, 24 divide n(n2 − 1)(3n+ 2) para todo n ∈ A ≡ N
Exercício 6.2.5.
a) Mostre que n5 − n é divisível por 30.
b) Mostre que n5 e n possuem o mesmo algarismo das unidades.
Demonstração.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
39
a) Pelo exercício 12 da Unidade 1, sabemos que 5|n5 − n para todo n ∈ N.
Resta mostrar que 6|n5 − n.
Afirmo: O produto de três números consecutivos é múltiplo de 6.
Com efeito, sejam os três números consecutivos n− 1, n e n+ 1.
Seja M = (n− 1)n(n+ 1) = n(n2 − 1).
Sabemos que todo número natural podemos escrever como algum elemento do con-
junto A = { 3k, 3k + 1, 3k + 2 ∀ k ∈ N } ≡ N então:
Se n = 3k ⇒ M = (3k)(9k2 − 1) = 6α ⇒ 6|M .
Pois, o fator k é par se k-par, e o fator 9k2 − 1 é par se k-ímpar.
Se n = 3k + 1 ⇒ M = (3k)(3k + 1)(3k + 2) = 6β ⇒ 6|M .
Pois, o fator k é par se k-par, e o fator 3k + 1 é par se k-ímpar.
Se n = 3k + 2 ⇒ M = 3(3k + 1)(3k + 2)(k + 1) = 6γ ⇒ 6|M .
Pois, o fator 3k + 2 é par se k-par, e o fator k + 1 é par se k-ímpar.
Assim, 6|n(n2 − 1).
Voltando ao problema, como n5−n = n(n4−1) = n(n2−1)(n2+1) = 6ρ(n2+1) ⇒
6|n5 − n e de 5|n5 − n, sendo (5, 6) = 1 temos que n5 − n é divisível por 30.
b) Primeira solução: Seja n ∈ N tal que n = . . . 102a2+10a1+ a0, então n = 10k+ a0,
logo aplicando a parte a) deste exercício como a50 − a0 = 30β.
n5 = (10k + c)5 =
4∑
j=0
Cj
5(10k)
5−jaj0 + a50 = 10α + a50 =
n5 = 10α + (30β + a0) = 10γ + a0
Portanto, n5 e n possuem o mesmo algarismo das unidades.
b) Segunda solução: Mostramos na parte a) que 30|n5 − n, logo 10|n5 − n.
Seja n = . . . a2a1a0 ⇒ n = . . . a2a10 + a0
Também temos n5 = . . . b2b1b0 ⇒ n5 = . . . b2b10 + b0
A diferença destes números é
n5 − n = (. . . b2b10 + b0)− (. . . a2a10 + a0) = 10(. . . c2c1) + (b0 − a0)
Como 10|n5−n ⇒ n5−n = 10β, β ∈ N e a0 e b0 são algarismos das unidades,
então b0 − a0 = 0 de onde b0 = a0.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
40
Portanto, n5 e n possuem o mesmo algarismo das unidades.
Exercício 6.2.6.
Mostre que a|bc se, e somente se,
a
(a, b)
∣
∣
∣c.
Demonstração.
Suponhamos que a|bc, então bc = αa.
Para todo a, b ∈ N temos que
( a
(a, b)
,
b
(a, b)
)
= 1, então
ax
(a, b)
+
by
(a, b)
= 1 para
x, y ∈ Z, logo
axc
(a, b)
+
αay
(a, b)
= c ⇒
a
(a, b)
(xc+ αy) = c
Portanto, se a|bc então
a
(a, b)
|c.
Inversamente (⇐)
Suponhamos que
a
(a, b)
∣
∣
∣c, logo c = β
a
(a, b)
, assim bc = β
ab
(a, b)
=
[
βb
(a, b)
]
a.
Portanto, se
a
(a, b)
∣
∣
∣c então a|bc.
Exercício 6.2.7.
Sejam a e b dois números inteiros e (a, b) = 1.
a) Mostre que (b+ a, b− a) é 1 ou 2
b) Mostreque (a+ b, a2 + b2) é 1 ou 2.
Demonstração.
a) Suponhamos que d = (b+ a, b− a) então b+ a = αd e b− a = βd
Resolvendo o sistema segue que 2b = (α + β)d e 2a = (α− β)d.
Sabe-se que (2a, 2b) = 2(a, b) = 2, logo ((α+ β)d, (α− β)d) = 2 então d(α+ β, α−
β) = 2.
Como (α + β, α− β) ∈ N então d = 1 ou d = 2.
Portanto, (b+ a, b− a) é 1 ou 2
b) Primeira solução: Mostre que (a+ b, a2 + b2) é 1 ou 2.
Deste exercício parte a) suponhamos que (b+ a, b− a) = 1 e como (1, b) = 1. Pelo
Exercício (6.2.13) - a) segue do Lema 1 (Lema de Euclides)
1 = (b+ a, b(b− a)) = (b+ a, a(b+ a) + b(b− a)) = (a+ b, a2 + b2)
Por outro lado, suponhamos que d = (a+b, a2+b2) então d = (a+b, (a+b)2−2ab),
logo d = (a+ b, −2ab) então d|a+ b e d|2ab
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
41
Como (a, b) = 1 ⇒ (a+ b, b) = 1 ou (a+ b, a) = 1 isto é a+ b ∤ a e a+ b ∤ b,
logo d|2 ⇒ d = 1 ou d = 2
Portanto, (a+ b, a2 + b2) = 1 ou 2.
b) Segunda solução: Mostre que (a+ b, a2 + b2) é 1 ou 2.
Suponhamos d = (a+ b, a2 + b2) então a+ b = αd e a2 + b2 = βd, α, βinn.
Como a + b = αd ⇒ (a + b)(a − b) = αd(a − b) ⇒ d|a2 − b2 logo existe
γ ∈ N tal que a2 − b2 = γd.
a2 + b2 = βd, a2 − b2 = γd ⇒ 2a2 = d(β + γ), 2b2 = d(β − γ)
Como (a, b) = 1, pelo Exercício (6.2.6) segue que (a2, b2) = 1 ⇒ a2x+ b2y =
1 ⇒ 2a2x+ 2b2y = 2 isto é
d(β + γ)x+ d(β − γ)y = 2 ⇒ d|2 d = 1 ou d = 2
Portanto, (a+ b, a2 + b2) = 1 ou 2.
Exercício 6.2.8.
Mostre que, se a, b, x, y ∈ Z, com ax+ by = (a, b), então (x, y) = 1.
Demonstração.
Suponhamos (a, b) = d, então pela hipótese segue ax+ by = d, além disso como como
(a, b) = d logo d|a e d|b, isto é existem α, β ∈ Z tais que a = αd e b = βd.
Substituindo em ax + by = d segue que x(αd) + y(βd) = d isto é d(xα + yβ) = d,
como d ̸= 0 segue que xα + yβ = 1.
Por outro lado, seja d1 = (x, y) então d1|x e d1|y, logo existem α1, β1 ∈ Z tais que
x = d1α1 e y = d1β1 de onde 1 = xα + yβ = d1(α1α + .β1β) então d1|1, logo d1 = 1.
Portanto, (x, y) = 1.
Exercício 6.2.9.
Sejam a e b dois números naturais com (a; b) = 1. Mostre que se
a
(a, b)
é par, então
b
(a, b)
é ímpar. Vale a recíproca?
Solução.
Exercício 6.2.10.
Um prédio possui duas escadarias, uma delas com 780 degraus e a outra com 700
degraus. Sabendo que os degraus das duas escadas só estão no mesmo nível quando con-
duzem a um andar, descubra quantos andares tem o prédio.
Solução.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
42
Pelo algoritmo de Euclides, temos 20 = 9(780)− 10(700).
Pela primeira escada, para chegar ao segundo andar temos que subir
780
20
= 39 degraus.
Para segunda escada para chegar ao segundo andar andar temos que subir
700
20
= 35
degraus.
O prédio tem 20 andares.
Exercício 6.2.11.
Calcule (1116, 984, 852).
Solução.
Partindo do princípio que o máximo divisor de dois números a e b não pode ultrapassar
ao máximo divisor comum de três números. a, b e c temos o seguinte.
Pelo algoritmo de Euclides obtemos 1116 = (1)× 852 + 264, de onde
12 = (−29)(1116) + (38)(852) = (1116, 852)
Logo, (1116, 984, 852) = ((1116, 852), 984) = (12, 984).
Observe que 984 = (82)× 12 + 0, então 12 = (12, 984).
Portanto, (1116, 984, 852) = 12.
Exercício 6.2.12.
Mostre que se três números inteiros são tais que dois deles são coprimos, então eles são
coprimos. Mostre que não vale a recíproca; isto é, exiba três números inteiros coprimos
mas que não são dois a dois coprimos.
Solução.
A demonstrar que: Se (a, b) = 1 , (a, c) = 1 e (b, c) = 1 então (a, b, c) = 1.
Suponhamos a, b, c ∈ N tais que (a, b) = 1, (a, c) = 1 e (b, c) = 1.
(a, b, c) = ((a, b) , c) = (1, c) = 1 ou (a, (b, c)) = (a, 1) = 1 ou = (b, (a, c)) = 1
Em qualquer caso (a, b, c) = 1.
Portanto, se (a, b) = 1 e (a, c) = 1 e (b, c) = 1 então (a, b, c) = 1.
A recíproca é
Se (a, b, c) = 1 então (a, b) = 1 e (a, c) = 1 e (b, c) = 1
Por contra-exemplo.
Temos (6, 14, 21) = 1 observe que (6, 14) = 2 ̸= 1 e (6, 21) = 3 ̸= 1 e
(14, 21) = 7 ̸= 1
Portanto, a recíproca nem sempre é verdadeira.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
43
Exercícios suplementares
Exercício 6.2.13.
Suponha que (a, b) = (a, d) = (c, b) = (c, d) = 1.
a) Mostre que, se n ∈ N, então (a+ b, bn) = (a− b, bn) = 1.
Demonstração.
a) Suponhams a ̸= b então a− b ̸= 0, como (a, b) = 1, então existem x, y ∈ Z tais que
1 = ax+ by = (a− b)x+ b(y + x) ⇒ 1 = (a− b, b)
Como (a − b, b) = 1, (1, bm−1) = 1 e pela parte a) deste exercício segue que
(a− b, bm) = 1 para todo m ∈ N.
De modo análogo 1 = ax + by = (a + b)x + b(y − x) ⇒ 1 = (a + b, b),
(1, bm−1) = 1 e pela parte b) deste exercício segue que (a+ b, bm) = 1 para todo
m ∈ N.
Portanto, se a ̸= b e n ∈ N, então (a+ b, bn) = (a− b, bn) = 1.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
44
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
MA-14 - Aula 04
Semana 26/08 a 01/09
Unidade 7
7.2 Mínimo Múltiplo Comum: Problemas
Exercício 7.2.1.
Calcule o mmc dos pares de números.
a) 38 e 46 b) 35 e 75 c) 235 e 740
Solução.
Exercício 7.2.2.
Mostre o seguinte:
a) Sejam a, b ∈ Z não nulos e seja n ∈ N; mostre que [na, nb] = n[a, b].
b) Se m é um múltiplo comum de a e b, mostre que m = [a, b] ⇔ (
m
a
,
m
b
) = 1.
c) Se r e s não são nulos e ra = sb, mostre que
ra
(r, s)
=
sb
(r, s)
= [a, b].
Demonstração.
45
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
46
a) Pela Proposição 1 da Unidade 7, segue que [na, nb](na, nb) = na · nb então
na · nb = n · [na, nb](a, b) ⇒ n ·
ab
(a, b)
= [na, nb] ⇒ n[a, b] = [na, nb]
Portanto, se a, b ∈ N e n ∈ Z temos [na, nb] = n[a, b].
b) Se m é um múltiplo comum de a e b, então a|m e b|m, logo m = βa e m = αb
Como m = [a, b], então pela Proposição 1 da Unidade 7 segue que [a, b] · (a, b) = ab
de onde (ma, mb) = ab assim,
1
ab
(ma, mb) = 1 ⇒ (
m
b
,
m
a
) = 1
Portanto, se m = [a, b] ⇒ (
m
a
,
m
b
) = 1..
Inversamente (⇐)
Suponhamos que (
m
a
,
m
b
) = 1, como m é múltiplo de a e b, segue que m = βa e
m = αb então (α, β) = 1.
De onde (m · α, m · β) = m, sendo m · α e m · β múltiplos de a e b, e como m|mα e
m|mβ, e m é o menor dos múltiplos de a e b, segue que m = [a, b].
Portanto, (
m
a
,
m
b
) = 1. ⇒ m = [a, b].
c) Sendo r e s não nulos, logo podemos dividir por esses números. Sabe-se que [a, b] ·
(a, b) = ab então [a, b] =
ab
(a, b)
=
ra · b
r(a, b)
=
rab
(ra, rb)
=
rab
(sb, rb)
=
ra
(r, s)
.
De modo análogo, temos [a, b] =
ab
(a, b)
=
sa · b
s(a, b)
=
sab
(sa, sb)
=
sab
(sa, ra)
=
sb
(r, s)
.
Portanto, se ra = sb entãora
(r, s)
=
sb
(r, s)
= [a, b].
Exercício 7.2.3.
Sejam a, b, c três números naturais não nulos. Mostre que abc = [a, b, c](ab, ac, bc).
Demonstração.
Seja d = (a, b), como (ab, ac, bc) = (ab, (ac, bc)) então
(ab, ac, bc) = (ab, (ac, bc)) = (ab, c(a, b)) = (ab, cd) ⇒
(ab, ac, bc) = (ab, cd) =
abcd
[ab, cd]
(7.9)
Por outro lado, [a, b, c] = [[a, b], c] = [
ab
d
, c] = [am, c] onde b = md.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
47
Em (7.9)
(ab, ac, bc) =
abcd
[ab, cd]
=
abcd
[amd, cd]
=
abcd
[amd, cd]
=
abc
[am, c]
(ab, ac, bc) =
abc
[am, c]
=
abc
[a, b, c]
⇔ (ab, ac, bc)[a, b, c] = abc
Exercício 7.2.4.
Seja n ∈ N; calcule [n2 + 1, n+ 1].
Demonstração.
Temos pela Proposição 9 unidade 1, que (n2+1, n+1) = ((n2−1)+2, n+1) = (2, n+1).
Supondo que 2|n2+1 ou n+1|n2+1 segue que n = 0 ou n = 1. Logo (n2+1, n+1) = 1
ou (n2 + 1, n+ 1) = 2.
Suponhamos que (n2 + 1, n+ 1) = 1, então n-par e,
[n2 +1, n+1] · (n2 +1, n+1) = (n2 +1) · (n+1) ⇒ [n2 +1, n+1] = n3 +n2 +n+1
Suponhamos que (n2 + 1, n+ 1) = 2, então n-ímpar e,
[n2+1, n+1] · (n2+1, n+1) = (n2+1) · (n+1) ⇒ [n2+1, n+1] =
1
2
(n3+n2+n+1)
Exercício 7.2.5.
a) Mostre que (a, b) = [a, b] ⇔ a = b.
b) Mostre que, [an, bn] = [a, b]n, a, b ∈ Z, n ∈ N.
c) Mostre que, se b = a2, então, [a, b] = (a, b)2.
Demonstração.
a) Seja (a, b) = [a, b], então pela Proposição 1 da Unidade 7 [a, b] · (a, b) = ab ⇒
[a, b]2 = ab.
Como m = [a, b] é tal que m = βa e m = αb segue
m2 = (βa)2 = ab ⇒ β2a = b ou m2 = (αb)2 = ab ⇒ α2b = a
Substituindo um no outro α2(β2a) = a ⇒ (αβ)2 = 1 ⇒ α = β = 1, logo
a = b.
Inversamente, suponhamos que a = b.
Temos [a, b] = [a, a] = a e (a, b) = (a, a) = a, assim [a, b] = (a, b).
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
48
b)
c) Mostre que, se b = a2, então, (a, b) = (a, a2) = a. Por outro lado, [a, b] = [a, a2] = a2.
Destas duas igualdades, segue que [a, b] = [a, a2] = a2 = (a, b)2
Portanto, se b = a2, então, [a, b] = (a, b)2.
Exercício 7.2.6.
Sejam a, b ∈ Z ambos não nulos. Considere o conjunto
M(a, b) = aZ ∩ bZ = { x ∈ Z; ∃ n, m ∈ Z tais que x = na e x = mb }
a) Mostre que [a, b] = min {M(a, b) ∩ N}.
b) Mostre que M(a, b) = [a, b]Z .
Demonstração.
a) Seja x ∈ M(a, b), então ∃ n, m ∈ Z tais que x = na e x = mb. Quando m = n = 1
temos que x = a = b ∈ Z, logo M(a, b) ̸= ∅ ainda mais, M(a, b) ⊂ N.
Pelo princípio da Boa Ordem, existe P ∈ M(a, b) tal que P = n0a e P = m0b
para algum m0, n0 ∈ N além disso P ≤ x para todo x ∈ M(a, b). Portanto,
P = min M(a, b).
Suponhamos que [a, b] = c, então a|c e b|c, logo c = βa e c = αb onde α, β ∈ N.
Pela definição de M(a, b) segue que c ∈ M(a, b).
Como P é múltiplo comum de a e b então c|P , assim c ≤ P .
Por outro lado, sendo P o menor elemento de M(a, b), então P ≤ x para todo
x ∈ M(a, b), em particular para c, assim P ≤ c
Das duas últimas desigualdades P = c = [a, b] = min M(a, b).
Portanto, P = [a, b] = min M(a, b).
b) Pela parte (a) temos que qualquer elemento de x ∈ M(a, b) é múltiplo de P , isto é
x = γP , onde γ ∈ N
Portanto, todo elemento de M(a, b) é múltiplo de min M(a, b).
Exercício 7.2.7.
Sejam d,m ∈ N . Mostre que uma condição necessária e suficiente para que existam
a, b ∈ Z tais que (a, b) = d e [a, b] = m é que d|m.
Demonstração.
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
49
Condição necessária (⇒)
Suponhamos que m = [a, b], então m =
ab
(a, b)
= a ·
b
(a, b)
= b ·
a
(a, b)
, logo a|m e
b|m
Por hipótese (a, b) = d logo a = αd e b = ηd isto é d|a e d|b.
Assim, a|m e d|a logo d|m, de modo análogo b|m e d|b logo d|m
Condição suficiente (⇐)
Suponhamos que d|m, então existe β ∈ N tal que m = βd. Sabemos que (β, 1) = 1
logo (βd, d) = d
Chamando a = βd e b = d temos que existe, a, b ∈ Z tal que (a, b) = d.
Por outro lado, pela definição de a e b temos que a|m e b|m, logo m é múltiplo
comum de a e b.
Sabemos que [a, b] =
ab
(a, b)
=
ad
d
= a = m.
Portanto se d|m, existem a, b ∈ Z tais que (a, b) = d e [a, b] = m é que .
Exercício 7.2.8.
Sejam a1, · · · , an ∈ Z r {0}. Mostre que
(ai, aj) = 1, i ̸= j ⇔ [a1, · · · , an] = a1 · · · an
Demonstração.
Indução sobre n ∈ N.
Condição necessária (⇒)
Se n = 2 temos (a1, a2) = 1, ⇒ [a1, a2](a1, a2) = a1a2 isto é [a1, a2] = a1a2 é
verdade.
Suponhamos para h ∈ N,sejam a1, · · · , ah ∈ Z tais que
(ai, aj) = 1, i ̸= j ⇒ [a1, · · · , ah] = a1 · · · ah
Seja h + 1 ∈ N e (ai, aj) = 1, i ̸= j, ∀ i, j = 1, 2, . . . , h, h + 1, sabemos pela
Proposição 5.3.2. do livro 2 que
[a1, · · · , ah, ah+1] = [a1, a2, a3, · · · , [ah, ah+1]]
Da hipótese (ah, ah+1) = 1 ⇒ [ah, ah+1] = ahah+1, logo
[a1, · · · , ah, ah+1] = [a1, a2, a3, · · · , (ahah+1)] =
Como (ai, ah) = 1 e (ai, ah+1) = 1 ⇒ (ai, ahah+1) = 1, ∀ i = 1, 2, . . . , h− 1.
2“Elementos de Aritmética” de A Hefez
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
50
Assim, temos da hipótese indutiva
[a1, · · · , ah, ah+1] = a1a2a3 · · · (ahah+1) = a1a2a3 · · · ahah+1
Condição suficiente (⇐)
Suponhamos que [a1, a2] = a1a2 seja verdade, então [a1, a2] =
a1a2
(a1, a2)
= a1a2 de onde
(a1, a2) = 1
Para qualquer h ∈ N suponhamos que
[a1, · · · , ah] = a1 · · · ah ⇒ (ai, aj) = 1, i ̸= j ∀ i, j = 1, 2, . . . , h
Para h+ 1 ∈ N temos
[a1, · · · , an, an+1] = a1 · · · anan+1 =
a1 · · · anan+1
(a1, · · · , an, an+1)
logo (a1, · · · , an, an+1) = 1. Pela Proposição 5.2.2. do livro 3 que
1 = (a1, · · · , ah, ah+1) = (a1, a2, a3, · · · , ah−1, (ah, ah+1)) ⇒
temos (ai, aj) = 1, i ̸= j ∀ i, j = 1, 2, . . . , h − 1 sendo d = (ah, ah+1), também
(ai, d) = 1, ∀ i = 1, 2, . . . , h− 1. Para dois elementos temos
[ah, ah+1] =
ahah+1
(ah, ah+1)
= ahah+1 ⇒ (ah, ah+1) = 1
[ai, ah+1] =
aiah+1
(ai, ah+1)
= aiah+1 ⇒ (ai, ah+1) = 1, ∀ i = 1, 2, . . . , h− 1
Portanto, (ai, aj) = 1, i ̸= j, ∀ i, j = 1, 2, . . . , h, h+ 1.
Exercício 7.2.9.
Sejam a, b, c ∈ Z não nulos. Mostre que:
a) (a, [b, c]) = [(a, b), (a, c)]; b) [a, (b, c)] = ([a, b], [a, c]).
Demonstração.
x
3“Elementos de Aritmética” de A Hefez
Document shared on https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/
Downloaded by: antonio-paulo-santos-1 (antoniopaulompb@gmail.com)
https://www.docsity.com/pt/aritmetica-solucao-de-todas-as-listas/5146064/?utm_source=docsity&amp;utm_medium=document&amp;utm_campaign=watermark
51
Unidade 8
Equações Diofantinas Lineares
8.2 Equações Diofantinas Lineares: Problemas
Exercício 8.2.1.
Resolva em Z as equações:
a) 90X + 28Y = 22 b) 50X + 56Y = 74
c) 40X + 65Y = 135 d) 8X + 13Y = 23
Solução.
a) 90X − 28X = 22 ⇒ 45X − 14Y = 11 como mdc{45, 14} = 1 e 45 = 3× 14 +
3, 14 = 4× 3 + 2, 3 = 1× 2 + 1, logo
1 = 3−(1)(2) = 3−(1)(14−4×3) = 5×3−14 = 5(45−3(14))−14 = 5(45)−16(14)
Assim, 45(5)− 14(16) = 1 ⇒ 45(55 + 14t)− 14(176 + 45t) = 11
Portanto, X = 55 + 14t, Y = 176 + 45t, ∀ t ∈ Z.
b) Primeira solução: 50X − 56Y = 74 ⇒ 25X − 28Y = 37 como mdc{25, 28} = 1
e 28 = 1×25+3, 25 = 8×3+1, logo 1 = 25−8(3) = 25−8(28−25) = 9×25−8(28)
Assim, 25(9)− 28(8) = 1 ⇒ 25(333)− 28(296) =