\documentclass[11pt,a4paper]{article}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\setlength{\oddsidemargin}{-0.5cm} \setlength{\textwidth}{ 500pt}
%\topmargin = -1cm \headheight = 0cm \headsep = 0cm
%\pagestyle{empty}
%\textheight 26cm \textwidth 17.cm


\usepackage{a4wide}
\usepackage{latexsym}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage[isolatin]{inputenc}
\usepackage[portuges]{babel}


\linespread{1.1}
%\textwidth15cm
%\textheight25cm


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\ZZ{{\mathbb{Z}}}
\def\CC{{\mathbb{C}}}
\def\NN{{\mathbb{N}}}
\def\KK{{\mathbb{K}}}
\def\RR{{\mathbb{R}}}
\def\cM{\mathcal{M}}
\def\ben{\begin{enumerate}}
\def\een{\end{enumerate}}
\def\l({\left(}
\def\r){\right)}
\def\lsqbr{\left[}
\def\rsqbr{\right]}
\def\lbr{\left[}
\def\rbr{\right]}
\def\ZZ{{\mathbb{Z}}}
\def\CC{{\mathbb{C}}}
\def\NN{{\mathbb{N}}}
\def\KK{{\mathbb{K}}}
\def\RR{{\mathbb{R}}}
\def\cMmn{\mathcal{M}_{m\times n}}
\def\cMrp{\mathcal{M}_{r\times p}}
\def\cMrn{\mathcal{M}_{r\times n}}
\def\cMm{\mathcal{M}_{m}}
\def\cMn{\mathcal{M}_{n}}
\def\cMp{\mathcal{M}_{p}}
\def\cMq{\mathcal{M}_{q}}
\def\cMk{\mathcal{M}_{k}}
\def\cM{\mathcal{M}}
\def\cLT{\mathcal{LT}}
\def\cLTn{\mathcal{LT}_n}
\def\parR{\left( \RR \right)}
\def\parC{\left( \CC \right)}
\def\parK{\left( \KK \right)}
%\def\epf{\hfill \rule{2mm}{4mm}}
\def\epf{\endproof}
\def\iff{\Leftrightarrow}
\def\imply{\Rightarrow}
\def\beqn{\begin{eqnarray*}}
\def\eeqn{\end{eqnarray*}}
\def\barr{\begin{array}}
\def\earr{\end{array}}
\def\vN{\l(1\r)}
\def\para{\rightarrow}
\def\lin{\langle}
\def\rin{\rangle}

\newtheorem{theorem}{Teorema}[section]
\newtheorem{definition}[theorem]{Defini\c{c}\~{a}o}
\newtheorem{lemma}[theorem]{Lema}
\newtheorem{proposition}[theorem]{Proposi\c{c}\~{a}o}
\newtheorem{corollary}[theorem]{Corol\'{a}rio}
\newtheorem{exemplo}[theorem]{Exemplo}
\newtheorem{obs}[theorem]{Observa\c{c}\~{a}o}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}
\pagestyle{empty}
\noindent
{\sf Universidade do Minho}
\hfill {\sf L.E.M., L.M.C.C. -- 4$^\circ$ ano}

\noindent{\small {\sf Departamento de Matem\'{a}tica}}
\hfill {\sf Mat. (Esp. Ensino), L.C.C. -- 3$^\circ$ ano}


\vskip 0.3cm \centerline{{\Large{\sf Teoria de Números Computacional}}}


\vskip 0.3cm
 \noindent\rule{1.5cm}{0.2mm}
 \raisebox{-0.5ex}[0cm][0cm]{ {\ \small{\sf{folha ii}}}} \hrulefill \rule{1.5cm}{0.2mm}
 \raisebox{-0.5ex}[0cm][0cm]{ {\ \small{\sf{$2^\circ$ semestre, 2006/2007}}}} \rule{1.5cm}{0.2mm}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ben

\item 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$.
\ben
\item Prove que $\displaystyle\sum_{k=1}^n f_k=f_{n+2}-1$. [Repare que $f_k= f_{k+2}-f_{k+1}$, com $k\in \NN$.]
\item Use o segundo princípio de indução para mostrar que $f_n >\alpha^{n-2}$, onde $\alpha =\frac{1+\sqrt{5}}{2}$ é o \textit{número de ouro} ou \textit{número áureo}. [Repare que $\alpha$ é solução de $x^2-x-1=0$.]
\item 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$.
\item Mostre que o quociente da divisão inteira de termos consecutivos da sucessão de Fibonacci é 1. 
\item 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$. 
\een

\item Use o algoritmo estendido de Euclides\footnote{Será boa ideia escrever uma função no pari/gp...} para encontrar $s,r\in \ZZ$ para os quais $(a,b)=as+br$, onde $a$ e $b$ são, respectivamente,
\ben
\item 45, 75
\item 666, 1414
\item 102, 222
\item 20785, 44350
\item 34709, 100313
\item 9876543210, 123456789
\item 11111111111, 1000000001
\item 45666020043321, 73433510078091009
\een

\item 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.

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


\een

\end{document}