Universidade do Minho L.E.M., L.M.C.C. - 4$^\circ$ ano

Departamento de Matemática Mat. (Esp. Ensino), L.C.C. - 3$^\circ$ ano

Teoria de Números Computacional

folha ii $2^\circ$ semestre, 2006/2007

1. Recorde a sucessão de Fibonacci $(f_n)$ : $f_1=1,f_2=1, f_n=f_{n-1}+f_{n-2}$ , para $n\ge 3$ .
   1. Prove que $$\sum_{k=1}^n f_k=f_{n+2}-1$$ . [Repare que $f_k= f_{k+2}-f_{k+1}$ , com $k\in {\mathbb{N}}$ .]
   2. Use o segundo princípio de indução para mostrar que $f_n >\alpha^{n-2}$ , onde $\alpha =\frac{1+\sqrt{5}}{2}$ é o número de ouro ou número áureo. [Repare que $\alpha$ é solução de $x^2-x-1=0$ .]
   3. Mostre que se $a_n=\frac{1}{\sqrt{5}}(\alpha^n-\beta^n)$ , onde $\alpha =\frac{1+\sqrt{5}}{2}, \beta =\frac{1-\sqrt{5}}{2}$ , então $a_n=a_{n-1}+a_{n-2}$ e $a_1=a_2=1$ . Conclua que $f_n=a_n$ .
   4. Mostre que o quociente da divisão inteira de termos consecutivos da sucessão de Fibonacci é 1.
   5. Sejam $f_{n+1},f_{n+2}$ termos consecutivos da sucessão de Fibonacci, com $n>1$ . Mostre que o algoritmo de Euclides tem exactamente $n$ passos para mostrar que $(f_{n+1},f_{n+2})=1$ .

2. Use o algoritmo estendido de Euclides¹ para encontrar $s,r\in {\mathbb{Z}}$ para os quais $(a,b)=as+br$ , onde $a$ e $b$ são, respectivamente,
   1. 45, 75
   2. 666, 1414
   3. 102, 222
   4. 20785, 44350
   5. 34709, 100313
   6. 9876543210, 123456789
   7. 11111111111, 1000000001
   8. 45666020043321, 73433510078091009

3. Implemente uma função no pari/gp que tenha como argumento um natural $n>2$ e como retorno a lista dos números primos não superiores a $n$ , fazendo uso do crivo de Eratóstenes.

4. Implemente uma função no pari/gp que teste a primalidade de um número à custa da divisão trivial.