1. Utilize o algoritmo de Euclides para calcular $d=\mbox{mdc}(a,b)$ e inteiros $u,\ v$ tais que $ua+vb=d$, sendo
- $a=232$, $b=136$;
- $a=187$, $b=221$;
- $a=-25$, $b=5$;
- $a=-39$, $b=17$.
2. Seja $n$ um número maior que 1 e verifique as seguintes igualdades:
- $\mbox{mdc}(n,2n+1)=1$;
- $\mbox{mdc}(2n+1,3n+1)=1$;
- $\mbox{mdc}(n!+1,(n+1)!+1)=1$.
3. Denote por $F_n$ os termos da sequência de Fibonacci ($F_0=F_1=1$, $F_2=2$, etc).
- Mostre que $\mbox{mdc}(F_i,F_{i+1})=1$ para todo $i\geq 0$.
- Quantas divisões são necessárias para calcular $\mbox{mdc}(F_i,F_{i+1})=1$ usando o Algoritmo de Euclides?
4 Mostre, para $n\geq 0$, que $\varphi^{n-1}\leq F_n\leq \varphi^{n}$ onde $\varphi = (1+\sqrt 5)/2$.
5. Sejam $a$ e $b$ números com três algarismos na base decimal
tal que $a>b$.
- No máximo, quantas divisões o algoritmo de Euclides vai precisar para
terminar se for executado para os números $a$ e $b$? - Ache dois números $a$ e $b$ com três algarismos na base
decimal tais que a computação de $\mbox{mdc}(a,b)$ precisa do número maximal
dos passos entre todos os números com três algarismos.