lista_P1

Prévia do material em texto

Lista 0: revisão de tópicos do ensino médio
1. Por definição temos que se b é um número real e n um inteiro positivo, então
bn = b · b · · · b︸ ︷︷ ︸
n vezes
.
Prove, usando apenas esta definição, que se m e n são inteiros positivos, então
bn · bm = bn+m.
2. Determine quais das seguintes afirmações são falsas e quais são verdadeiras.
Demonstre aquelas que são verdadeiras e dê um contra-exemplo para as que
são falsas.
(a) Se a é um inteiro cujo quadrado é par, então a é par.
(b) Se a é um inteiro cujo quadrado é divisível por 3, então a é divisível por
3.
(c) Se a é um inteiro cujo quadrado é divisível por 27, então a é divisível por
27.
3. Calcule
(a) (x− y)(x+ y);
(b) (x− y)(x2 + xy + y2);
(c) (x− y)(x3 + x2y + xy2 + y3).
4. Considere a progressão geométrica de razão q e primeiro termo a e seja S a
soma dos seus n primeiros termos. Isto é:
S = a+ aq + aq2 + · · ·+ aqn−1.
Faça o que se pede:
(a) Calcule (q − 1)S = qS − S em termos de a e q.
(b) Use o item anterior para determinar a fórmula da soma S.
Aparte: por que n− 1 e não n na última parcela da soma definida acima?
5. Ao longo do curso usaremos como símbolos várias letras do alfabeto grego.
Para o caso de você não conhecê-las, aqui vão as mais frequentemente usadas
com seus respectivos nomes. Para aprender a desenhá-las corretamente visite
a página http://www.foundalis.com/lan/hw/grkhandw.htm.
1
2
α β γ δ θ λ µ
alfa beta gama delta teta lambda mi
pi ρ σ τ φ ψ ω
pi rô sigma tau fi psi omega
Lista 1: algoritmos básicos
1. Resolva os exercícios 1, 2, 3, 4 e 5 da página 32 do livro-texto.
2. A sequência de Fibonacci Fn é definida por
F0 = F1 = 1 e Fn = Fn−1 + Fn−2.
Calcule o quociente e o resto da divisão de Fm por Fm−2, quando m for um
inteiro maior do que 23452552!.
3. Determine o máximo divisor comum entre p2 − p + 1 e (p2)! + 1, sabendo-se
que p é um primo positivo. De que modo a resposta depende de p ?
4. Seja n > 2100! um número inteiro. Determinemdc(6n+1, 6n!+(n−1)!+6n−3).
5. Ache infinitas soluções inteiras da equação 23303x+ 2359y = 21.
6. Determine múltiplos de 330 e de 240 cuja soma seja 210.
7. Determine números inteiros x e y que sejam soluções da equação 7001x +
503y = 2 e prove que esta equação tem infinitas soluções inteiras.
8. Seja n > 2100! um número inteiro. Use o algoritmo euclidiano estendido
para calcular d = mdc(5n + 3, 3n + 2) e dois inteiros α e β tais que d =
(5n+ 3)α + (3n+ 2)β.
9. Determine mdc(a, c) sabendo-se que a, b e c são inteiros maiores que 2200! e
que c divide a+ b e mdc(a, b) = 1;
10. Use o algoritmo euclidiano estendido para determinar um inteiro a de modo
que 6765 · a− 1 seja divisível por 10946.
3
Lista 2: primos e fatoração
1. Resolva as seguintes questões do livro-texto:
(a) 1, 2, 3, 5, 6 e 7 da página 48-49;
(b) 3, 4, 5, 6, 7, 8 e 9 da página 66.
2. Determine o maior número possível de fatores primos de um inteiro n que não
tem nenhum fator ≤ n1/3.
3. Determine dois fatores próprios de 6883901 e de 999367 pelo algoritmo de
Fermat.
4. Sejam 2 < p < q dois primos ímpares e seja n = pq. Determine o número de
tentativas para achar x que o algoritmo de Fermat terá que fazer até obter
um fator próprio de n.
5. Considere os números primos p1 < · · · < pr. Seja N = p1 · p2 · · · pr o produto
destes primos e
S =
N
p1
+
N
p2
+ · · ·+ N
pr
.
(a) Mostre, por contradição, que S é um número inteiro que não é divisível
por nenhum dos primos p1, p2, · · · , pr.
(b) Use (a) para dar uma demonstração (por contradição) de que existem
infinitos números primos.
6. O objetivo desta questão é dar uma outra demonstração de que existem in-
finitos números primos. Para isso, suponha que exista um número finito de
primos, que são todos menores que um número inteiro positivo n ≥ 3.
(a) Mostre que, sob a hipótese acima, teríamos que ter que mdc(n!− 1, n!) é
diferente de 1.
(b) Mostre que (a) leva a uma contradição, e use isto para provar que existem
infinitos números primos.