Lista___Aritimética

Prévia do material em texto

Lista Aritimética
1. Mostre que se (a, b) = 1, então (ac, b) = (c, b).
Sejam d = (ac, b) e e = (c, b). Como d = (ac, b), existem r, s ∈ N tais que
ac · r + b · s = d.
Logo, temos c · [ar] + b · [s] = d. Portanto, e | d.
Resta mostrar que d | e. Seja d = (ac, b). Temos que d | ac e d | b. Como (d, a) | a e (d, a) | d, e
d | b, então (d, a) | (a, b) = 1, o que implica que (d, a) = 1. Portanto, d | ac e (d, a) = 1 implica que
d | c. Como d | b, temos que d | e.
2. Verdadeiro ou Falso.
(a) (a, b, a+ b) = (a, b).
VERDADEIRA. Seja d = (a, b, a+ b) e e = (a, b). Como d | a e d | b, temos d | e. Como e | a
e e | b, temos e | a+ b e e | d. Logo, d = e.
(b) (a+ b, c) = (a, c) + (b, c).
FALSO. Temos (1 + 2, 3) = (3, 3) = 3 ̸= 1 + 1 = (1, 3) + (2, 3).
(c) (a, bc) = b · (a, c).
FALSO. Temos 1 = (1, 6) = (1, 2 · 3) ̸= 2 · 1 = 2 · (1, 3).
(d) Se a | b ⇒ [a, b] = b
VERDADEIRO. Como a | b → (a, b) = a. Como a · b = (a, b) · [a, b] ⇒ [a, b] = b.
(e) (a, b) = [a, b] ⇐⇒ a = b.
VERDADEIRO.A volta é imediata!
Sejam, p1, p2, . . . , pn todos os primos que a aparecem na decomposição de a e b. Desta forma,
a = pα1
1 . . . pαn
n em que αi ≥ 0 e b = pβ1
1 . . . pβn
n em que βi ≥ 0.
Como (a, b) = pγ11 . . . pγnn em que γi = min{αi, βi} e [a, b] = pδ11 . . . pδnn em que δi = max{αi, βi}.
Como (a, b) = [a, b] ⇒ min{αi, βi} = max{αi, βi} ⇒ αi = βi para todo i ⇒ a = b.
(f) Se a e b são de paridades distintas, então (a, b) = 1
FALSO. Considere o caso: (3, 6) = 3.
(g) ar + bs = 1 ⇒ (a, s) = (r, b) = (r, s) = 1
VERDADEIRO. É imediato, para cada um dos casos existe uma combinação destes que
resulta em 1, logo o mdc de cada um destes vale 1.
3. a | bc ⇒ a | b ou a | c
Isso é FALSO, basta tomar a = 6, b = 2 e c = 3.
4. (a, a+ 2) = 1 ou 2.
Como (a, a+ 2) = (a, 2) temos que, se a for ímpar, então (a, 2) = 1 e se a for par, então (a, 2) = 2.
1
5. (a, 4) = (b, 4) = 2 ⇒ (a+ b, 4) = 4
Como (a, 4) = 2 segue que a = 2k em que (k, 2) = 1 isto é, k é impar. Analogamente, b = 2q em que
q é ímpar. Logo, a+ b = 2k + 2q = 2(k + q). Como k + q = 2p, segue que a+ b = 2 · 2p = 4p.
Logo, (a+ b, 4) = (4p, 4) = 4 · (p, 1) = 4.
6.
(
2n+ 1,
n(n+ 1)
2
)
= 1 para todo n
NÃO CONSEGUI FAZER AINDA.
7. Sejam a, b, c ∈ N
(a) Se a | b e (b, c) = 1 ⇒ (a, c) = 1
Como a | b → b = ak e pelo fato de (b, c) = (ak, c) = 1 → ∃r, s : (ak)r+ cs = 1 → a(kr) + cs =
1 ⇒ (a, c) = 1
(b) (a, c) = (b, c) = 1 ⇐⇒ (ab, c) = 1
Ida: Como (a, c) = 1 → (ab, c) = (b, c) = 1.
Volta: Como (ab, c) = 1 → ∃r, s : (ab)r + cs = 1 → a(br) + cs = 1 e b(ar) + cs = 1 ⇒ (a, c) =
(b, c) = 1.
8. Determinar todos a, n ∈ Z tais que a+ 1 | a2n+1 − 1.
Proposição 3.8 livro Abramo H.: Sejam a, b ∈ Z e n ∈ N ∪ {0}. Temos a+ b | a2n+1 + b2n+1.
Tomando b = 1 concluímos que: a+ 1 | a2n+1 + 1.
Como queremos garantir que a+ 1 | a2n+1 − 1 ⇒ a+ 1 | (a2n+1 + 1)− 2 ⇒ a+ 1 | −2. Desta forma,
a+ 1 = ±1 e a+ 1 = ±2 ⇒ S = {−3,−2, 0, 1},ou seja, a = 1 e n ∈ N ∪ {0}.
9. Dados a, b ∈ Z, prove que, para todo n ∈ N :
(a) (a, b) = 1 ⇐⇒ (an, bn) = 1.
Ida: Já vimos que se (a, b) = 1 → (ac, b) = (c, b). Tomando c = a, temos que (a2, b) = (a, b) =
1. Suponha que o resultado seja válido para n − 1, i.e., (an−1, b) = 1, queremos provar que
(an, b) = 1. De fato, como (an−1, b) = 1 ⇒ (an, b) = (an−1 · a, b) = (a, b) = 1. Mantendo fixo an
e fazendo a mesma demonstração para b, concluímos que (an, bn) = 1.
Volta: Seja d = (a, b) → a = dm e b = dn : (m,n) = 1. Logo, (ak, bk) = (dk ·mk, dk · nk) = dk ·
(mk, nk) = dk·1 = dk = (a, b)k, pela ida. Desta forma, se (an, bn) = 1 ⇒ (a, b)n = 1 ⇒ (a, b) = 1.
(b) an | bn ⇐⇒ a | b
Volta: Imediata, se a | b → b = k · a → bn = kn · an ⇒ an | bn.
Ida: Assuma que an | bn → bn = k · an. Logo, (an, bn) = |a|n e por outro lado, (an, bn) = (a, b)n.
Concluímos então que: (a, b) = |a|, ou seja, |a| | b e como a | |a| segue que a | b.
10. Não existem a, b ∈ Z : (a, b) = 3 e a+ b = 100.
Suponha, por absurdo, que existam tais a, b. Como (a, b) = 3 segue que a = 3m e b = 3n tais que
(m,n) = 1. Como também, a+ b = 100 → 3m+3n = 100 → 3 · (m+ n) = 100 ⇒ 3 | 100.. Absurdo!
Logo, tais a, b não existem.
2
11. Existem infinitos a, b ∈ Z : (a, b) = 5 e a+ b = 100.
Sejam a, b tais que (a, b) = 5 segue que a = 5m e b = 5n tais que (m,n) = 1. Como também,
a+ b = 100 → 5m+ 5n = 100 → 5 · (m+ n) = 100 → m+ n = 20.
Tome um caso particular: m = 7 + 5t e n = 13 − 5t. Logo, a = 35 + 25t e b = 65 − 25t com t ∈ Z
formam uma solução para cada t ∈ Z. Ou seja, tem infinitas soluções.
12. Mostar que 38 − 252 é composto e determinar dois de seus divisores próprios.
Note que:
38 − 252 = (34)2 − 252 = (34 − 25) · (34 + 25) = (81− 25) · (81 + 25 · (81− 25) = 106 · 56.
Logo, é composto e dois de seus divisores são: 106 e 56.
13. Fatorar de duas formas x6 − y6
x6 − y6 = (x3)2 − (y3)2 = (x3 − y3) · (x3 + y3)
x6 − y6 = (x2)3 − (y2)3 = (x2 − y2) · (x4 + x2y2 + y4)
14. Mostre que para cada inteiro n > 1, são compostos:
(a) n4 + 4
n4 + 4 = n4 + 4n4 + 4− 4n2 = (n2 + 2)2 − (2n)2 = (n2 − 2n+ 2) · (n2 + 2n+ 2)
(b) n4 + n2 + 1
n4 + n2 + 1 = n4 + 2n2 + 1− n2 = (n2 + 1)2 − n2 = (n2 − n+ 1) · (n2 + n+ 1)
(c) 8n − 1
8n + 1 = (23)n + 1 = (2n)3 + 1 = (2n + 1) · (4n − 2n + 1)
15. Sejam a, b ∈ Z, p um primo e (a, b) = p. Quais os valores possíveis para:
(a) (a2, b2)
Já vimos que (an, bn) = (a, b)n, desta forma: (a2, b2) = (a, b)2 = p2.
(b) a2, b
O único primo em comum à a, b é p,com expoente mínimo igual a 1 em ambas fatorações, desta
forma: acontece alguma das situações:
i. a = p · k e b = p · q com (k, q) = 1
Assim, (a2, b) = p
ii. a = p1+n · k e b = p · q com (k, q) = 1 e n ≥ 1
Assim, (a2, b) = p
3
iii. a = p · k e b = p1+n · q com (k, q) = 1 e n ≥ 1
Assim, (a2, b) = (p2, p1+n) = p2
(c) (a3, b2)
De forma análoga, vamos analisar os casos:
i. a = p · k e b = p · q com (k, q) = 1
Assim, (a3, b2) = (p3, p2) = p2
ii. a = p1+n · k e b = p · q com (k, q) = 1 e n ≥ 1
Assim, (a3, b2) = (p3+3n, p2) = p2
iii. a = p · k e b = p1+n · q com (k, q) = 1 e n ≥ 1
Assim, (a3, b2) = (p3, p3+3n) = p3
16. Determine inteiros positivos a e b tais que a+ b = 396 e [a, b] = 10185.
Como [a, b] =
a · b
(a, b)
e podemos fatorar 10185 como 3 · 5 · 7 · 97, temos que os inteiros que procuramos
podem ter somente esses 4 primos em sua decomposição. Vamos agora procurar uma composição
destes de modo que a soma dê 396.
É fácil ver que um dos inteiros deve ser o 3 · 97 = 291, já que ou o 97 está só ou multiplicado por 3,
e assim o outro inteiro será o 3 · 5 · 7 = 105.
17. Se n > 4 é composto e p o menor primo que divide n, então n | (n− p)!
Usando a questão anterior, que é a dica da questão a ser resolvida, vemos que n | (n−2)!. Queremos
provar que, se p for o menor primo que divide n, então n | (n− p)!.
Para tal, vamos usar que, (n, n− i) = (n,−i) = (n, i) e notar que como p é o menor primo que divide
n, então (n, i) = 1 para todo i ≤ p. Desta forma, (n, n− i) = 1 para todo i ≤ p.
Suponha, sem perda de generalidade que p ̸= 2, pois se p = 2 então o resultado é a questão anterior,
desta forma, como n | (n − 2)! = (n − p)! · (n − (p − 1)) · (n − (p − 2)) . . . (n − (p − (p − 2))) e
(n, n− (p− i)) = 1 para todo i = 1, 2, . . . , p− 2 implica que n | (n− p)! como queríamos mostrar.
(Usamos que se a | b · c e (a, c) = 1 ⇒ a | b.)
18. Encontre três soluções para a equação p2 + 1 = q2 + r2, em que, p, q e r são primos.
As soluções serão triplas da forma (p, q, r) e foi feito tentativa e erro considerando p ≥ q, r.
(7, 5, 5), (13, 11, 7) e (23, 19, 13).
19. Encontre todos os primos p que dividem 50!.
Neste caso, basta procurar todos os número primos que são menores do que 50. Assim, p ∈
{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}
20. Explique porque:
(a) n2 − 1 não é primo se n > 2.
Note que, n2−1 = (n−1) ·(n+1). Como n > 2 → n−1 ≥ 2 e n+1 ≥ 4, isto é, n é decomposto
em um produto de dois números que são maiores que 2, ou seja, não é primo.
4
(b) 3n − 1 não é primo se n > 1.
Note que,
3n − 1 = (3− 1) ·
(
n−1∑
i=0
3i
)
= 2 ·
n−1∑
i=0
3i,
como n > 1 → n− 1 ≥ 1,desta forma, a parte do somatório será maior ou igual a 4, isto é, n é
decomposto em um produto de dois números que são maiores que 2, ou seja, não é primo.
21. Se p ≥ q ≥ 5 são primos. Prove que 24 | p2 − q2.
Para responder essa questão, vamos usar que:
Se a | c e b | c e (a, b) = 1 ⇒ ab | c.
Para tal, vamos mostrar que 3 | p2 − q2 e 8 | p2 − q2.
• 3 | p2 − q2
Usando a dica do livro e vendo que se m ≥ 5 é primo então m = 6k+1 ou m = 6k−1 (ou 6k+5),
desta forma, m2 = 36k2 ± 12k + 1.
Como p, q são primos que satisfazem a condição acima, então p = 6k ± 1 e q = 6l ± 1. Logo,
p2− q2 = 36(k2− l2)+12(±k∓ l). Como 3 divide cada uma das parcelas das somas, concluímos
que 3 | p2 − q2.
• 8 | p2 − q2
Veja também que, se m ≥ 5 é primo então m = 4k+1 ou m = 4k− 1 (ou 4k+5), desta forma,
m2 = 16k2 ± 8k + 1.
Como p, q são primos que satisfazem a condição acima, então p = 4k ± 1 e q = 4l ± 1. Logo,
p2 − q2 = 16(k2 − l2) + 8(±k∓ l). Como 8 divide cada uma das parcelas das somas, concluímos
que 8 | p2 − q2.
22. Sejam p e q primos gêmeos. Prove que:
(a) pq + 1 é um quadrado perfeito.
Suponha, s.p.g., que p > q, como eles são gêmeos significa que existe um inteiro n tal que:
(q, n, p) são números inteiros consecutivos. Desta forma, q = n− 1 e p = n+ 1.
Assim, pq + 1 = (n+ 1) · (n− 1) + 1 = n2 − 1 + 1 = n2, ou seja, é um quadrado perfeito.
(b) Se q > p > 3, então 12 | p+ q.
Vamos usar que p, q são gêmeos e que um primo maior ou igual a 5 pode ser escrito da forma
6k ± 1.
• Suponha que p = 6k − 1
Como q > p então q = 6k + 1. Logo, p+ q = 12k, isto é: 12 | p+ q.
• Suponha que p = 6k + 1
Como q > p então q = 6k + 3 = 3(k + 1). Pelo fato de q ser primo, temos que k + 1 = 1,
ou seja, k = 0. Logo, q = 3.
Absurdo, pois por hipótese, q > p > 3.
5
Desta forma, concluímos que o resultado é verdadeiro e além disso, p é da forma 6k−1 [ou 6(k−
1) + 5] e q é da forma 6k + 1.
23. Mostre por meio de um exemplo que nem todo número natural pode ser escrito da forma p+ a2, em
que p é primo ou p = 1 e a > 0.
O número 25 será nosso contraexemplo. Repare que tanto p, a2