\documentclass[12pt]{article}
\usepackage{amsmath,amsthm,amsfonts,amssymb,amscd,amsbsy}
\usepackage{graphics}

\usepackage[latin1]{inputenc}

\headsep=-1truecm

\oddsidemargin=0pt
\evensidemargin=0pt
\textwidth=17truecm
\textheight=23truecm

%\setcounter{page}{3}

\renewcommand{\baselinestretch}{1.5}

\def\esima{${}^{\text{\b a}}$}
\def\esimo{${}^{\text{\b o}}$}

\newcommand{\ve}{{\varepsilon}}
\newcommand{\be}{{\beta}}
\newcommand{\la}{{\lambda}}
\newcommand{\Om}{{\Omega}}
\newcommand{\La}{{\Lambda}}
\newcommand{\ga}{{\gamma}}
\newcommand{\Ga}{{\Gamma}}
\newcommand{\po}{{\partial}}
\newcommand{\ro}{{\rho}}
\newcommand{\ov}{\overline}
\newcommand{\z}{{\mathbb{z}}}
\newcommand{\Q}{{\mathbb{Q}}}
\newcommand{\F}{{\mathbb{F}}}
\newcommand{\U}{{\mathcal{U}}}
\newcommand{\h}{{\mathcal{H}}}
\newcommand{\al}{{\alpha}}
\newcommand{\vr}{{\varphi}}
\newcommand{\na}{{\mathbb{N}}}
\newcommand{\ca}{{\mathcal{C}}}
\newcommand{\re}{{\mathbb{R}}}
\newcommand{\Z}{{\mathbb Z}}



\def\ov{\overline}
\def\und{\underline}
\def\fa{{\Cal F}}
\def\H{{\Cal H}}
\def\B{{\Cal B}}
\def\E{{\Cal E}}
\def\O{{\Cal O}}
\def\P{{\Cal P}}
\def\L{{\Cal L}}
\def\C{{\Cal C}}
\def\M{{\Cal M}}
\def\N{{\Cal N}}
\def\R{{\Cal R}}
\def\sa{{\Cal S}}
\def\I{{\Cal I}}
\def\A{{\Cal A}}
\def\K{{\Cal K}}
\def\te{{\theta}}
\def\Te{{\Theta}}
\def\vr{\varphi}
\def\ga{{\gamma}}
\def\Ga{{\Gamma}}
\def\om{{\omega}}
\def\Om{{\Omega}}
\def\la{{\lambda}}
\def\La{{\Lambda}}
\def\ro{{\rho}}
\def\po{{\partial}}

\def\bp{{\Bbb P}}
\def\bq{{\Bbb Q}}
\def\bz{{\Bbb Z}}
\def\bq{{\Bbb Q}}
\def\re{{\Bbb R}}
\def\na{{\Bbb N}}
\def\si{{\Cal S}}
\def\co{{\Bbb C}}
\def\AA{{\Bbb A}}
\def\Ii{{\frak I}}

\def\lg{\langle}
\def\rg{\rangle}
\def\lV{\left\Vert}
\def\rV{\right\Vert }
\def\lv{\left\vert}
\def\rv{\right\vert }

\def\esima{${}^{\text{\b a}}$}
\def\esimo{${}^{\text{\b o}}$}

\def\Hom{\operatorname{{Hom}}}
\def\codim{\operatorname{{codim}}}
\def\cotg{\operatorname{{cotg}}}
\def\dom{\operatorname{{dom}}}
\def\VIP{\operatorname{{VIP}}}
\def\argmin{\operatorname{{argmin}}}
\def\Sol{\operatorname{{Sol}}}
\def\Ker{\operatorname{{Ker}}}
\def\diag{\operatorname{{diag}}}
\def\diam{\operatorname{{diam}}}
\def\Diff{\operatorname{{Diff}}}
\def\Log{\operatorname{{Log}}}
\def\Aff{\operatorname{{Aff}}}
\def\tni{\operatorname{{int}}}
\def\ord{\operatorname{{ord}}}

\def\_#1{{\lower 0.7ex\hbox{}}_{#1}}

\def\bib#1{\setbox0=3D\hbox{[01]}\par\noindent\hangindent=3D\wd0 #1}
\def\bibb#1{\setbox0=3D\hbox{[01] Ma}\par\noindent\hangindent=3D\wd0 #1}

\def\itemitemitem{\par\indent\indent
      \hangindent3\parindent\textindent}
\def\itemitemitemitem{\par\indent\indent\indent
      \hangindent4\parindent\textindent}
\def\itemitemitemitemitem{\par\indent\indent\indent\indent\indent
      \hangindent5\parindent\textindent}


\newcommand{\Li}{\operatorname{Li}}
\newcommand{\rd}{{\rm d}}
\newcommand{\mdc}{\operatorname{mdc}}
\newcommand{\NN}{{\mathbb{N}}}
\newcommand{\ZZ}{{\mathbb{Z}}}
\newcommand{\QQ}{{\mathbb{Q}}}
\newcommand{\RR}{{\mathbb{R}}}
\newcommand{\CC}{{\mathbb{C}}}
\newcommand{\FF}{{\mathbb{F}}}

\newcommand{\nobf}{\medskip\noindent\bf}
\newcommand{\ordem}{\operatorname{ord}}
\newcommand{\alphab}{\overline{\alpha}}

\parskip=4pt plus 8pt

\renewcommand\emptyset{\varnothing}
\def\qed{\unskip\nobreak\hfil\penalty50\hskip1.75em\null\nobreak\hfil
$\blacksquare$ {\parfillskip=0pt \finalhyphendemerits=0 \par}\goodbreak}

\begin{document}

\vglue 1in

\renewcommand{\thepage}

\centerline{\LARGE\bf Introdução à Teoria dos Números}

\vskip .2in

\centerline{\bf (com ênfase em Aproximações Diofantinas)}

\vskip .9in

\centerline{\large\sc Carlos Gustavo T. de A. Moreira}

\vskip .3in

\centerline{I M P A }
\centerline{\sl Estrada Dona Castorina 110, Jardim Botânico}
\centerline{\sl Rio de Janeiro-RJ}
\centerline{CEP 22.460-320 - Brasil}

\centerline{Correio eletrônico: gugu@impa.br}
\centerline{Página na internet:  www.impa.br/$\sim$ gugu}

\newpage

\vglue .5in

\centerline{\LARGE\bf Conteúdo}

\vskip .4in

{\large\bf Introdução} \dotfill 3

\vskip .2in

{\bf PARTE I: \quad CONGRUÊNCIAS E NÚMEROS PRIMOS}

\vskip .2in

\noindent
{\large\bf Capítulo 1:}{\bf \,\, Divisibilidade e Congruências} \hfill {\bf 7}

1\,\, Divisão euclidiana e o teorema fundamental da aritmética \dotfill 7

2\,\, Congruências \dotfill 10

3\,\, A função de Euler e o pequeno teorema de Fermat \dotfill 14

4\,\, A função de Möbius \dotfill  18

5\,\, Bases \dotfill 21

6\,\, Corpos e polinômios \dotfill 23

7\,\, Ordens e raízes primitivas\dotfill 28

8\,\, Raízes primitivas em $\mathbb Z/(n)$ \dotfill 30

9\,\, A lei da reciprocidade quadrática \dotfill 32

10\,\, Extensões quadráticas de corpos finitos \dotfill 35

\vskip .2in

\noindent
{\large\bf Capítulo 2:}{\bf \,\, Números Primos} \hfill {\bf 37}


1\,\, Sobre a distribuição dos números primos \dotfill 37

2\,\, Outros resultados e conjecturas sobre primos \dotfill 41

3\,\, Fórmulas para primos e testes de primalidade \dotfill 44

4\,\, Testes de primalidade baseados em fatorações de $n-1$ \dotfill 45

5\,\, Primos de Mersenne \dotfill 47

\vskip .2in

{\bf PARTE II:\quad APROXIMAÇÕES DIOFANTINAS}

\vskip .2in

\noindent
{\large\bf Capítulo 3:}{\bf \,\, Frações Contínuas, Representações de Números e Aproximações} \hfill {\bf 54}

1\,\, Reduzidas e boas aproximações \dotfill 56

2\,\, Boas aproximações são reduzidas \dotfill 60

3\,\, Frações contínuas periódicas \dotfill 62

\quad Aplicação: a equação de Pell \dotfill 64

\vskip .2in

\noindent
{\large \bf Capítulo 4:}{\bf \,\, Propriedades Estatísticas de Frações Contínuas e Aproximações}

\qquad\qquad\qquad {\bf Dioantinas: O Teorema de Khintchine} \hfill {\bf 66} 


1\,\, O Teorema de Khintchine via frações contínuas \dotfill 68

2\,\, O Teorema de Khintchine $n$-dimensional \dotfill 71

\vskip .2in

{\large\bf Apêndice:}{\bf \,\, Aproximações diofantinas não-homogêneas \dotfill 75}

\vskip .2in

\noindent
{\large\bf Capítulo 5:}{\bf \,\, Os Espectros de Markov e Lagrange} \hfill {\bf 77}

1\,\, Definições e enunciados \dotfill 77

2\,\, Dimensões de Hausdorff e somas aritméticas de conjuntos de Cantor

\quad\,  de frações contínuas \dotfill 79

3\,\, Idéias das demonstrações dos resultados sobre os espectros \dotfill 81

4\,\, Espectros de Markov e Langrange dinâmicos \dotfill 83

\vskip .1in

{\large \bf Apêndice:}{\bf \,\, Conjuntos de Cantos Regulares e Dimensões Fractais \dotfill 85}

1.0\,\, Conjuntos de Cantor \dotfill 85

1.1\,\, Conjuntos de Cantor regulares \dotfill 86

1.2\,\, Distorção limitada e geometrias limite \dotfill 88

1.3\,\, Dimensões fractais \dotfill 91

\vskip .1in

{\large\bf Referências} \dotfill{\bf  96}

\newpage

\renewcommand{\thepage}{\arabic{page}}

\setcounter{page}{3}

\vglue .5in

\noindent
{\Large\bf Introdução}

\vskip .3in

Estas são as notas de um mini-curso que fui convidado a dar no IMCA em novembro de 2001. Boa parte do material aqui contido foi adaptado das notas dos
cursos ``Primos de Mersenne \linebreak (e outros primos muito grandes)'', em colaboração com Nicolau Saldanha e ``Conjuntos de Cantor, Dinâmica e Aritmética'', que dei no XXII Colóquio Brasileiro de Matemática, em 1999, e do artigo ``Propriedades Estatísticas de Frações Contínuas e Aproximações Diofantinas'', publicado na Revista Matemática Universitária.

O objetivo dessas notas é ser uma referência introdutória sobre teoria dos números e
\linebreak a\-pro\-xi\-ma\-ções diofantinas, destinada a alunos de graduação ou mestrado em matemática. Boa parte do material é totalmente elementar, sendo acessível a bons alunos do ensino médio \linebreak (em particular aos olímpicos...). Agradeço aos Professores Cesar Camacho e Roger Metzger pelo convite e a oportunidade de visitar o Peru e dar aulas sobre esse assunto tão fascinante.

\vskip .5in

\rightline{Rio de Janeiro, 26 de outubro de 2001.}

\newpage

\quad

\newpage

\vglue 3in

\centerline{\LARGE\bf PARTE I}

\vskip .5in

\centerline{\LARGE \bf CONGRUÊNCIAS E NÚMEROS PRIMOS}

\newpage

\quad

\newpage



\centerline{\Large\bf CAPÍTULO 1}

\vskip .5in

\centerline{\Large\bf Divisibilidade e Congruências}

\vskip .5in

Neste primeiro capítulo veremos os tópicos básicos de teoria dos números,
como divisibilidade, congruências e aritmética módulo $n$.

\section{Divisão euclidiana e o teorema fundamental da \newline aritmética}

A divisão euclidiana, ou divisão com resto,
é uma das quatro operações que toda criança aprende na escola.
Sua formulação precisa é:
dados $a \in \ZZ$, $b \in \ZZ^\ast$
existem $q, r \in \ZZ$ com $0 \le r < |b|$ e $a = bq + r$.
Tais $q$ e $r$ estão unicamente determinados
e são chamados o {\sl quociente} e {\sl resto}
da divisão de $a$ por $b$.
Se $b > 0$ podemos definir $q = \lfloor a/b \rfloor$ e
se $b < 0$,  $q = \lceil a/b \rceil$;
em qualquer caso, $r = a - bq$.
O resto $r$ é às vezes denotado por $a \bmod b$;
definimos $a \bmod 0 = a$.
Lembramos que
$\lfloor x \rfloor$ denota o único inteiro $k$ tal que
$k \le x < k + 1$ e
$\lceil x \rceil$ o único inteiro $k$ tal que
$k - 1 < x \le k$.

Dados dois inteiros $a$ e $b$ (em geral com $b \ne 0$)
dizemos que $b$ {\sl divide} $a$, ou que $a$ é um {\sl múltiplo} de $b$,
e escrevemos $b | a$, se existir $q \in \ZZ$ com $a = qb$.
Se $a \ne 0$, também dizemos que $b$ é um {\sl divisor} de $a$.
Assim, $b | a$ se e somente se $a \bmod b = 0$.


{\nobf Proposição 1.1: }
{Dados $a, b \in \ZZ$ existe um único $d \in \NN$ tal que
$d|a$, $d|b$ e, para todo $c \in \NN$, se $c|a$ e $c|b$ então $c|d$.
Além disso existem $x, y \in \ZZ$ com $d = ax + by$.}

Esse natural $d$ é chamado o {\sl máximo divisor comum},
ou mdc, entre $a$ e $b$.
Escrevemos $d = \mdc(a, b)$ ou
(se não houver possibilidade de confusão) $d = (a,b)$.

{\nobf Dem: }
O caso $a = b = 0$ é trivial (temos $d = 0$).
Nos outros casos, seja $I(a,b) = \{ax + by; x, y \in \ZZ\}$ e seja
$d = a x_0 + b y_0$ o menor elemento positivo de $I(a,b)$.
Como $d \in \NN^\ast$,
existem $q, r \in \ZZ$ com $a = dq + r$ e $0 \le r < d$.
Temos $r = a - dq = a (1 - q x_0) + b (- q y_0) \in I(a,b)$;
como $r < d$ e $d$ é o menor elemento positivo de $I(a,b)$,
$r = 0$ e $d | a$.
Analogamente, $d | b$.
Suponha agora que $c|a$ e $c|b$;
temos $c | a x + b y$ para quaisquer valores de $x$ e $y$
donde, em particular, $c|d$.
\qed

O {\sl algoritmo de Euclides} para calcular o mdc baseia-se
nas seguintes observações simples.
Se $a = bq + r$, $0 \le r < b$, temos
(com a notação da demonstração acima)
$I(a,b) = I(b,r)$, donde $(a,b) = (b,r)$.
Definindo $a_0 = a$, $a_1 = b$ e
$a_n = a_{n+1} q_{n+2} + a_{n+2}$, $0 \le a_{n+2} < a_{n+1}$
(ou seja, $a_{n+2}$ é o resto da divisão de $a_n$ por $a_{n+1}$)
temos $(a,b) = (a_0,a_1) = (a_1,a_2) = (a_2,a_3) = \cdots = (a_n,a_{n+1})$
para qualquer valor de $n$.
Seja $N$ o menor natural para o qual $a_{N+1} = 0$:
temos $(a,b) = (a_N,0) = a_N$.

{\nobf Lema 1.2: }{\sl Se $(a, b) = 1$ e $a|bc$ então $a|c$.}

{\nobf Dem: }
Como $(a, b) = 1$, existem $x, y \in \ZZ$ com $ax + by = 1$,
logo $a | c = acx + bcy$.
\qed

Quando $(a,b) = 1$ dizemos que $a$ e $b$ são {\sl primos entre si}.
Um natural $p > 1$ é chamado {\sl primo}
se os únicos divisores positivos de $p$ são $1$ e $p$.
Um natural $n > 1$ é chamado {\sl composto} se admite
outros divisores além de 1 e $n$.

Claramente, se $p$ é primo e $p \nmid a$ temos $(p,a) = 1$.
Usando o lema anterior e indução temos o seguinte resultado:

{\nobf Corolário 1.3: }
{\sl Sejam $p$ um número primo e sejam $a_1, \ldots a_m \in \ZZ$.
Se $p|a_1 \cdots a_m$ então $p|a_i$ para algum $i$, $1 \le i \le n$.}

Estamos agora prontos para enunciar e provar o teorema
que diz que todo inteiro admite fatoração única como produto de primos.

{\nobf Teorema 1.4: \rm (Teorema fundamental da aritmética) }
{Seja $n \ge 2$ um número natural.
Podemos escrever $n$ de uma única forma como um produto
$$n = p_1 \cdots p_m$$
onde $m \ge 1$ é um natural e $p_1 \le \ldots \le p_m$ são primos.}

{\nobf Dem: }
Mostramos a existencia da fatoração por indução.
Se $n$ é primo não há o que provar (escrevemos $m = 1$, $p_1 = n$).
Se $n$ é composto podemos escrever $n = ab$, $a, b \in \NN$,
$1 < a < n$, $1 < b < n$.
Por hipótese de indução,
$a$ e $b$ se decompõem como produto de primos.
Juntando as fatorações de $a$ e $b$
(e reordenando os fatores) obtemos uma fatoração de $n$.

Vamos agora mostrar a unicidade, também por indução.
Suponha que 
$$n = p_1 \cdots p_m = q_1 \cdots q_{m'},$$
com $p_1 \le \ldots \le p_m$, $q_1 \le \ldots \le q_{m'}$.
Como $p_1 | q_1 \cdots q_{m'}$ temos $p_1 | q_i$ para algum valor de $i$,
donde, como $q_i$ é primo, $p_1 = q_i$ e $p_1 \ge q_1$.
Analogamente temos $q_1 \le p_1$, donde $p_1 = q_1$.
Mas por hipótese de indução
$$n/{p_1} = p_2 \cdots p_m = q_2 \cdots q_{m'}$$
admite uma única fatoração, donde $m = m'$ e $p_i = q_i$ para todo $i$.
\qed

Outra forma de escrever a fatoração é
$$n = p_1^{e_1} \cdots p_m^{e_m},$$
com $p_1 < \cdots < p_m$, $e_i > 0$.
Ainda outra formulação é escrever
$$n = 2^{e_2} 3^{e_3} 5^{e_5} \cdots p^{e_p} \cdots$$
onde o produto é tomado sobre {\sl todos} os primos 
mas apenas um número finito de expoentes é maior do que zero.

Segue deste teorema o outro algoritmo comum para calcular o mdc
de dois números:
fatoramos os dois números e tomamos os fatores comuns
com os menores expoentes.
Este algoritmo é bem menos eficiente do que o de Euclides
para inteiros grandes (que em geral não sabemos fatorar)
mas é instrutivo saber que os dois algoritmos dão o mesmo resultado.

{\nobf Corolário 1.5: }{\sl Se $(a,n) = (b,n) = 1$ então $(ab,n) = 1$.}

{\nobf Dem: }
Evidente a partir do algoritmo descrito acima.
\qed

{\nobf Teorema 1.6: \rm (Euclides) }
{\sl Existem infinitos números primos.}

{\nobf Dem: }
Suponha por absurdo que $p_1, p_2,..., p_m$ fossem {\sl todos} os primos.
O número $N = p_1 \cdot p_2 \cdots p_m + 1 > 1$
não seria divisível por nenhum primo,
o que contradiz o teorema fundamental da aritmética.
\qed

Observe que {\sl não} provamos que $p_1 \cdot p_2 \cdots p_m + 1$
é primo para algum conjunto finito de primos
(por exemplo, os $m$ primeiros primos).
Aliás,
$2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$,
$2 \cdot 3 \cdot 5 \cdot 7 - 1 = 209 = 11 \cdot 19$,
$4! + 1 = 25 = 5^2$ e $8! - 1 = 40319 = 23 \cdot 1753$ não são primos.
Não existe nenhuma fórmula simples conhecida que gere sempre números primos.
Veja a seção 3.1.

\section{Congruências}

Sejam $a, b, n \in \ZZ$.
Dizemos que {\sl $a$ é congruente a $b$ módulo $n$},
e escrevemos $a \equiv b \pmod n$, se $n|b - a$.
Como a congruência módulo 0 é a igualdade
e quaisquer inteiros são côngruos módulo 1,
em geral estamos interessados em $n > 1$.

{\nobf Proposição 2.1: }
{\sl Para quaisquer $a, a', b, b', c, n \in \ZZ$ temos:

{\rm (a)}


\begin{itemize}

\item[1.] {$a \equiv a \pmod n$;}
\item[2.] {se $a \equiv b \pmod n$ então $b \equiv a \pmod n$;}
\item[3.] {se $a \equiv b \pmod n$ e $b \equiv c \pmod n$
então $a \equiv c \pmod n$;}
\item[4.] {se $a \equiv a' \pmod n$ e $b \equiv b' \pmod n$
então $a + b \equiv a' + b' \pmod n$;}
\item[5.] {se $a \equiv a' \pmod n$
então $- a  \equiv - a' \pmod n$;}
\item[6.] {se $a \equiv a' \pmod n$ e $b \equiv b' \pmod n$
então $a \cdot b \equiv a' \cdot b' \pmod n$.}
\end{itemize}
}

{\nobf Dem: }
Para o item (a) basta observar que $n | a - a = 0$.
Em (b), se $n | b - a$ então $n | a - b = -(b-a)$.
Em (c), se $n | b - a$ e $n | c - b$ então $n | c - a = (c - b) + (b - a)$.
Em (d), se $n | a' - a$ e $n | b' - b$ então
$n | (a' + b') - (a + b) = (a' - a) + (b' - b)$.
Em (e), se $n | a' - a$ então $n | (-a') - (-a) = -(a' - a)$.
Em (f), se $n | a' - a$ e $n | b' - b$ então
$n | a'b' - ab = a'(b' - b) + b(a' - a)$.
\qed

Os itens (a), (b) e (c) da proposição acima dizem, nesta ordem, que a relação
$\equiv \pmod n$ (``ser côngruo módulo $n$'')
é uma relação reflexiva, simétrica e transitiva.
Relações satisfazendo estas três propriedades são chamadas
{\sl relações de equivalência}.
Dada uma relação de equivalência $\sim$ sobre um conjunto $X$
e um elemento $x \in X$ definimos a {\sl classe de equivalência}
$\overline x$ de $x$ como
$$\overline x = \{y \in X | y \sim x\};$$
observe que $x \sim y$ se e somente se $\overline x = \overline y$.
As classes de equivalência formam uma partição de $X$, i.e.,
uma coleção de subconjuntos não vazios e disjuntos de $X$ cuja união é $X$.
O conjunto $\{ \overline x | x \in X \}$ das classes de equivalência
é chamado o {\sl quociente} de $X$ pela relação de equivalência $\sim$
e é denotado por $X/\sim$.

Aplicando esta construção geral ao nosso caso, definimos o quociente
$\ZZ/(\equiv \pmod n)$, chamado por simplicidade de notação de
$\ZZ/(n)$, $\ZZ/n\ZZ$ ou às vezes $\ZZ_n$.
Dado $a \in \ZZ$, a definição de $\overline a$ como um subconjunto de $\ZZ$
raramente será importante: o importante é sabermos que
$\overline a = \overline{a'}$ se e somente se $a \equiv a' \pmod n$.
Se $n > 0$, a divisão euclidiana diz que todo inteiro $a$ é côngruo a um único
inteiro $a'$ com $0 \le a' < n$; podemos reescrever este fato na nosso
nova linguagem como
$$\ZZ/(n) = \{\overline 0, \overline 1, \ldots, \overline{n-1} \}.$$
Quando não houver possibilidade de confusão omitiremos as barras e
chamaremos os elementos de $\ZZ/(n)$ simplesmente de $0, 1, \ldots, n-1$.

Os itens (d), (e) e (f) da proposição dizem que as operações de soma,
diferença e produto são compatíveis com a relação de congruência.
É esta propriedade que torna congruências tão úteis,
nos possibilitando fazer contas módulo $n$.
Podemos por exemplo escrever
\begin{align}
196883 &=
1 \cdot 10^5 + 9 \cdot 10^4 + 6 \cdot 10^3 +
8 \cdot 10^2 + 8 \cdot 10^1 + 3 \cdot 10^0 \notag\\
&\equiv
1 \cdot 1^5 + 9 \cdot 1^4 + 6 \cdot 1^3 +
8 \cdot 1^2 + 8 \cdot 1^1 + 3 \cdot 1^0  \notag\\
&= 1 + 9 + 6 + 8 + 8 + 3 \notag\\
&= 35 \notag\\
&\equiv 8 \pmod 9,\notag
\end{align}
já que $10 \equiv 1 \pmod 9$
(mostrando assim porque funciona o conhecido critério de divisibilidade por 9).
Uma formulação mais abstrata da mesma idéia é dizer que as operações
$+$ e $\cdot$ {\sl passam ao quociente}, i.e., que podemos definir
$$+: \ZZ/(n) \times \ZZ/(n) \to \ZZ/(n), \qquad
\cdot: \ZZ/(n) \times \ZZ/(n) \to \ZZ/(n)$$
por $\overline a + \overline b = \overline{a+b}$ e
$\overline a \cdot \overline b = \overline{a\cdot b}$.
A dúvida à primeira vista seria se a escolha de $a$ e $b$ não afeta a resposta:
afinal existem infinitos inteiros $a'$ e $b'$ com
$\overline a = \overline{a'}$ e $\overline b = \overline{b'}$.
Os itens (d) e (f) da proposição são exatamente o que precisamos:
eles nos dizem que nestas condições
$\overline{a+b} = \overline{a'+b'}$ e
$\overline{a\cdot b} = \overline{a'\cdot b'}$.

{\nobf Proposição 2.2: }
{\sl Sejam $a, n \in \ZZ$, $n > 0$.
Então existe $b \in \ZZ$ com $ab \equiv 1 \pmod n$
se e somente se $(a,n) = 1$.}

{\nobf Dem: }
Se $ab \equiv 1 \pmod n$ temos $nk = 1 - ab$ para algum $k$,
donde $(a,n) | ab + nk = 1$ e $(a,n) = 1$.
Se $(a,n) = 1$ temos $ax + ny = 1$ para certos inteiros $x$ e $y$,
donde $ax \equiv 1 \pmod n$.
\qed

Dizemos portanto que $a$ é {\sl invertível}
\footnote{Alguns autores preferem escrever {\sl inversível}.
Os interessados em discutir esta questão ortográfica devem escrever
para o Prof. Zoroastro Azambuja, IMPA, Estr. D. Castorina 110,
Rio de Janeiro, RJ}
módulo $n$ quando $(a,n) = 1$
e chamamos $b$ com $ab \equiv 1 \pmod n$ de {\sl inverso}
de $a$ módulo $n$.
O inverso é sempre único módulo $n$:
se $ab \equiv ab' \equiv 1 \pmod n$ temos
$b \equiv ab^2 \equiv abb' \equiv b' \pmod n$.

{\nobf Corolário 2.3: }
{\sl Se $(a,n) = 1$ e $ab \equiv ab' \pmod n$ então $b \equiv b' \pmod n$.}

{\nobf Dem: }
Basta escrever $b \equiv abc \equiv ab'c \equiv b' \pmod n$
onde $c$ é o inverso de $a$ módulo $n$.
\qed

Definimos $(\ZZ/(n))^\ast \subset \ZZ/(n)$ por
$$(\ZZ/(n))^\ast = \{ \overline a ; (a,n) = 1 \}.$$
Observe que o produto de elementos de $(\ZZ/(n))^\ast$
é sempre um elemento de $(\ZZ/(n))^\ast$ (corolário 1.5).

{\nobf Teorema 2.4: \rm (Teorema Chinês dos restos) }
{\sl Se $(m, n) = 1$ então
\begin{align}
f: \ZZ/(mn) &\to \ZZ/(m) \times \ZZ/(n) \notag\\
\overline a &\mapsto (\overline a, \overline a) \notag
\end{align}
é uma bijeção.
Além disso, a imagem por $f$ de $(\ZZ/(mn))^\ast$ é
$(\ZZ/(m))^\ast \times (\ZZ/(n))^\ast$.
}

Note que cada $\overline a$ na definição de $f$
é tomado em relação a um módulo diferente.
A função está bem definida pois $a \bmod mn$
determina $a \bmod m$ e $a \bmod n$.

{\nobf Dem: }
Como $\ZZ/(mn)$ e $\ZZ/(m) \times \ZZ/(n)$ têm $mn$ elementos cada,
para provar que $f$ é bijetiva basta verificar que $f$ é injetiva.
E, de fato, se
$a \equiv a' \pmod m$ e $a \equiv a' \pmod n$
então $m | (a - a')$ e $n | (a - a')$,
donde $mn | (a - a')$ e $a \equiv a' \pmod {mn}$.
A imagem de $(\ZZ/(mn))^\ast$ é
$(\ZZ/(m))^\ast \times (\ZZ/(n))^\ast$
pois $(a,mn) = 1$ se e somente se $(a,m) = (a,n) = 1$.
\qed

Dados inteiros $m_1, m_2, \ldots , m_r$, dizemos que estes inteiros
são {\sl primos entre si} se $(m_i,m_j) = 1$ para quaiquer $i \ne j$.

{\nobf Corolário 2.5: }
{\sl Se $m_1, m_2, \ldots, m_r$ são inteiros primos entre si.  Então
\begin{align}
f: \ZZ/(m_1 m_2 \cdots m_r) &\to
\ZZ/(m_1) \times \ZZ/(m_2) \cdots \ZZ/(m_r)\notag\\
\overline a &\mapsto (\overline a, \overline a, \ldots, \overline a) \notag
\end{align}
é uma bijeção.}

{\nobf Dem: }
Basta aplicar o teorema anterior $r$ vezes.
\qed

A aplicação mais comum deste teorema é para garantir que existe
$a$ com $a \equiv a_i \pmod {m_i}$ onde $a_i$ são inteiros dados quaisquer.

\vskip .1in

\noindent
{\bf Problema resolvido:}
Prove que dado $n\in\mathbb N$ existe um conjunto de $n$ elementos $A\subset\mathbb N$ tal que para todo $B\subset A$, $B\ne \emptyset$, $\sum\limits_{x\in B}x$ é uma potência não trivial (isto é, um número da forma $m^k$, onde $m,k$ são inteiros maiores ou iguais a 2), ou seja, $A=\{x_1,x_2,\dots x_n\}$ tal que $x_1,x_2,\dots x_n, x_1+x_2, x_1+x_3,\dots,x_{n-1}+x_n,\dots,x_1+x_2+\dots x_n$ são todos potências não triviais.

\vskip .1in

\noindent
{\bf Solução:}
$A=\{4\}$ é solução para $n=1$, $A=\{9,16\}$ é solução para $n=2$. Vamos provar a existência de um tal conjunto por indução em $n$. Suponha que $A=\{x_1,\dots,x_n\}$ é um conjunto com $n$ elementos e para todo $B\subset A$, $B\ne\emptyset$, $\sum\limits_{x\in B}x=m_B^{k_B}$. Vamos mostrar que existe $c\in \mathbb N$ tal que o conjunto $\tilde A=\{c x_1,c x_2,\dots,cx_n,c\}$ satisfaz o enunciado.

Seja $\ell=\text{mmc}\{k_b,B\subset A,\,\, B\ne\emptyset\}$ o mínimo múltiplo comum de todos os exponentes $k_B$.

Para cada $B\subset A$, $B\ne\emptyset$ associamos um número primo $p_B>\ell$, de forma que $B_1\ne B_2\Rightarrow p_{B_1}\ne p_{B_2}$, e associamos um natural $r$ com $r_B\equiv 0$ (módulo $p_x$), $\forall\, X\ne B$, $\ell r_B+1\equiv 0$ (módulo $p_B$) (tal $r_B$ existe pelo teorema chinês dos restos), e tomamos
$$
c=\prod_{\substack{B\subset A \\ B\ne\emptyset}} (1+m_B^{k_B})^{\ell r_B}.
$$
Como $c$ é uma potência $\ell$-ésima, $c$ é uma potência 
$k_B$-ésima para todo $B\subset A$, $B\ne\emptyset$, portanto, para $B'\subset\{cx_1,cx_2,\dots,cx_n\}$, $B'\ne\emptyset$, teremos $B'=\{cx \mid x\in B\}$ para algum $B\subset A$, $B\ne\emptyset$. Logo $\sum\limits_{x\in B'}x$ será uma potência $k_B$-ésima.

Além disso,
$$
\sum_{X\in B'U\{c\}}x=c(1+m_B^{K_B})= \left[ \prod_{\substack{X\subset A \\ X\ne \emptyset,B}}(1+m_X^{K_X})^{\ell r_X} \right] \cdot (1+m_B^{K_B})^{\ell r_B+1},
$$
que é uma potência $p_B$-ésima, pois $r_X$ é múltiplo de $p_B$ para $X\ne B$ e $\ell r_B+1$ é múltiplo de $p_B$. \qed


\section{A função de Euler e o pequeno teorema de Fermat}

Definimos $\varphi(n) = |(\ZZ/(n))^\ast|$
(onde $|X|$ denota o número de elementos de $X$).
A função $\varphi$ é conhecida como a {\sl função de Euler}.
Temos $\varphi(1) = \varphi(2) = 1$, e, para $n > 2$, $1 < \varphi(n) < n$.
Se $p$ é primo, $\varphi(p) = p-1$;
mais geralmente $\varphi(p^k) = p^k - p^{k-1}$
pois $(a,p^k) = 1$ se e somente se $a$ não é múltiplo de $p$
e há $p^{k-1}$ múltiplos de $p$ no intervalo $0 \le a < p^k$. 

Dizemos que os $n$ números inteiros
$a_1, a_2, \ldots, a_n$ formam um {\sl sistema completo de resíduos}
(ou s.c.r.) módulo $n$ se
$\{\overline{a_1}, \overline{a_2}, \ldots \overline{a_n} \}
= \ZZ/(n)$,
isto é, se os $a_i$ representam todas as classes de congruência módulo $n$.
Por exemplo, 0, 1, 2, \ldots $n -1$ formam um s.c.r. módulo $n$.
Equivalentemente, podemos dizer que
$a_1, a_2, \ldots, a_n$ formam um s.c.r. módulo $n$
se e somente se $a_i \equiv a_j \pmod n$ implicar $i = j$.
Os $\varphi(n)$ números inteiros $b_1, b_2, \ldots, b_{\varphi(n)}$
formam um {\sl sistema completo de invertíveis} (s.c.i.) módulo $n$ se
$$\{\overline{b_1}, \overline{b_2}, \ldots \overline{b_{\varphi(n)}} \}
= (\ZZ/(n))^\ast,$$
isto é, se os $b_i$ representam todas as classes de congruências invertíveis
módulo $n$.
Também equivalentemente, $b_1, b_2, \ldots, b_{\varphi(n)}$ 
formam um s.c.i. módulo $n$
se e somente se $(b_i,n) = 1$ para todo $i$ e
$a_i \equiv a_j \pmod n$ implicar $i = j$.

{\nobf Proposição 3.1: }
{\sl Sejam $q, r, n \in \ZZ$, $n > 0$, $q$ invertível módulo $n$,
$a_1, a_2, \ldots, a_n$ um s.c.r. módulo $n$ e
$b_1, b_2, \ldots, b_{\varphi(n)}$ um s.c.i. módulo $n$.
Então $qa_1 + r, qa_2 + r, \ldots, qa_n + r$
formam um s.c.r. módulo $n$ e
$qb_1, qb_2,...qb_{\varphi(n)}$ formam um s.c.i. módulo n.}

{\nobf Dem: }
Se $qa_i + r \equiv qa_j + r \pmod n$ então $n | q(a_i - a_j)$
e $a_i \equiv a_j \pmod n$, donde $i = j$;
com isto provamos que $qa_1 + r, qa_2 + r, \ldots, qa_n + r$ 
formam um s.c.r..

Como $(q,n) = (b_i,n) = 1$, temos $(q b_i, n) = 1$.
Por outro lado, se $qb_i \equiv qb_j \pmod n$
temos $b_i \equiv b_j \pmod n$ (como no parágrafo anterior) e $i = j$.
Isto conclui a demonstração.
\qed

{\nobf Teorema 3.2: \rm (Euler) }
{\sl Sejam $a, n \in \ZZ$, $n > 0$, tais que $(a, n) = 1$.
Então $a^{\varphi(n)} \equiv 1 \pmod n$.}

{\nobf Dem: }
Seja $$b_1, b_2, \ldots.b_{\varphi(n)}$$ um s.c.i. módulo $n$.
Pela proposição anterior,
$$ab_1, ab_2, \ldots  ab_{\varphi(n)}$$ também formam um s.c.i. módulo $n$.
Assim,
$$b_1 \cdot b_2 \cdots b_{\varphi(n)} \equiv
ab_1 \cdot ab_2 \cdots ab_{\varphi(n)} \pmod n$$
pois módulo $n$ os dois lados têm os mesmos fatores a menos de permutação.
Mas isto pode ser reescrito como
$$a^{\varphi(n)} (b_1 \cdot b_2 \cdots b_{\varphi(n)}) \equiv
1 \cdot (b_1 \cdot b_2 \cdots b_{\varphi(n)}) \pmod n$$
e pelo corolário 1.9 isto implica $a^{\varphi(n)} \equiv 1 \pmod n$.
\qed

{\nobf Corolário 3.3: \rm (Pequeno Teorema de Fermat) }
{\sl Se $p$ é primo então, para todo inteiro $a$,  $a^p \equiv a \pmod p$.}

{\nobf Dem: }
Se $p|a$, então $a^p \equiv a \equiv 0 \pmod p$.
Caso contrário, $\varphi(p) = p-1$, $a^{p-1} \equiv 1 \pmod p$
e novamente $a^p \equiv a \pmod p$.
\qed

Outra demonstração do pequeno teorema de Fermat é por indução em $a$
usando o binômio de Newton e algumas propriedades de números binomiais.
Se $0 < i < p$ temos 
$$\binom{p}{i} = \frac{p!}{i! (p-i)!} \equiv 0 \pmod p$$
pois há um fator $p$ no numerador que não pode ser cancelado
com nada que apareça no denominador.
Os casos $a = 0$ e $a = 1$ do teorema são triviais.
Supondo válido o teorema para $a$, temos
\begin{align}
(a+1)^p &= a^p + \binom{p}{1} a^{p-1} + \cdots + \binom{p}{p-1} a + 1 \notag\\
&\equiv a^p + 1 \notag\\
&\equiv a + 1 \pmod p \notag
\end{align}
e a indução está completa.

{\nobf Corolário 3.4: }
{\sl Se $(m, n) = 1$ então $\varphi(mn) = \varphi(m) \varphi(n)$.}

{\nobf Dem: }
Construimos uma bijeção entre $(\ZZ/(mn))^\ast$ e
$(\ZZ/(m))^\ast \times (\ZZ/(n))^\ast$,
o que garante que estes conjuntos têm o mesmo número de elementos.
\qed

{\nobf Corolário 3.5:}
{\sl Se $$n = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m}$$
com $p_1 < p_2 < \ldots < p_m$ e $e_i > 0$ para todo $i$ então
\begin{align}
\varphi(n) &=
(p_1^{e_1} - p_1^{e_1 - 1})(p_2^{e_2} - p_2^{e_2 - 1})\cdots
(p_m^{e_m} - p_m^{e_m - 1}) \notag\\
&= n\left({1 - \frac{1}{p_1}}\right)
\left({1 - \frac{1}{p_2}}\right) \cdots
\left({1 - \frac{1}{p_m}}\right). \notag
\end{align}
}

{\nobf Dem: }
Isto segue da fórmula que já vimos para $\varphi(p^e)$ e do corolário anterior.
\qed

Em particular, se $n > 2$ então $\varphi(n)$ é par.


\vskip .1in

\noindent
{\bf Problema resolvido:}
Exiba $n\in \mathbb N$ tal que $2^n$ tenha mais de duas mil casas decimais e tenha entre suas 2000 últimas casas decimais 1000 zeros consecutivos.

\vskip .1in

\noindent
{\bf Solução:}
$2^{\varphi(5^{2000})}\equiv 1$ (módulo $5^{2000}$), pelo Teorema de Euler. Portanto, existe $b\in\mathbb N$ com $2^{\varphi(5^{2000})}= 5^{2000} b+1$, e teremos $2^{2000+\varphi(5^{2000})}=10^{2000}b+2^{2000}$, e portanto os $2000$ últimos dígitos de $2^{2000+\varphi(5^{2000})}$ coincidem com a representação decimal de $2^{2000}$, que tem no máximo 667 dígitos, pois $2^3<10\Rightarrow 2^{2000}<2^{3.667}<10^{667}$. Desta forma, $2^{2000+\varphi(5^{2000})}$ tem pelo menos $2000-667=1333$ zeros consecutivos dentre as $2000$ últimas casas decimais, de modo que $n=4.5^{1999}+2000$ satisfaz as condições do enunciado (pois $\varphi(5^{2000})=4.5^{1999})$. \qed

\vskip .1in


Mais adiante estudaremos equações do segundo grau em $\ZZ/(p)$;
vejamos desde já um pequeno resultado deste tipo
que garante que os únicos $a$ que são seus próprios inversos
módulo $p$ são 1 e $-1$.

{\nobf Lema 3.6: }
{\sl Se $p$ é primo então as únicas soluções de $x^2 = 1$
em $\ZZ/(p)$ são 1 e $-1$.
Em particular,se $x\in (\ZZ/(p))^\ast - \{1,-1\}$
então $x^{-1} \neq x$ em $\ZZ/(p)$.
}

{\nobf Dem: }
Podemos reescrever a equação como $(x-1)(x+1) = 0$,
o que torna o resultado trivial.
\qed

{\nobf Teorema 3.7: \rm (Wilson) }
{\sl Seja $n > 4$.
Então $(n-1)! \equiv -1 \pmod n$ se $n$ é primo e
$(n-1)! \equiv 0 \pmod n$ se $n$ é composto.}

{\nobf Dem: }
Se $n$ é composto mas não é o quadrado de um primo
podemos escrever $n = ab$ com $1 < a < b < n$:
neste caso tanto $a$ quanto $b$ aparecem em $(n-1)!$
e $(n-1)! \equiv 0 \pmod n$.
Se $n = p^2$, $p > 2$, então $p$ e $2p$ aparecem em $(n-1)!$
e novamente $(n-1)! \equiv 0 \pmod n$;
isto demonstra que para todo $n$ composto, $n > 4$,
temos $(n-1)! \equiv 0 \pmod n$.

Se $n$ é primo podemos escrever
$(n-1)! \equiv - (2 \cdot 3 \cdots n-2) \pmod n$;
mas pelo lema anterior podemos juntar os inversos aos pares
no produto do lado direito, donde
$(n-1)! \equiv -1 \pmod n$.
\qed

\section{A função de Möbius}

Vejamos inicialmente uma propriedade da função $\varphi$.

{\nobf Teorema 4.1: }
{\sl Para todo natural $n$,
$$\sum_{d|n}{\varphi(d)} = n.$$
}

Este teorema segue facilmente da fórmula que provamos para $\varphi(n)$
na seção anterior. Daremos entretanto uma demonstração {\sl bijetiva}.

{\nobf Dem: }
Considere as $n$ frações
\[ \frac{0}{n}, \frac{1}{n}, \ldots , \frac{n-1}{n} \]
e simplifique cada uma delas:
obtemos assim, para cada $d | n$, $\varphi(d)$ frações com denominador $d$,
donde segue a identidade do enunciado.

Mais formalmente,
dado $\overline a \in \ZZ/(n)$, sejam $d = n/(n,a)$ e $a' = a/(n,a)$.
Claramente $\overline{a'} \in (\ZZ/(d))^\ast$
e definimos assim uma função de $\ZZ/(n)$ para 
a união disjunta dos conjuntos $(\ZZ/(d))^\ast$, 
onde $d$ varia sobre os divisores de $n$.
A inversa desta função leva $\overline{a'} \in (\ZZ/(d))^\ast$
em $\overline a$, $a = na'/d$, donde a função é uma bijeção.
\qed

O processo de construir $g$ a partir de $f$ como
$$g(n) = \sum_{d|n} f(d)$$
é bastante comum em teoria dos números.
Seria interessante poder inverter esta identidade para escrever
$f$ a partir de $g$.
O teorema anterior nos mostra que se fazemos $f = \varphi$
na equação acima temos $g(n) = n$;
invertendo esta identidade teríamos uma fórmula para $\varphi$.
O objetivo desta seção é mostrar como fazer este tipo de inversão.

Definimos a {\sl função de Möbius} $\mu: \NN^\ast \to \ZZ$ por
$$\mu(n) =
\begin{cases}
(-1)^m,& \text{se $n = p_1 p_2 \cdots p_m$, com $p_1 , p_2, \cdots, p_m $
primos distintos,}\notag\\
0,& \text{se $n$ tem algum fator primo repetido em sua fatoração.}
\end{cases}$$
Assim, $\mu(1) = \mu(6) = \mu(10) = 1$,
$\mu(2) = \mu(3) = \mu(5) = \mu(7) = -1$ e
$\mu(4) = \mu(8) = \mu(9) = 0$.

{\nobf Lema 4.2: }
{\sl 
Para todo inteiro positivo $n$ temos
$$\sum_{d|n} \mu(d) =
\begin{cases}
1,& \text{se $n=1$,}\notag\\
0,& \text{se $n>1$.}\notag\\
\end{cases}$$
}

{\nobf Dem: }
O caso $n = 1$ é trivial.
Se $n>1$, seja $p$ um divisor primo de $n$ e
seja $n = p^e n'$ com $p \nmid n'$.
Temos
\begin{align}
\sum_{d|n} \mu(d) &=
\sum_{d|n, p \nmid d} \mu(d) +
\sum_{d|n, p | d, p^2 \nmid d} \mu(d) +
\sum_{d|n, p^2 | d} \mu(d)\notag\\
&= 
\sum_{d|n'} \mu(d) +
\sum_{d'|n'} \mu(p d') + 0\notag\\
&=
\sum_{d|n'} \mu(d) -
\sum_{d'|n'} \mu(d') \notag\\
&= 0.\notag
\end{align}
\nobreak
\qed
\goodbreak


{\nobf Teorema 4.3: \rm (Fórmula de inversão de Möbius) }
{\sl Se para todo $n > 0$ temos
\[ g(n) = \sum_{d|n} f(d) \]
então
\[ f(n) = \sum_{d|n} \mu(n/d) g(d). \]}

Observe que a fórmula do corolário 1.16 para $\varphi(n)$
segue facilmente dos dois teoremas acima.

{\nobf Dem: }
Basta provar que
$$f(n) = \sum_{d|n} \mu(n/d) \left({ \sum_{d'|d} f(d') }\right).$$
Mas, escrevendo $d'' = n/d$ e $m = n/d'$ temos
\[
\sum_{d|n} \mu(n/d) \left({ \sum_{d'|d} f(d') }\right) =
\sum_{m|n} \left({ \sum_{d''|m} \mu(d'') }\right) f(n/m) =
f(n).
\]
\qed

{\nobf Teorema 4.4: \rm (Segunda fórmula de inversão de Möbius) }
{\sl Sejam $f$ e $g$ funções reais com domínio $(0, +\infty)$ tais que
$f(t) = g(t) = 0$ para todo $t < 1$.
Se
\[ g(x) = \sum_{k = 1}^{\infty} f\left({\frac{x}{k}}\right) =
\sum_{1 = k}^{\lfloor x \rfloor} f\left({\frac{x}{k}}\right)
\]
para todo $x$ então
então
\[ f(x) = \sum_{k = 1}^{\infty} \mu(k) g\left({\frac{x}{k}}\right) =
\sum_{1 = k}{\lfloor x \rfloor} \mu(k) g\left({\frac{x}{k}}\right).
\]
}

{\nobf Dem: }
Basta provar que
\[ f(x) = \sum_{k=1}^{\infty} \mu(k) \left({
\sum_{r = 1}^{\infty} f\left({\frac{x}{kr}}\right)
}\right),
\]
mas, tomando $m = kr$ a última soma é igual a
\[
\sum_{m=1}^{\infty} \left({ \left({
\sum_{k|m} \mu(k) }\right) f\left({\frac{x}{m}}\right) }\right)
\]
que pelo lema é igual a $f(x)$.
\qed



Apesar de não estar relacionada com o resto da nossa discussão,
não podemos deixar de mencionar a seguinte conjectura.

{\nobf Conjectura 4.5: \rm (Hipótese de Riemann) }
{\sl Se $\alpha > 1/2$ então
$$\lim_{n \to \infty} \frac{1}{n^\alpha} \sum_{1 \le m}^n \mu(m) = 0.$$}

Esta é uma das formulações da famosa hipótese de Riemann,
um dos problemas em aberto mais importantes da matemática.

Podemos reenunciar esta conjectura assim:
seja $f: (0, +\infty) \to \RR$ definida por $f(t) = 0$ se $ t<1 $  e 
\[ \sum_{k=1}^{\infty} f(t/k) = 1, \quad \text{se }t \ge 1 \]
então, para todo $\alpha > 1/2$,
\[ \lim_{t \to \infty} \frac{f(t)}{t^\alpha} = 0. \]
De fato, pela segunda fórmula de inversão de Möbius temos
\[ f(t) = \sum_{m = 1}^{\lfloor t \rfloor} \mu(m). \]



\section{Bases}


A notação usual para naturais é a chamada base 10, com algarismos $0, \ldots, 9$.
Isto significa, por exemplo, que
$$196883 =
1 \cdot 10^5 + 9 \cdot 10^4 + 6 \cdot 10^3 +
8 \cdot 10^2 + 8 \cdot 10^1 + 3 \cdot 10^0.$$
O teorema abaixo mostra como escrever qualquer natural em qualquer base $d$.

{\nobf Teorema 5.1: }
{\sl Seja $n \ge 0$ e $d > 1$. Então existe uma única seqüência
$a_0, \ldots, a_k, \ldots$ com as seguintes propriedades:

{\rm (a)}

\begin{itemize}
\item[{\rm 1.}] {para todo $k$, $0 \le a_k < d$,}
\item[{\rm 2.}] {existe $m$ tal que se $k \ge m$ então $a_k = 0$,}
\item[{\rm 3.}] {$n = \sum_k a_k d^k$.}
\end{itemize}
}

{\nobf Dem: }
Escrevemos $n = n_0 = n_1 d + a_0$, $0 \le a_0 < d$,
$n_1 = n_2 d + a_1$, $0 \le a_1 < d$, e em geral
$n_k = n_{k+1} d + a_k$, $0 \le a_k < d$.
Nossa primeira afirmação é que $n_k = 0$ para algum valor de $k$.
De fato, se $n_0 < d^m$ então $n_1 < d^{m-1}$
e mais geralmente, por indução, $n_k < d^{m-k}$;
fazendo $k \ge m$ temos $n_k < 1$ donde $n_k = 0$.
Segue daí que $a_k = 0$ para $k \ge m$.
A identidade do item (c) é facilmente demonstrada por indução.

Para a unicidade, suponha $\sum_k a_k d^k = \sum_k b_k d^k$.
Se as seqüências $a_k$ e $b_k$ são distintas existe um menor
índice, digamos $j$, para o qual $a_j \ne b_j$.
Podemos escrever
$a_j + \sum_{k > j} a_k d^{k-j} =
b_j + \sum_{k > j} b_k d^{k-j}$
donde $a_j \equiv b_j \pmod d$, o que é uma contradição.
\qed

Às vezes é interessante considerar expansões não apenas
em outras bases mas com outros conjuntos de algarismos
(veremos um exemplo disso no último capítulo).
Por exemplo, podemos preferir algarismos negativos pequenos
a algarismos positivos grandes e assim um bom conjunto
de algarismos na base 10 seria $$-4, -3, -2, -1, 0, 1, 2, 3, 4, 5.$$
Desta forma, escrevemos $13 = 1 \cdot 10 + 3$ mas escrevemos
$9 = 1 \cdot 10 - 1$ e $64 = 1 \cdot 10^2 - 4 \cdot 10 + 4$.
Generalizando, os algarismos na base $d$ seriam
os inteiros $a$ com $-d/2 < a \le d/2$, ou seja,
$$a = - \lfloor (d-1)/2 \rfloor, - \lfloor (d-1)/2 \rfloor + 1, \ldots,
-1, 0, 1, \ldots, \lfloor d/2 \rfloor - 1, \lfloor d/2 \rfloor.$$
Este conjunto de algarismos nos permite enunciar um teorema análogo
ao anterior, com a diferença que agora números negativos
não precisam ser tratados em separado.

{\nobf Teorema 5.2: }
{\sl Seja $n \in \ZZ$ e $d > 2$. Então existe uma única seqüência
$a_0, \ldots, a_k, \ldots$ com as seguintes propriedades:

{\rm (a)}

\begin{itemize}
\item[{\rm 1.}] {para todo $k$, $-d/2 < a_k \le d/2$,}
\item[{\rm 2.}] {existe $m$ tal que se $k \ge m$ então $a_k = 0$,}
\item[{\rm 3.}] {$n = \sum_k a_k d^k$.}
\end{itemize}
}

{\nobf Dem: }
Escrevemos $n = n_0 = n_1 d + a_0$, $-d/2 < a_0 \le d/2$,
$n_1 = n_2 d + a_1$, $-d/2 < a_1 \le d/2$, e em geral
$n_k = n_{k+1} d + a_k$, $-d/2 < a_k \le d/2$.
Novamente,
nossa primeira afirmação é que $n_k = 0$ para algum valor de $k$.
De fato, se $$-d^m/2 < n_0 \le d^m/2$$ então, por indução,
$$-d^{m-k}/2 < n_k \le d^{m-k}/2;$$
fazendo $k \ge m$ temos $n_k = 0$.
Segue daí que $a_k = 0$ para $k \ge m$.
A identidade do item (c) e a unicidade são demonstradas
como no teorema anterior.
\qed

Pode-se estudar representações na base $d$
com outros conjuntos $X$ de algarismos.
Algumas condições mínimas para que $X$ seja um conjunto de algarismos
interessante são que $0 \in X$, que $X$ seja um sistema completo de resíduos
e que o mdc dos elementos de $X$ seja 1.

\section{Corpos e polinômios}

Um {\sl grupo} é um conjunto $G$ munido de uma operação
$\ast: G \times G \to G$ e um elemento $e \in G$ com as seguintes
propriedades:

\begin{itemize}
\item[1.] {para quaisquer $a, b, c \in G$, $a*(b*c) = (a*b)*c$.}
\item[2.] {para qualquer $a \in G$, $a*e = e*a = a$,}
\item[3.] {para qualquer $a \in G$ existe $b \in G$ com $a*b = b*a = e$.}
\end{itemize}
Se além disso tivermos $a*b = b*a$ para quaisquer $a, b \in G$
dizemos que o grupo é {\sl comutativo} ou {\sl abeliano}.
Quando a operação $\ast$ se chama $+$ dizemos que $G$ é um grupo aditivo
e chamamos o elemento neutro $e$ de 0.
Se a operação se chama $\cdot$ chamamos $G$ de grupo multiplicativo
e denotamos o elemento neutro $e$ por 1.
Assim, $\ZZ/(n)$ é um grupo abeliano aditivo e
$(\ZZ/(n))^\ast$ é um grupo abeliano multiplicativo.

Um {\sl anel comutativo com unidade} é um grupo abeliano aditivo $A$
munido de uma segunda operação $\cdot: A \times A \to A$ satisfazendo
$a \cdot (b \cdot c) = (a \cdot b) \cdot c$,
$a \cdot (b+c) = (a \cdot b) + (a \cdot c)$,
$a \cdot b = b \cdot a$ para quaisquer $a, b, c \in A$
e um elemento $1 \in A$ com $1 \cdot a = a$ para todo $a \in A$.
Assim, $\ZZ/(n)$ é um anel comutativo com unidade.

Um {\sl corpo} é um anel comutativo com unidade onde para todo $a \in K$
com $a \ne 0$ existe $b \in K$ com $a \cdot b = 1$.
Repetindo então, $K$ é munido de duas operações
$+: K \times K \to K$ e $\cdot:K \times K \to K$,
de uma função $-:K\to K$ e dois elementos especiais distintos chamados 0 e 1
satisfazendo as seguintes propriedades:
\begin{align}
a+(b+c) &= (a+b)+c \notag\\
a+0 &= a \notag
\end{align}
\begin{align}
a+(-a) &= 0 \notag\\
a+b &= b+a \notag\\
a(b+c) &= ab + ac \notag\\
a(bc) &= (ab)c \notag\\
a1 &= a \notag\\
ab &= ba \notag
\end{align}
e onde para todo $a \in K$, $a \ne 0$ existe $b \in K$ com
$$ab = 1.$$
Os exemplos mais conhecidos de corpos são $\QQ$, $\RR$ e $\CC$.
Vimos no capítulo anterior que $\ZZ/(p)$ também é um corpo se $p$ é primo;
veremos a seguir outros exemplos de corpos finitos.

Dado um corpo $K$, definimos o anel comutativo com unidade $K[x]$
como sendo o conjunto das expressões
da forma $P = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$,
chamados de {\sl polinômios} com coeficientes em $K$.
Observe que $x$ é um símbolo formal e não um elemento de $K$;
apesar disso, cada polinômio define uma {\sl função polinomial}
\begin{align}
P: K &\to K \notag\\
c &\mapsto  P(c) = a_0 + a_1 c + a_2 c^2 + \cdots + a_n c^n \notag
\end{align}
também chamada de $P$.
A distinção entre um polinômio e uma função polinomial
é bem ilustrada pelo polinômio $P = x^p - x \in (\ZZ/(p))[x]$:
este polinômio é não nulo pois seus coeficientes são não nulos
mas para todo $x \in \ZZ/(p)$ temos $P(x) = 0$
pelo pequeno teorema de Fermat.

Se $P = \sum a_i x^i$  e $Q = \sum b_i x^i$ são polinômios definimos
$P+Q = \sum (a_i + b_i) x^i$ e $PQ = \sum c_i x^i$ onde
$c_k = \sum_{i+j = k} a_i b_j$.
Definimos o {\sl grau} $\deg P$ de um polinômio
$P = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n$
como sendo $n$ se $a_n \ne 0$ mas $a_m = 0$ para $m > n$;
definimos ainda o grau do polinômio 0 como sendo $-\infty$.

{\nobf Lema 6.1: }
{\sl Para quaisquer polinômios $P$ e $Q$ temos
$\deg(PQ) = \deg(P) + \deg(Q)$ e \linebreak
$\deg(P + Q) \le \max\{ \deg(P), \deg(Q)\}$.}

{\nobf Dem: }
Fácil.
\qed

Observe que definimos $-\infty < n$ e
$(-\infty) + (-\infty) = -\infty +  n = -\infty$ para todo $n$.
Temos uma forma de divisão com resto em $K[x]$.

{\nobf Teorema 6.2: }
{\sl Sejam $A, B \in K[x]$, $B \ne 0$.
Então existem únicos polinômios $Q, R \in K[x]$ com
$A = QB + R$ e $\deg R < \deg B$.}

{\nobf Dem: }
A demonstração é feita por indução no grau de $A$.
Se $\deg(A) < \deg(B)$, tomamos $Q = 0$, $R = A$.
Caso contrário, sejam $n$ e $m$ os graus de $A$ e $B$
e sejam $a$ e $b$ os coeficientes de mais alto grau destes polinômios.
Podemos escrever $A = (a/b) x^{n-m} B + A_1$,
com $\deg(A_1) < \deg(A)$.
Pela hipótese de indução, temos $A_1 = Q_1 B + R$, com $\deg(R) < \deg(B)$.
Fazendo $Q = (a/b) + x^{n-m} + Q_1$ temos $A = QB + R$.
A unicidade segue facilmente do lema anterior.
\qed

A demonstração acima nada mais é do que
o algoritmo usual de divisão usual.
Um polinômio $P$ tem {\sl raiz} $a$ (i.e., $P(a) = 0$)
se e somente se $(x - a) | P$.
Mais geralmente, $P(a)$ é o resto da divisão de $P$ por $x-a$.

{\nobf Proposição 6.3: }
{\sl Um polinômio $P$ não nulo de grau $n$ tem no máximo $n$ raízes. }

{\nobf Dem: }
A demonstração é feita por indução em $n = \deg(P)$;
os casos $n = 0$ e $n = 1$ são triviais.
Se $P$ tivesse $n+1$ raízes distintas $a_1, \ldots, a_{n+1}$
então $P$ seria múltiplo de $(x - a_{n+1})$;
$P/(x - a_{n+1})$ teria grau $n-1$ e raízes $a_1, \ldots, a_n$,
contradizendo a hipótese de indução.
\qed

A partir da divisão com resto podemos repetir
muitas das construções feitas para $\ZZ$ no capítulo anterior;
dizemos que $K[x]$ (assim como $\ZZ$) é um {\sl domínio euclidiano}.
Daremos um esboço desta teoria;
estes resultados não serão necessários para acompanhar o resto do livro.

Definimos $A|B$ se existe $C$ com $AC = B$
e dizemos que um polinômio $P$ de grau maior que $n>0$ é {\sl irredutível}
se seus divisores todos têm grau 0 ou $n$
(assim generalizando o conceito de número primo).
O conceito de mdc também se generaliza,
como indicado na proposição abaixo.

{\nobf Proposição 6.4: }
{\sl Dados polinômios não nulos $A, B \in K[x]$
existe um único $D \in K[x]$ (a menos de multiplicação por constante)
tal que $D|A$, $D|B$ e, para todo $C \in K[x]$, se $C|A$ e $C|B$ então $C|D$.
Além disso existem $E, F \in \ZZ$ com $D = AE + BF$.}

{\nobf Dem: }
Definimos $I(A,B) = \{AE + BF; E, F \in K[x]\}$
e tomamos $D$ de grau mínimo dentre os elementos não nulos de $I(A,B)$;
o resto da demonstração é análoga à da proposição 1.1.
\qed

Polinômios irredutíveis são como números primos:
um produto de polinômios só é múltiplo de um polinômio irredutível
se um dos fatores o for.

{\nobf Proposição 6.5: }
{\sl Sejam $P$ um polinômio irredutível e sejam $A_1, \ldots A_m \in K[x]$.
Se $P|(A_1 \cdots A_m)$ então $P|A_i$ para algum $i$, $1 \le i \le n$.}

{\nobf Dem: }
Análoga à do corolário 1.3.
\qed

Temos também um teorema de fatoração única.

{\nobf Teorema 6.6: }
{\sl Todo polinômio pode ser fatorado
como um produto de polinômios irredutíveis;
esta fatoração é única a menos da ordem dos fatores.}

{\nobf Dem: }
Análoga à do teorema fundamental da aritmética,
usando a proposição acima e fazendo indução no grau do polinômio.
\qed

Os exemplos mais evidentes de polinômios irredutíveis
são os da forma $x - a$, $a \in K$.
Quando estes são os {\sl únicos} polinômios irredutíveis
dizemos que o corpo é {\sl algebricamente fechado}.
Polinômios de grau 2 e 3 são irredutíveis
se e somente se não têm raízes.


O pequeno teorema de Fermat também admite uma formulação
em termos de polinômios.

{\nobf Teorema 6.7: }
{\sl Seja $p$ primo; em $(\ZZ/(p))[x]$ temos
$$x^p - x = x(x-1)(x-2)\cdots (x-(p-1)).$$}

{\nobf Dem: }
Os dois polinômios dos dois lados da equação têm grau $p$
e o coeficiente de $x^p$ é 1 nos dois casos.
Assim, a diferença tem grau menor do que $p$
mas se anula em $p$ pontos: 0, 1, \ldots $p-1$.
Pelo corolário anterior, esta diferença deve ser o polinômio zero.
\qed

A partir do teorema acima temos uma nova prova do teorema de Wilson:
$x^{p-1} - 1 = (x-1)(x-2)\cdots (x-(p-1))$ em $(\ZZ/(p))[x]$,
mas o coeficiente independente é $-1$ do lado esquerdo
e $(p-1)!$ do lado direito.

Podemos definir congruências em $K[x]$:
$$A \equiv B \pmod P \iff P | (B-A).$$
As propriedades básicas de congruências podem ser traduzidas
para este novo contexto e podemos definir um quociente $K[x]/(P)$
da mesma forma como definimos $\ZZ/(n)$;
demonstra-se que $K[x]/(P)$ é um corpo exatamente quando $P$ é irredutível.

Prometemos que veríamos outros exemplos de corpos finitos além de $\ZZ/(p)$:
o parágrafo acima ensina que podemos construir tais corpos como
$(\ZZ/(p))[x]/(P)$ onde $P \in (\ZZ/(p))[x]$ é irredutível.
Por exemplo, o polinômio $x^2 + x + 1$ é irredutível em $(\ZZ/(2))[x]$
o que nos permite construir um corpo de 4 elementos: 0, 1, $x$ e $x+1$.
As operações em $\ZZ/(2)$ e a relação $x^2 = x + 1$
definem as operações neste corpo (denotamos $x+1$ por $x'$):

\begin{figure}[h]
\begin{center}
\includegraphics{Figura4.eps}
%\caption{}
\end{center}
\end{figure}

De fato existem em $(\ZZ/(p))[x]$ polinômios irredutíveis de qualquer grau
e todo corpo finito pode ser construido desta forma.
Enunciaremos sem demonstração um teorema
que classifica os corpos finitos.

{\nobf Teorema 6.8: }
{\sl Existe um corpo finito com $q$ elementos se e somente se
$q$ é da forma $p^n$ para algum primo $p$ e algum inteiro positivo $n$.
Além disso, dados dois corpos finitos $K_1$ e $K_2$
com o mesmo número de elementos
existe uma única bijeção $f: K_1 \to K_2$
com $f(a+b) = f(a) + f(b)$ e $f(ab) = f(a) f(b)$
para quaisquer $a, b \in K_1$.}

Uma bijeção como a descrita acima é chamada de {\sl isomorfismo}
e dois corpos são ditos {\sl isomorfos} se existe entre eles um isomorfismo;
a idéia é que corpos isomorfos são iguais a menos dos nomes dos elementos.
Veremos mais tarde outras formas mais concretas de construir corpos finitos.

\section{Ordens e raízes primitivas}

Dados $n, a \in \ZZ$ com $n > 0$ e $(a, n) = 1$,
definimos a {\sl ordem de $a$ módulo $n$},
denotada por $\ordem_n a$,
como sendo o menor inteiro positivo $t$
com $a^t \equiv 1 \pmod n$.
Analogamente, se $K$ for um corpo finito e $a \in K$, $a \ne 0$,
definimos a {\sl ordem de $a$ em $K$},
denotada por $\ordem_K a$,
como sendo o menor inteiro positivo $t$
com $a^t = 1 \in K$;
temos $\ordem_p a = \ordem_{\ZZ/(p)} a$.

Claramente $a^e \equiv a^{e'} \pmod n$
se e somente se $e \equiv e' \pmod {\ordem_n a}$;
pelo teorema de Euler, $\ordem_n a|\varphi(n)$.

Dizemos que $a$ é uma {\sl raiz primitiva módulo $n$}
se $\ordem_n a = \varphi(n)$.
Analogamente, dizemos que $a$ é uma {\sl raiz primitiva em $K$}
se $\ordem_K a = q-1$, onde $q = |K|$ é o número de elementos de $K$.
Por exemplo, 2 é raiz primitiva módulo 5 mas
2 não é raiz primitiva módulo 7 ($2^3 \equiv 1 \pmod 7$).
Também é fácil verificar que não existe raiz primitiva módulo 8
pois se $x$ é ímpar então $x^2 \equiv 1 \pmod 8$.
Podemos também dizer que $a$ é raiz primitiva se a função
\begin{align}
\ZZ/(\varphi(n)) &\to (\ZZ/(n))^\ast \notag\\
r &\mapsto a^r \notag
\end{align}
ou
\begin{align}
\ZZ/(q - 1) &\to K^\ast \notag\\
r &\mapsto a^r \notag
\end{align}
é injetora.
Como o domínio e contradomínio são conjuntos finitos
com o mesmo número de elementos,
a função é injetora se e somente se ela é sobrejetora.
Podemos assim dizer que $a$ é uma raiz primitiva módulo $n$
se e somente se para todo $b \in (\ZZ/(n))^\ast$ 
(ou para todo $b \in K^\ast$) existe $r$ com $a^r = b$.

Um corolário desta caracterização de raízes primitivas
é que se $a$ é raiz primitiva módulo $n$ e $m|n$ então
$a$ é raiz primitiva módulo $m$.
O objetivo da próxima seção é caracterizar
os valores de $n$ para os quais existe uma raiz primitiva módulo $n$.
Nesta seção mostraremos que todo corpo finito admite raiz primitiva;
em particular existe raiz primitiva módulo $p$ para qualquer primo $p$.

Precisamos primeiro de uma versão do pequeno teorema de Fermat
para corpos finitos:

{\nobf Teorema 7.1: }
{\sl Se $K$ é um corpo finito e $q = |K|$
então $a^q - a = 0$ para todo $a \in K$.}

{\nobf Dem: }
Se $a = 0$ o teorema vale; vamos supor a partir de agora $a \ne 0$.
Sejam $b_1, \ldots b_{q-1}$ os elementos não nulos de $K$.
Os elementos $a b_1, \ldots a b_{q-1}$ são todos não nulos e distintos,
logo são os {\sl próprios} $b_1, \ldots b_{q-1}$, apenas permutados.
Assim
\begin{align}
b_1 \cdot b_2 \cdots b_{q-1} &= (a b_1) (a b_2) \cdots (a b_{q-1}) \notag\\
&= a^{q-1} (b_1 \cdot b_2 \cdots b_{q-1}) \notag
\end{align}
e $a^{q-1} = 1$.
\qed

Segue deste teorema que $\ordem_K a | q-1$,
analogamente ao que já sabiamos para $\ZZ/(n)$.
A partir do que vimos sobre polinômios temos também que 
$$x^q - x = x(x - b_1)\cdots (x - b_{q-1})$$ em $K[x]$.

{\nobf Teorema 7.2: }
{\sl Se $K$ é um corpo finito então existe raiz primitiva em $K$.}

{\nobf Dem: }
Seja $d$ um divisor de $q-1$:
definimos $N(d)$ como o número de elementos de $K^\ast$ de ordem $d$.
Claramente $\sum_{d | q-1} N(d) = q-1$.

Se $N(d) > 0$, seja $a_d$ um elemento de $K$ com $\ordem_K a_d = d$:
os elementos $1, a_d, a_d^2, \ldots a_d^{d-1}$
são raízes do polinômio $x^d - 1 = 0$.
Como este polinômio tem no máximo $d$ raízes,
estas são todas as raízes.
Assim, os elementos de $K$ de ordem $d$ são precisamente
$a_d^r$, $r \in (\ZZ/(d))^\ast$.
Assim os únicos valores possíveis para $N(d)$ são 0 e $\varphi(d)$.
Mas como $\sum_{d | q-1} N(d) = \sum_{d | q-1} \varphi(d) = q-1$,
temos $N(d) = \varphi(d)$ para todo $d | q-1$.
Em particular $N(q-1) > 0$ e existem raízes primitivas.
\qed

Apesar de existirem raízes primitivas módulo $p$ para todo primo $p$
não existe uma fórmula simples para obter uma raiz primitiva.
Por outro lado, conjectura-se que todo inteiro que não é um quadrado
é raiz primitiva para infinitos valores de $p$ (conjectura de Artin).

{\nobf Corolário 7.3: }
{\sl Dados $x \in K^\ast$  e um inteiro positivo $k$
existe $y \in K^\ast$ com $y^k = x$
se e somente se $x^{(q-1)/\mdc(k,q-1)} = 1$, onde $q = |K|$.}

{\nobf Dem: }
Se $x = y^k$ então $x^{(q-1)/\mdc(k,q-1)} = (y^{q-1})^{k/\mdc(k,q-1)} = 1$
pois $y^{q-1} = 1$.
Suponha agora que $x^{(q-1)/\mdc(k,q-1)} = 1$.
Sejam $a$ uma raiz primitiva de $K$ e $r \in \ZZ$ com $x = a^r$.
Temos $(a^r)^{(q-1)/\mdc(k,q-1)} = 1$ donde $\mdc(k,q-1) \mid r$
e portanto existem inteiros $u, v$ com $ku + (q-1)v = r$.
Assim $x = a^r = a^{ku + (q-1)v} = (a^u)^k \cdot (a^{q-1})^v = y^k$
onde $y = a^u$.
\qed



\section{Raízes primitivas em $\ZZ/(n)$}


Nesta seção caracterizaremos os inteiros $n$ para os quais
existe raiz primitiva módulo $n$.



{\nobf Lema 8.1: }
{\sl Sejam $p$ um número primo e $a \in \ZZ$
uma raiz primitiva módulo $p$.
Então $a$ ou $a' = a + p$ é raiz primitiva módulo $p^2$.}

{\nobf Dem: }
Pelo binômio de Newton, ${a'}^p = (a+p)^p \equiv a^p \pmod {p^2}$.
Sem perda de generalidade, podemos supor $a^p \not\equiv a \pmod {p^2}$
ou $a^{p-1} \not\equiv 1 \pmod {p^2}$, donde $\ordem_{p^2} a \ne p-1$.
Como $p-1 = \ordem_p a \mid \ordem_{p^2} a \mid \varphi(p^2) = p(p-1)$
isto implica em $\ordem_{p^2} a = p(p-1)$.
\qed

{\nobf Lema 8.2: }
{\sl  Se $p$ é um número primo ímpar e $a$ é raiz primitiva
módulo $p^2$ então $a$ é raiz primitiva módulo $p^k$ para todo $k > 2$,
$k \in \ZZ$.}

{\nobf Dem: }
Temos $a^{p-1} \equiv  1 \pmod p$, mas $a^{p-1} \not\equiv 1 \pmod {p^2}$,
donde $a^{p-1} = 1 + b_0 p$ com $b_0 \not\equiv 0 \pmod p$.
Vamos mostrar por indução que $a^{p^j (p-1)} = 1 + b_j p^{j+1}$
com $b_j \equiv b_0 \pmod p$.
Podemos escrever
\begin{align}
a^{p^{j+1} (p-1)} &= (a^{p^j (p-1)})^p \notag\\
&= (1 + b_j p^{j+1})^p \notag\\
&= 1 + p b_j p^{j+1} + \binom{p}{2} b_j^2 p^{2j+2}
+ \cdots + b_j^p p^{pj+p} \notag\\
&= 1 + b_j (1 + \binom{p}{2} b_j p^{j} + \cdots b_j^{p-1} p^{(p-1)j + p - 2})
p^{j+2} \notag\\
&= 1 + b_{j+1} p^{j+2} \notag
\end{align}
com $b_{j+1} \equiv b_j \pmod p$ pois o parêntesis na penúltima linha
é da forma $1 + $ um múltiplo de $p$.
Esta última afirmação segue da positividade dos expoentes de $p$
{\sl exceto} no caso $j = 0$;
neste caso o expoente do primeiro termo não trivial é zero
mas temos $\binom{p}{2} \equiv 0 \pmod p$ pois $p > 2$
(é neste ponto que precisamos da hipótese de $p$ ser ímpar).
O lema segue de $a^{(p-1)p^{k-2}} \not\equiv 1 \pmod {p^k}$ por indução,
pois teremos $(p-1) p^{k-2} = \ordem_{p^{k-1}} a \mid \ordem_{p^k} a \mid
\varphi(p^k) = (p-1) p^{k-1}$, donde $\ordem_{p^k} a = (p-1) p^{k-1}$.
\qed


\vskip .1in

\noindent
{\bf Exemplo:}
2 é raiz primitiva módulo $5^k$, $\forall\, k\in\mathbb N$. De fato, 2 é raiz primitiva módulo 5, e, como $2^4=16\ne 1$ (módulo 25), 2 é raiz primitiva módulo $25=5^2$ (como no Lema 8.1). Portanto, pelo Lema 8.2,\,\,
2 é rais primitiva módulo $5^k$, $\forall\, k\in \mathbb N$.

\vskip .1in

\noindent
{\bf Problema resolvido:}
Mostre que existe $n$  natural tal que os mil últimos dígitos de $2^n$ pertencem a $\{1,2\}$.

\vskip .1in

\noindent
{\bf Solução:}
Observamos inicialmente que para todo $k\in\mathbb N$ existe um número $m_k$ de $k$ algarismos, todos $1$ ou $2$, divisível por $2^k$. De fato, $m_1=2$ e $m_2=12$ satisfazem o enunciado.

Seja $m_k=2^k\cdot r_k$, $r_k\in\mathbb N$. Se $r_k$ é par, tome $m_{k+1}=2\cdot 10^k+m_k=2^{k+1}(5^k+r_k/2)$, e se $r_k$ é ímpar, tome $m_{k+1}=10^k+m_k=2^{k+1}(5^k+r_k)/2$.

Como $m_{1000}\equiv 2$ (módulo 10), 5 não divide $r_{1000}=m_{1000}/2^{1000}$. Como 2 é raiz primitiva módulo $5^{1000}$, existe $k\in\mathbb N$ com $2^k\equiv r_{1000}$ (módulo $5^{1000}$). Logo $2^k=b\cdot 5^{1000}+ r_{1000}$, para algum $b\in\mathbb N$. Portanto, $2^{k+1000}=b\cdot 10^{1000}+
2^{1000}\cdot r_{1000}=b\cdot 10^{1000}+m_{1000}$, e as $1000$ últimas casas de $2^{k+1000}$ são as $1000$ casas de $m_{1000}$, que pertencem todas a $\{1,2\}$. \qed

\vskip .1in


{\nobf Lema 8.3: }
{\sl Seja $n > 1$.
O número de soluções para a congruência
$x^2 \equiv 1 \pmod n$ é:

\begin{itemize}

\item[{\rm 1.}]\quad {1 se $n = 2$,}
\item[{\rm 2.}]\quad {2 se $n = 4$,}
\item[{\rm 3.}]\quad {4 se $n = 2^k$, $k > 2$,}
\item[{\rm 4.}]\quad  {2 se $n = p^k$, $p$ um primo ímpar,}
\item[{\rm 5.}] \quad {$2^{m + i}$ se $n = 2^k p_1^{e_1} \cdots p_m^{e_m}$,
onde $i = 0$ se $k \le 1$, $i = 1$ se $k = 2$ e $i = 2$ se $k > 2$.}
\end{itemize}
}

{\nobf Dem: }
Os itens (a) e (b) são verificáveis diretamente.
As quatro soluções no item (c) são
1, $2^{k-1} - 1$, $2^{k-1} + 1$ e $2^k - 1$.
De fato, é fácil verificar que estes quatro valores são soluções da congruência.
Por outro lado,
para que $a$ seja solução da congruência devemos ter
$2^k | (a+1)(a-1) = a^2 - 1$;
portanto $a$ deve ser ímpar.
Um dentre $a-1$ e $a+1$ deve ser da forma $2b$, $b$ ímpar.
Assim o outro deve ser múltiplo de $2^{k-1}$,
o que diz que $a$ deve ter um dos quatro valores acima.
Analogamente para o item (d), apenas um dentre $a - 1$ e $a + 1$
é múltiplo de $p$, o que só permite as soluções 1 e $n-1$.

Para o item (e) usamos os itens anteriores e o teorema chinês dos restos:
$a$ é solução da congruência acima se e somente se $a$ satisfaz
$a^2 \equiv 1 \pmod {2^k}$ e $a^2 \equiv 1 \pmod {p_i^{e_i}}$ para cada $i$.
Assim, o número de soluções módulo $n$ é o produto do número
de soluções módulo $2^k$, $p_1^{e_1}$, \dots, $p_m^{e_m}$,
o que nos dá a fórmula do item (e).
\qed


{\nobf Teorema 8.4: }
{\sl Um inteiro $n > 1$ admite raiz primitiva
se e somente se $n = 2$, $n = 4$ ou $n$ é da forma $p^k$ ou $2 p^k$,
onde $p$ é um primo ímpar, admite raiz primitiva.}

{\nobf Dem: }
Os casos $n = 2$ e $n = 4$ podem ser verificados diretamente.
A existência de uma raiz primitiva módulo $p^k$ ($p$ um primo ímpar)
segue dos dois primeiros lemas desta seção.
Para o caso $2 p^k$, seja $a$ uma raiz primitiva módulo $p^k$:
$a$ ou $a + p^k$, aquele que for ímpar,
será uma raiz primitiva módulo $2 p^k$ pois $\varphi(2 p^k) = \varphi(p^k)$.

Se $n$ não for de uma destas formas, o lema anterior garante que a congruência
$x^2 \equiv 1 \pmod n$ admite mais de duas soluções.
Por outro lado, a existência de uma raiz primitiva $a$ módulo $n$
garante que a congruência $x^2 \equiv 1 \pmod n$ só tem as soluções 1 e $n-1$.
De fato, qualquer solução pode ser escrita da forma $a^k$ para algum $k$
e nossa congruência torna-se $a^{2k} \equiv 1 \pmod n$
ou $2k \equiv 0 \pmod {\varphi(n)}$,
que só tem as soluções $k = 0$ ($a^k = 1$) e $k = (\varphi(n))/2$
($a^k \equiv n-1 \pmod n$).

Outra demonstração, sem usar o lema anterior, consiste em observar que
se $n$ não for de uma destas duas formas então $n = n_1 n_2$,
com $n_1, n_2 \ge 3$ e $\mdc(n_1,n_2) = 1$.
Temos então $a^{\varphi(n)/2} \equiv 1 \pmod n$ para todo $a$ inteiro
com $\mdc(a,n) = 1$, pois $\varphi(n_1) \mid \varphi(n)/2$ e
$\varphi(n_2) \mid \varphi(n)/2$.
\qed

\section{A lei da reciprocidade quadrática}

A lei de Gauss de reciprocidade quadrática afirma que se $p$ e $q$ são primos
há uma relação direta entre $p$ ser quadrado módulo $q$
e $q$ ser quadrado módulo $p$.
Este teorema fornece um rápido algoritmo para determinar se $a$ é
quadrado módulo $p$ onde $a$ é um inteiro e $p$ um número primo.


{\nobf Definição 9.1: }
{\sl Seja $p$ um primo e $a$ um inteiro. Definimos o
símbolo de Lagrange $(\frac{a}{p})$ por
\[ \left(\frac{a}{p}\right) =
\begin{cases}
0& \text{se $p$ divide $a$}\\
-1& \text{se $a$ não é quadrado módulo $p$}\\
1& \text{se $p\nmid a$ e $a$ é quadrado módulo $p$}.
\end{cases} 
\]
}


{\nobf Proposição 9.2: }
{\sl Seja $p$ um primo ímpar e $a\in\ZZ$ tal que
$p\nmid a$. Então $\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p$.}


{\nobf Dem:}
Sabemos que se $p\nmid a$ então $a^{p-1}\equiv 1 \pmod p$,
ou seja, $X^{p-1}-1$ tem como raízes $1,2,\dots,p-1$ em $\ZZ/(p)$.
Por outro lado, $X^{p-1}-1 =
({X^{\frac{p-1}{2}}-1})(X^{\frac{p-1}{2}} + 1)$.
Se existe $b \in \ZZ$ tal que $a \equiv b^2 \pmod p$ então
$a^{\frac{-1}{2}} \equiv b^{p-1} \equiv 1 \pmod p$;
ou seja,
$\left(\frac{a}{p}\right) = 1 \equiv a^{\frac{p-1}{2}} \pmod p$.
Como $X^2 \equiv Y^2 \pmod p \Leftrightarrow X \equiv \pm Y \pmod p$,
há pelo menos $\frac{p-1}{2}$ quadrados em $(\ZZ/(p))^*$, logo os quadrados
são exatamente as raízes de $X^{\frac{p-1}{2}} - 1$ em $\ZZ/(p)$, donde os não
quadrados são exatamente as raízes de $X^{\frac{p-1}{2}} + 1$, ou seja, se
$(\frac bp)=-1$ então $b^{\frac{p-1}{2}} \equiv -1 \pmod p$.
\qed


{\nobf Corolário 9.3: }
{\sl Se $p$ é primo ímpar então $(\frac{-1}{p}) = (-1)^{\frac{p-1}{2}}$.}

Vamos agora reinterpretar a Proposição 1.
Seja $a \in (\ZZ/(p))^\ast$.
Para cada $j = 1,2,\ldots,\frac{p-1}{2}$ escrevemos $a \cdot j$ como
$\ve_j m_j$ com $\ve_j \in \{-1,1\}$ e
$m_j \in \{1,2,\dots,\frac{p-1}{2}\}$.
Se $m_i \ne m_j$ temos
$a \cdot i = a \cdot j$ ou $a \cdot i = - a \cdot j$;
a primeira possibilidade implica $i = j$ e a segunda é impossível.
Assim, se $i \ne j$ temos $m_i \ne m_j$ donde
$\{m_1,m_2,\dots,m_{\frac{p-1}{2}}\} =
\{1,2,\dots,\frac{p-1}{2}\}$.
Assim
\begin{align}
\left(\frac{a}{p}\right) &\equiv a^{\frac{p-1}{2}} \notag\\
&= \frac{ (a\cdot 1)(a\cdot 2)\cdots(a \cdot {\frac{p-1}{2}}) }%
{1 \cdot 2 \cdots \frac{p-1}{2}} \notag\\
&\equiv
\frac{\ve_1 \ve_2 \cdots \ve_{\frac{p-1}{2}}\,m_1,m_2,\dots,m_{\frac{p-1}{2}}}%
{1 \cdot 2 \cdots \frac{p-1}{2}} \notag\\
&= \ve_1 \ve_2 \cdots \ve_{\frac{p-1}{2}} \pmod p
\end{align}
donde $(\frac ap) = \ve_1\ve_2\dots\ve_{\frac{p-1}{2}}$,
pois ambos pertencem a $\{-1,1\}$.
Assim, $(\frac ap) = (-1)^m$ onde $m$ é o número de
elementos $j$ de $\{1,2,\ldots,\frac{p-1}{2}\}$ tais que $\ve_j=-1$.
Como primeira conseqüência deste fato temos o seguinte resultado.


{\nobf Proposição 9.4: }
{\sl Se $p$ é um primo ímpar então 
\[
(\frac{2}{p}) = (-1)^{\frac{p^2-1}{8}} =
\begin{cases}
1, & \text{se }p \equiv \pm 1 \pmod 8,\\
-1, & \text{se }p \equiv \pm 3 \pmod 8.
\end{cases}
\]
}


{\nobf Dem: }
Se $p\equiv 1 \pmod 4$, digamos $p=4k+1$, temos $\frac{p-1}{2} = 2k$.
Como $1 \le 2j \le \frac{p-1}{2}$ para $j \le k$ e
$\frac{p-1}{2} < 2j \le p-1$ para $k+1 \le j \le 2k$, temos
\[
(\frac ap) = (-1)^k = 
\begin{cases}
1, &\text{se }p \equiv 1 \pmod 8,\\
-1, &\text{se }p \equiv 5 \pmod 8.
\end{cases}
\]

Se $p\equiv 3 \pmod 4$, digamos $p = 4k+3$, temos $\frac{p-1}{2} = 2k+1$.
Para $1 \le j \le k$ temos $1 \le 2j \le \frac{p-1}{2}$ e
para $k+1 \le j \le 2k+1$ temos $\frac{p-1}{2} < 2j \le p-1$, donde
\[
(\frac ap) = (-1)^{k+1} = 
\begin{cases}
-1, &\text{se }p \equiv 3 \pmod 8,\\
1, &\text{se }p \equiv 7 \pmod 8.
\end{cases}
\]
\qed

{\nobf Teorema 9.5: }{\rm (Lei de reciprocidade quadrática)}
{\sl
Sejam $p$ e $q$ primos ímpares. Então $(\frac pq) =
(-1)^{(p-1)(q-1)/4} (\frac qp)$.
}


{\nobf Dem: }
Na notação acima, com $a=q$, para cada $j \in P$, onde
\[ P = \{ 1, 2, \ldots, (p-1)/2 \}, \]
temos que $\varepsilon_j = -1$ se e só se existe $y \in \ZZ$ tal
que $-(p-1)/2 \le qj - py < 0$.
Tal $y$ deve pertencer a $Q$, onde
\[ Q = \{ 1, 2, \ldots, (q-1)/2 \}. \]
Assim, temos que $(\frac qp) = (-1)^m$ onde $m = |X|$ e
\[
X = \left\{(x,y) \in P \times Q \mid -(p-1)/2 \le qx - py < 0 \right\};
\]
note que $qx - py$ nunca assume o valor 0.
Analogamente, $(\frac pq) = (-1)^n$, onde $n = |Y|$ e
\[
Y = \left\{(x,y) \in P \times Q \mid 0 < qx - py \le (q-1)/2 \right\}.
\]
Daí segue que $(\frac pq)(\frac qp) = (-1)^k$ onde $k = m+n = |Z|$ onde
\[
Z =
\left\{(x,y) \in P \times Q \mid -(p-1)/2 \le qx - py \le (q-1)/2 \right\} 
\]
pois $qx - py$ nunca assume o valor 0.
Temos $k = |C| - |A| - |B|$ onde $C = P \times Q$,
\begin{align}
A &= \{(x,y) \in C \mid qx-py < -(p-1)/2 \}, \notag\\
B &= \{(x,y) \in C \mid qx-py > (q-1)/2 \}. \notag
\end{align}
Como $|C| = (p-1)(q-1)/4$, basta mostrar que $|A| = |B|$.
Mas $f: C \to C$ definida por $f(x,y) = (((p+1)/2) - x, ((q+1)/2) - y)$
define uma bijeção entre $A$ e $B$.
\qed

\section{Extensões quadráticas de corpos finitos}

Sejam $p$ primo e $d$ um inteiro que não seja quadrado perfeito.
O anel $(\ZZ/(p))[\sqrt d]$ é o conjunto
\[
\{a + b\sqrt d,\,\, a,b \in \ZZ/(p)\}
\]
onde
\begin{align}
(a+b\sqrt d) + (\tilde a+\tilde b\sqrt d) &=
(a+\tilde a) + (b+\tilde b)\sqrt d \notag\\
(a+b\sqrt d)(\tilde a+\tilde b\sqrt d) &=
(a\tilde a + db\tilde b) + (a\tilde b + \tilde a b)\sqrt d. \notag
\end{align}
Por definição,
\[
a+b\sqrt d = \tilde a + \tilde b \sqrt d \Leftrightarrow
a=\tilde a, b = \tilde b.
\]
Como grupo aditivo, $(\ZZ/(p))[\sqrt d] = \ZZ/(p) \times \ZZ/(p)$.
Vamos investigar a estrutura multiplicativa de $(\ZZ/(p))[\sqrt d]$.
Observemos inicialmente que, se $d$ é um quadrado módulo $p$
então $(\ZZ/(p))[\sqrt d]$ não pode ser um corpo, pois se $a^2 = d$
em $\ZZ/(p)$ então $(a + \sqrt{d})(a - \sqrt{d}) = 0$ em $(\ZZ/(p))[\sqrt d]$.
A próxima proposição é uma recíproca deste fato:

{\nobf Proposição 10.1: }
{\sl Se $(\frac dp) = -1$ então $(\ZZ/(p))[\sqrt d]$ é um corpo.}


{\nobf Dem: }
De fato, se $(a,b) \ne (0,0)$,
$(a+b\sqrt d)^{-1} = (a-b\sqrt d)/(a^2-db^2)$.
Temos que $a^2-db^2 \in (\ZZ/(p))^*$,
pois $d$ não é quadrado mod $p$,
logo, se $b\ne0$,\,\, $a^2-db^2=0$,
que equivale a $d=(a/b)^2$ seria uma contradição e,
se $b=0$,\,\,\, $a^2-db^2 = a^2 \ne 0$
pois $(a,b) \ne (0,0) \Rightarrow a\ne 0 \Rightarrow a^2 \ne 0$.
\qed

\vskip .1in

\noindent
{\bf Problemas:}

\begin{itemize}

\item[1)] Sejam $a,n>1$ inteiros. Prove que 

\begin{itemize}

\item[i)] Se $a^n-1$ é primo então $a=2$ e $n$ é primo.
\item[ii)] Se $a^n+1$ é primo então $n=2^k$ para algum inteiro $k$.
\end{itemize}

\item[2)] Prove que existem infinitos números primos congruentes a 3 módulo 4.

\item[3)] Determine todos os $n$ naturais tais que $(2^n-1)/n$ é inteiro.

\item[4)] Determine todos os $n$ naturais que $(2^n+1)/n^2$ é inteiro.

\item[5)] Prove que se $a$ e $b$ são naturais e $(a^2+b^2)/(ab+1)$ é inteiro então $(a^2+b^2)/(ab+1)$ é quadrado perfeito.

\item[6)] Sejam $a,n\in \mathbb N^*$. Considere a seqüência $(x_n)$ definida por $x_1=a$, $x_{k+1}=a^{x_k}$, $\forall\, k\in\mathbb N$. Mostre que existe $N\in \mathbb N$ tal que $x_{k+1}\equiv x_k$ (módulo $n$), para todo $k\ge N$.

\end{itemize}

\noindent
{\bf Obs.:}
Os Problemas 4 e 5 foram propostos na 31${}^{\underbar{\text{a}}}$ e na 29${}^{\underbar{\text{a}}}$ Olimpíada Internacional de Matemática (1990 e 1988) respectivamente.

\newpage

\setcounter{section}{0}%para numerar capitulos



\centerline{\Large \bf CAPÍTULO 2}

\vskip .5in

\centerline{\Large\bf Números Primos}

\vskip .3in

\section{Sobre a distribuição dos números primos}

Já vimos que existem infinitos primos;
o teorema dos números primos dá uma estimativa de quantos primos
existem até um inteiro $x$, ou seja, descreve a distribuição dos primos.
Defina $\pi(x)$ como sendo o número de primos $p$ com $2 \le p \le x$.

{\nobf Teorema 1.1: }{\rm (Teorema dos números primos)}
{\sl
\[
\lim_{x\to\infty} \frac{\pi(x)}{x/\log x} = 1.
\]
}

Observe que aqui e em todo o livro $\log$ denota o logaritmo natural.
Este resultado foi conjecturado por vários matemáticos,
inclusive por Legendre e Gauss, mas a demonstração completa só foi
encontrada em 1896, por de la Vallée Poussin e Hadamard (independentemante).
Não demonstraremos este teorema:
as demonstrações elementares conhecidas são todas bastante difíceis
(lembramos que uma demonstração é dita {\sl elementar}
quando não usa ferramentas avançadas: 
muitas demonstrações elementares são longas e sofisticadas).
Daremos uma demonstração da seguinte proposição (devida a Tchebycheff)
que é claramente uma versão fraca do teorema dos números primos.

{\nobf Proposição 1.2: }
{\sl
Existem constantes positivas $c < C$ tais que
\[
c \frac{x}{\log x} < \pi(x) < C \frac{x}{\log x}
\]
para todo $x \ge 2$.}

{\nobf Dem:}
Observemos inicialmente que $\binom{2n}{n} = \frac{(2n)!}{n!n!}$ é
múltiplo de todos os primos $p$ que satisfazem $n < p \le 2n$.
Como 
\[
\binom{2n}{n} < \sum_{0 \le k \le 2n} \binom{2n}{k} = 2^{2n},
\]
segue que o produto dos primos
entre $n$ e $2n$ é menor do que $2^{2n}$.
Como há $\pi(2n) - \pi(n)$ primos como esses segue que
$n^{\pi(2n)-\pi(n)} < 2^{2n}$
(pois todos esses primos são maiores que $n$),
donde $(\pi(2n) - \pi(n))\log n < 2n \log 2$
e
\[
\pi(2n)-\pi(n) < \frac{2n \log 2}{\log n}.
\]
Isso implica facilmente, por indução, que
\[
\pi(2^{k+1}) \le \frac{5 \cdot 2^k}{k}
\]
(começando com $k=5$; até $k=5$ segue de $\pi(n) \le n/2$).
Daí segue que se $2^k < x \le 2^{k+1}$ então
\[
\pi(x) \le \frac{5\cdot2^k}{k} \le \frac{5x\log 2}{\log x}
\]
pois $f(x) = x\log 2/\log x$ é uma função crescente para $x \ge 3$.

Vamos agora provar a outra desigualdade.
O expoente do primo $p$ na fatoração de $n!$ é 
\begin{align}
w_p(n) &=
\left\lfloor{\frac{n}{p}}\right\rfloor +
\left\lfloor{\frac{n}{p^2}}\right\rfloor + \cdots \notag\\
&= \sum_{k=1}^\infty
\left\lfloor{\frac{n}{p^k}}\right\rfloor \notag
\end{align}
(esta é uma soma finita pois se $k > \log_pn = \log n/\log p$ então
$\lfloor\frac{n}{p^k}\rfloor = 0$).
De fato,
$\lfloor\frac{n+1}{p^j}\rfloor -
\lfloor\frac{n}{p^k}\rfloor$ é sempre 0 ou 1,
e é igual a 1 se e só se $p^j$ divide $n+1$.
Assim, $w_p(n+1) - w_p(n)$
é igual ao expoente de $p$ na fatoração de $n+1$,
o que fornece uma prova por indução do fato acima.

Assim, o expoente de $p$ em $\binom{2n}{n} = (2n)!/n!^2$ é
\[
\sum_{k=1}^\infty
\left({
\left\lfloor{\frac{2n}{p^k}}\right\rfloor -
2 \left\lfloor{\frac{n}{p^k}}\right\rfloor}\right).
\]
Temos agora que
$\lfloor\frac{2n}{p^k}\rfloor - 2 \lfloor\frac{n}{p^k}\rfloor$
é sempre 0 ou 1 (pois $0 \le x- \lfloor x \rfloor < 1$ para todo $x$),
donde o expoente de $p$ em $\binom{2p}{p}$ é no máximor
$\log_p n = \log n/\log p$ para todo primo $p$.
Por outro lado, se $n < p \le 2n$, o expoente de $p$ em $\binom{2p}{p}$ é 1.
Assim, se $\binom{2n}{n} = \prod_{p < 2n} p^{\al_p}$
é a fatoração de $\binom{2n}{n}$ então
\begin{align}
\log \binom{2n}{n} &= \sum_{p < 2n} \al_p\log p \notag\\
&= \sum_{p\le n} \al_p\log p +
\sum_{n< p \le 2n} \log p \notag\\
&\le \pi(n)\log n + (\pi(2n)-\pi(n))\log(2n) \notag\\
&\le \pi(2n)\log(2n) \notag
\end{align}
donde
\[
\pi(2n) \ge \log \binom{2n}{n}/\log(2n) \ge n\log 2/\log(2n)
\]
pois 
\[
\binom{2n}{n} =
\frac{2n}{n} \cdot \frac{2n-1}{n-1} \cdots \frac{n+1}{1} 
\ge 2^n, 
\]
donde
\[
\pi(x) \ge \frac{x\log 2}{\log x}
\]
para todo $x$ par, o que implica na mesma estimativa
para todo $x$ inteiro, pois $\pi(2k-1) = \pi(2k)$.
\qed

{\nobf Corolário 1.3: }
{\sl Seja $f: \NN \to [0,+\infty)$ uma função decrescente.
A série
\[ \sum_{p \text{ primo}} f(p) \]
converge se e somente se a série
\[ \sum_{n = 2}^\infty \frac{f(n)}{\log n} \]
converge.
Em particular,
\[ \sum_{p \text{ primo}} \frac{1}{p}  = + \infty.\]
}

Deixamos a demonstração deste corolário como exercício.

Uma aproximação mais precisa para $\pi(x)$ é dada por
\[
\Li(x) = \int_0^x \frac{dt}{\log t},
\]
onde tomamos o valor principal desta integral, ou seja,
\[
\Li(x) =
\lim_{\ve \to 0} \int_\ve^{1-\ve} \frac{dt}{\log t} +
\int_{1+\ve}^x \frac{dt}{\log t};
\]
claramente
\[
\lim_{x \to \infty}\frac{\Li(x)}{\log(x)/x} = 1.
\]
Sabe-se entretanto que
\[
|\pi(x) - \Li(x)| \le C x e^{-a(\log x)^{3/5} (\log \log x)^{-1/5}}
\]
para algum valor das constantes $a$ e $C$ (independente de $x$).
Em particular, para qualquer $k > 0$ existe $C > 0$ tal que,para todo x,
\[
|\pi(x)-\Li(x)| \le C \frac{x}{(\log x)^k},
\]
o que mostra que $\Li(x)$ (e mesmo $x/(\log x-1)$) é uma 
aproximação de $\pi(x)$ bem melhor do que $x/\log x$.

A hipótese de Riemann, já mencionada, equivale a dizer que
para todo $\ve > 0$ existe $C$ com
\[
|\pi(x) - \Li(x)| \le C  x^{1/2+\ve};
\]
ninguém sabe demonstrar que esta estimativa
seja correta sequer para algum valor de $\ve < 1/2$.
A hipótese de Riemann também implica que
existe $C$ com
\[
|\pi(x) - \Li(x)| \le C  x^{1/2} \log x,
\]
o que daria uma estimativa para o tamanho deste erro muito melhor
de que as que se sabe demonstrar.
Por outro lado, sabe-se demonstrar que não pode existir nenhuma
estimativa muito melhor do que esta para $|\pi(x) - \Li(x)|$:
existe uma constante $C > 0$ e inteiros $x_1$ e $x_2$ arbitrariamente
grandes com
\begin{align}
\pi(x_1) - \Li(x_1) &< -C \frac{\sqrt{x_1} \log\log\log x_1}{\log x_1}, \notag\\
\pi(x_2) - \Li(x_2) &>  C \frac{\sqrt{x_2} \log\log\log x_2}{\log x_2}. \notag
\end{align}

\section{Outros resultados e conjecturas sobre primos}

Nesta seção veremos o enunciado de alguns resultados clássicos
sobre números primos. Também veremos vários problemas em aberto famosos.

{\nobf Teorema 2.1: } {\rm (Dirichlet)}
{\sl Dados naturais $a, d$ com $\mdc(a,d) = 1$,
existem infinitos primos da forma $a + dn$ (com $n$ natural). }

A demonstração usual deste teorema usa variáveis complexas.
Muitos casos particulares admitem demonstrações elementares
mais ou menos simples. O leitor não deve ter dificuldade
em demonstrar, por exemplo, que existem infinitos primos
da forma $4n + 3$ ou $6n + 5$.

Existem vários refinamentos conhecidos do teorema de Dirichlet.
Definimos $\pi_{d,a}(x)$ como sendo o número de primos da forma
$a + dn$ no intervalo $[2,x]$. De la Vallée Poussin provou que
\[ lim_{x \to +\infty} \frac{\pi_{d,a}(x)}{\pi(x)} = \frac{1}{\varphi(d)}, \]
isto é, todas as possíveis classes módulo $d$ têm aproximadamente
a mesma proporção de primos.

Por outro lado, Tchebycheff observou que para valores pequenos de $x$
$\pi_{3,2}(x) - \pi_{3,1}(x)$ e $\pi_{4,3}(x) - \pi_{4,1}(x)$
são positivos. Um teorema de Littlewood, entretanto,
demonstra que estas funções mudam de sinal infinitas vezes.
Em 1957, Leech demonstrou que o menor valor de $x$ para o qual
$\pi_{4,3}(x) - \pi_{4,1}(x) = -1$ é 26861 e em 1978
Bays e Hudson demonstraram que o menor valor de $x$ para o qual
$\pi_{3,2}(x) - \pi_{3,1}(x) = -1$ é 608981813029.

Seja $p(d,a)$ o menor primo da forma $a + dn$, $n$ inteiro e
\[ p(d) = \max \{ p(d,a) \mid 0 < a < d, \mdc(a,d) = 1\}. \]
Linnik (1944) provou que existe $L > 1$ com $p(d) < d^L$
para todo $d$ suficientemente grande.
A melhor estimativa conhecida para $L$ é $L \le 5,5$,
devida a Heath-Brown (1992), que também conjecturou que
\[ p(d) \le C d (\log d)^2. \]

Por outro lado, não se sabe demonstrar que existam infinitos primos
da forma $n^2 + 1$; aliás, não existe nenhum polinômio $P$ em uma variável
e de grau maior que 1 para o qual se saiba demonstrar que existem
infinitos primos da forma $P(n)$, $n \in \ZZ$.
Por outro lado, existem muitos polinômios em mais de uma variável
que assumem infinitos valores primos:
por exemplo, prova-se facilmente que todo primo da forma $4n + 1$
pode ser escrito também na forma $a^2 + b^2$, $a, b \in \ZZ$.
Por outro lado, Friedlander e Iwaniec provaram recentemente
um resultado muito mais difícil: que existem infinitos primos
da forma $a^2 + b^4$.

Um dos problemas em aberto mais famosos da matemática
é a conjectura de Goldbach:
todo número par maior ou igual a 4 é a soma de dois primos.
Chen demonstrou que todo número par suficientemente grande
é a soma de um primo com um número com no máximo dois fatores primos.
Vinogradov demonstrou que todo ímpar suficientemente grande
(por exemplo, maior do que $3^{3^{15}}$) é uma soma de três primos.

Quando $p$ e $p+2$ são ambos primos, dizemos que eles são {\sl primos gêmeos}.
Conjectura-se, mas não se sabe demonstrar, que existem infinitos primos gêmeos.
Brun, por outro lado, provou que primos gêmeos são escassos no seguinte sentido:
se $\pi_2(x)$ é o número de pares de primos gêmeos até $x$ então
\[ \pi_2(x) < \frac{100 x}{(\log x)^2} \]
para $x$ sufientemente grande.
Em particular,
\[ \sum_{p \text{ primo gêmeo}} \frac{1}{p} < +\infty. \]
Acredita-se que $\pi_2(x)$ seja assintótico a $Cx/(\log x)^2$
para alguma constante positiva $C$.
Dei\-xa\-mos como exercício provar a seguinte caracterização de primos gêmeos
devida a Clement.
Seja $n \ge 2$; os inteiros $n$ e $n+2$ são ambos primos se e somente se
\[ 4((n-1)! + 1) + n \equiv 0 \pmod {n(n+2)}. \]

Seja $p_n$ o $n$-ésimo número primo.
O teorema dos números primos equivale a dizer que
\[ \lim_{n \to \infty} \frac{p_n}{n \log n} = 1. \]
Por outro lado, sabe-se muito pouco sobre o comportamento
da função $d_n = p_{n+1} - p_{n}$.
Por exemplo, a conjectura de que existem infinitos primos gêmeos
equivale a dizer que $\liminf d_n = 2$.
Não se sabe provar nem que
\[ L = \liminf \frac{d_n}{\log p_n} = 0; \]
Erdös provou que $L < 1$ e Maier que $L \le 0,248$.
Erdös também provou que o conjunto dos pontos de acumulação de
$d_n/\log p_n$ tem medida positiva.
Por outro lado, é um teorema clássico, conhecido como postulado de Bertrand,
que sempre existe pelo menos um primo entre $m$ e $2m$, ou seja, $d_n < p_n$.
Em 1931, Westzynthius provou que 
\[ \limsup \frac{d_n}{\log p_n} = \infty, \]
e em 1963 Rankin, completando um trabalho de Erdös,
mostrou que
\[ \limsup \frac{d_n (\log\log\log p_n)^2 }%
{\log p_n \log\log p_n \log\log\log\log p_n} \ge e^\gamma 
\approx 1,78107 \]
onde $\gamma$ é a constante de Euler-Mascheroni,
\[ \gamma =
\lim_{n \to \infty}
\left({1 + \frac{1}{2} + \cdots + \frac{1}{n} - \log n }\right)
\approx 0,5772156649; \]
este resultado foi melhorado posteriormente por Pomerance e Pintz,
que provou que o lado esquerdo é maior ou igual a
$2 e^\gamma$ ({\bf [Pintz]}).
Conjectura-se que 
\[ \limsup \frac{d_n}{(\log p_n)^2} = C \]
para alguma constante positiva $C$.
Outra conjectura famosa é que sempre há pelo menos um primo entre
$n^2$ e $(n+1)^2$.
Observamos que a primeira vez que $d_n > 1000$ ocorre para
$p_n = 1693182318746371$, quando $d_n = 1132$,
o que foi descoberto recentemente por T. Nicely e D. Nyman.

Sierpinski provou que existem infinitos números naturais $k$
tais que $k \cdot 2^n + 1$ é composto para todo natural $n$
e Riesel provou o mesmo resultado para $k \cdot 2^n - 1$.
Conjectura-se que os menores valores de $k$ com as propriedades acima
são respectivamente 78557 e 509203. Há um projeto cooperativo,
que consiste em procurar primos grandes,
para demonstrar estas conjecturas
(veja {\tt http://vamri.xray.ufl.edu/proths/}).

O leitor interessado em aprender mais sobre problemas em aberto
em teoria dos números pode consultar {\bf [Guy]}.

\section{Fórmulas para primos e testes de primalidade}

Mencionamos na introdução deste capítulo que
não se conhece nenhuma fórmula simples
para gerar primos arbitrariamente grandes.
Uma palavra imprecisa mas importante nesta frase é ``simples''.
Existem fórmulas que geram números primos,
mas que são tão complicadas que não ajudam muito nem a gerar
números primos explicitamente nem a responder perguntas teóricas
sobre a distribuição dos primos.
Um exemplo de fórmula para $p_n$, o $n$-ésimo primo, é
\[
p_n = \left\lfloor{
1 - \frac{1}{\log 2} \log\left(
{-\frac{1}{2} + \sum_{d| P_{n-1}}\frac{\mu(d)}{2^d - 1}}
\right) } \right\rfloor,
\]
onde $P_{n-1} = p_1 p_2 \cdots p_{n-1}$;
deixamos a demonstração a cargo do leitor.
Outra fórmula é
\[
p_n = \lfloor 10^{2^n} c \rfloor - 10^{2^{n-1}} \lfloor 10^{2^{n-1}} c \rfloor,
\]
onde
\[ c = \sum_{n = 1}^\infty \frac{p_n}{10^{2^n}} =
0.0203000500000007\ldots . \]
A inutilidade desta última fórmula vem do fato que para calcular $c$
devemos encontrar todos os primos;
a fórmula se tornaria mais interessante se existisse outra interpretação
para o número real $c$, o que parece muito improvável.
Por outro lado, existe um número real $a > 1$
tal que $\lfloor a^{3^n} \rfloor$ é sempre primo.

Um tipo de fórmula para primos, de certa forma mais intrigante,
são polinômios de coeficientes inteiros
em $S$ variáveis com a seguinte propriedade quase mágica:
a interseção da imagem de $\NN^S$ com $\NN$
é exatamente o conjunto dos números primos.
Note que se tomarmos um ponto de $\NN^S$ ``ao acaso'',
o valor do polinômio neste ponto quase certamente será negativo;
assim, é difícil usar o polinômio para gerar primos.
A título de curiosidade, vejamos um exemplo de polinômio
com estas propriedades; aqui $N = 26$, o valor do polinômio é $P$,
as variáveis chamam-se $a, b, \ldots, z$ e $A, B, \ldots, N$
são expressões auxiliares:
\begin{align}
% P &= (k+2)(1 - A^2 - B^2 - C^2 - D^2 - E^2 - F^2 - G^2 -
% H^2 - I^2 - J^2 - K^2 - L^2 - M^2 - N^2),\notag\\
P &= (k+2)(1 - A^2 - B^2 - C^2 - \cdots - N^2), \notag\\
A &= wz + h + j - q,\notag\\
B &= (gk + 2g + k + 1)(h+j) + h - z,\notag\\
C &= 16(k+1)^3 (k+2) (n+1)^2 + 1 - f^2,\notag\\
D &= 2n + p + q + z - e,\notag\\
E &= e^3 (e+2) (a+1)^2 + 1 - o^2,\notag\\
F &= (a^2 - 1)y^2 + 1 - x^2,\notag\\
G &= 16 r^2 y^4 (a^2 - 1) + 1 - u^2,\notag\\
H &= ((a + u^2(u^2 - a))^2 - 1)(n+4dy)^2 + 1 - (x+cu)^2,\notag\\
I &= (a^2 - 1)l^2 + 1 - m^2,\notag\\
J &= ai + k + 1 - l - i,\notag\\
K &= n + l + v - y,\notag\\
L &= p + l(a-n-1) + b(2an + 2a - n^2 - 2n - 2) - m,\notag\\
M &= q + y(a - p - 1) + s(2ap + 2a - p^2 - 2p - 2) - x,\notag\\
N &= z + pl(a-p) + t(2ap - p^2 - 1) - pm.\notag
\end{align}
Algumas observações simples: a única forma de $P$ ser positivo
é se $A = B = \cdots = N = 0$; neste caso seu valor será $k+2$.
Vemos assim que para produzir um número primo $P$ com este polinômio
devemos antes de mais nada tomar $k = P-2$.
As expressões auxiliares viram equações:
como  $A = 0$ temos $q = wz + h + j$.
Assim, dado $k$ para o qual $k+2$ é primo,
precisamos procurar valores para as outras letras
que satisfaçam estas equações.
Estes valores de certa forma {\sl encodificam}
uma demonstração de que $P = k+2$ é primo.


\section{Testes de primalidade baseados em fatorações de $n-1$}

{\nobf Proposição 4.1: }
{\sl Seja $n > 1$. Se para cada fator primo $q$ de $n-1$ existe um inteiro $a_q$
tal que $a_q^{n-1} \equiv 1 \pmod n$ e $a_q^{(n-1)/q} \not\equiv 1 \pmod n$
então $n$ é primo. }

{\nobf Dem: }
Seja $q^{k_q}$ a maior potência de $q$ que divide $n-1$.
A ordem de $a_q$ em $(\ZZ/(n))^\ast$ é um múltiplo de $q^{k_q}$,
donde $\varphi(n)$ é um múltiplo de $q^{k_q}$.
Como isto vale para todo fator primo $q$ de $n-1$,
$\varphi(n)$ é um múltiplo de $n-1$ e $n$ é primo. \qed

{\nobf Proposição 4.2:} {\rm (Pocklington) }
{\sl Se $n - 1 = q^k R$ onde $q$ é primo
e existe um inteiro $a$ tal que $a^{n-1} \equiv 1 \pmod n$
e $\mdc(a^{(n-1)/q} - 1, n) = 1$ então qualquer fator primo de $n$
é congruo a 1 módulo $q^k$.}

{\nobf Dem: }
Se $p$ é um fator primo de $n$ então $a^{n-1} \equiv 1 \pmod p$
e $p$ não divide $a^{(n-1)/q} - 1$, donde $\ordem_p a$,
a ordem de $a$ módulo $p$, divide $n-1$ mas não divide $(n-1)/q$.
Assim, $q^k | \ordem_p a | p - 1$, donde $p \equiv 1 \pmod q^k$. \qed


{\nobf Corolário 4.3: }
{\sl Se $n - 1 = FR$, com $F > R$ e
para todo fator primo $q$ de $F$ existe $a > 1$
tal que $a^{n-1} \equiv 1 \pmod n$ e $\mdc(a^{(n-1)/q} - 1, n) = 1$
então $n$ é primo.}

{\nobf Dem: }
Seja $q$ um fator primo de $F$ e $q^k$ a maior potência de $q$ que divide $F$;
pela proposição anterior, todo fator primo de $n$
deve ser côngruo a 1 módulo $q^k$.
Como isto vale para qualquer fator primo de $F$,
segue que qualquer fator primo de $n$ deve ser côngruo a 1 módulo $F$.
Como $F > \sqrt{n}$, isto implica que $n$ é primo. \qed

De fato, basta conhecer um conjunto de fatores primos cujo produto seja
maior do que $(n-1)^{1/3}$ para, usando o resultado de Pocklington,
tentar demonstrar a primalidade de $n$ (o que deixamos como exercício).
Os seguintes critérios clássicos
são conseqüências diretas das proposições acima.

Fermat conjecturou que todo número da forma $F_n = 2^{2^n} + 1$ fosse primo
e verificou a conjectura para $n \le 4$.
Observe que $2^n + 1$ (e em geral $a^n + 1$ com $a \ge 2$) {\sl não} é primo 
se $n$ não é uma potência de 2:
se $p$ é um fator primo ímpar de $n$,
podemos escrever
$a^n + 1 = b^p + 1 = (b+1)(b^{p-1} - b^{p-2} + \cdots + b^2 - b + 1)$
onde $b = a^{n/p}$.
Euler mostraria mais tarde que $F_5$ não é primo
(temos $F_5 = 4294967297 = 641 \cdot 6700417$)
e já se demonstrou que $F_n$ é composto para
vários outros valores de $n$;
nenhum outro primo da forma $F_n = 2^{2^n} + 1$ é conhecido,
mas se conhecem muitos primos (alguns bastante grandes) da forma 
$a^{2^n} + 1$, que são conhecidos como primos de Fermat generalizados.
O teste a seguir mostra como testar eficientemente a primalidade de $F_n$.

{\nobf Corolário 4.4:} { \rm (Teste de Pépin) }
{\sl Seja $F_n = 2^{2^n} + 1$;
$F_n$ é primo se e somente se
$3^{(F_n - 1)/2} \equiv -1 \pmod {F_n}$.}

{\nobf Dem: }
Se $3^{(F_n - 1)/2} \equiv -1 \pmod {F_n}$ então a primalidade de $F_n$
segue da Proposição 4.1. Por outro lado, se $F_n$ é primo então
$3^{(F_n - 1)/2} \equiv (\frac{3}{F_n}) =
(\frac{F_n}{3}) = (\frac{2}{3}) = -1 \pmod {F_n}$. \qed

{\nobf Corolário 4.5: } {\rm (Teorema de Proth; 1878) }
{\sl Seja $n = h\cdot 2^k + 1$ com $2^k > h$.
Então $n$ é primo se e somente se existe um inteiro $a$
com $a^{(n-1)/2} \equiv -1 \pmod n$.}

{\nobf Dem: }
Se $n$ é primo, podemos tomar $a$ qualquer com $(\frac{a}{n}) = -1$;
ou seja, metade dos inteiros entre 1 e $n-1$ serve como $a$.
A recíproca segue do Corolário 4.3  com $F = 2^k$. \qed

{\nobf Corolário 4.6: }
{\sl Se $n = h\cdot q^k + 1$ com $q$ primo e $q^k > h$.
Então $n$ é primo se e somente se existe um inteiro $a$
com $a^{n-1} \equiv 1 \pmod n$ e $\mdc(a^{(n-1)/q} - 1, n) = 1$.}

{\nobf Dem: }
Se $n$ é primo, podemos tomar $a$ qualquer que não seja da forma
$x^q$ módulo $n$;
ou seja, uma proporção de $(q-1)/q$ dentre inteiros entre 1 e $n-1$
serve como $a$.
A recíproca segue do Corolário 4.3 com $F = q^k$. \qed

Uma expressiva maioria entre os 100 maiores primos
conhecidos estão nas condições do teorema de Proth (ver tabelas).
Isto se deve ao fato de primos desta forma serem freqüentes
(mais freqüentes do que, por exemplo, primos de Mersenne)
e que sua primalidade é facilmente demonstrada usando este resultado.

\vskip .2in

\noindent
{\Large\bf  5\quad Primos de Mersenne}

\vskip .1in

\noindent
Um número de Mersenne é um número da forma $M_p = 2^p - 1$. Os 5 maiores números primos conhecidos atualmente são primos de 
Mersenne. O maior deles é $2^{13466917}-1$, descoberto em 14/11/2001. Este é um dos dois primos conhecidos com mais de um milhão 
de dígitos. O outro é $2^{6972593}-1$ (também primo de Mersenne). Ambos foram descobertos pelo  GIMPS (veja {\tt www.mersenne.org}).
 O critério de
Lucas-Lehmer, que apresentaremos nesta seção, é um dos fatores para que isso ocorra pois fornece um teste de primalidade bastante 
rápido para números de Mersenne.
Vejamos primeiramente que $2^p - 1$ só tem chance de ser primo
quando $p$ é primo.

{\nobf Proposição 5.1: }
{\sl Se $2^n - 1$ é primo então $n$ é primo.}

{\nobf Dem: } Se $n = ab$ com $a, b \ge 2$ então
$1 < 2^a - 1 < 2^n - 1$ e
$2^n - 1 = 2^{ab} - 1 = (2^a)^b - 1 \equiv 1^b - 1 = 0 \pmod {2^a - 1}$
e $2^n - 1$ é composto. \qed

Por outro lado, não se sabe demonstrar nem que existam infinitos
{\sl primos de Mersenne} nem que existem infinitos primos $p$
para os quais $M_p$ é composto.
Conjectura-se, entretanto, que existam infinitos primos $p$
para os quais $M_p$ é primo e que, se $p_n$ é o $n$-ésimo primo
deste tipo, temos
\[ 0 < A < \frac{\log p_n}{n} < B < +\infty \]
para constantes $A$ e $B$.
Existem algumas conjecturas mais precisas quanto ao valor de
\[ \lim_{n \to \infty} \sqrt[n]{p_n}; \]
Eberhart conjectura que este limite exista e seja igual a $3/2$;
Wagstaff por outro lado conjectura que o limite seja 
\[ 2^{e^{-\gamma}} \approx 1,4757613971 \]
onde $\gamma$ é a já mencionada constante de Euler-Mascheroni.

Primos de Mersenne são interessantes também
por causa de {\sl números perfeitos}.
Dado $n \in \NN^\ast$, definimos
$$\sigma(n) = \sum_{d|n} d,$$
a soma dos divisores (positivos) de $n$.
Pelo teorema fundamental da aritmética demonstramos facilmente
que se
$$n = p_1^{e_1} p_2^{e_2} \cdots p_m^{e_m},$$
com $p_1 < p_2 < \cdots < p_m$ então
\begin{align}
\sigma(n) &=
(1 + p_1 + \cdots + p_1^{e_1})\cdots (1 + p_m + \cdots + p_m^{e_m}) \notag\\
&= \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdots \frac{p_m^{e_m + 1} - 1}{p_m - 1}.
\notag
\end{align}
Em particular, se $(a,b) = 1$ então $\sigma(ab) = \sigma(a) \sigma(b)$.
Um inteiro positivo $n$ é dito {\sl perfeito} se $\sigma(n) = 2n$;
os primeiros números perfeitos são 6, 28 e 496.
Nosso próximo resultado caracteriza os números perfeitos pares.

{\nobf Proposição 5.2: }
{\sl Se $M_p$ é um primo de Mersenne então $2^{p-1} M_p$ é perfeito.
Além disso, todo número perfeito par é da $2^{p-1} M_p$ para algum
primo $p$, sendo $M_p$ um primo de Mersenne.}

{\nobf Dem: }
Se $M_p$ é primo então
$$\sigma(2^{p-1} M_p) = (2^p - 1)(M_p + 1) = 2 \cdot 2^{p-1} M_p.$$
Por outro lado seja $n = 2^k b$, com $k > 0$ e $b$ ímpar,
um número perfeito par.
Temos $\sigma(n) = 2n = \sigma(2^k) \sigma(b)$ donde
$2^{k+1} b = (2^{k+1} - 1) \sigma(b) \ge (2^{k+1} - 1)(b+1)$,
valendo a igualdade apenas se $b$ for primo.
Desta desigualdade temos $b \le 2^{k+1} - 1$.
Por outro lado, como $(2^{k+1} - 1)| 2^{k+1} b$ e
$(2^{k+1} - 1, 2^{k+1}) = 1$, temos $(2^{k+1} - 1)|b$
e $2^{k+1} - 1 \le b$.
Assim $b = 2^{k+1} - 1$ e
$2^{k+1} b = (2^{k+1} - 1)(b+1)$, donde $b$ é primo.
Pela proposição 3.9, $p = k+1$ é primo, $b = M_p$ e $n = 2^{p-1} M_p$.
\qed

Por outro lado, um dos problemas em aberto mais antigos da matemática
é o da existência de números perfeitos ímpares.
Sabe-se apenas que um número perfeito ímpar, se existir,
deve ser muito grande (mais de 300 algarismos)
e satisfazer simultaneamente várias condições complicadas.

{\nobf Conjectura 5.3: }
{\sl Não existe nenhum número perfeito ímpar.}


Nosso próximo resultado é o critério de Lucas-Lehmer,
a base dos algoritmos que testam para grandes valores de $p$
se $2^p - 1$ é ou não primo:

{\nobf Teorema 5.4:}
{\sl Seja $S$ a seqüência definida por $S_0 = 4$,
$S_{k+1} = S_k^2 - 2$ para todo natural $k$.
Seja $n > 2$; $M_n = 2^n - 1$ é primo se e somente se
$S_{n-2}$ é múltiplo de $M_n$.}

{\nobf Dem: }
Observemos inicialmente que
$$S_n = (2+\sqrt{3})^{2^n} + (2-\sqrt{3})^{2^n}$$
para todo natural $n$.
A demonstração por indução é simples:
claramente $S_0 = 4 = (2+\sqrt{3})^{2^0} + (2-\sqrt{3})^{2^0}$ e
\begin{align}
S_{k+1} &= S_k^2 - 2 = ((2+\sqrt{3})^{2^k} + (2-\sqrt{3})^{2^k})^2 - 2 \notag\\
&= ((2+\sqrt{3})^{2^k})^2 + 2 \cdot (2+\sqrt{3})^{2^k} \cdot (2-\sqrt{3})^{2^k} + ((2-\sqrt{3})^{2^k})^2 - 2 \notag\\
&= (2+\sqrt{3})^{2^{k+1}} + (2-\sqrt{3})^{2^{k+1}}.\notag
\end{align}

Suponha por absurdo que
$M_n | (2+\sqrt{3})^{2^{n-2}} + (2-\sqrt{3})^{2^{n-2}}$
e que $M_n$ seja composto, com um fator primo $q$ com $q^2 < M_n$.
Teremos $(2+\sqrt{3})^{2^{n-2}} + (2-\sqrt{3})^{2^{n-2}} \equiv 0 \pmod q$
donde, no grupo multiplicativo $G = (\ZZ/(q) [\sqrt{3}])^\ast$, temos
$(2+\sqrt{3})^{2^{n-2}} = - (2-\sqrt{3})^{2^{n-2}}.$
Como $2 - \sqrt{3} = (2 + \sqrt{3})^{-1}$ esta equação pode ser reescrita
como $(2+\sqrt{3})^{2^{n-1}} = -1$ (ainda em $G$),
o que significa que a ordem de $2+\sqrt{3}$ em $G$ é exatamente $2^n$.
Isto é um absurdo, pois o número de elementos de $G$ é apenas $q^2 - 1 < 2^n$.
Fica portanto demonstrado que se $S_{n-2}$ é múltiplo de $M_n$
então $M_n$ é primo.

Suponha agora $M_n$ primo, $n > 2$. Lembramos que $n$ é um primo ímpar.
Por reciprocidade quadrática temos
$(\frac{3}{M_n}) = - (\frac{M_n}{3}) = -1$,
pois $3 \equiv M_n \equiv -1 \pmod 4$ e $M_n \equiv 1 \pmod 3$.
Assim, 3 não é um quadrado em $\ZZ/(M_p)$ e
$K = \ZZ/(M_p)[\sqrt{3}]$ é um corpo de ordem $M_n^2$. Além disso, $3^{\frac{m_n-1}{2}}=(\frac{3}{M_n})=-1 $ em $K$.
Queremos provar que 
$(2+\sqrt{3})^{2^{n-2}} + (2-\sqrt{3})^{2^{n-2}} \equiv 0 \pmod M_p$,
ou seja, que é igual a 0 em $K$.
Isto equivale a demonstrarmos que temos
$(2+\sqrt{3})^{2^{n-2}} = - (2-\sqrt{3})^{2^{n-2}}$ em $K$,
o que pode ser reescrito como $(2+\sqrt{3})^{2^{n-1}} = -1$;
devemos portanto provar que a ordem de $2+\sqrt{3}$ é exatamente $2^n$.
Note que $2^n = M_n + 1$ donde
$(2 + \sqrt{3})^{2^n} = (2 + \sqrt{3})^{M_n} (2 + \sqrt{3}) =
(2 - \sqrt{3}) (2 + \sqrt{3}) = 1$ (note que, em $K$, $(2+\sqrt 3)^{M_n} = (2^{M_n}+\sqrt 3)^{M_n}= 2 + 3^{\frac{M_n-1}{2}} \cdot \sqrt 3= 2-\sqrt 3$); 
assim é claro que a ordem de $2 + \sqrt{3}$ é um divisor de $2^n$.

Como $K^\ast$ tem $M_n^2 - 1 = 2^{n+1}(2^{n-1} - 1)$ elementos,
devemos provar que $2 + \sqrt{3}$ não é uma quarta potência em $K$.
Note que $(2 + \sqrt{3})^{2^n} = 1$ demonstra que $2 + \sqrt{3}$
é um quadrado, o que aliás pode ser visto mais diretamente:
$2 + \sqrt{3} = (1 + \sqrt{3})^2/2$
e $2 = 2^{n+1} = 2^{(n+1)^2}$ é uma quarta potência em $K$.
Resta-nos assim demonstrar que $\pm(1 + \sqrt{3})$ não são quadrados em $K$.
Suponha por absurdo que
$\epsilon (1 + \sqrt{3}) = (a + b \sqrt{3})^2$, com $\epsilon = \pm 1$;
temos $\epsilon (1 - \sqrt{3}) = (a - b \sqrt{3})^2$
e, multiplicando, $-2 = (a^2 - 3 b^2)^2$,
o que significa que $-2$ é um quadrado módulo $M_n$
(pois $a$ e $b$ são inteiros).
Isto, entretanto, é claramente falso:
$(\frac{-2}{M_n}) = (\frac{-1}{M_n}) (\frac{2}{M_n}) = -1 \cdot 1 = -1$,
pois $M_n \equiv 3 \pmod 4$ e já vimos que 2 é um quadrado módulo $M_p$.
Isto conclui a demonstração.
\qed

Mesmo quando $M_p$ não é primo, podemos garantir que seus fatores primos
serão de certas formas especiais. Isto é muito útil quando procuramos
primos de Mersenne pois podemos eliminar alguns expoentes
encontrando fatores primos de $M_p$.
Isto também pode ser útil para conjecturarmos quanto à ``probabilidade''
de $M_p$ ser primo, ou, mais precisamente, quanto à distribuição
dos primos de Mersenne.

{\nobf Proposição 5.5: }
{\sl Sejam $p > 2$ e $q$ primos com $q$ um divisor de $M_p$.
Então $q \equiv 1 \pmod p$ e $q \equiv \pm 1 \pmod 8$.}

{\nobf Dem: }
Se $q$ divide $M_p$ então $2^p \equiv 1 \pmod q$,
o que significa que a ordem de 2 módulo $q$ é $p$ (pois $p$ é primo).
Isto significa que $p$ é um divisor de $q - 1$, ou seja, que
$q \equiv 1 \pmod p$.
Por outro lado, $2 \equiv 2^{p+1} = (2^{(p+1)/2})^2 \pmod q$,
donde $(\frac{2}{q}) = 1$, o que significa que $q \equiv \pm 1 \pmod 8$.
\qed

Os vários valores de $p$ para os quais a primalidade de $M_p$ foi testada
sugerem que para a ampla maioria dos valores de $p$,
$M_p$ {\it não} é primo.
Isto é apenas uma conjectura:
não se sabe demonstrar sequer que existem infinitos primos $p$
para os quais $M_p$ seja composto.
Vamos agora ver uma proposição que serve para garantir que
para certos valores especiais de $p$, alguns muito grandes,
$M_p$ {\it não} é primo.

{\nobf Proposição 5.6: }
{\sl Seja $p$ primo, $p \equiv 3 \pmod 4$.
Então $2p + 1$ é primo se e somente se $2p + 1$ divide $M_p$.}

{\nobf Dem: }
Se $q$ é primo então
$M_p = 2^p - 1 = 2^{(q-1)/2} - 1 \equiv (\frac{2}{q}) - 1 \pmod q$.
Mas $p \equiv 3 \pmod 4$ significa que $q \equiv 7 \pmod 8$,
donde $(\frac{2}{q}) = 1$.
Assim, $M_p \equiv 0 \pmod q$, o que demonstra uma das implicações
da proposição.

Por outro lado, se $2p + 1$ não é primo tem fatores primos $r$ com
$r \not\equiv 1 \pmod p$ (pois $r < p$). Se $2p + 1$ dividisse $M_p$,
$r$ seria um fator primo de $M_p$, contrariando a proposição anterior. \qed

Os primos $p$ para os quais $2p+1$ é primo são chamados de
{\sl primos de Sophie Germain}.
Alguns primos de Sophie Germain bastante grandes são conhecidos,
como $p_0 = 18458709 \cdot 2^{32611} - 1$;
assim, pela proposição anterior, $M_{p_0}$ é composto.
Sabe-se também que se $\pi_{\text{SG}}(x)$ denota o número de primos
de Sophie Germain menores do que $x$ então existe $C$ tal que para todo $x$
\[ \pi_{\text{SG}}(x) < C \frac{x}{(\log x)^2}. \]
Acredita-se que $\pi_{\text{SG}}(x)$ seja assintótico a $cx/(\log x)^2$
para algum $c > 0$ mas não se sabe de\-mons\-trar sequer que 
existem infinitos primos de Sophie Germain.

\newpage

\vglue 3in

\centerline{\LARGE\bf PARTE II}

\vskip .5in

\centerline{\LARGE\bf APROXIMAÇÕES DIOFANTINAS}

\newpage

\quad

\newpage

\setcounter{section}{0}%para numerar capitulos

\centerline{\Large\bf CAPÍTULO 3}

\vskip .5in

\centerline{\Large\bf  Frações Contínuas, Representações de Números}

\centerline{\Large\bf e Aproximações}

\vskip .5in

\noindent{\Large\bf Introdu\c c\~ao}

\vglue .3in

A teoria de fra\c c\~oes cont\'\i nuas \'e um dos mais belos temas da ma\-te\-m\'a\-ti\-ca elementar, sendo ainda hoje assunto de pesquisa recente (incluindo a do autor destas linhas). O objetivo deste artigo \'e servir como refer\^encia did\'atica em portugu\^es a n\'\i vel secund\'ario sobre o assunto.


Nas inclus\~oes $\na \subset \Z \subset \bq \subset \re$ a passagem de $\bq$
para $\re$ \'e sem d\'uvida a mais complicada conceitualmente, e a 
re\-presenta\c c\~ao de um n\'umero real est\'a diretamente ligada \`a
pr\'opria no\c c\~ao de n\'umero real.

De fato, o conceito de n\'umero natural \'e quase um conceito primitivo no
ensino secund\'ario. J\'a um n\'umero inteiro \'e um n\'umero natural com um
sinal que pode ser \,\,$+$\,\,\, ou \,\,$-$\,, e um n\'umero racional \'e a
raz\~ao entre um n\'umero inteiro e um natural n\~ao nulo. Por outro lado,
dizer o que \'e um n\'umero real \'e tarefa bem mais complicada, mas h\'a
coisas que podemos dizer sobre eles. Uma propriedade essencial de $\re$ \'e que
todo n\'umero real pode ser bem aproximado por n\'umeros racionais.
Efetivamente, dado $x \in \re$, existe $k \in \Z$\,\,\,$(k=[x])$ tal que $0 \le
x-k <1$. Podemos escrever a representa\c c\~ao decimal de $x-k = 0$,
$a_1a_2\dots a_n\dots$, \,\,\, $a_i \in \{0,1,\dots,9\}$, o que significa que se  $r_n = a_n + 10\cdot a_{n-1} + 100\cdot a_{n-2} +\dots + 10^{n-1}\cdot a_1$, ent\~ao 
$\dfrac{r_n}{10^n} \le x-k < \dfrac{r_n+1}{10^n}$\,, e portanto $k +
\dfrac{r_n}{10^n}$ \'e uma boa aproxima\c c\~ao racional de $x$, no sentido que o erro $\lv x - \big(k+\dfrac{r_n}{10^n}\big)\rv$ \'e menor que
$\dfrac{1}{10^n}$\,, que \'e um n\'umero bem pequeno se $n$ for grande. A representa\c c\~ao
decimal de um n\'umero real fornece pois uma seq\"u\^encia de aproxima\c c\~oes
por racionais cujos denominadores s\~ao pot\^encias de 10.

Dado qualquer $x \in \re$ e $q$ natural n\~ao nulo existe $p \in \Z$ tal que
$\dfrac pq \le x < \dfrac{p+1}{q}$\,, e portanto $\lv x-\dfrac pq\rv < \dfrac 1q$ e
$\lv x-\dfrac{p+1}{q}\rv \le \dfrac 1q$\,. Em particular h\'a aproxima\c c\~oes
de $x$ por racionais com denominador $q$ com erro menor que $\dfrac 1q$\,. A
representa\c c\~ao decimal de $x$ equivale a dar essas aproxima\c c\~oes para
os denominadores $q$ que s\~ao pot\^encias de 10, e tem m\'eritos como sua
praticidade para efetuar c\'alculos que a fazem a mais popular das representa\c
c\~oes dos n\'umeros reais. Por outro lado, envolve a escolha arbitr\'aria da
base 10, e oculta freq\"uentemente aproxima\c c\~oes racionais de $x$ muito
mais eficientes do que as que exibe. Por exemplo, 
$$
\lv \pi - \frac{22}{7}\rv <
\frac{1}{700} < \lv \pi - \frac{314}{100}\rv \text{ e } \lv \pi - \frac{355}{113}\rv <
\frac{1}{3000000} < \lv \pi - \frac{3141592}{1000000}\rv
$$
mostram que
$\dfrac{22}{7}$ e $\dfrac{355}{113}$ s\~ao melhores aproxima\c c\~oes de $\pi$ que apro\-xima\c c\~oes decimais com denominadores muito maiores, e de fato s\~ao
aproxima\c c\~oes muito mais espetaculares do que se podia esperar.

O objetivo deste artigo \'e apresentar uma outra maneira de re\-presentar
n\'umeros reais, que sempre fornece aproxima\c c\~oes racionais
surpreendentemente boas, e de fato fornece todas essas aproxima\c c\~oes
excepcionalmente boas, al\'em de ser natural e conceitualmente simples: a
representa\c c\~ao por fra\c c\~oes cont\'\i nuas.

Dado $x \in \re$, definimos $[x]$ como o \'unico inteiro tal que $[x] \le x < [x] + 1$. Definimos recursivamente
$$
\al_0=x,\quad a_n = [\al_n], \quad\text{e, se}\quad \al_n \in Z,\,\, \al_{n+1} = \frac{1}{\al_n-a_n}\,, \text{ para todo } n \in N.
$$
Se, para algum $n$,\,\,\,$\al_n=a_n$ temos
$$
x = \al_0 = a_0 + \cfrac1{a_1 + \cfrac1{a_2 +\dots+\cfrac1{a_n}}}
 =: [a_0;a_1,a_2,\dots,a_n].
$$
Sen\~ao denotamos
$$
x = a_0 +\cfrac1{a_1 + \cfrac1{a_2+\dots}}
 =: [a_0;a_1,a_2,\dots].
$$
O sentido dessa \'ultima nota\c c\~ao ficar\'a claro mais tarde. A representa\c
c\~ao acima se chama a representa\c c\~ao por fra\c c\~oes cont\'\i nuas de $x$.

\vglue .2in

\noindent{\bf \it Curiosidade}: O denominador da $n$-\'esima aproxima\c c\~ao em
base $B$ de um n\'umero real \'e $B^n$. J\'a o denominador $q_n$ da 
$n$-\'esima apro\-xima\c c\~ao por fra\c c\~ao cont\'\i nua de $x$ depende de
$x$. Apesar disso, para quase todo real $x$, $\root{n}\of{q_n}$ converge a
$e^{\pi^2/12\ln 2} = 3,27582291872\dots$ (meu n\'umero real preferido!) e
$\root{n}\of{\lv x-\dfrac{p_n}{q_n}\rv}$ converge a $e^{-\pi^2/6\ln 2} = 0,093187822954\dots$\,.

\vglue .2in

\noindent{\bf Observa\c c\~ao}: Os $\al_n$ (como fun\c c\~oes de $x$) s\~ao fun\c c\~oes distintas do tipo
$\dfrac{ax+b}{cx+d}$ com $a, b, c, d$ inteiros. Se a fra\c c\~ao cont\'\i nua de
$x$ \'e peri\'odica, ou seja, se $\al_{n+k} = \al_n$, $n\in\na$, $k \in \na^*$,
ent\~ao $x$ ser\'a raiz de uma equa\c c\~ao do segundo grau com coeficientes
inteiros, ou seja, ser\'a um irracional da forma $r+\sqrt s$, $r,s \in \bq$. A
rec\'\i proca \'e verdadeira (de fato j\'a foi enunciada no artigo de Jos\'e
Paulo Carneiro na RPN, ver refer\^encias), mas sua prova \'e mais dif\'\i cil, e ser\'a apresentada no Ap\^endice.

Se $x \in \bq$, sua representa\c c\~ao ser\'a finita, e seus coeficientes $a_n$ v\^em do algoritmo de Euclides:
\begin{align*}
x = \frac pq\,,\quad q > 0 &\qquad p = a_0q+r_0 \qquad\,\,\, 0 \le r_0 < q\\
                      &\qquad q = a_1r_0+r_1 \qquad 0 \le r_1 < r_0\\
                      &\qquad r_0=a_2r_1+r_2 \qquad 0 \le r_2 < r_1\\
                      &\quad\qquad\vdots \qquad\qquad\qquad\qquad\quad\vdots\\
                      &\qquad r_{n-2} = a_nr_{n-1}
\end{align*}

Isso j\'a \'e uma vantagem da representa\c c\~ao por fra\c c\~oes cont\'\i
nuas (al\'em de n\~ao depender de escolhas artificiais de base), pois o
reco\-nhecimento de racionais \'e mais simples que na representa\c c\~ao decimal.

\vglue .3in

\section{Reduzidas e boas aproxima\c c\~oes}

Seja $x = [a_0;a_1,a_2,\dots]$. Sejam $p_n \in \Z$, $q_n \in \na^*$ primos
entre si tais que $\dfrac{p_n}{q_n} = [a_0;a_1,a_2,\dots,a_n]$, $n \ge 0$. O
seguinte resultado ser\'a fundamental no que seguir\'a.

\vglue .2in

\noindent{\bf Proposi\c c\~ao 1.1:} \quad $(p_n)$ e $(q_n)$ satisfazem a
recorr\^encia $p_{n+2} = a_{n+2} p_{n+1} + p_n$\,, e $q_{n+2} = a_{n+2}q_{n+1}+q_n$\,, para todo $n\ge0$. Temos ainda 
$p_0 = a_0$\,, \,\,\,
$p_1 = a_0a_1+1$, \,\,\, $q_0 = 1$, \,\,\, $q_1=a_1$\,. Al\'em disso,
$p_{n+1}\,q_n - p_n\,q_{n+1} = (-1)^n$, $\forall\, n \ge 0$.

\vglue .1in

\noindent{\bf Dem:} Por indu\c c\~ao em $n$, provaremos que se $t_k > 0$, para $k > 1$ ent\~ao $[t_0;t_1,t_2,\dots,t_n] = \dfrac{x_k}{y_k}$ onde as seq\"u\^encias $(x_m)$ e $(y_m)$ s\~ao definidas por 
$x_0=t_0$\,,\,\, $y_0=1$,\,\, $x_1 = t_0t_1+1$, \,\,$y_1=t_0$\,\,\, $x_{n+2} =t_{n+2}\,x_{n+1}+x_n$\,, \,\, $y_{n+2} = t_{n+2}\,y_{n+1} + y_n$\,, $\forall\,n$. Suponha que a afirma\c c\~ao seja v\'alida para $k=n$. Para $k=n+1$ temos
\begin{align*}
&[t_0;t_1,t_2,\dots,t_n,t_{n+1}] = [t_0;t_1,t_2,\dots,t_n + \frac{1}{t_{n+1}}]\,=\\
&= \frac{\big(t_n+\dfrac{1}{t_{n+1}}\big)x_{n-1}+x_{n-2}}{\big(t_n + \dfrac{1}{t_{n+1}}\big)y_{n-1} + y_{n-2}} = \frac{t_{n+1}(t_nx_{n-1}+x_{n-2})+x_{n-1}}{t_{n+1}(t_ny_{n-1}+y_{n-2})+y_{n-1}} = \frac{t_{n+1}x_n+ x_{n-1}}{t_{n+1}y_n+y_{n-1}}\,\cdot
\end{align*}
Por outro lado as igualdades

\noindent $\bullet\qquad p_1q_0-p_0q_1 = (a_0a_1+1) - a_0a_1=1$

\noindent $\bullet\qquad p_{n+2}q_{n+1}-p_{n+1}q_{n+2} =
(a_{n+2}p_{n+1}+p_n)q_{n+1}$

\noindent \qquad $- (a_{n+2}\,q_{n+1}+q_n)p_{n+1} =
-(p_{n+1}q_n - p_nq_{n+1})$

\smallskip

\noindent mostram que $p_{n+1}\,q_n - p_n\,q_{n+1} = (-1)^n$, $\forall\, n \in \na$, o que implica em particular que os $p_n$\,, $q_n$ dados pelas recorr\^encias acima s\~ao primos entre si.\qquad\qed

\vglue .2in

\noindent{\bf Corol\'ario 1.2:} \quad $x = \dfrac{\al_np_{n-1}+p_{n-2}}{\al_nq_{n-1}+q_{n-2}}$ \quad e\quad $\al_n = \dfrac{p_{n-2}-q_{n-2}\al}{q_{n-1}\al-p_{n-1}}$\,, $\forall\,n\in\na$.

\vglue .1in

\noindent{\bf Dem:} A primeira igualdade \'e conseq\"u\^encia direta da prova, e a segunda \'e conseq\"u\^encia direta da primeira pois $x = [a_0;a_1,a_2,\dots,a_{n-1},\al_n]$. 

Note que as reduzidas de ordem par s\~ao menores e as de ordem \'\i mpar maiores que $x=[a_0;a_1,\dots]$.

\vglue .2in

\noindent{\bf Teorema 1.3:}\quad $\lv x-\dfrac{p_n}{q_n}\rv \le
\dfrac{1}{q_nq_{n+1}} < \dfrac{1}{q_n^2}$\,, $\forall\, n \in \na$. 

\noindent Al\'em disso,
$\lv x - \dfrac{p_n}{q_n}\rv < \dfrac{1}{2q_n^2}$ ou $\lv x -
\dfrac{p_{n+1}}{q_{n+1}}\rv < \dfrac{1}{2q_{n+1}^2}$\,, $\forall\, n\in\na$.

\vglue .1in

\noindent{\bf Dem:}\quad $x$ sempre pertence ao segmento de extremos
$\dfrac{p_n}{q_n}$ e $\dfrac{p_{n+1}}{q_{n+1}}$ cujo comprimento \'e
$$
\lv\frac{p_{n+1}}{q_{n+1}} - \frac{p_n}{q_n}\rv = \lv\frac{(-
1)^n}{q_nq_{n+1}}\rv = \frac{1}{q_nq_{n+1}} \Rightarrow \lv x -
\frac{p_n}{q_n}\rv \le \frac{1}{q_nq_{n+1}} < \frac{1}{q_n^2}\,\cdot
$$
Al\'em disso, se 
$$
\lv x - \frac{p_n}{q_n}\rv \ge \frac{1}{2q_n^2} \text{ e } 
\lv x-\frac{p_{n+1}}{q_{n+1}}\rv > \frac{1}{2q_{n+1}^2},
$$
ent\~ao
$$
\frac{1}{q_nq_{n+1}} = \lv x - \frac{p_n}{q_n}\rv + \lv x -
\frac{p_{n+1}}{q_{n+1}}\rv \ge \frac{1}{2q_n^2} + \frac{1}{2q_{n+1}^2}
\Rightarrow q_{n+1} = q_n\,, 
\text{ absurdo.}\qquad 
$$
\qed
\vglue .1in

\noindent{\bf Observa\c c\~ao}: De fato $\lv x-\dfrac{p_n}{q_n}\rv <
\dfrac{1}{q_nq_{n+1}} < \dfrac{1}{a_{n+1}q_n^2}$\,. Quanto maior for $a_{n+1}$ melhor ser\'a a aproxima\c c\~ao $\dfrac{p_n}{q_n}$ de $x$. O pr\'oximo resultado nos d\'a explicitamente o erro da aproxima\c c\~ao de $x$ por $\dfrac{p_n}{q_n}$\,.

\vglue .2in

\noindent{\bf Proposi\c c\~ao 1.4:} 
$$
x-\frac{p_n}{q_n} = \frac{(-1)^n}{(\al_{n+1}+\beta_{n+1})q_n^2}\,, \text{ onde } \beta_{n+1} = \frac{q_{n-1}}{q_n} 
= [0;a_n,a_{n-1},a_{n-2},\dots,a_1].
$$

\vglue .1in

\noindent{\bf Dem:} Temos $\al_{n+1} = \dfrac{p_{n-1}-q_{n-1}x}{q_nx-p_n}$\,. Portanto,
\begin{align*}
\al_{n+1}+\beta_{n+1} &= \frac{p_{n-1}-q_{n-1}x}{q_nx-p_n} + \frac{q_{n-1}}{q_n} = \frac{p_{n-1}q_n-p_nq_{n-1}}{q_n(q_nx-p_n)} =
 \frac{(-1)^n}{q_n(q_nx-p_n)} \Rightarrow x - \frac{p_n}{q_n}\, =\\
&=\frac{q_n(q_nx-p_n)}{q_n^2} = 
\frac{(-1)^n}{(\al_{n+1}+\beta_{n+1})q_n^2}\,.
\end{align*}
\qed
Como aplica\c c\~ao podemos provar o seguinte.

\vglue .2in

\noindent{\bf Teorema 1.5:} (Hurwitz, Markov). Para todo $\al$ irracional, $n\ge1$ temos $\lv\al-\dfrac pq\rv < \dfrac{1}{\sqrt5 q^2}$ para pelo menos um racional $\dfrac pq \in \bigg\{\dfrac{p_{n-1}}{q_{n-1}}, \dfrac{p_n}{q_n}, \dfrac{p_{n+1}}{q_{n+1}}\bigg\}$. Em particular $\lv\al - \dfrac pq\rv < \dfrac{1}{\sqrt 5 q^2}$ tem infinitas solu\c c\~oes racionais $p/q$.

\vglue .1in

\noindent{\bf Dem:} Suponha que o teorema seja falso. Ent\~ao existe $\al$ irracional, $n\ge1$ com $\al_n+\beta_n \le \sqrt 5$,\,\,$\al_{n+1}+\beta_{n+1} \le \sqrt 5$ e $\al_{n+2} + \beta_{n+2} \le 5$. Devemos portanto ter $a_n=a_{n+1} = a_{n+2} = 1$ (todos s\~ao claramente no m\'aximo 2, e se algum $a_k$ \'e igual a 2 com $k \in \{n, n+1, n+2\}$, ter\'\i amos $a_k + \beta_k \ge 2 + \dfrac 13 > \sqrt 5$, absurdo.)

\noindent Seja $x=1/\al_{n+2}$ e $y=\beta_{n+1}$\,. As desigualdades acima se traduzem em 
$$\frac{1}{1+x} + \frac 1y \le \sqrt 5,\,\,\, 1+x+y \le \sqrt 5 \text{ e } e \frac 1x + \frac{1}{1+y} \le \sqrt 5.
$$ 
Temos
$$
1+x+y \le \sqrt 5 \Rightarrow 1+x \le \sqrt 5-y \Rightarrow \frac{1}{1+x} + \frac 1y \ge \frac{1}{\sqrt 5-y} + \frac 1y = \frac{\sqrt 5}{y(\sqrt 5-y)}
$$
e portanto $y(\sqrt 5-y) \ge 1 \Rightarrow y \ge \dfrac{\sqrt 5-1}{2}\,\cdot$ Por outro lado temos
$$
x \le \sqrt 5 - 1 - y \Rightarrow \frac 1x + \frac{1}{1+4} \ge \frac{1}{\sqrt 5-1-y} + \frac{1}{1+4} = \frac{\sqrt 5}{(1+y)(\sqrt 5-1-y)}
$$
e portanto $(1+y)(\sqrt 5-1-y) \ge 1 \Rightarrow y \le \dfrac{\sqrt 5-1}{2}$\,, e portanto devemos ter $y = \dfrac{\sqrt 5-1}{2}$\,, o que \'e absurdo pois $y = \beta_{n+1} = \dfrac{q_{n-1}}{q_n} \in \bq$.

\vglue .2in

\noindent{\bf Observa\c c\~ao}: Em particular provamos que $\lv\al-\dfrac pq\rv < \dfrac{1}{\sqrt 5q^2}$ tem infinitas solu\c c\~oes racionais $\dfrac pq$\,, para todo $\al$ irracional. $\sqrt 5$ \'e o maior n\'umero com essa propriedade. De fato, se
$$
\ve > 0, \quad \al = \frac{1+\sqrt 5}{2} \quad\text{e}\quad \lv\al - \frac pq\rv < \frac{1}{(\sqrt 5+\ve)q^2}\,,
$$
temos
$$
\lv q\bigg(\frac{1+\sqrt 5}{2}\bigg)-p\rv < \frac{1}{(\sqrt 5+\ve)q} \Rightarrow \lv q\bigg(\frac{1+\sqrt 5}{2}\bigg) - p\rv\,\lv q\bigg(\frac{1-\sqrt 5}{2}\bigg)-p\rv < \frac{\lv\frac{1-\sqrt 5}{2}-\frac pq\rv}{\sqrt 5+\ve}\,,
$$
ou seja,
$$
|p^2-pq-q^2| < \lv\frac{1+\sqrt 5}{2} - \frac pq - \sqrt 5\rv
\bigg/(\sqrt 5+\ve).
$$
Se $q$ \'e grande, $1/q^2$ \'e pequeno, e $\dfrac{1+\sqrt 5}{2} - \dfrac pq$ \'e muito pr\'oximo de 0, donde \newline 
$\lv\dfrac{1+\sqrt 5}{2} - \dfrac pq - \sqrt 5\rv\bigg/(\sqrt 5+\ve)$ \'e muito pr\'oximo de $\dfrac{\sqrt 5}{\sqrt 5+\ve} < 1$, absurdo, pois\linebreak $|p^2-pq-q^2| \ge 1$ (de fato $p^2-pq-q^2$ \'e um inteiro n\~ao nulo, pois se $p^2-pq-q^2=0$ ter\'\i amos
$$
\bigg(\frac pq\bigg)^2 - \bigg(\frac pq\bigg) - 1 = 0 \Rightarrow \frac pq \in \bigg\{\frac{1+\sqrt 5}{2}, \frac{1-\sqrt 5}{2}\bigg\},
$$
absurdo, pois $\dfrac pq \in \bq$.)

\noindent Outra maneira de ver que, para todo $\ve > 0$,\,\,$\lv\dfrac{1+\sqrt 5}{2} - \dfrac pq\rv < \dfrac{1}{(\sqrt 5+\ve)q^2}$ tem apenas um n\'umero finito de solu\c c\~oes $\dfrac pq \in \Z$ \'e observar que as melhores aproxima\c c\~oes racionais de $\dfrac{1+\sqrt 5}{2}$ s\~ao as reduzidas $\dfrac{p_n}{q_n}$ de sua fra\c c\~ao cont\'\i nua $[1,1,1,1,\dots]$ (ver se\c c\~ao 2 e exemplos), para as quais temos $\lv\dfrac{1+\sqrt 5}{2} - \dfrac{p_n}{q_n}\rv = \dfrac{1}{(\al_{n+1}+\beta_{n+1})q_n^2}$\,, com $\al_{n+1} + \beta_{n+1}$ se aproximando cada vez mais de
$$
[1; 1, 1, 1,\dots] + [0; 1. 1. 1.\dots] = \frac{1+\sqrt 5}{2} + \frac{\sqrt 5-1}{2} = \sqrt 5.
$$

\vglue .2in

\noindent{\bf Exemplos:}

\begin{itemize}

\item[$\bullet$] $\pi = [3; 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14, 2, 1,\dots]$, portanto
\item[] $\dfrac{p_0}{q_0} = 3$, \quad $\dfrac{p_1}{q_1} = \dfrac{22}{7}$\,, \quad $\dfrac{p_2}{q_2} = \dfrac{333}{106}$\,, \quad $\dfrac{p_3}{q_3} = \dfrac{355}{113}\,\dots$

\item[$\bullet$] $e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8,\dots, 1, 1, 2n,\dots]$ (isso n\~ao \'e f\'acil de provar.)

\item[$\bullet$] $\sqrt 2 = [1; 2, 2, 2,\dots]$ pois
$$
\sqrt 2=1 + \frac{1}{\sqrt{2+1}} = 1 + \frac 1
2+\frac 1{ \sqrt{2+1}}  = 1 +   \frac12+ \frac 12+ \frac 1{\sqrt{2+1}}
 = \cdots
$$
$$
\frac{1+\sqrt 5}{2} = [1; 1,1,1,\dots] \text{ pois }  \frac{1+\sqrt 5}{2} = 1 + \frac{1 +\sqrt 5}{2} = 1 + \frac{1+ \sqrt 5}{2} + \frac {1+\sqrt 5} {2} = \cdots
$$
Isto prova em particular que $\sqrt 2$ e $\dfrac{1+\sqrt 5}{2}$ s\~ao irracionais, pois sua fra\c c\~ao cont\'\i nua \'e infinita.
\end{itemize}

\section{Boas aproxima\c c\~oes s\~ao reduzidas}

O pr\'oximo teorema (e seu Corol\'ario 2) caracteriza as reduzidas em termo do
erro reduzido da aproxima\c c\~ao de $x$ por $p/q$, o qual \'e, por defini\c
c\~ao, a raz\~ao entre $|x-p/q|$ e o erro m\'aximo da aproxima\c c\~ao por
falta com denominador $q$, que \'e $1/q$. Assim, o erro reduzido da aproxima\c
c\~ao de $x$ por $p/q$ \'e $|qx-p|$.

\vglue .2in

\noindent{\bf Teorema 2.1:}\quad $|q_nx-p_n| < |qx-p|$,\,\, $\forall\, p,q\in\Z$,\,\, $0 < q < q_n$\,\, $\dfrac pq \ne \dfrac{p_n}{q_n}\,\cdot$. Al\'em disso, $|q_nx-p_n| \le |qx-p|$, \,\,$\forall\,p,q \in \Z$,\,\, $0< q < q_{n+1}$\,.

\vglue .1in

\noindent{\bf Dem:}\quad $\lv\dfrac pq - \dfrac{p_n}{q_n}\rv \ge \dfrac{1}{qq_n}
> \dfrac{1}{q_nq_{n+1}}$ se $q < q_{n+1}$\,, e assim $\dfrac pq$ est\'a fora do intervalo $\bigg(\dfrac{p_n}{q_n}, \frac{p_{n+1}}{q_{n+1}}\bigg)$. Portanto
\begin{align*}
\lv x-\frac pq\rv &\ge \min\bigg\{\lv\frac pq - \frac{p_n}{q_n}\rv, \lv\frac pq
- \frac{p_{n+1}}{q_{n+1}}\rv\bigg\}  \ge \frac{1}{qq_{n+1}} \Rightarrow |qx-p|\\
&\ge \frac{1}{q_{n+1}} \ge |q_nx-p_n|.
\end{align*}
Al\'em disso, se vale a igualdade, ent\~ao $x = \dfrac{p_{n+1}}{q_{n+1}}$\,, donde
$a_{n+1} \ge 2$, e $q_{n+1} > 2q_n$\,, pois numa fra\c c\~ao cont\'\i nua
finita, como no algoritmo de Euclides, o \'ultimo coeficiente $a_n$ \'e sempre maior que 1. Nesse caso, se $q < q_n$\,, teremos
\begin{align*}
\lv x-\frac pq\rv &\ge \lv x-\frac{p_n}{q_n}\rv - \lv \frac{p_{n+1}}{q_{n+1}} -
\frac{p_n}{q_n} \rv \ge \frac{1}{qq_n} - \frac{1}{q_nq_{n+1}} = \frac{q_{n+1}-q}{qq_nq_{n+1}}\\
& > \frac{1}{qq_{n+1}} \Rightarrow |qx-p|
 > \frac{1}{q_{n+1}} \ge |q_nx-p_n|.
\end{align*}


\vglue .1in

\noindent{\bf Corol\'ario 2.2:}\quad $\lv x - \dfrac{p_n}{q_n}\rv < \lv x - \dfrac pq\rv$,\,\, $\forall\, q < q_n$\,.

\vglue .2in

\noindent{\bf Corol\'ario 2.3:} Se $|qx-p| < |q'x-p'|$,\,\, $\forall\, q' \le q$,\,\, $\dfrac pq \ne \dfrac{q'}{q'}$ ent\~ao $p/q$ \'e uma reduzida da fra\c c\~ao cont\'\i nua de $x$.

\vglue .1in

\noindent{\bf Dem:} Tome $n$ tal que $q_n \le q < q_{n+1}$\,.

\noindent Teremos $|q_nx-p_n| \le |qx-p|$, e portanto $p/q = p_n/q_n$\,. \qquad\quad\qed

\vglue .2in

\noindent{\bf Teorema 2.4:} Se $\lv x-\dfrac pq\rv < \dfrac{1}{2q^2}$ ent\~ao $\dfrac pq$ \'e uma reduzida da fra\c c\~ao cont\'\i nua de $x$.

\vglue .1in

\noindent{\bf Dem:} Seja $n$ tal que $q_n < q \le q_{n+1}$\,. Suponha que $\dfrac pq \ne \dfrac{p_{n+1}}{q_{n+1}}$\,. Ent\~ao, temos duas possibilidades:

\begin{itemize}

\item[{a)}]\quad $q \ge \dfrac{q_{n+1}}{2} \Rightarrow \lv x-\dfrac pq\rv \ge \dfrac{1}{qq_{n+1}} \ge \dfrac{1}{2q^2}$\,.

\item[{b)}]\quad $q < \dfrac{q_{n+1}}{2} \Rightarrow q_{n+1} > 2q_n \Rightarrow 
\lv x - \dfrac pq\rv \ge \lv\dfrac{p_n}{q_n} - \dfrac pq\rv - \lv \dfrac{p_{nm}}{q_{nm}} - \dfrac{p_n}{q_n}\rv \ge \dfrac{1}{qq_n} - \dfrac{1}{q_nq_{n+1}} = \dfrac{q_{n+1}-q}{qq_nq_{n+1}} > \frac{1}{2qq_n} > \frac{1}{2q^2}$\,.

\end{itemize}


\section{Fra\c c\~oes cont\'\i nuas peri\'odicas}

Nesta se\c c\~ao provaremos que os n\'umeros reais com fra\c c\~ao cont\'\i nua peri\'odica s\~ao exatamente as ra\'\i zes de equa\c c\~oes do segundo grau com coeficientes inteiros.

Lembramos que na representa\c c\~ao de $x$ por fra\c c\~ao cont\'\i nua, $a_n$\,, $\al_n$ s\~ao definidos por recurs\~ao por
$$
\al_0 = x, \quad a_n = [\al_n],\quad \al_{n+1} = \frac{1}{\al_n-a_n}\,\cdot
$$
E temos
$$
\al_n = \frac{p_{n-2}-q_{n-2}x}{q_{n-1}x-p_{n-
1}}\,,\quad \forall\, n \in \na.
$$

Isso d\'a uma prova expl\'\i cita do fato de que se a fra\c c\~ao cont\'\i nua
de $x$ \'e peri\'odica, ent\~ao $x$ \'e raiz de uma equa\c c\~ao do segundo
grau com coeficientes inteiros. De fato, se $\al_{n+k} = \al_n$\,,\,\, $n \in \na$,\,\,$k \in \na^*$ ent\~ao
\begin{align*}
&\frac{p_{n-2}-q_{n-2}x}{q_{n-1}x-p_{n-1}} = \frac{p_{n+k-2} - q_{n+k-
2}x}{q_{n+k-1}x - p_{n+k-1}} \quad\Rightarrow (q_{n-1}\,q_{n+k-2} - q_{n-2}\,q_{n+k-1})x^2\\
& + (p_{n+k-1}\,q_{n-2} + p_{n-2}\,q_{n+k-1} - p_{n+k-2}\,q_{n-1} - p_{n-1}\,q_{n+k-2})x\\
&+ p_{n-1}\,p_{n+k-2} - p_{n-2}\,p_{n+k-1} = 0.
\end{align*}
Note que o coeficiente de $x^2$ \'e n\~ao-nulo, pois $\dfrac{q_{n-1}}{q_{n-2}}$
\'e uma fra\c c\~ao irredut\'\i vel (de fato $p_{n-1}q_{n-2} - p_{n-2}q_{n-1} =(-1)^n$) de denominador $q_{n-2}$ e
$\dfrac{q_{n+k-1}}{q_{n+k-2}}$ \'e uma fra\c c\~ao irredutivel de denominador $q_{n+k-2} > q_{n-2}$\,, donde $\dfrac{q_{n-1}}{q_{n-2}} \ne \dfrac{q_{n+k-1}}{q_{n+k-2}} \Rightarrow q_{n-1}\,q_{n+k-2} - q_{n-2}\,q_{n+k-1} \ne 0$.

Vamos provar agora um resultado devido a Lagrange segundo o qual se $x$ \'e uma {\it irracionalidade quadr\'atica}, isto
\'e, se $x$ \'e um irracional do tipo $r+\sqrt s$, $r,s \in \bq$, $s > 0$ ent\~ao a fra\c c\~ao cont\'\i nua de $x$ \'e peri\'odica, i.e., existem $n\in\na$, $k\in\na^*$ com $\al_{n+k} = \al_n$\,. Neste caso, existem $a$, $b$, $c$ inteiros tais que $ax^2 + bx + c = 0$, com $b^2-4ac > 0$ e $\sqrt{b^2-4ac}$
irracional. Como vimos na se\c c\~ao 1,
$$
x = \frac{p_{n-1}\al_n + p_{n-2}}{q_{n-1}\al_n + q_{n-2}}\,,
$$
e portanto
\begin{align*}
ax^2+bx+c=0 &\Rightarrow a\bigg(\frac{p_{n-1}\al_n+p_{n-2}}{q_{n-1}\al_n+q_{n-2}}\bigg)^2 + b\bigg(\frac{p_{n-1}\al_n+p_{n-2}}{q_{n-1}\al_n+q_{n-2}}\bigg) + c= 0\\
&\Rightarrow A_n\al_n^2 + B_n\al_n + C_n = 0,
\end{align*}
onde
\begin{align*}
&A_n = a\,p_{n-1}^2 + b\,p_{n-1}q_{n-1} + c\,q_{n-1}^2\\
&B_n = 2a\,p_{n-1}p_{n-2} + b(p_{n-1}q_{n-2} + p_{n-2}q_{n-1}) + 2c\,q_{n-1}q_{n-2}\\
&C_n = a\,p_{n-2}^2 + b\,p_{n-2}q_{n-2} + c\,q_{n-2}^2\,.
\end{align*}

Note que $C_n = A_{n-1}$\,. Vamos provar que existe $M > 0$ tal que $0 < |A_n|\le M$ para todo $n\in\na$, e portanto $0 < |C_n| \le M$,\,\, $\forall\, n\in\na$:
$$
A_n = a\,p_{n-1}^2 + b\,p_{n-1}q_{n-1} + c\,q_{n-1}^2 = a\,q_{n-1}^2\bigg(x -
\frac{p_{n-1}}{q_{n-1}}\bigg)\bigg(\bar x - \frac{p_{n-1}}{q_{n-1}}\bigg),
$$
onde $x$ e $\bar x$ s\~ao as ra\'\i zes de $a,X^2 + b\,X + c = 0$, mas
\begin{align*}
\lv x - \frac{p_{n-1}}{q_{n-1}}\rv &< \frac{1}{q_{n-1}^2} \le 1 \Rightarrow
|A_n| = a\,q_{n-1}^2\lv x - \frac{p_{n-1}}{q_{n-1}}\rv\,\lv\bar x - \frac{p_{n-1}}{q_{n-1}}\rv\\
&\le a\bigg(|\bar x-x| + \lv x - \frac{p_{n-1}}{q_{n-1}}\rv\bigg) \le a(|\bar x-x|+1) =: M.
\end{align*}

Notemos agora que $B_n^2 - 4A_nC_n = b^2-4ac$,\,\, $\forall\, n\in\na$. De fato, $B_n^2 - 4A_nC_n = (p_{n-1}q_{n-2} - p_{n-2}q_{n-1})^2(b^2-4ac) = b^2-4ac$. 
Portanto,
$B_n^2 \le 4A_nC_n + b^2-4ac = 4M^2 + b^2 - 4ac \Rightarrow B_n \le M'= \sqrt{4M^2+b^2-4ac},\quad \forall\, n\in\na$.

Provamos assim que $A_n$\,, $B_n$ e $C_n$ est\~ao uniformemente limitados, donde h\'a apenas um n\'umero finito de poss\'\i veis equa\c c\~oes $A_nX^2 +
B_nX + C_n=0$, e portanto de poss\'\i veis valores de $\al_n$\,. Assim,
necessariamente $\al_{n+k} = \al_n$  para alguma escolha de $n\in\na$,
$k\in\na^*$.

\pagebreak

\noindent
{\bf Aplicação:} A equação de Pell.

Seja $A$ um inteiro positivo. Estamos interessados na equação $x^2-Ay^2=1$, com $x$ e $y$ inteiros. Se $A$ é um quadrado perfeito, digamos $a=k^2$, temos que $x^2-Ay^2=(x-ky)(x+ky)=0$ admite apenas as soluções triviais $y=0$, $x=\pm 1$, pois teríamos $x-ky=x+ky=\pm 1$. o caso itneressante é quando $A$ não é um quadrado pergeito, e portanto $\sqrt A$ é um irracional (de fato, se $\sqrt A=\frac pq$, com $\mdc(p,q)=1$ e $q>1$, teríamos $A=\frac{p^2}{q^2}$ o que é um absurdo, pois $\mdc(p,q)=1\Rightarrow \mdc(p^2,q^2)=1$, donde $p^2/q^2$ não pode ser inteiro). nesse caso, a equação $x^2-Ay^2=1$ é conhecida como uma {\it equação de Pell\/}. Nosso resultado principal é o seguinte:

\vskip .2in

\noindent
{\bf Teorema 3.1:} A equação $x^2-Ay^2=1$ tem infinitas soluções inteiras $(x,y)$. Além disso, as soluções com $x$ e $y$ inteiros positivos podem ser enumeradas por $(x_n,y_n)$, $n\ge0$ de modo que, para todo $n$, $x_n+y_n\sqrt A=(x_1+y_1\sqrt A)^n$, e portanto
$$
x_n=\frac{(x_1+y_1\sqrt A)^n+(x_1-y_1\sqrt A)^n}{2} \quad \text{ e }\quad
y_n=\frac{(x_1+y_1\sqrt A)^n+(x_1-y_1\sqrt A)^n}{2\sqrt A}.
$$

\noindent
{\bf Observação:} As seqüências $(x_n)$ e $(y_n)$ acma satisfazem a recorrência $u_{n+2}=2x_0u_{n+1}-u_n$, $\forall\,\, n\ge 1$.

\vskip .1in

\noindent
{\bf Dem:} Observemos inicialmente que, se $D=\{x+y\sqrt A \mid x,y\in\mathbb Z\}$ então $N\colon D\to D$, $N(x+y\sqrt A)=x^2-Ay^2$ é uma função multiplicativa, isto é,
$$
N((x+y\sqrt A)(u+v\sqrt A))=N(x+y\sqrt A) N(u+v\sqrt A),\,\, \forall\, x,y,u,v\in \mathbb Z.
$$
De fato,
\begin{align*}
N((x+y\sqrt A)(u+v\sqrt A)) & = N((xu+ayv)+(xv+yu)\sqrt A) = (xu+Ayv)^2-A(xv+yu)^2 \\
&= x^2u^2+A^2y^2v^2-A(x^2v^2+y^2u^2) = (x^2-Ay^2)(u^2-Av^2).
\end{align*}
Usaremos agora o fato de que, como $\sqrt A$ é irracional, a desigualdade $|\sqrt A-\frac pq| <\frac1{q^2}$ tem infinitas soluções racionais $p/q$. Note que se $|\sqrt A-\frac pq|<\frac1{q^2}$ então
\begin{align*}
|p^2-Aq^2| &= |p-q\sqrt A| |p+q\sqrt A| = q|\sqrt A-\frac pq| |p+q\sqrt A | < q\cdot \frac 1{q^2} \cdot |p+q\sqrt A |\\
&= | \frac pq + \sqrt A| \le 2\sqrt A+ | \sqrt A-\frac pq| < 2\sqrt A+1.
\end{align*}
Considerando infinitos pares de inteiros positivos $(p_n,q_n)$ com $|\sqrt A-\frac{p_n}{q_n}|< \frac 1{q_n^2}$, teremos sempre $|p_n-Aq_n^2|<2\sqrt A+1$, e portanto temos um número finito de possibilidades para o valor (inteiro) de $p_n-Aq_n^2$. consequentemente, existe um inteiro $k\ne0$ tal que $p_n-Aq_n^2=k$ para infinitos valores de $n$. Obtemos portanto duas seqüências crescentes de pares de inteiros positivos $u_r), (v_r)$, $r\in\mathbb N$ tais que $u_r^2-k v_r^2=k$ para todo $r$.

Como há apenas $|k|^2$ possibilidades para os pares $(\overline u_r(\text{mod }|k|), \overline v_r(\text{mod }|k|))$, axistem inteiros $a$ e $b$ e infinitos valores de $r$ tais que $u_r\equiv a(\text{mod }|k|)$ e $v_r\equiv b(\text{mod }|k|)$. Tomamos então $r<s$ com as propriedades acima.
Seja
\begin{align*}
x+y\sqrt A &= \frac{u_s+v_s\sqrt A}{u_r+v_r\sqrt A}= \frac{(u_s+v_s\sqrt A)(u_r-v_r\sqrt A)}{u_r^2-Av_r^2} \\
&= \frac{u_su_r-Av_sv_r}{k}+\left( \frac{u_rv_s-u_sv_r}{k} \right) \sqrt A.
\end{align*}
Temos  $u_su_r-Av_sV_r\equiv u_r^2-Av_r^2=k\equiv 0(\text{mod }|k|)$ e $u_rv_s-u_sv_r\equiv ab-ab=0(\text{mod }|k|)$, e portanto $x=\frac{u_su_r-Av_sv_r}{k}$ e $y=\frac{u_rv_s-u_sv_r}{k} $ são inteiros. Por outro lado, $(x+y\sqrt A)(u_r+v_r\sqrt A)=u_s+v_s\sqrt A$, donde $N(x+y\sqrt A)N(u_r+v_r\sqrt A)=N(u_s+v_s\sqrt A)$. Como $N(u_r+v_r\sqrt A)=N(u_s+v_s\sqrt A)=k$, segue que $N(x+y\sqrt A)=x^2-Ay^2=1$. Além disso, como $s>r$, $u_s+v_s\sqrt A>u_r+v_r\sqrt A$, donde $x+y\sqrt A=\frac{u_s+v_s\sqrt A}{u_r+v_r\sqrt A}>1$.

Sejam agora $x_1,y_1\in\mathbb Z$ tais que $x_1+y_1\sqrt A>1$ e $x_1^2-Ay_1^2=1$ com $x_1+y_1\sqrt A$ mínimo. Temos então $(x_1+y_1\sqrt A)^{-1}=x_1-y_1\sqrt A$. Vamos mostrar que, se $\tilde x+\tilde y\sqrt A>1$ e
$\tilde x^2-A\tilde y^2=1$ (com $\tilde x$ e $\tilde y$ inteiros) então $\tilde x+\tilde y\sqrt A=(x_1+y_1\sqrt A)^n$ para algum inteiro positivo $n$. Para isso, tome $n\ge1$ tal que $(x_1+y_1\sqrt A)^n\le \tilde x+\tilde y\sqrt A<(x_1+y_1\sqrt A)^{n+1}$. Temos então $1\le(\tilde x+\tilde y\sqrt A)(x_1-y_1\sqrt A)^n< x_1+y_1\sqrt A$. Se $u+v\sqrt A=(\tilde x+\tilde y\sqrt A)(x_1-y_1\sqrt A)^n$, com $u$ e $v$ inteiros, temos
$$
u^2-Av^2=N(u+v\sqrt A)=N(\tilde x+\tilde y\sqrt A)N(x_1-y_1\sqrt A)^n=1,
$$
donde $u+v\sqrt A=1$, pela minimalidade de $x_1+y_1\sqrt A$, pois $1\le u+v\sqrt A < x_1+y_1\sqrt A$. Note finalmente que se $x$ e $y$ são inteiros e $x^2-Ay^2=1$ então $x+y\sqrt A>1$ equivale a termos $x$ e $y$ positivos, pois temos $0<(x+y\sqrt A)^{-1}=x-y\sqrt A<1$, donde
$x=\frac{(x+y\sqrt A)+(x-y\sqrt A)}{2}$  e 
$y=\frac{(x+y\sqrt A)-(x-y\sqrt A)}{2\sqrt A}$ são positivos. \qed

\newpage

\setcounter{section}{0}%para numerar capitulos

\centerline{\Large\bf CAPÍTULO 4}

\vskip .5in

\centerline{\Large\bf Propriedades Estatísticas de Frações Contínuas}

\centerline{\Large\bf e Aproximações Diofantinas: O Teorema de Khintchine}

\vskip .5in

\noindent
{\Large\bf Introdução:}

\vskip .2in

 O problema básico da teoria de aproximações diofantinas é o de estudar boas aproximações de números reais por números racionais. Uma extensão natural desse problema é o estudo de aproximações simultâneas de $n$ números reais por números racionais com o mesmo denominador.

Dado um número irracional $\al$, um resultado clássico de Dirichlet (que já provamos usando frações contínuas) afirma que existem infinitos racionais $\frac pq$ tais que $|\al-\frac pq|<\frac 1{q^2}$ (vejamos outra prova simples: dado $N\in\na$, consideramos os $N+1$ elementos de $[0,1)$ da forma $j\al-\lfloor j\al \rfloor$, com $0\le j\le N$. Como $[0,1)=\bigcup_{k=0}^{N-1} \left[ \frac kN, \frac{k+1}N \right)$, existem dois desses elementos, digamos $j_1\al-\lfloor j_1\al \rfloor$ e $j_2\al-\lfloor j_2\al\rfloor$ num mesmo intervalo $\left\lfloor \frac kN,\frac{k+1}N \right)$, e portanto, se $j_1<j_2$, $q=j_2-j_1$ e $p=\lfloor j_2\al \rfloor- \lfloor j_1\al\rfloor$, temos $0<|q\al-p|<\frac 1N\Rightarrow |\al-\frac pq|<\frac 1{qN}\le \frac 1{q^2})$. Hurwitz e Markov provaram que de fato $|\al-\frac pq|<\frac 1{\sqrt 5 q^2}$ tem infinitas soluções $\frac pq\in\Q$, para todo irracional $\al$, e que $\sqrt 5$ é a maior constante com essa propriedade. Markov ([Ma]) provou que, para todo $c<3$, o conjunto dos $\al\in\re$ tais que $|\al-\frac pq|<\frac 1{cq^2}$ tem apenas um número finito de soluções $\frac pq\in\Q$ é enumerável, mas o conjunto dos $\al\in\re$ tais que $|\al-\frac pq|<\frac1{3q^2}$ tem apenas um número finito de soluções tem o mesmo cardinal que $\re$.

Neste artigo, vamos estudar desigualdades do tipo 
$$
 |\al-\frac pq|<\frac{f(q)}q, \eqno{(1)}
$$
 onde $f\colon\na\to\re^+$ é uma função decrescente, do ponto de vista da teoria da medida. Vamos provar o teorema de Khintchine, segundo o qual, se $\sum_{q=1}^\infty f(q)=+\infty$ então (1) tem infinitas soluções $\frac pq\in\Q$, para quase todo $\al\in\re$, mas se $\sum_{q=1}^\infty f(q)<+\infty$ então (1) tem apenas um número finito de soluções $\frac pq\in \Q$, para quase todo $\al\in\re$.

Note que do ponto de vista topológico a situação é diferente: qualquer que seja a função positiva $f$, (1) tem infinitas soluções $\frac pq\in\Q$ para $\al\in R_f$, onde $R_f$ é um conjunto residual, i.e. contém (de fato é) uma interseção enumerável de abertos densos.

A principal técnica usada para estudar aproximações de números reais por números racionais são as frações contínuas, que fornecem todas as boas a\-pro\-xi\-ma\-ções de um irracional $\al$ por racionais. As definições e provas dos resultados a seguir sobre frações contínuas podem ser encontradas em [Mo].

Dado $\al\in\re$, definimos $\al_0=\al$, $a_n=\lfloor \al_n\rfloor$ e, se $\al_n\notin\Z$, $\al_{n+1}=\frac1{\al_n-a_n}$, para todo $n\in\na$. Para cada $n\in\na$ tomamos $p_n\in\Z$ e $q_n\in\na^*$ primos entre si tais que
$$
\frac{p_n}{q_n}=[a_0; a_1,a_2,\dots,a_n]:= a_0+ \frac{1}{a_1+ \frac{1}{a_2+{}_{\ddots{}_{+\frac{1}{a_n}}}}}.
$$
Temos
$$
\frac{1}{(a_{n+1}+2)q_n^2} < |\al-\frac{p_n}{q_n}| < \frac 1{a_{n+1}q_n^2} \le \frac 1{q_n^2},\quad \text{ para todo } n\in\na.
$$
As seqüências $p_n$ e $q_n$ satisfazem $p_{n+1}q_n-p_nq_{n+1}=(-1)^n$, $\forall\, n\ge0$. Se $|\al-\frac pq|<\frac1{2q^2}$ então $\frac pq=\frac{p_n}{q_n}$, para algum $n\in\na$. Por outro lado, para todo $n\in\na$ vale $|\al-\frac{p_n}{q_n}|<\frac1{2q_n^2}$ ou $|\al-\frac{p_{n+1}}{q_{n+1}}|<
\frac1{2q_{n+1}^2}$. 

Temos
$$
p_{n+2}=a_{n+2}p_{n+1}+p_n,\,\, q_{n+2}=a_{n+2}q_{n+1}+q_n\text{ e }
\al=\frac{\al_{n+1}p_n+p_{n-1}}{\al_{n+1}q_n+q_{n-1}},\,\text{ para todo } n\in\na.
$$

A prova que apresentaremos na Seção 1, baseada no estudo de propriedades estatísticas de frações contínuas, é inspirada em conversas que tive há uns 9 anos com o Prof. Nicolau Corção Saldanha sobre o tema.

O problema básico de aproximações simultâneas é o seguinte: dado \linebreak $\al_1,\al_2,\dots,\al_n\in\re$ queremos encontrar números racionais $\frac{p_1}q,\frac{p_2}q,\dots,\frac{p_n}q$ tais que $|\al_j-\frac{p_j}q|$ seja pequeno para todo $j\le n$. Em geral sempre é possível encontrar racionais tais que $|\al_j-\frac{p_j}q|<\frac1{q^{1+1/n}}$, o que estende o teorema de Dirichlet e pode ser provado de modo análogo: dado $N\in\na$ consideramos os $N^n+1$ pontos
$$
p_j=(\al_1j-\lfloor\al_1  j\rfloor, \al_2 j-\lfloor \al_2 j\rfloor,\dots,\al_n j-\lfloor \al_n j\rfloor),\quad 0\le j\le N^n
$$
 no hipercubo $[0,1)^n$. Dividimos $[0,1)^n$ como $\left(\bigcup_{k=0}^{N-1} \left[ \frac kN, \frac{k+1}N \right) \right)^n$ em $N^n$ cubos de lado $\frac 1N$. Haverá necessariamente dois pontos $p_{j_1}$ e $p_{j_2}$ num mesmo cubo dessa decomposição,  e, se $j_1<j_2$, $q=j_2-j_1$, $p_j=\lfloor j_2\al_j\rfloor-\lfloor j_1 \al_j\rfloor$, teremos $|\al_j-\frac{p_j}{q_j}|  <  \frac1{Nq_j} \le \frac 1{q_j^{1+1/n}}$, para todo $j\le n$.

Infelizmente não há um substituto satisfatório para a teoria de frações contínuas em dimensão maior que um, mas é possível provar uma versão $n$-dimensional do Teorema de Khinchine (provada originalmente em [K]), o que faremos na Seção 2.

Para maiores informações sobre aproximações diofantinas, veja [C1] e [S].


\section{O Teorema de Khintchine via frações contínuas}

{\nobf Teorema 1.1:} (Khintchine) {\it Seja $f\colon\na\to\re^+$ uma função decrescente tal que $h(n)=nf(n)\colon \na\to\re^+$ também seja decrescente. 

\begin{itemize}

\item[{\rm a)}] Se\,\, $\sum_{n=1}^\infty f(n)<+\infty$ então a equação $|\al-\frac pq|<\frac{f(q)}q$ tem apenas um número finito de soluções racionais $p/q$, para quase todo $\al\in\re/\Q$

\item[{\rm b)}] Se\,\, $\sum_{n=1}^\infty f(n)=+\infty$ então a equação $|\al-\frac pq|<\frac{f(q)}q$ tem um número infinito de soluções racionais $p/q$, para quase todo $\al\in\re/\Q$.
\end{itemize}
}

\medskip

\noindent
{\bf Observação:} A condição de $nf(n)$ ser decrescente não é de fato necessária, como veremos na seção 2, mas simplifica a prova. Por outro lado, não podemos retirar a hipótese de $f$ ser decrescente (veja [C2]).

\medskip

\noindent
{\bf Dem:}

\medskip

\noindent
{\bf Lema 1.2:} {\it Sejam $n,k\in\na$, e seja $[0,a_1,a_2,\dots]$ a fração contínua de um número $\al\in[0,1]$. A probabilidade de um termo $a_{n+1}$ ser igual a $k$ dado que $a_1=k_1$, $a_2=k_2,\dots,a_n=k_n$ está entre $1/(k+1)(k+2)$ e $2/k(k+1)$, $\forall\,\, k_1,k_2,\dots,k_n\in\na^*$.\/}

\bigskip

\noindent
{\bf Dem:} Sejam $p_{n-1}/q_{n-1}=[0;a_1,a_2,\dots,a_{n-1}]$ e $p_n/q_n=[0; a_1,a_2,\dots,a_{n-1},a_n]$. Se $\al\in[0,1]$, $\al=[0;a_1,a_2,\dots,a_n,\al_{n+1}]$, $\al_{n+1}\in[1,+\infty)$ então $\al\in \left[ \frac{p_n+p_{n-1}}{q_n+q_{n-1}}, \frac{p_n}{q_n} \right)$, e, se além disso $a_{n+1}=k$, temos $\al\in \left[ \frac{kp_n+p_{n-1}}{kq_n+q_{n-1}}, \frac{(k+1)p_n+p_{n-1}}{(k+1)q_n+q_{n-1}} \right]$, e valem as recíprocas (as ordens dos extremos dos intervalos podem estar trocadas). Os comprimentos dos referidos intervalos são, respectivamente, $\frac1{q_n(q_n+q_{n-1})}$ e 
$\frac1{(kq_n+q_{n-1})((k+1)q_n+q_{n-1})}$ (pois $|p_n q_{n-1}-p_{n-1}q_n|=1)$, e portanto a razão entre seus comprimentos é $\frac{q_n(q_n+q_{n-1})}{(kq_n+q_{n-1})((k+1) 
q_n+q_{n-1})} =
\frac{1+\be}{(k+\be)(k+1+\be)}$, onde $\be=q_{n-1}/q_n\in [0,1]$. Portanto, a razão pertence a $[1/(k+1)(k+2), 2/k(k+1)]$. \qed

\bigskip

\noindent
{\bf Corolário 1.3:} A probabilidade de $a_{n+1}\ge k$, nos termos do Lema acima, pertence a  \linebreak $[1/(k+1), 2/k]$.

\bigskip

\noindent
{\bf Lema 1.4:} {\it Para quase todo $\al\in\re$ existe $c\in\re$ tal que $q_n\le c^n$, para todo $n\in\na$\/}.

\bigskip

Antes de provar o Lema 1.4 vamos mostrar como termina a prova do Teorema de Khintchine. Suponhamos que $\Sigma f(n)<\infty$. Seja $\ga=\frac{1+\sqrt 5}2$. Se a aproximação $p_n/q_n$ de $\al$ é tal que $|\al-\frac{p_n}{q_n}|<\frac{f(q_n)}{q_n}$ então $a_{n+1}+2> \frac1{q_n f(q_n)} > \frac1{\ga^{n-1} f(\ga^{n-1})}$ (pois para todo $\al\in \re\setminus \Q$ vale $q_n>\ga^{n-1}$, $\forall\, n\in\na$). $\Rightarrow a_{n+1}>  \frac1{\ga^{n-1}f(\ga^{n+1})}-2$. A probabilidade de $a_{n+1}\le \frac1{\ga^{n-1}f(\ga^{n-1})} -2 =: A(n)$ é pelo menos $1- \frac2{A(n)}$, $\forall \, n \in\na$ (pelo corolário do Lema 1.2), e a hipótese de $\sum_{n=1}^\infty f(n)<\infty$ implica que $\sum_{n=1}^\infty \frac2{A(n)}<\infty$, por comparação com 
$$
\sum_{k=1}^\infty \ga^k f(\ga^k)<
\frac\ga{\ga-1} \sum_{k=0}^\infty (\ga^{k+1}-\ga^k)f(\ga^{k+1})<\sum_{n=1}^\infty f(n)<+\infty.
$$ 

Temos portanto $\prod_{n=1}^\infty(1-\frac2{A(n)})>0\Rightarrow$ para cada $\ve>0$
existe $n_0\in\na$ tal que $\prod_{n=n_0}^\infty(1-\frac2{A_n})>1-\ve$, donde com probabilidade total $a_{n+1}\le A(n)$ para todo $n$ suficientemente grande $\Rightarrow$ $|\al-\frac pq|<\frac{f(q)}q$ tem apenas um número finito de soluções.

Suponhamos agora que $\Sigma f(n)=+\infty$, fixemos $c>0$ e vamos nos restringir ao conjunto $X_c$ dos $\al\in[0,1]$ tais que $q_n<c^n$ para todo $n\in\na$ (a união dos conjuntos $X_c$ para todo $c\in\na$ tem probabilidade total em $[0,1]$,  pelo Lema 1.4).

Se $a_{n+1}>\frac1{q_nf(q_n)}$ teremos $|\al-\frac{p_n}{q_n}|<\frac{f(q_n)}{q_n}$. Como $q_n<c^n$, $\frac 1{q_n f(q_n)}<\frac 1{c^nf(c^n)}$. Vamos mostrar que com probabilidade total temos $a_{n+1}\ge\frac1{c^nf(c^n)}$ para infinitos valores de $n\in\na$. Isso segue de $\prod_{n=1}^\infty \left(1-\frac1{B(n)+1} \right)=0$, onde $B(n)=\frac1{c^n f(c^n)}$, que por sua vez segue de $\sum_{n=1}^\infty c^n f(c^n) \ge c^{-1} \sum_{n=1}^\infty (c^{n+1}-c^n)f(c^n)=+\infty$. Portanto, para todo $n_0\in\na$ temos $\prod_{n=n_0}^\infty \left(1-\frac1{B(n)+1}\right)=0$, e, com probabilidade total, existe $n\ge n_0$ com $a_{n+1}\ge \frac1{c^nf(c^n)}$, donde a equação $|\al-\frac{p_n}{q_n}|< \frac{f(q_n)}{q_n}$ é satisfeita com probabilidade total para infinitos valores de $n\in\na$. \qed

\bigskip

\noindent
{\bf Prova do Lema 1.4:} Sejam $n,k\in\na$. A probabilidade de que $k$ apareça pelo menos $4n/k(k+1)$ vezes entre $a_1,a_2,\dots,a_n$ é limitada por 
$\sum_{j=sn}^n C_n^j(\frac s2)^j(1-\frac s2)^{n-j}$, onde $s=\frac4{k(k+1)}$, que é menor que $(\frac34)^{\frac n{k(k+1)}}$ para $\frac n{k(k+1)}$ grande (de fato,
$\frac{C_n^{j+1}(\frac s2)^{j+1}(1-\frac s2)^{n-j-1}}{C_n^j(\frac s2)^j(1-\frac s2)^{n-j}}= \frac{n-j}{j+1}\cdot \frac s{2-s} < \frac{4-3s}{3s}\cdot \frac s{2-s}=\frac{4-3s}{6-3s} < \frac 23$, se $j\ge\frac{3sn}4$, logo, como $\sum_{j=0}^n C_n^j (\frac s2)^j (1-\frac s2)^{n-j}=1$, para $j=\frac{3sn}4$, $C_n^j(\frac s2)^j(1-\frac s2)^{n-j}\le 1$, donde $C_n^{sn}(\frac s2)^{sn}(1-\frac s2)^{(1-s)n}\le (\frac23)^{sn/4}$ e $\sum_{j=sn}^n C_n^j(\frac s2)^j(1-\frac s2)^{n-j}\le (\frac 23)^{sn/4}\sum_{k=0}^\infty (\frac 23)^k=3 (\frac 23)^{sn/4}= 3 (\frac 23)^{n/k(k+1)}< (\frac 34)^{n/k(k+1)}$, se $n/k(k+1)$ é suficientemente grande).
 A probabilidade disso acontecer pra algum $k<[ \sqrt[\uproot{2} 3]{n}]$ é no máximo $\sqrt[\uproot{2} 3]{n}  \cdot (\frac34)^{\sqrt[\uproot{2} 3]{n}}$, que converge a zero quando $n\to+\infty$. Por outro lado, com probabilidade total, $a_n<n^2 $ para todo $n$ suficientemente grande $\Rightarrow q_n<\prod_{k=1}^n(a_k+1)<\left( \prod_{r=1}^{\sqrt[\uproot{2} 3]{n}} (r+1) ^{\frac{4n}{r(r+1)}} \right) \cdot (n^2)^{4n/ \sqrt[\uproot{2} 3]{n}}$ com probabilidade total para todo $n$ grande, pois também com probabilidade total o número de termos maiores ou iguais a $\sqrt[\uproot{2} 3]{n}$ entre $a_1,a_2,\dots,a_n$ é no máximo $4n/\sqrt[\uproot{2} 3]{n}$, para $n$ suficientemente grande. 

Como $\lim\limits_{n\to\infty} 8\log n/\sqrt[\uproot{2} 3]{n}=0$, temos com probabilidade total 
$$
\limsup_{n\to\infty} \sqrt[\uproot{2} n]{q_n} \le \exp \left( \sum_{r=1}^\infty \frac{4\log(r+1)}{r(r+1)} \right)< +\infty.
$$
\qed

\bigskip

\noindent
{\bf Observação:} Pode-se provar com métodos de teoria ergódica que para quase todo $\al\in\re$ vale
$$
\lim_{n\to\infty }\sqrt[\uproot{2} n]{q_n} = e^{\pi^2/12\,ln\, 2} \simeq 3,2758229\dots
$$
Pretendemos discutir este e outros resultados finos ligados a propriedade estatísticas de frações contínuas num próximo artigo.

\bigskip

\noindent
{\bf Corolários do Teorema de Khintchine:}

\begin{itemize}

\item[i)] Para quase todo $\al\in\re$, $|\al-\frac pq|<\frac1{q^2\log^2q}$ tem
apenas um número finito de soluções $\frac pq\in\Q$, e portanto
 $|\al-\frac pq|<\frac1{q^{2+\ve}}$ tem apenas um número finito de soluções racionais $\frac pq$, para todo $\ve>0$. Em particular $\text{ord } \al=2$ para quase todo $\al\in\re$ (onde $\text{ord }\al:=\inf\{\nu>0 | |\al-\frac pq | < \frac 1{q^\nu}$ tem infinitas soluções $\frac pq\in\Q\}$).

\item[ii)] Para quase todo $\al\in\re$, $|\al-\frac pq|<\frac1{q^2\log q}$ tem infinitas soluções racionais $p/q$, e portanto, para todo $k\in\re$, $|\al-\frac pq|<\frac 1{kq^2}$ tem infinitas soluções $\frac pq\in \Q$.

\end{itemize}

\section{O Teorema de Khintchine $n$-dimensional} 

{\nobf Teorema 2.1:} Sejam $f_1,f_2,\dots,f_n\colon\na\to\re^+$ funções decrescentes e $F\colon\na\to\re^+$ dada por $F(k)=f_1(k)f_2(k)\dots f_n(k)$. Seja $\al=(\al_1,\dots,\al_2,\dots,\al_n)\in\re^n$. O sistema de aproximação simultâneas
$$
|\al-\frac{p_i}q|<\frac{f_i(q)}q,\quad 1\le i\le n\text{ é tal que } \eqno{(*)}
$$

\begin{itemize}

\item[a)] Se $\sum_{q=1}^\infty F(q)<+\infty$ então (*) tem apenas um número finito de soluções $\left(\frac{p_1}q, \frac{p_2}q,\dots,\frac{p_n}q\right)\in\Q^n$, para quase todo $\al\in\re^n$

\item[b)] Se $\sum_{q=1}^\infty F(q)=+\infty$ então (*) tem infinitas soluções $\left( \frac{p_1}q,\dots,\frac{p_n}q \right) \in \Q^n$ para quase todo $\al\in\re^n$.

\end{itemize}

\bigskip

\noindent
{\bf Dem:} 

\noindent
{\bf Dem. de a):} Dado $q_0\in\na$, consideremos o conjunto
$$
S(q_0)=\bigcup_{q\ge q_0} \bigcup_{0\le p_1,\dots,p_n<q} \prod_{i=1}^n \left( \frac{p_i}q - \frac{f_i(q)}q, \frac{p_i}q+ \frac{f_i(q)}q \right),
$$
que é o conjunto dos $\al\in [0,1)^n$ tais que a desigualdade (*) do enunciado do Teorema tem alguma solução com $q\ge q_0$ (e logo $\bigcap_{q_0\in\na}S(q_0)$ é o conjunto dos $\al\in\re^n$ tais que (*) tem infinitas soluções $(\frac{p_i}q,\dots,\frac{p_n}q) \in \Q^n$). Temos $m(S(q_0))\le \sum_{q=q_0}^\infty q^n (\frac{2^n F(q)}{q^n})=2^n \sum_{q=q_0}^\infty F(q)$, que tende a $0$ quando $q$ tende a $\infty$, pois $\sum_{q=1}^\infty F(q)$ converge. Portanto, $m(\bigcap_{q_0\in\na}S(q_0))=0$.

\bigskip

\noindent
{\bf Dem. de b):} Primeiro obtemos funções decrescentes $g_1,g_2,\dots,g_n\colon\na\to\re^+$ tais que $\lim\limits_{q\to s_0}\frac{g_i(q)}{f_i(q)}=0$ e $G=g_1,g_2,\dots,g_n\colon\na\to\re^+$ satisfaz $\lim\limits_{q\to\infty} q G(q)=0$ e $\sum_{q=1}^\infty G(q)=+\infty$ (podemos tomar $G_1(k)=(F(1)+F(2)+\dots+F(k))^{-1}\cdot F(k)$ e $G(k)=(G_1(1)+G_1(2)+\dots+G_1(k))^{-1}G_1(k)$, $\forall\, k\in\na$. Teremos $G_1$ e $G$ decrescentes, $G_1(k)\le 1/k$, $kG(k)\to0$, 
$\Sigma G_1(k)=\infty$, $\Sigma G(k)=\infty$, e definimos $g_i(q)=f_i(q)\cdot(G(q)/F(q))^{1/n})$.

Fixemos agora $q_0\in\na$ grande e definimos $s_0=s_0(q_0)=\min\{s\in\na | G(q_0)+G(q_0+1)+\dots+G(s)\ge \tilde c\}$, onde $\tilde c$ é uma constante que escolheremos posteriormente. Note que $\lim_{q\to\infty} \frac{s_0(q)}q=+\infty$.

Para cada $s$ com $q_0\le s\le s_0$ vamos estimar o número de $\left( \frac{r_1}s, \frac{r_2}s,\dots,\frac{r_n}s\right) \in \Q^n$ com $r_i\in\Z$, $1\le i\le n$, $0\le r_i<s$ tais que existem $q$ com $q_0\le q<s$, $p_1,p_2,\dots,p_n\in\Z$, $0\le p_i<q$ satisfazendo
$$
|\frac{r_i}s-\frac{p_i}q|<\frac{g_i(q)}q+\frac{g_i(s)}s,\quad \forall\,\, i=1,2,\dots,n.\eqno{(**)}
$$
Temos que, como cada $g_i$ é decrescente, (**) implica 
$$
|r_iq-p_is|<2qs\frac{g_i(q)}q=2sg_i(q),\quad i=1,2,\dots,n.
$$
Para um tal  $\left(\frac{r_1}{s},\dots,\frac{r_n}s\right)$ que não satisfaz (**) para nenhum $q$ com $q_0\le q<s$, $p_1,\dots,p_n$ o bloco $\prod_{i=1}^n\left(\frac{r_i}s-\frac{g_i(s)}s, \frac{r_i}s+\frac{g_i(s)}s \right)$ será disjunto de todos os blocos associados a $\left(\frac{p_1}q,\dots,\frac{p_n}q\right)$, $\forall\, q$ com $q_0\le q<s$, $\forall\, p_1,\dots,p_n\in\Z$ com $0\le p_i<q$.

\bigskip

\noindent
{\bf Lema 2.2:} Para todo $k\in\na$ existe $c_k>0$ tal que $\sum_{j=1}^n\left(\frac{\vr(j)}j \right)^k\ge c_k n$.

\bigskip

\noindent
{\bf Dem:} Para $k=1$ segue de 
\begin{align*}
\lim\limits_{n\to\infty}\frac 1n \sum_{j=1}^n \frac{\vr(j)}j &=
\lim\limits_{n\to\infty}\frac1n \sum_{q=1}^n \sum_{d|q} \frac{\mu(d)}d \\
&=\lim\limits_{n\to\infty}\frac 1n \sum_{d=1}^n \lceil \frac nd \rceil \frac{\mu(d)}d \\
&= \sum_{d=1}^\infty \frac{\mu(d)}{d^2} \\
& = \frac{6}{\pi^2}
\end{align*}
 pois $\sum_{r=1}^\infty \frac{\mu(m)}{m^2} \sum_{k=1}^\infty \frac 1{k^2}=$ $\sum_{n=1}^\infty \frac{\sum_{m|n}\mu(m)}{n^2}=1$, e $\sum_{k=1}^\infty \frac 1{k^2}=\frac{\pi^2}6$. Como $h(x)=x^k$ é convexa para $k\ge1$, temos
$\frac1n\sum_{j=1}^n \left(\frac{\vr(j)}j \right)^k \ge \left(\frac 1n\sum_{j=1}^n \frac{\vr(j)}j \right)^k$, donde segue o resultado (com $C_k=\left(\frac6{\pi^2}\right)^k$). \qed

Se $q_0\le q<s$,  o número de soluções de $|r_iq-p_is|<2sg_i(q)$ com $0\le p_i<q$, $0\le r_i<s$ é no máximo $4sg_i(q)$ desde que $\text{mdc}(r_i,s)=1$. De fato,  nessas condições $r_iq-p_is$ não se anula, senão teríamos $\frac{p_i}{q}=\frac{r_i}{s}$, que é uma fração irredutível de denominador $s>q$, absurdo. Seja $d=\text{mdc}(s,q)$. Dado $k\in \mathbb Z$, a equação diofantina $rq-ps=k$ só tem solução de $d|k$, quando tem $d$ soluções com $0\le r<s$. Portanto, $0<rq-ps<x$ (resp. $-x<rq-ps<0)$ tem no máximo $d\lfloor\frac{x}{d} \rfloor\le x$ soluções $(p,r)$ com $0\le r<s$, o que claramente implica a afirmação. Portanto, o número de soluções da desigualdade acima para todo $i$ com  $1\le i\le n$ é no máximo $4^ns^n G(q)$. Por outro lado há $\vr(s)^n$ pontos $\left(\frac{r_i}{s},\dots,\frac{r_n}s \right)$, $0\le r_i<s$, $\text{mdc}(r_i,s)=1$, $1\le i \le n$. Isso nos dá a estimativa do número de novos blocos disjuntos dos anteriormente considerados que têm denominador $s$ de pelo menos $\vr(s)^n-4^ns^n \sum_{q=q_0}^{s-1}G(q)$, e para o volume da união dos blocos disjuntos adicionados até o denominador $s_0$ de pelo menos
\begin{align*}
\, & \sum_{s=q_0}^{s_0}(\vr(s)^n-4^ns^n\sum_{q=q_0}^{s-1}G(q)) \frac{2^nG(s)}{s^n}\\
& = 2^k \sum_{s=q_0}^{s_0} \left(\frac{\vr(s)}s \right)^n G(s)-8^n \sum_{s=q_0}^{s_0} \left(\sum_{q=q_0}^{s-1}G(q) \right)G(s).
\end{align*}
Por outro lado, com $s_0=\min\{s\ge q_o | \sum_{q=q_0}^s G(q)\ge\tilde c\}$, temos
\begin{align*}
\sum_{s=q_0}^{s_0} \left( \frac{\vr(s)}s \right)^nG(s) &= \sum_{s=q_0}^{s_0-1}(G(s)-G(s+1)) \sum_{j=q_0}^s \left(\frac{\vr(j)}j\right)^n +G(s_0) \sum_{j=q_0}^{s_0} \left(\frac{\vr(j)}j \right)^n \\
&\ge \sum_{s=q_0}^{s_0-1}(G(s)-G(s+1))(c_ns-q_0)+G(s_0)(c_ns_0-q_0) \\
&= c_n \sum_{s=q_0+1}^{s_0}G(s)-(1-c_n)q_0G(q_0) \\
&= c_n\tilde c+\ve_1 \quad\text{ onde $\ve_1\to0$ quando $q_0\to\infty$}
\end{align*}
(pois $\lim\limits_{q_0\to\infty} q_0G(q_0)=0)$.

Por outro lado, $8^n\sum_{s=q_0}^{s_0} \left(\sum_{q=q_0}^{s-1}G(q) \right)G(s) \le
8^n\tilde c\sum_{s=q_0}^{s_0}G(s)\le 8^n \tilde c(\tilde c+\ve_2)$ onde $\ve_2=G(s_0)\to0$ quando $q_0\to\infty$. Assim, nosso volume é, pelo menos, $2^n(c_n\tilde c+\ve_1)-8^n\tilde c(\tilde c+\ve_2)$. Tomando $\tilde c=\frac{c_n}{4^{n+1}}$ temos que, se $q_0$ é suficientemente grande (e logo $\ve_1$ e $\ve_2$ suficientemente pequenos), o volume de $A(q_0)$ é pelo menos $c_n^2/2^{n+3}$, onde
$$
A(q_0)=\bigcup_{q\ge q_0} \bigcup_{0\le p_1,\dots,p_n<q} \prod_{i=1}^n \left( \frac{p_i}q - \frac{g_i(q)}q, \frac{p_i}q+ \frac{g_i(q)}q \right).
$$

Como $A(q)\supset A(q+1)$, $\forall\, q\in\na$, temos $m(A_\infty)\ge \frac1{15\cdot 2^n}>0$, onde $A_\infty=\bigcap_{q\in\na} A(q)$. Se $\be=(\be_1,\be_2,\dots,\be_n)\in A_\infty$, $|\be_i-\frac{p_i}q|<\frac{g_i(q)}q$, $i=1,2,\dots,n$ tem infinitas soluções $(\frac{p_1}q,\frac{p_1}q,\dots,\frac{p_n}q)\in\Q^n$. Como $m(A_\infty)>0$, dado $\ve>0$ existe cubo $Q=\prod_{i=1}^n [\frac{b_i}C,\frac{b_i+1}C]$, $C\in\na$, $b_i\in\Z$, $0\le b_i<C$ tal que $m(A_\infty\cap Q)\ge(1-\ve)m(Q)$. Se $T\colon\re^n\to\re^n$ é dada por $$
T(X_1,\dots,X_n)=(CX_1-b_1,CX_2-b_2,\dots,CX_n-b_n),
$$
 temos $T(Q)=[0,1]^n$ e $m(T(Q\cap A_\infty))\ge1-\ve$. Além disso, se $\al=(\al_1,\al_2,\dots,\al_n)\in T(Q\cap A_\infty)$, $\al=T(\be)$, $\be=(\be_1,\dots,\be_n)\in A_\infty\cap Q$, e portanto $|\be_i-\frac{p_i}q|<\frac{g_i(q)}q$, para todo $i=1,2,\dots,n$ tem infinitas soluções $(\frac{p_1}{q}, \frac{p_2}q,\dots,\frac{p_n}q)\in\Q^n$, donde $|\al_i-\frac{r_i}q|<\frac{Cg_i(q)}q$ (e logo $|\al_i-\frac{r_i}q|<\frac{f_i(q)}q$) tem infinitas soluções
$$
\left( \frac{r_1}q, \frac{r_2}q,\dots,\frac{r_n}q \right) = \left( \frac{Cp_1-b_1}q, \frac{Cp_1-b_2}q,\dots,\frac{Cp_n-b_n}q \right)\in \Q^n,
$$
e como $\ve>0$ pode ser feito arbitrariamente pequeno está provado o item b). \qed

\newpage

\noindent
{\Large\bf Apêndice:}\,\, {\bf Aproximações diofantinas não-homogêneas}

\vskip .3in

\noindent
{\bf Proposição A.1:} Se $\al\in\re\setminus\Q$ então $X=\{m+n\al | m, n\in\Z\}$ é denso em $\re$.

\medskip

\noindent
{\bf Dem:} Dado $\ve>0$ existem $p,q$ inteiros com $>1/\ve$ tais que $|\al-\frac pq|<\frac1{q^2}\Rightarrow 0 <|q\al-p|<\frac 1q <\ve$. Dado $x\in\re$ existe $k\in\Z$ tal que $x$ está entre $k(q\al-p)$ e $(k+1)(q\al-p)$, donde $|x-k(q\al-p)|\le\ve$. Como $k(q\al-p)=-pk+qk\al\in X$, o resultado está provado. \qed

\bigskip

O próximo resultado, devido a Kronecker, estende a Proposição A.1 para dimensão qualquer.

\medskip

\noindent
{\bf Proposição A.2:} Seja $\al=(\al_1,\al_2,\dots,\al_n)\in\re^n$. Suponha que $1,\al_1,\dots,\al_n$ sejam linearmente inependentes sobre $\Q$ (isto é, $k+m_1\al_1+m_2\al_2+\dots+m_n\al_n=0$ com $k,m_1,\dots,m_n\in\Z$ implica $k=m_1=\dots=m_n=0)$. Então $X=\{k\al+m_1e_1+m_2e_2+\dots+m_n e_n | k, \, m_1,\dots,m_n\in\Z\}$ é denso em $\re^n$, onde $e_1=(1,0,\dots,0),\dots, e_n=(0,\dots,0,1)$ são os elementos da base canônica de $\re^n$.

\medskip

\noindent
{\bf Dem:} Seja $\ov X\subset\re^n$ o fecho de $X$, e $V\subset \ov X$ um subespaço vetorial maximal de $\re^n$ contido em $\ov X$. Suponhamos por absudo que $V\ne\re^n$. Seja $f$ um funcional linear não nulo de $\re^n$.

Seja $V^\perp$ o complemento ortogonal de $V$, e seja $\pi\colon \re^n\to V^\perp$ a projeção ortogonal sobre $V^\perp$. Para todo $x\in\ov X$, $\pi(x)\in\ov X$, pois $\pi(x)=x+(\pi(x)-x)$, $\pi(x)-x\in C\subset\ov X$ e $\ov X$ é invariante por adição (pois $X$ também é).

Seja $k=\dim V^\perp$. Escolhemos vetores $e_{i_1},e_{i_2},\dots,e_{i_k}$ tais que $\pi(e_{i_1}), \pi(e_{i_2}),\dots,\pi(e_{i_k})$ geram $V^\perp$. Se fizermos $e_0=\al$, para todo $i=0,1,\dots,n$ escrevemos $\pi(e_i)=\sum_{j=1}^k \la_{ij}\pi(e_{i_j})$. Não podemos ter $\la_{i1}\in\Q$ para todo $i$, senão podemos definir um funcional linear $f$ da seguinte forma:
dado $x\in\re^n$ escrevemos $\pi(x)$ como $\sum_{j=1}^k\be_j\pi(e_{i_j})$, e tomamos $f(x)=\be_1$. Se $\la_{i1}=f(e_i)\in\Q$ para todo $i$, teríamos $\la_{01}=f(\al)=\sum_{i=1}^n\al_i f(e_i)=\sum_{i=1}^n \la_{i1}\al_i\in\Q$, contradizendo a hipótese da proposição.

Seja então $i_0$ tal que $\la_{i_01}\notin\Q$. Tomamos $\ga=(\la_{i_01},\dots,\la_{i_0k})\in\re^k$. Como observamos na introdução deste artigo, existem $x_n=q_n\ga-(p_{1n},p_{2n},\dots,p_{kn})\ne0$, com $q_n,p_{1n},\dots,p_{kn}\in\Z$ e $\lim\limits_{n\to\infty}|x_n|\le\lim\limits_{n\to\infty}|q_n|^{-1/k}=0$, e portanto, se $w_n=q_n\pi(e_{i_0)}-\sum_{j=1}^kp_{jn}\pi(e_{i_j})$, $\lim\limits_{n\to\infty}w_n=0$ (e $w_n\ne0$, $\forall\, n$). Passando a uma subseqüência, se necessário, podemos supor que $\lim\limits_{n\to\infty}\frac{w_n}{|w_n|}=\tilde w\in S^{n-1}\cap V^\perp$. Para todo $t\in\re$, temos que $t\tilde w=\lim\limits_{n\to\infty} \lfloor \frac t{w_n} \rfloor w_n\in\ov X$, $\forall\, n\in\na$. Portanto, como $\ov X$ é invariante por adição, o subespaço $\tilde V=\{v+t\tilde w | v\in V,\,\, t\in\re\}$ é tal que $\tilde V\subset \ov X$ e $\tilde V$ contém propriamente $V$, absurdo. \qed

\bigskip

\noindent
{\bf Observação:} A hipótese da Proposição A.2 é necessária, pois se existem inteiros $k,m_1,\dots,m_n$ não todos nulos tais que $k+m_1\al_1+\dots+m_n\al_n=0$ então $\ov X\subset\{(x_1,\dots,x_n)\in\re^n | m_1x_1+m_2x_2+\dots+m_nx_n\in\Z\}$, que é um fechado com interior vazio.

Deixamos para o leitor a prova do seguinte fato: Dado $\al=(\al_1,\dots,\al_n)\in\re^n$ satisfazendo a condição da Proposição 2, e $m\in\na$, definimos $\{m\al\}=(m\al_1-\lfloor m\al_1\rfloor,\dots,m\al_n-\lfloor m\al_n\rfloor)\in[0,1)^n$. A seqüência $\{m\al\}$ é uniformemente distribuida, isto é, para todo aberto $A\subset[0,1)^n$, se $f_A(k)=\#\{m\le k | \{m\al\}\in A\}$, então $\lim\limits_{k\to\infty}f_A(k)/k=m(A)$, onde $m(A)$ é a medida de Lebesgue de $A$. 
({\it Su\-ges\-tão\/}: sejam $C_1,C_2\subset[0,1)^n$ dois cubos abertos tais que $\ov C_2$ está contido em um transladado de $C_1$ $(\ov C_2\subset C_1+v,\,\, v\in\re^n)$. Use o fato de que existem vetores $\tilde v$ arbitrariamente próximos de $v$, com $\tilde v=(q\al_1+p_1,\dots,q\al_n+p_n)$, $q,p_1,\dots,p_n\in\Z$, e que $\{m\al\}\in C_2\Rightarrow\{(m-q)\al\}\in C_2-\tilde v\subset C_1$, se $\tilde v$ está suficientemente próximo de $v$, donde $f_{C_2}(k)\le f_{C_1}(k)+|q|\Rightarrow\limsup\limits_{k\to
\infty}f_{C_2}(k)/k\le \liminf\limits_{k\to\infty} f_{C_1}(k)/k)$.

\newpage

\setcounter{section}{0}

\centerline{\bf CAP\'ITULO 5}

\vglue .5in

\centerline{\Large\bf Os Espectros de Markov e Lagrange}

\vskip .5in

\section{Defini\c c\~oes e enunciados}

Seja $\al$ um n\'umero irracional. De acordo com o teorema de Dirichlet, a desigualdade $\lv\al - \dfrac pq\rv < \dfrac{1}{q^2}$ tem uma infinidade de solu\c c\~oes racionais $p/q$. Markov e Hurwitz melhoraram este resultado, provando que, para todo irracional $\al$, a desigualdade $\lv\al-\dfrac pq\rv < \dfrac{1}{\sqrt 5\cdot q^2}$ tem uma infinidade de solu\c c\~oes racionais, e que $\sqrt 5$ \'e a melhor constante com esta propriedade: para $\al = \dfrac{1+\sqrt 5}{2}$\,, e para qualquer $\ve > 0$, a desigualdade $\lv\al - \dfrac pq\rv < \dfrac{1}{(\sqrt 5+\ve)q^2}$ tem apenas um n\'umero finito de solu\c c\~oes (ver ap\^endice). Entretanto, fixado $\al$ irracional, pode-se esperar resultados melhores, o que nos leva a associar a cada $\al$ a sua constante de melhor aproxima\c c\~ao $k(\al) = \sup\{k > 0 \mid \lv\al-\dfrac pq\rv < \dfrac{1}{kq^2}$ tem uma infinidade de solu\c c\~oes racionais $p/q\} =  \limsup_{p,q\in\bz}\big(|q(q\al-p)|^{-1}) \in \re \cup \{+\infty\}$. Nossa discuss\~ao inicial mostra que $k(\al) \ge \sqrt 5$ para todo $\al \in \re$, e $k\bigg(\dfrac{1+\sqrt 5}{2}\bigg) = \sqrt 5$. N\~ao \'e dif\'\i cil provar que $k(\al) = +\infty$ para quase todo $\al \in \re$. Estaremos interessados nos $\al \in \re$ tais que $k(\al) < +\infty$, e, mais particularmente, na imagem da fun\c c\~ao $k$, isto \'e, no conjunto $L = \{k(\al) \mid \al \in \re\backslash \bz \text{ e } k(\al) < +\infty\}$. Este conjunto \'e conhecido como o {\it espectro de Lagrange}.

Provamos no ap\^endice uma f\'ormula para $k(\al)$: escrevemos $\al$ em fra\c c\~ao cont\'\i nua, $\al = [a_0,a_1,a_2,\dots]$ e definimos, para $n\in\na$,\quad $\al_n = [a_n, a_{n+1},a_{n+2},\dots]$ e\linebreak $\be_n = [0, a_{n-1},a_{n-2},\dots]$. Temos ent\~ao $k(\al) =  \limsup_{n\to\infty}\,(\al_n+\be_n)$. Isto segue dos resultados do Capítulo 3.

\'E interessante observar que se mud\'assemos um pouco as fun\c c\~oes envolvidas na defini\c c\~ao do espectro de Lagrange ele seria um conjunto bastante trivial: se para\linebreak $f\colon \re \to \re_+$ conside\-rarmos o conjunto $k_f(\al) := \sup\big\{k > 0 \mid |\al - \dfrac pq| < \dfrac{f(q)}{k}$ tem infinitas solu\c c\~oes racionais $p/q\big\}$ ent\~ao, caso tenhamos $ \lim_{q\to+\infty} q^2\,f(q)=0$ ent\~ao a imagem de $k_f$ seria $(0,+\infty]$ (ou $[0,+\infty]$, se consideramos $\sup(\emptyset)=0$ neste contexto) e, caso $ \lim_{q\to+\infty} q^2\,f(q)=+\infty$, ent\~ao a imagem de $k_f$ seria $\{+\infty\}$.

O conjunto $L$ encodifica uma s\'erie de propriedades diofantinas de n\'umeros reais, e vem sendo estudado h\'a bastante tempo. Talvez o primeiro resultado n\~ao-trivial sobre ele se deva a Markov, que provou em 1879 (ver [Ma]) que $L \cap (-\infty, 3) = \{k_1=\sqrt 5 < k_2 = 2\sqrt 2 < k_3 = \dfrac{\sqrt{221}}{5} <\cdots\}$, onde $(k_n)$ \'e uma seq\"u\^encia convergente a 3 tal que $k_n^2 \in \bq$ para todo $n$. Assim, o ``come\c co'' do espectro de Lagrange \'e discreto. Essa afirma\c c\~ao n\~ao \'e verdadeira para todo o conjunto $L$. Marshall Hall prova em 1947 ([H]) que $L$ cont\'em toda uma semi-reta (por exemplo $[6, +\infty)$), e G. Freiman determinou em 1975 a maior semi-reta que est\'a contida em $L$, que \'e $\bigg[4 + \dfrac{253589820 + 283748\sqrt{462}}{491993569}\,, +\infty\bigg)$. Estes dois \'ultimos resulados baseam-se fortemente no estudo de somas de conjuntos de Cantor regulares, cuja rela\c c\~ao com o espectro de Lagrange tem origem na f\'ormula que apresentamos para $k(\al)$, e \'e o tema principal deste cap\'\i tulo. Por exemplo, o resultado que M. Hall enuncia em seu artigo [H] \'e o seguinte: se $C(4)$ \'e o conjunto de Cantor regular dos reais de $[0,1]$ em cuja fra\c c\~ao cont\'\i nua aparecem apenas os coeficientes 1, 2, 3 e 4 ent\~ao $C(4)+C(4) = [\sqrt2 - 1, 4(\sqrt 2 - 1)]$, do qual n\~ao \'e dif\'\i cil deduzir que $L \supset [6,+\infty)$ via a f\'ormula para $k(\al)$.

De $k(\al) =  \limsup_{n\to\infty}\,(\al_n+\be_n)$ podemos obter a seguinte caracteriza\c c\~ao do espectro de Lagrange: seja $\Sigma = \big(\na^*\big)^{\na}$, o conjunto das seq\"u\^encias bi-infinitas de inteiros positivos, e $\sigma\colon \Sigma \to \Sigma$ o shift definido por $\sigma((a_n)\_{n\in\bz}) = (a_{n+1})\_{n\in\bz}$. Se $f\colon \Sigma \to \re$ \'e definida por $f((a_n)\_{n\in\bz}) = \al_0+\be_0 = [a_0,a_1,a_2,\dots] + [0;a_{-1},a_{-2},\dots]$ ent\~ao $L = \{ \limsup_{n\to+\infty}\,f(\sigma^n\und\te), \und\te \in \Sigma\}$. Outro conjunto de n\'umeros reais que ser\'a de nosso interesse \'e o {\it espectro de Markov\/} $M$, que \'e igual a $\{ \sup_{n\to\infty}\,f(\sigma^n\und\te), \und\te \in \Sigma\}$. O espectro de Markov tem a seguinte interpreta\c c\~ao aritm\'etica: $M = \{( \inf_{(x,y)\in\bz^2\backslash(0,0)} |f(x,y)|)^{-1}$;  $f(x,y) = ax^2 + bxy + cy^2,\,\, b^2-4ac=1\}$. S\~ao fatos conhecidos que $L$ e $M$ s\~ao subconjuntos fechados da reta e que $L \subset M$. Provamos em [M2] os seguintes resultados, que pretendemos discutir neste cap\'\i tulo:

\vglue .2in

\noindent
{\bf Teorema 1.1:} Para todo $t\in\re$, as dimens\~oes de Hausdorff de $L \cap (-\infty, t)$ e de $M \cap (-\infty, t)$ s\~ao iguais. Se denotarmos essas dimens\~oes por $d(t)$, temos os seguintes fatos:

\begin{itemize}

\item[{i)}]\quad $d\colon \re \to [0,1]$ \'e cont\'\i nua e sobrejetiva.
\item[{ii)}]\quad $d(t) = \min\{1,2\cdot HD(k^{-1}(-\infty,t))\}$
\item[{iii)}]\quad $\max\{t \in \re \mid d(t) = 0\} = 3$
\item[{iv)}]\quad $d(\sqrt{12}) = 1$

\end{itemize}

(As afirma\c c\~oes iii) e iv) s\~ao conseq\"u\^encias simples de ii)).

\vglue .2in

\noindent
{\bf Teorema 1.2:} O conjunto dos pontos de acumula\c c\~ao de $L$ \'e perfeito, isto \'e, $L'= L''$.

\vglue .2in

\noindent
{\bf Teorema 1.3:}\,\,  $0 < HD(M\backslash L) < 1$.

Estes teoremas s\~ao baseados na id\'eia de aproximar partes de $M$ e de $L$ por dentro e por fora por somas de conjuntos de Cantor regulares de dimens\~oes pr\'oximas. A prova do Teorema 1.1 depende de modo essencial de um resultado sobre dimens\~oes de Hausdorff de somas aritm\'eticas de conjuntos de Cantor regulares, que ser\'a discutido na pr\'oxima se\c c\~ao, e cuja prova depende do lema de recorr\^encia de escala de [MY].


\section{Dimens\~oes de Hausdorff e somas aritm\'eticas de conjuntos de Cantor de fra\c c\~oes cont\'\i nuas}


Vimos no cap\'\i tulo anterior que, se $K_1$ e $K_2$ s\~ao conjuntos de Cantor $C^2$ que satisfazem as hip\'oteses do lema de recorr\^encia de escalas, ent\~ao vale a f\'ormula $HD(K_1+K_2) = \min\{1, HD(K_1) + HD(K_2)\}$.

Iremos aplicar este resultado a conjuntos de Cantor regulares definidos por restri\c c\~oes da fun\c c\~ao de Gauss $g\colon (0,1] \to (0,1]$ definida por $g(x) = \dfrac 1x - \lfloor \dfrac 1x\rfloor$ (cuja rela\c c\~ao com fra\c c\~oes contínuas \'e evidente) a determinados dom\'\i nios de Markov (que ser\~ao uni\~oes finitas de intervalos cujos extremos ser\~ao irracionalidades quadr\'aticas). Para isso, precisamos provar que tais conjuntos de Cantor satisfazem as hip\'oteses do lema de recorr\^encia de escalas, isto \'e, que n\~ao s\~ao essencialmente afins.

Observemos inicialmente que qualquer conjunto de Cantor regular de Gauss (nome que atribuiremos aos conjuntos de Cantor descritos no par\'agrafo anterior) cont\'em um conjunto de Cantor {\it completo\/} de Gauss, nome que atribu\'\i mos ao seguinte tipo de conjunto de Cantor: A cada conjunto finito de seq\"u\^encias finitas de inteiros positivos $B$ associamos o conjunto $K(B) = \{[0; \be_1,\be_2,\dots] \mid \be_i \in B, \,\,\forall\,i\in\na\}$, que, excetuando os casos triviais onde $K(B)$ \'e um ponto, \'e um conjunto de Cantor regular completo de Gauss. Este fato pode ser provado do seguinte mod: tomamos duas palavras finitas admiss\'\i veis $\ga_1 = b_1b_2\dots b_nb_1$ e $\ga_2 = b_1 \tilde b_2 \tilde b_3 \dots \tilde b_m b_1$ come\c cando e terminado em $b_1$ que n\~ao sejam ambas c\'opias m\'ultiplas do mesmo bloco de s\'\i mbolos (aqui os s\'\i mbolos $b_i$ s\~ao inteiros positivos corespondentes a ramos $\dfrac 1x - b_i$ da fun\c c\~ao de Gauss $g$, que aparecem na constru\c c\~ao do Cantor regular de Gauss em quest\~ao $K$). Se $\tilde\ga_1 = b_1b_2\dots b_n$ e $\tilde\ga_2 = b_1 \tilde b_2 \dots \tilde b_m$ ent\~ao o Cantor completo de Gauss $K(\{\tilde\ga_1, \tilde\ga_2\})$ est\'a contido em $K$.

Basta provar agora que nenhum Cantor completo de Gauss \'e essencialmente afim. Observemos que $K(B)$ \'e definido por $\psi\colon  \bigcup_{\be\in B}\,I_\be \to I$, onde $I = [0,1]$ e, para cada $\be \in B$,\quad $I_\be = \{[0; \be,\al], \al \ge 1\}$ e $\psi_\be = \psi|_{I_\be}$ \'e o iterado de $g$ definido por $\psi_\be([0; \be,\al]) = 1/\al$.

Seja $x_\be = [0; \be,\be,\be,\dots]$ o ponto fixo de $\psi_\be$. Se $\be = (b_1,b_2,\dots,b_n)$ e $p_k/q_k = [0; b_1,b_2,\dots,b_k]$ s\~ao as reduzidas de $[0;\be]$, ent\~ao $\psi_\be(x) = \dfrac{q_{n-1}x-p_{n-1}}{p_n-q_nx}$\,, e os pontos fixos de $\psi_\be$ (estendido \`a reta pela sua f\'ormula) s\~ao as ra\'\i zes de $q_nx^2 + (q_{n-1} - p_n)x - p_{n-1} = 0$ (ver Se\c c\~ao 3 do Ap\^endice).

Existe um difeomorfismo $\al_\be\colon I \to I$ tal que $\al_\be(x_\be) = x_\be$\,\,\,\, $\al_\be'(x_\be) = 1$ e $\al_\be \circ \psi_\be \circ \al_\be^{-1}$ \'e afim. Al\'em disso, podemos tomar um tal $\al_\be$ da forma $\al_\be(x) = \dfrac{a_\be x+b_\be}{c_\be x+d_\be}$ (isto \'e um exerc\'\i cio sobre triangulariza\c c\~ao de matrizes...). N\~ao h\'a perda de generalidade em supor que $B$ cont\'em dois elementos $\be$ de $\ga$ do mesmo tamanho (i.e., com o mesmo n\'umero de s\'\i mbolos), pois, se n\~ao for esse o caso, podemos considerar etapas mais avan\c cada da constru\c c\~ao de $K(B)$ onde hja tais elementos. \'E suficiente agora mostrar que se $\al_\be \circ \al_\ve^{-1}$ \'e afim e $\ga$ tem o mesmo n\'umero de elementos que $\be$ ent\~ao $\ga=\be$, pois isso implicaria que $\al_\be \circ \psi_\ga \circ \al_\be^{-1}$ n\~ao \'e afim, donde \'e uma transforma\c c\~ao da forma $\dfrac{Ax+B}{Cx+D}$\,, cuja derivada segunda \'e zero apenas num conjunto finito, ou seja, $\al_\be \circ \psi \circ \al_\be^{-1}$ tem uma componente afim (a de $\psi_\be$), e outra componente cuja derivada segunda \'e n\~ao-nula em muitos pontos de $K(B)$ (a de $\psi_\ga$), o que implica que $K(B)$ n\~ao \'e essencialmente afim. Se $\al_\be \circ \psi_\ga \circ \al_\be^{-1}$ \'e afim ent\~ao $\infty$ \'e um ponto fixo comum de $\al_\be \circ \al_\be^{-1}$ e $\al_\be \circ \psi_\be \circ \al_\be^{-1}$\,, e portanto $\al_\be^{-1}(\infty)$ \'e ponto fixo comum de $\psi_\be(x) = \dfrac{q_{n-1}x-p_{n-1}}{p_n-q_nx}$ e $\psi_\ga = \dfrac{\tilde q_{n-1}x-\tilde p_{n-1}}{\tilde p_n - \tilde q_nx}$\,, donde \'e raiz comum dos polin\^omios $q_nx^2 + (q_{n-1}-p_n)x - p_{n-1}$ e $\tilde q_nx^2 + (\tilde q_{n-1}-\tilde p_n)x - \tilde p_{n-1}$\,, donde esses dois polin\^omios s\~ao iguais (pois s\~ao irredut\'\i veis em $\bz[x]$), donde suas outras ra\'\i zes coincidem, ou seja, $x_\be = x_\ga$ e portanto $\be=\ga$.

Provamos assim o seguinte resultado:

\vglue .2in

\noindent
{\bf Proposi\c c\~ao 2.1:} Se $K_1$ e $K_2$ s\~ao conjuntos de Cantor regulares de Gauss ent\~ao $HD(K_1+K_2) = \min\{1, HD(K_1)+HD(K_2)\}$. \qed

Outro fato importante na prova de nossos resultados sobre dimens\~oes de Hausdorff de partes dos espectros de Markov e Lagrange ser\'a discutido a seguir:

\vglue .2in

\noindent
{\bf Defini\c c\~ao 2.2:} Se $\be = (b_1,b_2,\dots,b_n)$ ent\~ao $\be^t = (b_n, b_{n-1},\dots,b_2,b_1)$, e se $B$ \'e um conjunto de seq\"u\^encias finitas ent\~ao $B^t = \{\be^t, \be \in B\}$.

Se $q_n(\be)$ \'e o denominador da fra\c c\~ao cont\'\i nua $[0;\be] = [0,b_1,\dots,b_n]$ ent\~ao $q_n(\be) = q_n(\be^t)$. Este \'e um fator j\'a conhecido por Euler, e uma boa refer\^encia sobre sua prova (que tamb\'em pode ser considerada como um exerc\'\i cio para o leitor) est\'a no ap\^endice 2 de [CF]. Como conseq\"u\^encia deste restulado e do fato de que os comprimentos dos intervalos da constru\c c\~ao de um conjunto de Cantor completo de Gauss dependerem essencialmente dos denominadores das fra\c c\~oes cont\'\i nuas finitas envolvidas, prova-se a seguinte

\vglue .2in

\noindent
{\bf Proposi\c c\~ao 2.3:}\quad $HD(K(B)) = HD(K(B^t))$ para todo conjunto finito $B$ de seq\"u\^encias finitas de inteiros positivos.\qquad\quad\qed

\vglue .2in

\noindent 
{\bf Corol\'ario 2.4:}\quad $HD(K(B)+K(B^t)) = \min\{1,2\cdot HD(K(B))\}$.\qquad\quad\qed

\section{Id\'eias das demonstra\c c\~oes dos resultados sobre os espectros}

Seja $\Sigma = \bz_+^{\bz}$,\,\,\, $\ell\colon \Sigma \to \re$ definida por $\ell(\und\te)  = \limsup_{n\to\infty}\, (\al_n+\be_n)$, onde, se $\und\te = (a_k)\_{k\in\bz}$ ent\~ao $\al_n = [a_n; a_{n+1},a_{n+2},\dots]$ e $\be_n = [0; a_{n-1},a_{n-2},\dots]$ e $m\colon \Sigma \to \re$ definida por $m(\und\te) =  \sup_{n\in\bz} (\al_n+\be_n)$. Ent\~ao, como observamos no in\'\i cio deste cap\'\i tulo, o espectro de Lagrange \'e o conjunto $L = \{\ell(\und\te), \und\te \in \Sigma\}$ e o espectro de Markov \'e o conjunto $M = \{m(\und\te), \und\te \in \Sigma\}$.

A prova dos resultados sobre a fun\c c\~ao $d(t)$ baseia-se, como mencionamos no in\'\i cio deste cap\'\i tulo, no fato de que podemos aproximar por dentro e por fora peda\c cos dos espectros de Markov e Lagrange por somas de conjuntos de Cantor regulares de Gauss com dimens\~oes de Hausdorff pr\'oximas (em geral essas somas ser\~ao do tipo $K(B)+K(B^t)$, e usaremos a proposi\c c\~ao acima). A principal ferramenta que usaremos na constru\c c\~ao de tais aproxima\c c\~oes ser\'a o seguinte lema t\'ecnico, cuja prova (assim como os detalhes da prova dos teoremas deste cap\'\i tulo) se encontra em [M2]:

\vglue .2in

\noindent
{\bf Lema 3.1:} Para cada $t > 0$ e $\ve > 0$, seja $\Sigma(t) = \{\und\te \in \Sigma \mid m(\und\te) \le t\}$, e seja $N_\ve(t)$ o n\'umero de seq\"u\^encias finitas $\al$ tais que o intervalo $I(\al) = \{x \in [0,1] \mid x = [0;\al,y],\,\,y \ge 1\}$ tem comprimento maior ou igual a $\ve$ e $\al$ aparece como subseq\"u\^encia de algum elemento de $\Sigma(t)$. Definimos $D(t) =  \lim_{\ve\to0} - \dfrac{\log N_\ve(t)}{\log \ve}$ (o limite existe pois existe $C > 0$ tal que $N_{\ve\delta}(t) \le C\,N_\ve(t)N_\delta(t)$,\,\,$\forall\,\ve,\delta > 0$). Ent\~ao, dado $\tau > 0$ existe $\delta > 0$ e um shift completo $\widetilde\Sigma \subset \Sigma(t-\delta)$ com $HD(\widetilde\Sigma_+, d) \ge D(t)-\tau$, onde $\Sigma_+ = \bz_+^{\bz}$\,,\,\,\, $\widetilde\Sigma_+ = \widetilde\Sigma \cap \Sigma_+$\,, e $d\colon \Sigma_+\times\Sigma_+ \to \re$ \'e a dist\^ancia definida por $d(\und\te, \und{\te}') = |I(\und\te \wedge \und{\te}')|$.\qquad\quad\qed

A id\'eia da prova de que $L'= L''$ \'e criar conjuntos de Cantor regulares de Gauss usando seq"u\^encias finits que aparecem infinitas vezes nas fra\c c\~oes cont\'inuas das preimagem por $k$ de uma seq\"u\^encia convergente de pontos de $L$. A imagem por $k$ do
Cantor de Gauss gerado por, digamos, duas seq\"u\^encias dessas fornecer\'a um conjunto de Cantor contido em $L$ pr\'oximo ao limiteda tal seq\"u\^encia. Aumentando o comprimento das seq\"u\^encias finitas consideradas obtemos o resultado.

Para estudar o complementar do espectro de Lagrange em rela\c c\~ao ao espectro de Markov, primeiro mostramos que $M\backslash L$ cont\'em conjuntos de Cantor regulares pr\'oximos a \linebreak $\al_\infty = [2; \ov{1,1,2,2,2,1,2}] + [0;1,2,2,2,1,1,2,1,\ov 2] \cong 3,293044265\dots$, que Freiman provou ser um ponto de acumula\c c\~ao de $M\backslash L$ (ver Cap\'itulo 3 de [CF]) (as barras superiores indicam per\'\i odo nas fra\c c\~oes cont\'\i nuas pr\'e-peri\'odicas acima), com um argumento semelhante \`a prova de $L'= L''$. A prova de $HD(M\backslash L) < 1$ \'e mais t\'ecnica e delicada, e depende da an\'alise de restri\c c\~oes \`a seq\"u\^encias finitas que podem aparecer nas fra\c c\~oes cont\'\i nuas de elementos de conjuntos de Cantor cuja imagem por $k$ esteja contida em $M\backslash L$. Veja [M2] para detalhes.

\section{Espectros de Markov e Lagrange din\^amicos}

As caracteriza\c c\~oes em termos de shift $\Sigma$ e das fun\c c\~oes $\ell$ e $m$ dos espectros de Markov e Lagrange admitem uma generaliza\c c\~ao natural no contexto de din\^amica hiperb\'olica: seja $\vr\colon M^2 \to M^2$ um difeomorfismo, $\La \subset M^2$ um conjunto hiperb\'olico para $\vr$ e $f\colon M^2 \to \re$ uma fun\c c\~ao real de classe $C^2$. Podemos definir espectros de Markov e Lagrange din\^amicos associados ao par $(f, \La)$ como segue: $L(f,\La) = \{ \limsup_{n\to+\infty} f(\vr^n(x)),  x \in \La\}$ e $M(f,\La) = \{ \sup_{n\in\bz} f(\vr^n(x)), x \in \La\}$. \'E poss\'\i vel provar de um modo an\'alogo ao que descrevemos neste cap\'itulo que para conjuntos abertos de $(f,\vr)$ (que cont\'em abertos densos de $\{(f,\vr) \mid \vr \text{ preserva \'area }\}$ a fun\c c\~ao $d(t) = d_{f,\La}(t) = HD(L(f,\La) \cap (-\infty,t))$ coincide com $HD(M(f,\La) \cap (-\infty,t))$, \'e cont\'\i nua e sua imagem \'e o intervalo $[0, \min\{1, HD(\La)\}]$. Genericamente, nesses casos, o ponto $t_1 = \inf\{t \in \re \mid d(t)=1\}$ pertence ao fecho do interior de $L(f,\La) \subset M(f,\La)$.

Vale notar que o resultado n\~ao \'e verdade em geral para $\vr$ dissipativo, pois h\'a conjuntos abertos de contraexemplos onde $d(t)$ tem um n\'umero finito de
descontinuidades, e sua imagem \'e uma uni\~ao finita de intervalos
n\~ao-degenerados.

As demonstra\c c\~oes desses \'ultimos resultados aparecer\~ao em [M3].

\newpage

\quad

\newpage

\noindent
{\Large\bf Apêndice:} \,\, {\bf  Conjuntos de Cantor Regulares e Dimensões Fractais}


\vskip .3in

\noindent
{\large\bf 1.0\quad Conjuntos de Cantor}

\vglue .1in

Normalmente as pessoas ouvem falar no ``Conjunto de Cantor'' antes de ouvir falar em ``conjuntos de Cantor'' em geral. O conjunto de Cantor \'e um engenhoso exemplo de um subconjunto da reta que \'e compacto, n\~ao-enumer\'avel e totalmente desconexo, que serve como fonte de exemplos interessantes em an\'alise e topologia. O Conjunto de Cantor, que denotaremos por $K$, pode ser definido de v\'arias maneiras. Por exemplo, $K$ \'e o conjunto de todos os n\'umeros do intervalo $[0,1]$ que podem ser escritos em base 3 utilizando apenas os algarismos 0 e 2, ou seja, $K = \bigg\{\sum\limits_{n-1}^\infty \dfrac{\sigma_n}{3^n}\,, \,\,\sigma_n \in \{0,2\},\,\, \forall\,n\in\na\bigg\}$. Outra maneira de descrever o conjunto $K$ \'e descrevendo explicitamente seu complementar: tomamos o intervalo $[0,1]$, retiramos seu ter\c co central $\bigg(\dfrac 13,\, \dfrac 23\bigg)$ e obtemos dois intervalos fechados: $\bigg[0, \dfrac 13\bigg]$ e $\bigg[\dfrac 23, 1\bigg]$. Retiramos os ter\c cos centrais desses intervalos e obtemos quatro intervalos fechados: $\bigg[0, \dfrac 19\bigg]$, $\bigg[\dfrac 29, \dfrac 13\bigg]$, $\bigg[\dfrac 23, \dfrac 79\bigg]$ e $\bigg[\dfrac 89, 1\bigg]$. Continuamos o processo, sempre retirando os ter\c cos centrais dos intervalos restantes. Os pontos do intervalo $[0,1]$ que n\~ao pertencem a nenhum dos intervalos retirados formam o conjunto de Cantor $K$. Notemos que, na $n$-\'esima etapa da constru\c c\~ao de $K$ sobram $2^n$ intervalos de comprimento $1/3^n$ cada, cuja uni\~ao cont\'em $K$. Isso implica que $K$ tem medida nula.

A terceira constru\c c\~ao do conjunto $K$ que mostraremos a seguir \'e de particular import\^ancia para n\'os, pois ser\'a generalizada para definir conjuntos de Cantor {\it regulares\/} ou dinamicamente definidos. Consideremos a fun\c c\~ao $\psi\colon \bigg[0, \dfrac 13\bigg] \cup \bigg[\dfrac 23, 1\bigg] \to [0,1]$ definida por $\psi(x) = \cases 3x \text{ se } \bigg[0,\dfrac 13\bigg]\\ 3x-2 \text{ se } x \in \bigg[\dfrac 23, 1\bigg]\endcases$. O dom\'\i nio da fun\c c\~ao $\psi$ \'e a primeira etapa da constru\c c\~ao anterior do conjunto $K$. Se denotarmos 

$\underbrace{\psi\circ\psi\circ\dots\circ\psi}_{n\text{ vezes}}$ por $\psi^n$, temos que $\psi^n$ n\~ao est\'a definida para todo $x$. Por exemplo, se $n=2$ e $x=0,2$, temos que $\psi(x) = 3x = 0,6$, que n\~ao pertence ao dom\'\i nio de $\psi$, donde $\psi^2(0,2)$ n\~ao est\'a definido. Podemos caracterizar o Conjunto de Cantor $K$ como o conjunto dos $x \in [0,1]$ tais que $\psi^n(x)$ est\'a definido para todo natural $n$, ou seja, $K = \bigcup_{n=0}^\infty \psi^{-n}([0,1])$. Podemos observar que $\psi^{-n}([0,1])$, ou seja, o dom\'\i nio de $\psi^n$ coincide com o conjunto obtido na $n$-\'esima etapa da constru\c c\~ao anterior.

$K$ \'e claramente compacto,  pois pela segunda constru\c c\~ao, por exemplo, seu complementar \'e aberto. Al\'em disso, $K$ \'e n\~ao-enumer\'avel, o que segue do fato de que a primeira constru\c c\~ao fornece uma bije\c c\~ao entre $K$ e $\{0,2\}^{\na}$, que de fato \'e um homeomorfismo, se dotarmos $\{0,2\}^\na$ da topologia produto.

Em geral dizemos que um conjunto de Cantor \'e um espa\c co topol\'ogico homeomorfo a $K$. Nosso principal interesse ser\'a nos conjuntos de Cantor contidos na reta real, que podem ser caracterizados como os compactos de interior vazio sem pontos isolados.

Em geral, espa\c cos m\'etricos (ou metriz\'aveis) compactos, totalmente desconexos (i.e., cujas componentes conexas s\~ao os pontos) e sem pontos isolados s\~ao conjuntos de Cantor (i.e., s\~ao homeomorfos a $K$). Deixamos a prova deste fato como exerc\'\i cio para o leitor. (Sugest\~ao: dado um conjunto como acima, tente decomp\^o-lo como uma uni\~ao disjunta de abertos e fechados com di\^ametro menor que a metade do di\^ametro original, repetir o processo e usar isso para reduzir o problema ao caso de subconjuntos da reta. no qual \'e poss\'\i vel construir homeomorfismos mon\'otonos razoavelmente expl\'\i citos).

\vglue .3in

\noindent{\large\bf 1.1\quad Conjuntos de Cantor regulares}

\vglue .1in

Mencionamos que a terceira constru\c c\~ao que exibimos para o conjunto $K$, que o 
ca\-rac\-te\-ri\-za como o maximal invariante pela fun\c c\~ao $\psi$ no intervalo $[0,1]$ \'e de particular interesse, pois caracteriza $K$ como um conjunto de Cantor dinamicamente definido. Vamos discutir informalmente algumas propriedades dos conjuntos de Cantor dinamicamente definidos, ou regulares (que ser\~ao nosso assunto principal) antes de defini-los mais precisamente. Uma propriedade fundamental do conjunto de Cantor $K$ \'e a sua {\it auto-semelhan\c ca}: pequenas partes de $K$ s\~ao c\'opias reduzidas de todo o conjunto $K$. De fato, dado $x \in K$ e $\ve > 0$ existe um subconjunto aberto e fechado de $K$ contendo $x$ e de di\^ametro menor que $\ve$ que \'e semelhante ao conjunto $K$ (por exemplo uma pe\c ca de uma etapa avan\c cada da constru\c c\~ao de $K$ que contenha o ponto $x$). Esta semelhan\c ca ser\'a dada por um certo iterado da fun\c c\~ao afim expansora $\psi$.

Os conjuntos de Cantor dinamicamente definidos, ou regulares, sempre apresentam um certo tipo de auto-semelhan\c ca: pequenas partes deles s\~ao difeomorfas ao conjunto todo, ou a partes grandes dele, com distor\c c\~ao uniformemente limitada. Assim, aspectos locais desses conjuntos n\~ao diferem muito de aspectos globais. Este tipo de propriedade \'e a principal caracter\'\i stica dos conjuntos de Cantor regulares, e est\'a ligada ao fato desses conjuntos, por defini\c c\~ao, serem caracterizados como maximais invariantes de fun\c c\~oes diferenci\'aveis expansoras (as quais suporemos de classe pelo menos $C^{1+\ve}$).

Vamos passar a defini\c c\~oes mais precisas:

Sejam $I,I_1,I_2,\dots,I_k \subset \re$ intervalos fechados tais que os intervalos $I_j$\,,\linebreak $1 \le j \le k$ s\~ao disjuntos e $I$ \'e o fecho convexo de $I_1 \cup I_2 \cup \dots \cup I_k$\,, e seja \linebreak $\psi\colon I_1 \cup I_2 \cup\dots\cup I_k \to I$ uma fun\c c\~ao expansora de classe $C^{1+\ve}$ para um certo $\ve > 0$, isto \'e, $\psi$ \'e de classe $C^1$,\,\, $|\psi'(x)| > 1$ para todo $x \in I_1 \cup I_2 \cup\dots\cup I_k$ e existe $C > 0$ tal que $|\psi'(x)-\psi'(y)| \le C|x-y|^\ve$\,\,\, $\forall\,x,y \in I_1\cup I_2 \cup\dots\cup I_k$\,. Suponhamos ainda que para todo $j$ com $1 \le j \le k$,\,\, $\psi(I_j)$ \'e o fecho convexo de uma uni\~ao de intervalos $I_i$\,, e que, para $n\in\na$ suficientemente grande, $\psi^n(I_j) \supset I_1 \cup I_2 \cup\dots\cup I_k$\,.

Dizemos que o conjunto de Cantor regular $K = K_\psi$ associado \`a fun\c c\~ao $\psi$ e \`a {\it parti\c c\~ao de Markov\/} $(I_1,I_2,\dots,I_k)$ \'e o conjunto dos $x \in I$ tais que $\psi^n(x)$ est\'a definido para todo $n\in\na$, isto \'e $K_\psi = \bigcap_{n\in\na} \psi^{-n}(I_1 \cup \dots \cup I_k)$. Se $\psi$ \'e de classe $C^r$, com $1 < r \le \infty$, dizemos que $K$ \'e um (conjunto de) Cantor regular de classe $C^r$.

Como indicamos na defini\c c\~ao acima, o conjunto dos intervalos $I_j$ com $1 \le j \le k$ \'e denominado a parti\c c\~ao de Markov de $K$. O conjuntos $I_1 \cup I_2 \cup \dots \cup I_k$ ser\'a chamado de {\it dom\'\i nio de Markov\/} de $K$, e pode ser visto como a etapa inicial da constru\c c\~ao de $K$.

Para entender melhor a estrutura do conjunto $K$ podemos considerar a {\it matriz de transi\c c\~ao\/} $B = (b_{ij})\_{k\times k}$ associada a uma parti\c c\~ao de Markov $(I_1,\dots,I_k)$ e a uma fun\c c\~ao $\psi$ como acima definida por $b_{ij} = \cases 1, \text{ se } \psi(I_i) \supset I_j\\ 0, \text{ se } \psi(I_i) \cap I_j = \emptyset\endcases$. A condi\c c\~ao diz que $\psi^n(I_j) \supset I_1 \cup \dots\cup I_k$ para todo $n$ grande equivale a todos os termos de $B^n$ serem estritamente positivos se $n$ \'e grande. A uma tal matriz $B$ podemos associar um {\it shift de Markov mixing de tipo finito}, isto \'e, o conjunto $\Sigma_B = \{\und{\te} = (\te_1,\te_2,\dots) \subset \{1,2,\dots,k\}^\na \mid b_{\te_i\te_{i+1}} = 1$,\,\, $\forall\,i \in \na\}$, no qual est\'a definida a fun\c c\~ao {\it shift unilateral\/} $\sigma\colon \Sigma_B \to \Sigma_B$\,, por $\sigma((\te_1,\te_2,\te_3,\dots)) = (\te_2,\te_3,\dots)$, isto \'e, $\sigma((\te_i)\_{i\in\na}) = (\te_{i+1})\_{i\in\na}$\,.

Veremos que h\'a uma identifica\c c\~ao natural entre o par $(K,\psi)$ e o par $(\Sigma_B,\sigma)$ (de fato um homeomorfismo que conjuga as din\^amicas). Para cada palavra finita $\und{a} = (a_1,a_2,\dots,a_n) \in \{1,2,\dots,k\}^n$ dizemos que $\und{a}$ \'e uma palavra de $\Sigma_B$ se existe algum elemento de $\Sigma_B$ que come\c ca por $\und{a}$, ou, equivalentemente, se $b_{a_ia_{i+1}} = 1$ para $i=1,2,\dots,n-1$. A uma tal palavra $\und{a}$ associamos o intervalo $I_{\und a} = I_{a_1}\cap \psi^{-1}(I_{a_2}) \cap \psi^{-2}(I_{a_3}) \cap \dots \cap \psi^{-(n-1)}(I_{a_n})$, e a condi\c c\~ao $\und a$ ser uma palavra de $\Sigma_B$ equivale a $I_{\und a}$ ser n\~ao-vazio.
 Por outro lado, a expansividade de $\psi$ faz com que o comprimento $|I_{\und a}|$ do intervalo $I_{\und a}$ seja exponencialmente pequeno se $n$ \'e grande, isto \'e, existe $\la < 1$ tal que para todo $\und{a} \in \{1,2,\dots,k\}^n$ que \'e uma palavra de $\Sigma_B$ (de tamanho $n$),\,\, $|I_{\und a}| < \la^n|I|$.

Dado $\und{\te} = (\te_1,\te_2,\dots) \in \Sigma_B$, para cada $n$ definimos $\und{\te}^{(n)} = (\te_1,\te_2,\dots,\te_n)$. Note que $\und{\te}^{(n)}$ \'e sempre uma palavra de $\Sigma_B$\,.  Podemos definir uma fun\c c\~ao $h\colon \Sigma_B \to K$ definida por $\{h(\und\te)\} = \bigcap_{n\in\na} I_{\und{\te}^{(n)}}$, isto \'e, $h(\und\te)$ \'e o \'unico ponto que pertence a $I_{\und{\te}^{(n)}}$ para todo $n \in \na$. N\~ao \'e dif\'\i cil verificar que $h$ \'e um homeomorfismo, e que $\psi\circ h = h\circ\sigma$, isto \'e, $h$ \'e uma conjuga\c c\~ao entre $\sigma$ e $\psi$. Se $x=h(\und\te)$, dizemos que $\und\te$ \'e o endere\c co do ponto $x$.

\vglue .3in

\noindent{\large\bf 1.2\quad Distor\c c\~ao limitada e geometrias limite}

\vglue .1in

Vamos agora provar uma proposi\c c\~ao de grande import\^ancia, segundo a qual conjuntos de Cantor regulares t\^em a propriedade de {\it distor\c c\~ao limitada}:

\vglue .2in

\noindent
{\bf Proposi\c c\~ao A.1:} Seja $K \subset \re$ um conjunto de Cantor regular, definido por uma fun\c c\~ao expansora $\psi \in C^{1+\ve}$ como acima. Dado $\delta > 0$ existe $C(\delta) > 0$ fun\c c\~ao decrescente de $\delta$ com $\lim_{\delta\to0} C(\delta) = 0$ tal que para todo $x,y \in K$ satisfazendo

\begin{itemize}

\item[{i)}]\,\,$|\psi^n(x)-\psi^n(y)| \le \delta$
\item[{ii)}]\,\,O intervalo $[\psi^j(x), \psi^j(y)]$ est\'a contido no dom\'\i nio de Markov $I_1\cup\dots\cup I_k$ para $0 \le j \le n$ temos $\log|(\psi^n)'(y)| - \log|(\psi^n)'(x)| \le C(\delta)$.

\end{itemize}

\vglue .1in

\noindent
{\bf Dem:} Se $\sigma > 1$ \'e tal que $|\psi'(t)| > \sigma$ para todo $t$ no dom\'\i nio de Markov, teremos $|\psi^j(y) - \psi^j(x)| \le \sigma^{1-n}\cdot\delta$ para $0 \le j \le n$, donde
$$
|\log|(\psi^n)'(y)| - \log|(\psi^n)'(x)| \le \sum_{j=0}^{n-1} |\log|\psi'(\psi^j(y))| - \log|\psi'(\psi^j(x))||,
$$
e, como $\psi'$ (e tamb\'em $\log|\psi'|$) \'e de classe $C^\ve$, existe $C > 0$ tal que $|\log|\psi'(s)| - \log|\psi'(t)| \le C|s-t|^\ve$ para $s$, $t$ no dom\'\i nio de Markov, donde as express\~oes acima s\~ao majoradas por
$$
c \sum_{j=0}^{n-1}(\sigma^{j-n}\cdot\delta)^\ve < c\dot\delta^\ve\cdot\sum_{m=1}^\infty \sigma^{-m\ve} = c\delta^\ve\cdot\frac{\sigma^{-\ve}}{1-\sigma^{-\ve}}\,\cdot 
$$
\qed

Uma maneira de reformular a proposi\c c\~ao acima com significado geom\'etrico mais evidente \'e dizer que se $x$, $y$ e $z$ pertencem a um mesmo intervalo $I_{\und{\te}^{(n)}}$ da $n$-\'esima etapa da constru\c c\~ao de $K$ ent\~ao
$$
e^{-c}\,\frac{|z-x|}{|y-x|} \le \frac{|\psi^n(z)-\psi^n(x)|}{|\psi^n(y)-\psi^n(x)|} \le e^c\,\frac{|z-x|}{|y-x|}
$$
onde $c = c(|I|)$ \'e uma constante. Al\'em disso, se $\psi^n(x)$, $\psi^n(y)$ e $\psi^n(z)$ est\~ao pr\'oximos, $c$ pode ser tomada pequena. Isto significa que dist\^ancias relativas numa escala microsc\'opica s\~ao no m\'aximo distorcidas por um fator constante em rela\c c\~ao a dist\^ancias re\-lativas correspondentes numa escala maior, e cada vez menos distorcidas se diminuimos o tamanho da escala maior.

Vamos agora introduzir o conceito de {\it geometrias limite\/} de um conjunto de Cantor regular, que d\~ao informa\c c\~oes mais precisas sobre a estrutura local de um conjunto de Cantor regular.

Para isto, seja $K$ um conjunto de Cantor regular e $\Sigma_B$ seu shift de Markov associado. Vamos considerar o shift dual associado a $\Sigma_B$, denotado por $\Sigma_B^-$\,, dado por $\Sigma_B^- - \{\und{\te} = (\te_n)\_{n\le0},\,\, f_{\te_i\te_{i+1}}=1, \forall\, i < 0\} \subset \{1,2,\dots,k\}^{\bz^-}$\,.

Dados $\und{\te}\ne\und{\tilde\te}$ em $\Sigma_B^-$\,, definimos $\und{\te} \wedge \und{\tilde\te}$ como $(\te_{-n},\te_{1-n},\dots,\te_0) \in \{1,2,\dots,k\}^{n+1}$, onde $n$ \'e tal que $\tilde\te_{-j} = \te_{-j}$ para $0 \le j \le n$ e $\tilde\te_{-n-1} \ne \te_{-n-1}$\,, e equipamos $\Sigma_B^-$ com a seguinte dist\^ancia:
$$
d(\und{\te},\und{\tilde\te}) =
\cases
1 \quad \text{se}\quad \te_0 \ne \tilde\te_0\\
|I_{\und{\te}\wedge\und{\tilde\te}}|, \text{ caso contr\'ario}
\endcases
$$

Dado $\und{\te} \in \Sigma_B^-$ e $n > 0$, definimos $\und{\te}^n = (\te_{-n},\dots,\te_0)$, e $B(\und{\te}^n)$ como sendo a fun\c c\~ao afim que leva $I_{\und{\te}^n}$ em $I_{\te_0}$ tal que o difeomorfismo $k_n^{\und{\te}} = B(\und{\te}^n) \circ f_{\und{\te}^n}$ preserva orienta\c c\~ao, onde $f_{\und{\te}^n} :=\big(\psi^n\big|_{I_{\und{\te}^n}}\big)^{-1}$.

Com essas defini\c c\~oes, $k_n^{\und{\te}}$ \'e um difeomorfismo de $I_{\te_0}$ em $I_{\te_0}$\,, e a imagem de $K \cap I_{\te_0}$ por $k_n^{\und{\te}}$ \'e uma c\'opia ampliada de $K \cap I_{\und{\te}^n}$\,.

Com essas nota\c c\~oes, temos o seguinte resultado, que caracteriza as geometrias limite de um Cantor regular (ver [Su]):

\vglue .2in

\noindent
{\bf Proposi\c c\~ao A.2:} Seja $r \in (1,+\infty)$, e $K$ um conjunto de Cantor regular de classe $C^r$ como acima, ent\~ao:

\vglue .1in

\noindent i) Para cda $\und{\te} \in \Sigma_B^-$ existe um difeomorfismo de classe $C^r$ que preserva orienta\c c\~ao $k^{\und\te} = I_{\te_0} \to I_{\te_0}$ tal que $k_n^{\und\te}$ converge a $k^{\und\te}$ na topologia $C^\al$ para todo $\al < r$. A converg\^encia \'e uniforme numa $C^r$-vizinhan\c ca de $\psi$.

\vglue .1in

\noindent ii) Se $r \ge 2$ \'e um inteiro ent\~ao $k_n^{\und\te}$ converge a $k^{\und\te}$ em $\Diff_+^r(I_{\te_0})$. Al\'em disso, existe $C > 0$ tal que $||k_n^{\und\te} - k^{\und\te}||_{C^{r-1}} \le C|I_{\und{\te}^n}|$. 

\vglue .1in

\noindent Do item ii) segue que $\und{\te}\to k^{\und\te}$ \'e Lipschitziana: $||k^{\und\te} - k^{\und{\tilde\te}}||_{C^{r-1}} \le C\cdot d(\und{\te}, \und{\tilde\te})$,\,\, $\forall\, \und{\te}, \und{\tilde\te} \in \Sigma_B^-$\,. Al\'em disso, se $r=1+\al$, com $0 < \al < 1$, ent\~ao, para
$$
||k^{\und\te} - k^{\und{\tilde\te}}||_{C^1} \le C\cdot d(\und{\te}, \und{\tilde\te})^\be,\,\, \forall\, \und{\te}, \und{\tilde\te} \in \Sigma_B^-\,.
$$

Esta proposi\c c\~ao diz que conjuntos de Cantor regulares t\^em a seguinte propriedade: se ampliarmos a interse\c c\~ao de um conjunto de Cantor regular $K$ com intervalos pequenos de sua constru\c c\~ao, obtemos conjuntos de Cantor difeomorfos a partes fixas de todo o conjunto $K$ (as interse\c c\~oes $K \cap I_a$\,, com $a \in \{1,2,\dots,k\}$), estando esses difeomorfismos muito pr\'oximos da fam\'\i lia compacta $\{k^{\und\te}, \und{\te} \in \Sigma_B^-\}$ que tem dimens\~ao de Hausdorff finita por exemplo na m\'etrica $C^1$ (ver a pr\'oxima se\c c\~ao sobre dimens\~ao de Hausdorff).

Definimos, para $\und{\te} \in \Sigma_B^-$\,, o conjunto de Cantor $K^{\und\te} := k^{\und\te}(K)$. Os conjuntos $K^{\und\te}$ s\~ao conjuntos de Cantor regulares t\~ao diferenci\'aveis quanto $K$, e s\~ao conhecidos como as {\it geometrias limite\/} de $K$.

\vglue .1in

\noindent
{\bf Dem:} A prova da Proposi\c c\~ao A.2 n\~ao \'e muito dif\'\i cil. De fato, $k_n^{\und\te} = B(\und{\te}^n) \circ f_{\und{\te}^n}$\,, onde $f_{\und{\te}^n} = \big(\psi\big|_{I_{\und{\te}^n}}\big)^{-1}$ pode ser escrito como $g_n\circ g_{n-1}\circ\dots\circ g_1$\,, onde, para $1 \le k \le n$,\quad $g_k = g_k^{\und\te}\colon I_{\te_0} \to I_{\te_0}$ \'e dada por $g_k = A_k\circ\big(\psi\big|_{I_{\und\te}^k}\big)^{-1}\circ A_{k-1}^{-1}$\,, e os $A_k\colon I_{\und{\te}^k} \to I_{\te_0}$ s\~ao difeomorfismos afins tais que $A_0$ \'e a identidade e $g_k$ preserva orienta\c c\~ao para todo $K$.

O resultado segue do fato de que os difeomorfismos $g_k$\,, para $K$ grande, est\~ao exponencialmente perto da identidade (de modo uniforme em $\und\te$), nas topologias indicadas no enunciado da proposi\c c\~ao, e portanto a composi\c c\~ao deles converge exponencialmente nessas topologias. Os detalhes ficam como exerc\'\i cio para o leitor.\qquad\quad\qed

\vglue .3in

\noindent{\large\bf 1.3\quad Dimens\~oes fractais}

\vglue .1in

\noindent{\bf 1.3.1 - A dimens\~ao de Hausdorff}

\vglue .1in

Quase todos os conjuntos de Cantor que consideramos neste livro t\^em medida de Lebesgue nula. Entretanto, h\'a medidas mais finas do tamanho de subconjuntos da reta (e, em geral, de um espa\c co m\'etrico). Come\c caremos pelo conceito que ser\'a mais importante para n\'os: a dimens\~ao de Hausdorff:

Se $X$ \'e um espa\c co m\'etrico compacto e $\U = \{U_1,U_2,\dots,U_n\}$ \'e uma cobertura finita de $X$, definimos a medida de Hausdorff de dimens\~ao $\al > 0$ associada \`a cobertura $\U$ por $m_\al(\U) = \sum\limits_{i=1}^n \diam(U_i)^\al$, onde
$$
\diam(U_i) = \sup_{x,y\in U_i} d(x,y) \quad\text{\'e o di\^ametro de $U_i$}\,,
$$
e definimos a medida de Hausdorff de dimens\~ao $\al$ de $X$ por $m_\al(X) = \liminf_{||\U||\to0} m_\al(\U)$, onde $U$ denota uma cobertura finita de $X$ e $||\U|| = \max_{U\in\U}\,(\diam U)$ \'e a norma da parti\c c\~ao $\U$. \'E f\'acil mostrar que existe um \'unico $h$ em $[0,+\infty]$ tal que se $\al < h$ ent\~ao  $m_\al(X) = +\infty$ e se $\al > h$ ent\~ao $m_\al(X)=0$. Esse n\'umero $h$ \'e, por defini\c c\~ao, a {\it dimens\~ao de Hausdorff\/} de $X$. A dimens\~ao de Hausdorff tem algumas propriedades importantes. Uma delas \'e que, se $f\colon X \to X$ \'e Lipschitziana e $K \subset X$ tem dimens\~ao de Hausdorff $d$ ent\~ao $f(K)$ tem dimens\~ao de Hausdorff menor ou igual a $d$. Em particular, se $X$ e $Y$ s\~ao intervalos fechados e $f$ \'e um difeomorfismo ent\~ao as dimens\~oes de Hausdorff de $K$ e $f(K)$ s\~ao iguais. Outra observa\c c\~ao simples \'e que se $K \subset \re^n$ tem dimens\~ao de Hausdorff menor que $n$ ent\~ao tem medida de Lebesgue nula.

\'E poss\'\i vel provar que a dimens\~ao de Hausdorff de conjuntos de Cantor regulares da reta depende continuamente da din\^amica que os define (mesmo na topologia $C^1$), e, no caso da din\^amica ser pelo menos $C^{1+\ve}$, est\'a sempre estritamente entre 0 e 1, e a medida de Hausdorff correspondente \'e finita e positiva no conjunto de Cantor (ver [PT2]).

Podemos definir outra dimens\~ao fractal, a {\it capacidade limite}, como segue: Se $K$ \'e um espa\ co m\'etrico compacto, definimos $N_\ve(K)$ como sendo o n\'umero m\'inimo de conjuntos de Di\^ametro menor ou igual a $\ve$ necess\'arios para cobrir $K$. A capacidade limite de $K$ \'e, por defini\c c\~ao, $d(K) = \limsup_{\ve\to0} - \dfrac{\log\,N_\ve(K)}{\log\,\ve}\,\cdot$ \'E poss\'ivel provar que, se $K$ \'e um conjunto de Cantor regular (mesmo que apenas de classe $C^1$) ent\~ao sua dimens\~ao de Hausdorff coincide com sua capacidade limite (ver [PT2]). Tamb\'em \'e verdade que, se $f\colon X \to Y$ \'e Lipschitziana e $K \subset X$ ent\~ao $d(f(K)) \le d(K)$ e que $d(K_1\times K_2) \le d(K_1) + d(K_2)$. Al\'em disso, em geral a dimens\~ao de Hausdorff de $K$ \'e sempre menor ou igual a $d(K)$ (\`as vezes a desigualdade \'e estrita, como por exemplo se $K=\{0\}\cup\{1/n,\,\, n \text{ inteiro positivo}\}$, que tem dimens\~ao de Hausdorff 0 e capacidade limite $1/2$).

Deixamos a prova destas \'ultimas afirma\c c\~oes como exerc\'\i cio para o leitor.

\vglue .3in

\noindent{\bf 1.3.2 - Espessuras}

\vglue .1in

\noindent
{\bf Defini\c c\~ao A.3:} Um {\it gap\/} de um conjunto de Cantor \'e uma componente conexa de seu complementar.

Dado um gap $U$ de um conjunto de Cantor $K$, associamos a ele os intervalos $E_U$ e $D_U$, que s\~ao os intervalos \`a sua esquerda e \`a sua direita que o separam dos gaps maiores que ele mais pr\'oximos:

\begin{figure}[h]
\begin{center}
\includegraphics{Figura1.eps}
%\caption{}
\end{center}
\end{figure}

\pagebreak

\noindent Definimos 

\noindent $\tau_D(U) = \dfrac{\lv D_U \rv}{\lv U \rv},\,\,
\tau_E(U) = \dfrac{\lv E_U \rv}{\lv U \rv}$,

\vglue .1in

\noindent $\tau_D(K) = \inf\{\tau_D(U)\vert U$ gap limitado de $K\}$, a {\it espessura direita\/} de $K$;

\vglue .1in

\noindent $\tau_E(K) = \inf\{\tau_E(U)\vert U$ gap limitado de $K\}$, a {\it espessura esquerda\/} de $K$, e

\vglue .1in

\noindent $\tau(K) = \min\{\tau_D(K), \tau_E(K)\}$, a {\it espessura\/} de $K$.

\vglue .1in

\noindent
{\bf Observa\c c\~ao:} Dado um conjunto de Cantor $K$, uma apresenta\c c\~ao de $K$ \'e uma enumera\c c\~ao $\{U_1,U_2,\dots \}$ de seus gaps limitados.  Podemos definir os intervalos $E_U$ e $D_U$ como sendo  os intervalos entre $U$ e os gaps de \'\i ndice menor que o de $U$ mais pr\'oximos.  No nosso caso estamos usando a
apresenta\c c\~ao pela ordem de tamanho dos gaps, o que maximiza a espessura $\tau(K)$. Veja [PT2].

A import\^ancia das espessuras reside no seguinte resultado, que \'e uma adapta\c c\~ao do ``gap lemma''.

\vglue .1in

\noindent
{\bf Afirma\c c\~ao:} Dados $K_1$ e $K_2$ conjuntos de Cantor, se $\tau_D(K_1) \cdot \tau_E(K_2)>1$ e $\tau_E(K_1) \cdot \tau_D(K_2)>1$, ent\~ao ou $K_1$
est\'a contido num gap de $K_2$ ou $K_2$ est\'a contido num gap de $K_1$ ou $K_1\cap K_2\ne\emptyset$.

\vglue .1in

\noindent
{\bf Observa\c c\~ao:} Isso vale em particular se $\tau(K_1)\cdot\tau(K_2)>1$, que \'e a
hip\'otese do ``gap lemma'' cl\'assico.  O gap lemma tal como enunciado aqui fornece mais informa\c c\~ao, como veremos adiante.

\vglue .1in

\noindent
{\bf Dem:} Considere o caso em que nenhum dos $K_i$'s est\'a contido num gap do outro. Ent\~ao existe um par de gaps encaixados, como nas figuras abaixo (dizemos nesse  caso que $K_1$ e $K_2$ est\~ao {\it intercalados})

\pagebreak

\noindent a) 

\begin{figure}[h]
\begin{center}
\includegraphics{Figura2.eps}
%\caption{}
\end{center}
\end{figure}



Como $\tau_D(U_1) \tau_E(U_2) > 1$, ou $\lv D_{U_1} \rv > \lv U_2 \rv$ ou $\lv E_{U_2} \rv > \lv U_1 \rv \,\Rightarrow$ existe novo par
de gaps como em b) menor que o par $(U_1,U_2)$

\vglue .1in

\noindent b)

\begin{figure}[h]
\begin{center}
\includegraphics{Figura3.eps}
%\caption{}
\end{center}
\end{figure}


Como $\tau_E(U_1) \tau_D(U_2) > 1$, ou $\lv E_{U_1} \rv > \lv U_2 \rv$ ou $\lv D_{U_2} \rv > \lv U_1 \rv \Rightarrow$ existe novo par de gaps como em a) menor que o par $(U_1,U_2)$.

Em qualquer caso obtemos um par de gaps menor, por exemplo no sentido de que a soma dos comprimentos dos gaps  dos pares decresce, e reaplicando o argumento obtemos uma seq\"u\^encia de pares de gaps convergindo a um ponto que necessariamente pertence a $K_1\cap K_2$.\qquad\quad \qed

\

Podemos definir, para $p\in K$, $\tau_{\text{loc}} (K,p) = \underset{\ve\to 0}{\lim\sup}\, \tau (\ov{K \cap (p-\ve,p+\ve)})$, e analogamente $(\tau_D)_{\text{loc}}(K,p)$ e $(\tau_E)_{\text{loc}} (K,p)$. Para conjuntos de Cantor dinamicamente definidos,
$\tau_{\text{loc}} (K,p)$ n\~ao depende de $p$ (ver [PT2]), e a mesma
prova mostra que $(\tau_D)_{\text{loc}}(K,p)$ \,\, e \,\,
$(\tau_E)_{\text{loc}} (K,p)$ \,\,tamb\'em n\~ao dependem de $p$.
Vamos, portanto, denot\'a-los por $\tau_{\text{loc}}(K)$, 
$(\tau_D)_{\text{loc}}(K)$ \,\,e \,\,$(\tau_E)_{\text{loc}}(K)$ (as {\it espessuras locais\/} de $K$).

A afirma\c c\~ao acima  implica que se $(\tau_D)(K_1)\cdot
(\tau_E) (K_2)\ge 1$ e se $(\tau_E)(K_1)\cdot(\tau_D)(K_2)\ge~1$ ent\~ao $K_1-K_2$ cont\'em intervalo.

Como conseq\"u\^encia, se $(\tau_D)_{\text{loc}}(K_1)\cdot
(\tau_E)_{\text{loc}}(K_2)>1$  e  $(\tau_E)_{\text{loc}}(K_1)\cdot
(\tau_D)_{\text{loc}}(K_2) >~1$ ent\~ao $K_1-K_2$ cont\'em  intervalo.
Para este \'ultimo resultado necessitamos desigualdades estritas.

 De fato, no exemplo de Sannami de um conjunto de Cantor dinamicamente definido $K$ com $\la(K-K) > 0$ e int$(K - K)=\emptyset$ temos $\tau_{\text{loc}}(K) = 1$. 


\vglue .5in

\newpage

\centerline{\Large\bf  Refer\^encias}

\vglue .2in

\begin{itemize}

\item[{[AGP]}]
     W. R. Alford, A. Granville e C. Pomerance,
{\sl There are infinitely many
     Carmichael numbers}, Ann. of Math., {\bf 140} (1994) 703-722.

\item[{[APR]}] L. M. Adleman, C. Pomerance e R. S. Rumely,
{\sl On distinguishing prime
     numbers from composite numbers}, Ann. Math. (2) {\bf 117} (1983) 173-206.


\item[{[B]}] N. Beskin,  Fra\c c\~oes cont\'\i nuas - Inicia\c c\~ao \`a Matem\'atica - Editora Mir.

\item[{ [Bach]}]
 Eric Bach, {\sl Explicit bounds for primality testing and
 related problems}, Math. of Comp. {\bf 55}, (1990), pp. 355-380.

\item[{ [BCR]}]
     R. P. Brent, G. L. Cohen e H. J. J. te Riele,
{\sl Improved techniques for
     lower bounds for odd perfect numbers}, Math. Comp., {\bf 57} (1991) 857-868
     (MR 92c:11004).

\item[{[BLS]}]
     J. Brillhart, D. H. Lehmer e J. L. Selfridge,
{\sl New primality criteria
     and factorizations of $2m \pm 1$}, Math. Comp., {\bf 29} (1975) 620-647.

\item[{[BPMV]}] R. Bam\'on, S. Plaza, C.G. Moreira and J. Vera, {\sl Differentiable structures of central Cantor sets}, Ergod. Th. and Dynam. Syst. {\bf 17} (1997), pp. 
1027--1042.

\item[{[BPV]}] R. Bam\'on, S. Plaza and J. Vera, {\sl On Central Cantor Sets with 
self-arithmetic difference of positive Lebesgue measure}, J. London Math. Soc. {\bf 51} (1995), pp. 137--146.

\item[{[Br]}]
     J. W. Bruce, {\sl A really trivial proof of the Lucas-Lehmer test},
Amer.  Math. Monthly, April (1993) 370-371.

\item[{[C]}] Jos\'e Paulo Q. Carneiro, {\sl Um processo finito para a raiz quadrada},  RPM {\bf 34}, (1997), pp. 36--44.

\item[{[Ca1]}] J.W.S. Cassels, {\sl An introduction to diophantine approximation\/}, Cambridge Univ. Pres, (1957).

\item[{[Ca2]}] J.W.S. Cassels, {\sl Some metrical theorems in Diophantine approximation I\/}, Proc. Camb. Phil. Soc. {\bf 46} (1950), 209--218.

\item[{[CB]}]
M. Clausen e U. Baum, {\sl Fast Fourier Transforms},
BI-Wiss.-Verl., (1993).

\item[{[Cipolla]}]
M. Cipolla, 
{\sl Sui numeri composti $P$, che verificano la congruenza di Fermat
$a^{P-1} \equiv 1 \pmod P$},
Annali di Matematica, (3), {\bf 9}, (1904), 139-160.

\item[{[CF]}]
     R. Crandall e B. Fagin, {\sl Discrete weighted transforms and
     large-integer arithmetic}, Math. Comp., {\bf 62:205} (1994) 305-324.

\item[{[CF]}] T.W. Cusick and M.E. Flahive,\ {\sl The Markoff and Lagrange spectra}, Math. Surveys and Monographs, no. {\bf 30}, A.M.S. (1989).

\item[{[E]}]
     P. Erdös, {\sl On a new method in elementary number theory
which leads to
     an elementary proof of the prime number theorem},
Proc. Nat. Acad. Sci.  (Washington) {\bf 35} (1949) 374-384.

\item[{[EP]}]
     P. Erdös e Carl Pomerance, {\sl On the number of false witnesses for a
     composite number}, Math. Comp., {\bf 46} (1986) 259-279.

\item[{[F]}] G.A. Freiman,\ {\sl Diophantine approximation and geometry of numbers (The Markoff spectrum)}, Kalininskii Gosudarstvennyi Universitet, Moscow, (1975).

\item[{[GK]}]
     S. Goldwasser e J. Kilian, {\sl Almost all primes can be quickly
     certified}, Proc. 18th STOC (Berkeley, May 28-30, 1986), ACM, New York,
     (1986), 316-329.

\item[{[Guy]}]
     R. K. Guy, {\sl Unsolved Problems in Number Theory}, Springer-Verlag,
     New York, (1994) (QA241.G87, ISBN 3-540-94289-0).

\item[{[H]}] M. Hall, \ {\sl On the sum and product of continued fractions}, Annals of Math., Vol. {\bf 48}, (1947), pp. 966--993.

\item[{[HW]}]
     G. H. Hardy e E. M. Wright,
{\sl An Introduction to the Theory of Numbers 5e},
Oxford University Press, (1979).

\item[{[K]}] A. Khintchine: {\sl Zur metrischen Theorie der diophantischen Approximationen\/}, Math. Z. {\bf 24} (1926), 706--714.

\item[{[KP]}]
     Su Hee Kim e Carl Pomerance, {\sl The probability that a random probable
     prime is composite}, Math. Comp., {\bf 53:188} (1989) 721-741.


\item[{[Per]}] L., Per, \ {\sl L'ensemble difference de deux ensembles de Cantor aleatoires}, C.R. Acad. Sci. Paris S\'er. I Math. {\bf 310} (1990), no. 10, 735--738.

\item[{[Le]}]
     D. H. Lehmer, {\sl An extended theory of Lucas' functions},
Ann. Math.  31 (1930) 419-448.
Reprinted in {\sl Selected Papers} (ed. D. McCarthy), Vol {\bf 1},
Ch. Babbage Res. Center, St. Pierre, Manitoba Canada, 11-48, (1981).

\item[{[Lu]}]
E. Lucas, {\sl Théorie des fonctions numériques simplement périodiques},
Amer. J. Math., {\bf 1}, (1878), 184-240 e 289-321.


\item[{[M1]}] C.G. Moreira, \ {\sl Stable intersections of Cantor sets and homoclinic bifurcations}, Ann. Inst. H. Poincar\'e Anal. Non Lin\'eaire {\bf 13} (1996), no. 6, pp. 741--781.

\item[{[M2]}] C.G. Moreira, \ {\sl Geometric properties of the Markov and Lagrange spectra}.
Preprint- IMPA.

\item[{[M3]}] C.G. Moreira, \ {\sl Geometric properties of dynamical spectra}. To
appear

\item[{[M4]}] C.G. Moreira,
{\sl Conjuntos de Cantor,bifurcações dinâmicas e aproximações diofantinas},
22.o Colóquio Brasileiro de Matemática.

\item[{[M5]}] C.G. Moreira,
{\sl Propriedades estatísticas de frações contínuas e aproximações diofantinas:o
teorema de Khintchine},
Revista Matemática Universitária número {\bf 29}, pp. 125-137

\item[{[M6]}] C.G. Moreira, {\sl Frações contínuas, representações de números e 
a\-pro\-xi\-ma\-ções\/}, Eureka {\bf 3} (1998), 44--55.

\item[{[Mai]}]
     H. Maier, {\sl Primes in short intervals}, Michigan math. J., {\bf 32} (1985)
     221-225.

\item[{[Mar1]}] A. Markoff, \ {\sl A new sequence of minima in the geometry of numbers}, \ Math. Ann. {\bf 15} (1879), 381--406.

\item[{[Mar2]}] A. Markov, {\sl Sur les formes quadratiques binaires indéfinies\/}, Math. Ann. {\bf 15} (1879), 381--406.

\item[{[Mi]}]
     W. H. Mills, {\sl A prime representing function},
 Bull. Amer. Math. Soc., 53 604.

\item[{[MN]}] C.G. Moreira e Nicolau Saldanha,
{\sl Primos de Mersenne (e outros primos muito grandes)},
22.o Colóquio Brasileiro de Matemática

\item[{[Mo]}],
     R. A. Mollin, {\sl Prime-producing polynomials}, Amer. Math. Monthly {\bf 104}
     (June-July 1997) 529-544.

\item[{[MO]}] P. Mendes and F. Oliveira, \ {\sl On the topological structure of the arithmetic sum of two Cantor sets}, Nonlinearity, Vol. {\bf 7}, (1994), pp. 329--343.

\item[{[MY]}] C.G. Moreira and J.-C. Yoccoz, \ {\sl Stable intersections of regular Cantor sets with large Hausdorff dimensions}. Preprint - IMPA, (1998).

\item[{[MY2]}] C.G. Moreira and J.-C. Yoccoz, \ {\sl Tangences homoclines stables pour les ensembles hyperboliques de grande dimension fractale}. To appear.


\item[{[N1]}] S. Newhouse, \ {\sl Non density of Axiom $A(a)$ on $S^2$}, Proc. A.M.S. Symp. Pure Math., Vol. {\bf 14}, (1970), pp. 191--202.

\item[{[N2]}] S. Newhouse, \ {\sl Diffeomorphisms with infinitely many sinks}, Topology, Vol. {\bf 13}, (1974), pp. 9--18.

\item[{[N3]}] S. Newhouse, \ {\sl The abundance of wild hyperbolic sets and nonsmooth stable sets for diffeomorphisms}, Publ. Math. IHES, Vol. {\bf 50}, (1979), pp. 101--151.

\item[{[O]}] C.D. Olds, {\sl Continued Fractions},  New Mathematical Library, Random House.

\item[{[P]}] J. Palis, \ {\sl Homoclinic orbits, hyperbolic dynamics and fractional dimension of Cantor sets}, Contemporary Mathematics {\bf 58}, (1987), pp. 203--216.

\item[{[P1]}] J. Palis, \ {\sl Homoclinic bifurcations, sensitive chaotic dynamics and strange attractors}, Dynamical Syst. and Related Topics. World Scientific, (1991), pp. 466-473.

\item[{[Pi]}]
J. Pintz, {\sl Very large gaps between consecutive primes},
J. Number Theory {\bf 63} (1997), no. 2, 286-301.

\item[{[Po]}]
C. Pomerance, {\sl A new lower bound for the pseudoprimes counting function},
 Illinois J. Math, {\bf 26}, (1982), 4-9.

\item[{[PSW]}]
     C. Pomerance, J. L. Selfridge e S. S. Wagstaff Jr.,
{\sl The pseudoprimes
     to 25.109}, Math. Comp., {\bf 35} (1980) 1003-1026.

\item[{[PT]}] J. Palis and F. Takens, \ {\sl Cycles and measure of bifurcation sets for two-dimensional diffeomorphisms}, Invent. Math., Vol. {\bf 82}, (1985), pp. 379--442.

\item[{[PT1]}] J. Palis and F. Takens, \ {\sl Hyperbolicity and the creation of homoclinic orbits}, Annals of Math., Vol. {\bf 125}, (1987), pp. 337--374.

\item[{[PT2]}] J. Palis and F. Takens, \ {\sl Hyperbolicity and sensitive chaotic dynamics at homoclinic bifurcations: fractal dimensions and infinitely many attractors}, Cambridge Univ. Press, (1992).

\item[{[PY]}] J. Palis and J.C. Yoccoz, \ {\sl Homoclinic Tangencies for Hyperbolic sets of large Hausdorff Dimension Bifurcations}, Acta Mathematica, Vol. {\bf 172}, (1994), pp. 91--136.

\item[{[PY1]}] J. Palis and J.C. Yoccoz, \ {\sl On the arithmetic sum of regular Cantor sets}, Ann. Inst. H. Poincar\'e Anal. Non Lin\'eaire {\bf 14}  (1997), pp. 439--456.

\item[{[R]}] A.M. Rockett, P. Sz\"usz, {\sl  Continued Fractions}, World Scientific.

\item[{[Ri1]}]
     P. Ribenboim, {\sl The New Book of Prime Number Records},
3ed., Springer-Verlag, New York, (1995) (QA246 .R47 ISBN 0-387-94457-5).

\item[{[Ri2]}]
     P. Ribenboim, {\sl Vendendo primos}, Rev. Mat. Univ., 22/23, 1997, 1-13
(tradução de {\sl Selling primes}, Math. Mag., {\bf 68} (1995) 175-182).

\item[{[Rie1]}]
     H. Riesel, {\sl Naagra stora primtal}
(Sueco: {\sl Alguns primos grandes}),
     Elementa {\bf 39} (1956) 258-260.

\item[{[Rie2]}]
     H. Riesel, {\sl Prime Numbers and Computer Methods for Factorization},
     Progress in Mathematics, Birkhauser Boston, vol. {\bf 57}, (1985); and vol.
     126, 1994.

\item[{[S]}] A. Sannami, \ {\sl An example of a regular Cantor set whose difference set is a Cantor set with positive measure}, Hokkaido Math. Journal, Vol. {\bf XXI} (I), (1992), pp. 7--23.

\item[{[Sc]}] W.M. Schmidt: {\sl Diophantine approximations\/}, Lecture Notes in Mathematics {\bf 785}, Springer Verlag, (1980).

\item[{[Se]}]
     A. Selberg, {\sl An elementary proof of the prime number theorem},
Annals of Math. {\bf 50} (1949) 305-13.

\item[{[Si]}]
     W. Sierpinski, {\sl Sur un problème concernant les nombres
$k \cdot 2n+1$}, Elem.  Math., {\bf 15} (1960) 73-74.
Corrigendum: Elem. Math., {\bf 17} (1963) 85.

\item[{[Su]}] D. Sullivan, \ {\sl Differentiable structures on fractal-like sets, determined by intrinsic scaling functions on dual Cantor sets}, The mathematical heritage of Hermann Weyl (Durham, NC, 1987), 15--223, Proc. Sympos. Pure Math. {\bf 48}, Amer. Math. Soc., Providence, RI, (1988).

\item[{[WD]}]
     H. C. Williams e H. Dubner, {\sl The primality of R1031},
Math. Comp., {\bf 47} (1986) 703-711.


\item[{[We]}]
     E. Westzynthius, {\sl Über die Verteilung der Zahlen die zu den $n$ ersten
     Primzahlen teilerfremd sind}, Comm. Phys. math. Helsingfors, 5:5 (1931)
     1-37.

\item[{[Wi]}]
     H. Wilf, {\sl What is an answer?} Am. Math. Monthly, {\bf 89} (1982), 289-292.

\item[{[YP]}]
     J. Young e A. Potler, {\sl First occurence of primes gaps},
Math. Comp., {\bf 52} (1989) 221-224.

\end{itemize}
\end{document}