lista_inducao_aritmetica_modular_fermat

Prévia do material em texto

Lista 3: indução
1. Resolva as questões 1, 2, 3 e 4 da página 100.
2. Considere a recorrência an = an−1 + (n+ 1)2n, onde a1 = 4.
(1) Calcule an/n para alguns valores pequenos de n, compare o resultado
com os valores de n e advinhe uma fórmula para an.
(2) Prove que sua fórmula é verdadeira para todo n ≥ 1 usando indução em
n. Indique claramente cada etapa do método de indução.
3. O objetivo desta questão é obter e provar uma fórmula para a soma dos cubos
dos n primeiros inteiros positivos. Seja, então,
Sn = 1
3 + 23 + 33 + · · ·+ n3.
(a) Tabele os valores de Sn para n de 1 a 6 e compare-os com os valores
cor-respondentes para a soma dos n primeiros inteiros positivos. Use isto
para advinhar qual deve ser a fórmula para Sn.
(b) Prove a fórmula obtida em (1) por indução finita.
4. Considere o produto
An =
(
1 +
1
1
)(
1 +
1
2
)(
1 +
1
3
)
· · ·
(
1 +
1
n
)
.
Tabele os valores de An para n = 1, . . . , 5. Use estes valores para advinhar
uma fórmula simples para o produto. Prove que a sua fórmula é verdadeira
para qualquer n usando indução finita.
5. Mostre, por indução em n, que 24 divide 52n − 1 para todo n ≥ 1. Indique
claramente cada etapa da demonstração por indução.
6. Prove, por indução em n, que n! ≥ 4n para todo n ≥ 9.
7. Considere a recorrência definida por
S0 = 4 e Sk+1 = S2k − 2.
e sejam ω = 2 +
√
3 e ω = 2−√3. Prove, por indução em n, que
Sn = ω
2n + ω2
n
,
para todo n ≥ 1.
8. Os números binomiais são definidos pela fórmula:(
n
k
)
=
n!
k!(n− k)! .
1
2
(a) Prove, direto da definição acima, que(
n
k
)
+
(
n
k − 1
)
=
(
n+ 1
k
)
.
(b) Use (a) e indução em n para provar que
(x+ 1)n =
n∑
k=0
(
n
k
)
xn
em que x é um inteiro qualquer.
9. Seja m ≥ 10900 um inteiro fixado. Prove, por indução em n, que(
n+m
m
)
≥ 2(n+ 1)
para todo n ≥ 1. Indique claramente cada etapa da indução. Dica: relacione(
n+m
m
)
com
(
n−1+m
m
)
10. Seja a > 23452552! um número inteiro e considere a soma
Sn =
1
a(a+ 1)
+
1
(a+ 1)(a+ 2)
+ · · ·+ 1
(a+ n− 1)(a+ n) .
Prove, por indução em n, que a soma acima é sempre igual a n/a(a + n).
Você deve identificar claramente a base da indução, a hipótese de indução e
a recursão que vai ser utilizada.
3
Lista 4: aritmética modular e o teorema de Fermat
1. Resolva as questões 1, 2, 3, 4, 6, 7 e 8 da página 85 do livro-texto.
2. Resolva as questões 6, 7, 8, 9 e 11 da página 101 e 14 e 15 da página 102 do
livro-texto.
3. Determine qual é a maior potência de 2 que divide 3227 + 1.
4. Definição: a ordem k de uma classe a ∈ Zn é a menor potência diferente de
1 tal que ak ≡ 1 mod n. Determine um elemento de ordem
(a) 6 módulo 7;
(b) 3 módulo 7;
(c) 16 módulo 17;
(d) 8 módulo 32;
(e) 10 módulo 31;
(f) 7 módulo 31.
5. Calcule a ordem de 97 módulo 233 e use isto para achar o resto da divisão de
97234111 por 233.
6. Calcule:
(a) a ordem de 5 módulo 14 e a ordem de 7 módulo 113.
(b) o resto da divisão de 725100 por 113.
7. Calcule o resto da divisão de
(a) 3267! por F (4) = 224 + 1;
(b) 321024 por 31.
8. A seguinte afirmação é verdadeira ou falsa? Justifique sua resposta.
Qualquer que seja n ≥ 1 inteiro, o número 424n+1 + 32(18n2+1) é
divisível por 13.
9. Prove por indução em n que se n ≥ 2, então
23
n−2 ≡ 3n−1 − 1 (mod 3n).
10. Seja p 6= 2 um número primo, n = 10p − 1 e q > 3 um fator primo de n.
Calcule a ordem de 10 módulo q.
11. Sabendo-se apenas que p é primo, determine o resto da divisão de
(a) 1p−1 + 2p−1 + · · ·+ (p− 1)p−1 por p;
(b) 2p! − 1 por 2p+1 − 1.
4
De que maneira estes restos dependem de p?
12. Determine todos os primos positivos p para os quais a equação
2x+ xp + xp! ≡ 1 (mod p)
tem solução x 6≡ 0 (mod p).
13. Calcule, se existir, o inverso de
(a) 3 módulo 125;
(b) 6 módulo 123;
(c) 123 módulo 1001.
14. Seja n > 173452552 um número inteiro. Mostre que se (n− 1)! ≡ −1 (mod n)
então n é primo. Dica: mostre que nenhum 1 ≤ d ≤ n− 1 é fator de n.
15. Seja p > 2 um primo. Dizemos que um inteiro a 6≡ 0 (mod p) é um resíduo
quadrático módulo p se existe um inteiro b tal que a ≡ b2 (mod p). Determine
todos os resíduos quadráticos quando p = 5, p = 7 e p = 11.
16. Seja p > 2 um primo. Mostre que o produto de dois resíduos quadráticos
módulo p é um resíduo quadrático módulo p.
17. Seja p > 2 um primo e a um resíduo quadrático módulo p. Mostre que o
inverso de a módulo p também é um resíduo quadrático módulo p.
18. Seja p = 2m + 1 um número primo positivo. Mostre que se b é um resíduo
quadrático módulo p então bm ≡ 1 (mod p).