Exercícios de Matemática - Números e Divisibilidade

Prévia do material em texto

1a Lista de Exerćıcios
MA553 – 1o Semestre-2005
1. Construa as tábuas de adição e multiplicação na base 7. Desenvolva os algoŕıtimos para fazer essa operações. A
seguir escreva 3460, 251 e 3460 + 251 na base 7 e usando o algoŕıtimo desenvolvido antes, some os dois números
na base 7 e compare os resultados.
Notação: Dado um número natural n e uma “base” a se n = ar · ar + ar−1 · ar−1 + · · ·+ a0 · a0, 0 ≤ ai ≤ r é a
representação de n na base a escrevemos na = arar−1 . . . a0. Por exemplo 52 = 101, pois 5 = 1 · 20 +0 · 2+1 · 22.
Também 32 = 11 que somamos ao 52 pelo algoŕıtimo
101
11
1000
, coerente com 5 + 3 = 8 = 1 · 23 + 0 · 22 + 0 · 2 + 0 · 20.
2. Em que bases serão corretas as seguintes igualdades:
(3× 3)a = 10, (3× 3)a = 11, (3× 3)a = 12, 79a = 124, 72a = 2200.
3. Pode um número par ser representado em alguma base por 27? E por 37? Existe base a tal que um número
ı́mpar n tenha representação na = 72? E na = 82, pode ocorrer?
4. Qual a menor base a onde 301 (i.e. 3 · a2 + 0 · a1 + 1 · a0) representa um natural ao quadrado?
5. Se a > 2, mostre que na = 121 é um quadrado.
6. Se a > 4, mostre que na = 40001 é diviśıvel por ma = 221.
7. Prove que o produto de três números inteiros consecutivos é diviśıvel por 6 e que o produto de quatro números
consecutivos é diviśıvel por 24.
8. Para todo n ∈ Z vale que 4 - (n2 + 2)?
9. Se n ∈ Z é impar, então 8|(n2 − 1).
10. Prove que se x, y ∈ Z são impares, então x2 + y2 é par, mas 4 - (x2 + y2.
Definição: Chama-se principio de indução ao seguinte argumento: Seja P (n) uma propriedade associada a cada
natural n ≥ 1 para a qual sabemos que P (1) é verdade e se P (k) for verdade, então P (k + 1) também é verdade.
O prinćıpio de indução diz que nessas condições a propriedade P (n) valerá para todo natural n.
Por exemplo: Para todo natural n existe um inteiro q tal que n = 2q ou n = 2q + 1 (†).
Temos então que P (n) significa: Existe q ∈ Z tal que n = 2q ou n = 2q + 1. Neste exemplo temos P (1) =
exite q ∈ Z tal que 1 = 2q ou 1 = 2q+1. Então P (1) é verdade pois existe q = 0 que torna uma das alternativas
verdadeira. Tomando-se como hipótese que P (n) é verdadeira temos que n = 2q ou n = 2q + 1, para algum
q ∈ Z. Logo n + 1 = 2q + 1 no primeiro caso e n + 1 = 2q + 1 + 1 = 2(q + 1) no segundo caso. Isto é, da hipótese
P (n) pode-se deduzir P (n + 1). Logo podemos concluir que a afirmação (†) é sempre verdadeira. Isto é, (†) é
um teorema.
11. Prove por indução sobre n, n ∈ N que:
(a) n2 − n é par para todo n.
(b) Se x, y ∈ N, então (x + y)n =
n∑
i=1
(
n
i
)
xiyn−i
(c) Se X é um conjunto com n elementos e ℘(X) = conjunto das partes de X, i.e. ℘(X) = {A | A ⊆ X},
então ℘(X) tem 2n elementos.
12. Sejam n, m números inteiros com n > m ≥ 1. Mostre que: se o resto da divisão de n por m é r então o resto da
divisão de 2n − 1 por 2m − 1 é 2r − 1.
13. Sejam n > m ≥ 1 números inteiros. O objetivo desta questão é calcular o m.d.c.(22n + 1, 22m + 1).
(a) Usando que 22
k+1 − 1 = (22k + 1)(22k − 1), para todo k ∈ N, mostre que: 22n − 1 é múltiplo de 22m + 1.
Qual é o quociente desta divisão?
(b) Usando o item anterior mostre que o resto da divisão de 22
n
+ 1 por 22
m
+ 1 é 2.
(c) Usando o item anterior determine o m.d.c.(22
n
+ 1, 22
m
+ 1).
14. Sendo n ∈ N, n > 1, mostre as seguintes igualdades:
(a) m.d.c.(n, 2n + 1) = 1 (b) m.d.c.(2n + 1, 3n + 1) = 1 (c) m.d.c.(n! + 1, (n + 1)! + 1) = 1
15. Pergunta-se: Existem inteiros x e y tais que x + y = 100 e m.d.c.(x, y) = 3?
16. Sejam a, b ∈ Z inteiros tais que m.d.c.(a, 4) = 2 e m.d.c.(b, 4) = 2. Prove que m.d.c.(a + b, 4) = 4.
17. Encontre todos os pares de números inteiros positivos a, b tais que a < b, m.d.c.(a,b) = 10. Fazer o mesmo para
m.d.c.(a,b) = 100.
18. Para cada par de números inteiros a, b a seguir calcule o mdc entre eles e determine números inteiros x, y tais
que m.d.c.(a,b) = ax + by. (a) 14 e 35 (b) 6643 e 2873 (c) 7469 e 2464
19. Demonstre as afirmações abaixo:
(a) m.d.c.(m · a,m · b) = m ·m.d.c.(a,b).
(b) Sabendo-se que g|a e g|b, então m.d.c.(a
g
,
b
g
) =
1
g
m.d.c.(a,b).
(c) Se m.d.c.(a,m) = 1 = m.d.c.(b,m), então m.d.c.(a · b,m) = 1.
(d) Se c|a · b e m.d.c.(c, a) = 1, então c|b.
(e) Sabendo-se que a|c e b|c, se m.d.c.(a,b) = 1, então a · b|c.
(f) Sabendo-se que a|c e b|c e d = m.d.c.(a,b), então e = a · b
d
também divide c.
Definição: Dado p ∈ Z, dizemos que p é primo caso os únicos divisores de p sejam ± 1 e ± p.
20. Sejam a, b, p ∈ Z com p primo. Se p|a·b, então p|a, ou p|b. Mais geralmente, dados, um primo p, e a1, . . . , an ∈ Z
tais que p|a1 · a2 · · · an, então existe 1 ≤ i ≤ n tal que p|ai.
21. Seja p um número primo impar. Mostre que uma e somente uma das seguintes afirmações é verdadeira: 4|p + 1,
ou 4|p− 1.
22. Sejam p1, p2, . . . , pn primos distintos. Mostre que existe um primo q tal que q 6= p1, . . . , pn.
23. Mostre que todo número primo da forma 3k +1 é da forma 6k +1. Isto é verdade para qualquer número inteiro?
24. Mostre que um número positivo da forma 3k + 2 tem um fator primo p da mesma forma, i.e, existe p = 3s + 2,
primo, tal que p|(3k + 2).
25. Seja p um número primo, mostre que:
(a) p |
(
p
k
)
, para todo 1 ≤ k ≤ p− 1.
(b) Dados x, y ∈ Z, então p divide (x + y)p − xp − yp.
Definição: Para todo número real r seja [r] ∈ Z tal que [r] ≤ r e se n ∈ Z também satisfaz n ≤ r, então n ≤ [r].
O inteiro [r] é chamado de parte inteira de r e a função [ ] : R −→ Z é chamada de função maior inteiro.
Exemplos: [−3
2
] = −2, [ 3
2
] = 1, [
√
5] = 2, [−
√
5] = −3. Para todo inteiro n, [n] = n.
26. Sejam a, b ∈ Z, b 6= 0, tais que a = bq + r com 0 ≤ r < b. Então [a
b
] = q.
27. Sejam a, b ∈ Z com 0 < a ≤ b. Se n = [ b
a
], então o conjuto {a · j | 0 < a · j ≤ b } tem n elementos.
28. Quantos números inteiros existem entre 100 e 1000 que são múltiplos de 7?
29. Quantos inteiros positivos n ≤ 3600 existem que são co-primos com 3600. Dizemos que dis inteiros a e b são
co-primos se m.d.c.(a,b) = 1.
30. Quantos números inteiros positivos n ≤ 3600 existem que tem um fator 6= 1 em comum com 3600.
2