% preambula dokumenta \documentclass[a4paper,12pt]{article} \usepackage[slovene]{babel} \usepackage[cp1250]{inputenc} \usepackage[T1]{fontenc} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsmath} \usepackage[dvips]{graphicx} \newtheorem{defn}{Definicija} \newtheorem{lema}{Lema} \newtheorem{izrek}{Izrek} \newtheorem{algoritem}{Algoritem} \newtheorem{posledica}{Posledica} \newenvironment{zgled}{\noindent\textsc{Zgled:~}}{} \newenvironment{dokaz}{\noindent\textsc{Dokaz:~}}{\hfill$\Box$\bigskip} \advance\textwidth by +1.6in \advance\oddsidemargin by -.8in \advance\evensidemargin by -.8in \advance\textheight by +1in \advance\headheight by -.6in \advance\topmargin by -1cm %\advance\ by -.6in %\parindent=0pt % telo dokumenta \begin{document} \noindent David Gajser \hfill \small{20.~10.~2009, 5.~11.~2009} %\maketitle \LARGE \begin{center} Veri\v{z}ni ulomki\end{center} \normalsize \vspace{1cm} \noindent Kon"cni veri"zni ulomek je izraz oblike: $$ a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\ddots a_{N-1} + \frac{1}{a_N}}}},$$ kjer je $a_0\in\mathbb{Z} $, $a_1,a_2, \ldots, a_N \in\mathbb{N}$. Kraj"se ga predstavimo s tabelo $$[a_0; a_1, a_2, \ldots, a_N].$$ Zaradi enoli"cnosti zapisa bomo v"casih privzeli $a_N\neq 1$. Naj bo $a_0\in\mathbb{Z} $ in $a_1,a_2, \ldots$ zaporedje naravnih "stevil. "Ce zaporedje $x_N=[a_0; a_1, a_2,\ldots , a_N]$ konvergira, limiti pravimo vrednost neskon"cnega veri"znega ulomka $$[a_0; a_1, a_2, \ldots]= a_0 + \frac{1}{a_1 + \frac{1}{a_2 + \frac{1}{\ddots }}}.$$ V razdelku~\ref{section:nesk} bomo dokazali, da zaporedje $x_N$ zmeraj konvergira. S pomo"cjo veri"znih ulomkov lahko predstavimo racionalna in iracionalna "stevila. Veri"zni ulomki racionalnih "stevil so kon"cni. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %\newpage \section{Enoli"cnost kon"cnih veri"znih ulomkov} Naj bo $x=[a_0; a_1, a_2,\ldots , a_N]$, $a_N\neq 1$, kon"cen veri"zni ulomek. \begin{izrek} \label{lema1} Za pozitiven $N$ je $x-a_0$ zmeraj strogo med $0$ in $1$. \end{izrek} \begin{dokaz} Naj bo $N>0$. Ker vrednost veri"znega ulomka $[a_1; a_2,\ldots , a_N]=\frac{1}{x-a_0}$ dobimo le s se"stevanjem in deljenjem pozitivnih "stevil, je $x-a_0>0$. "Ce je $N=1$, je po privzetku $a_N\neq 1$ res $a_1\geq 2$, zato $x-a_0 \leq \frac{1}{2}$, torej izrek velja. Za $N>1$ pa vemo, da je $[a_2; a_3,\ldots , a_N]>0$, zato $\frac{1}{x-a_0}=[a_1; a_2,\ldots , a_N]>a_1\geq 1$, torej $x-a_0<1$. \end{dokaz} \begin{izrek} "Ce lahko $x$ zapi"semo s kon"cnim veri"znim ulomkom, je ta z zahtevo $a_N\neq 1$ enoli"cno dolo"cen. \end{izrek} \begin{dokaz} Denimo, da velja $x=[a_0; a_1,\ldots , a_N]=[b_0; b_1,\ldots , b_M]$. Brez "skode za splo"snost smemo privzeti $N\leq M$. Po izreku \ref{lema1} za $N>0$ velja $00$, je $0a_{n+1}$. Naj bo $a_N\neq 1$ ali $N>n+2$. Naj bo $b_M\neq 1$ ali $M>n+1$. "Ce je $n$ sod, je $x>y$, sicer je $y>x$. \end{izrek} \begin{dokaz} "Ce je $a_N=1$, potem je $N>n+1$ in $x=[a_0;a_1,a_2,\ldots, a_n, a_{n+1},\ldots,a_{N-1}+1]$. Podobno za $y$. Tako dobimo razvoja $x$ in $y$ v kon"cen veri"zni ulomek, kjer zadnji "clen ni enak $1$, $(n+1)$-vi "clen pa ostane nespremenjen. Recimo, da je $n$ lih in $x\geq y$. Potem hiter ra"cun poka"ze, da velja: $$[a_1;a_2,a_3,\ldots, a_n, a_{n+1},\ldots,a_N]\leq[a_1;a_2,a_3,\ldots, a_n, b_{n+1},\ldots,b_M].$$\noindent Postopek izvedemo "se $n$-krat, in ker je $n$ lih, dobimo $$[a_{n+1},\ldots,a_N]\geq[ b_{n+1},\ldots,b_M].$$ Ker pa velja $b_{n+1}>a_{n+1}$, je $$[ b_{n+1},\ldots,b_M]>b_{n+1}\geq a_{n+1}+1>[a_{n+1},\ldots,a_N].$$Pri"sli smo torej v protislovje. \newline Na podoben na"cin za sod $n$ in $x\leq y$ pridemo v protislovje. \end{dokaz} \vspace{1cm} \newpage \begin{zgled} \begin{itemize} \item Poi"s"cimo veri"zni ulomek za $\frac{54}{30}$: \begin{eqnarray*} 54 &= &\underline{1} \cdot 30 + 24\\ 30 &= &\underline{1} \cdot 24 + 6\\ 24 &= &\underline{4} \cdot 6 + 0 \end{eqnarray*} $a_1, a_2, \ldots, a_N$ preberemo iz Evklidovega algoritma. Dobimo: $$\frac{54}{30} = 1 + \frac{1}{1 + \frac{1}{4}}.$$ \item Poi"s"cimo veri"zni ulomek za $\frac{-54}{7}$: \begin{eqnarray*} -54 &= &\underline{-8} \cdot 7 + 2\\ 7 &= &\underline{3} \cdot 2 + 1\\ 2 &= &\underline{2} \cdot 1 + 0 \end{eqnarray*} $a_1, a_2, \ldots, a_N$ preberemo iz Evklidovega algoritma. Dobimo: $$\frac{-54}{7} = -8 + \frac{1}{3 + \frac{1}{2}}.$$ \end{itemize} \end{zgled} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Splo"sni veri"zni ulomki} "Ce je $a_0\in\mathbb{R}$, $a_1, a_2,\ldots , a_N \in\mathbb{R^+}$, imenujemo veri"zni ulomek splo"sni veri"zni ulomek. Kar bomo v tem razdelku dokazali za splo"sne, velja tudi za navadne veri"zne ulomke. Seveda vsakemu "stevilu ne pripada natanko en splo"sni veri"zni ulomek. \vspace{0.5cm} \begin{zgled} $[-2; \frac{1}{2}, \frac{3}{5}] = -2 + \frac{1}{\frac{1}{2} + \frac{1}{\frac{3}{5}}} = -2 + \frac{1}{\frac{1}{2} + \frac{5}{3}} = -2 + \frac{1}{\frac{13}{6}} = -2 + \frac{6}{13} = \frac{-20}{13}$ \end{zgled} Ozna"cimo $$x_0 = [a_0],$$ $$x_1 = [a_0; a_1],$$ $$\vdots$$ $$x_N = [a_0; a_1,\ldots , a_N].$$ "Stevilom $x_i$, $i = 1,\ldots , N$, pravimo pribli"zki veri"znega ulomka. \begin{izrek} \label{izrek:B} Za dan splo"sni veri"zni ulomek $[a_0; a_1,\ldots , a_N]$ definiramo "stevila: $$p_0 = a_0,\hspace{5mm} q_0 = 1,\hspace{5mm} p_1 = a_1 a_0 + 1,\hspace{5mm} q_1 = a_1$$ in za $2 \leq n \leq N$: $$p_n = a_np_{n-1} + p_{n-2},$$ $$q_n = a_nq_{n-1} + q_{n-2}.$$ Z njimi se izra"za pribli"zek $x_n$, $0 \leq n \leq N$, splo"snega veri"znega ulomka: $$x_n = \frac{p_n}{q_n}.$$ \end{izrek} \begin{dokaz} Dokazovali bomo z indukcijo na $n$. Za $n=0$ in $n=1$ izrek velja. Pa recimo, da velja za vse pribli"zke do $x_n$, $n x_3 > x_5 >\ldots $$ Vsak pribli"zek sodega indeksa je manj"si od vsakega pribli"zka z lihim indeksom, to je $x_{2j} < x_{2k + 1}$ za vsaka $2j$ in $2k + 1$, ki le"zita med $0$ in $N$. \end{izrek} \begin{dokaz} Pri $N=1$ imamo $$p_1 q_0-p_0 q_1=1=(-1)^{1-1}.$$ Pa recimo, da velja $p_nq_{n-1} - p_{n-1}q_n = (-1)^{n-1}$ za $n0$, $q_1>0$ in $q_n = a_nq_{n-1} + q_{n-2}$, so vsi definirani $q_i$ ve"cji od $0$. Torej lahko s $q_nq_{n-1}$ delimo in dobimo $$\frac{p_n}{q_n} - \frac{p_{n-1}}{q_{n-1}} = \frac{(-1)^{n-1}}{q_n q_{n-1}}.$$ \noindent Iz definicije $p_n$ in $q_n$ sledi $$p_nq_{n-2}-p_{n-2}q_n=(a_np_{n-1}+p_{n-2})q_{n-2}-p_{n-2}-p_{n-2}(a_nq_{n-1}+q_{n-2})=a_n(p_{n-1}q_{n-2}-p_{n-2}q_{n-1})=a_n(-1)^n.$$ Torej smo dokazali "se eno enakost iz trditve. Ker so $q_i>0$, lahko delimo s $q_nq_{n-2}$ in dobimo $$x_n-x_{n-2}=\frac{p_n}{q_n}-\frac{p_{n-2}}{q_{n-2}}=(-1)^n \frac{a_n}{q_nq_{n-2}}.$$ Torej za sode $n$ pribli"zki rastejo, za lihe $n$ pa padajo. \noindent Iz ena"cbe~\eqref{enacba} po deljenju s $q_nq_{n-1}$ dobimo $$x_n-x_{n-1}=\frac{p_n}{q_n}-\frac{p_{n-1}}{q_{n-1}}=\frac{(-1)^{n-1}}{q_nq_{n-1}}.$$ Torej je sodi pribli"zek z najve"cjim indeksom manj"si od lihega pribli"zka z najve"cjim indeksom in zaradi monotonosti sodih oz. lihih pribli"zkov so vsi sodi pribli"zki manj"si od vsakega lihega. S tem smo trditev v celoti dokazali. \end{dokaz} \begin{izrek} \label{izrek:D} Pribli"zek $\frac{p_n}{q_n}$ navadnega veri"znega ulomka $[a_0; a_1,\ldots , a_N]$ je za vsak indeks $n$, $0\leq n\leq N$, okraj"san ulomek. Zaporedje $(q_n)_{n=1}^N$ je strogo nara"s"cajo"ce, za vsak $n$ velja $q_n \geq 2^{\frac{n-1}{2}}$ in $q_n \geq n$. Za $n0$ pa iz enakosti~\eqref{enacba} sledi, da sta si $p_n$ in $q_n$ tuji. Da je zaporedje $(q_n)_{n=1}^N$ strogo nara"s"cajo"ce in da velja $q_n \geq n$, dobimo indukcijsko iz definicije $q_n$. Tudi oceno $q_n \geq 2^{\frac{n-1}{2}}$ lahko enostavno doka"zemo z indukcijo, kjer upo"stevamo monotonost $(q_n)_{n=1}^N$ . Iz enacbe~\eqref{enacba2} po deljenju s $q_nq_{n-2}$ dobimo $$|x_n-x_{n-2}|=|\frac{p_n}{q_n}-\frac{p_{n-2}}{q_{n-2}}|=|(-1)^n \frac{a_n}{q_nq_{n-2}}|> \frac{1}{q_nq_{n-1}}.$$ Pri tej oceni smo "ze upo"stevali monotonost $(q_n)_{n=1}^N$. "Ce ena"cbo~\eqref{enacba} delimo s $q_nq_{n-1}$, dobimo $$|x_n-x_{n-2}|> \frac{1}{q_nq_{n-1}}=|x_n-x_{n-1}|.$$ Zaradi monotonosti sodih in lihih pribli"zkov je $x_N$ nekje med $x_n$ in $x_{n-1}$, kar pomeni, da je zaporedje $x_{n-2}$, $x_n$, $x_N$, $x_{n-1}$ monotono. Sledi ocena $$|x_{n-2}-x_N|\geq |x_{n-2}-x_n|>|x_n-x_{n-1}|\geq |x_N-x_{n-1}|.$$ Torej se pribli"zki veri"znega ulomka njegovi vrednosti monotono pribli"zujejo. Za zadnji dve oceni iz izreka upo"stevamo, da je $x_N$ med $x_n$ in $x_{n+1}$ ter uporabimo ena"cbo\eqref{enacba}: $$|x_n-x_N|\leq|x_n-x_{n+1}|=\frac{1}{q_nq_{n+1}}.$$ Enkrat uporabimo $q_n \geq 2^{\frac{n-1}{2}}$, drugi"c pa $q_n \geq n$ in dobimo "zeljen rezultat. \end{dokaz} \noindent Z uporabo veri"znih ulomkov se da enostavno dokazati naslednji izrek: \begin{izrek}(Hin"cin, 1956) Za dana $\alpha \in\mathbb{Q}$ in $n \in\mathbb{N}$ najdemo v polinomskem "casu (polinomskem v dol"zini zapisa $n$ in dol"zini zapisa $\alpha$) tak $\beta \in\mathbb{Q}$ z imenovalcem najve"c $n$, da je izraz $|\alpha - \beta |$ minimalen. \end{izrek} \begin{dokaz} Naj bo $\alpha=[a_0; a_1,\ldots , a_N]$. Ra"cunajmo pribli"zke tega veri"znega ulomka $x_k=\frac{p_k}{q_k}$, vse dokler ne dobimo $\alpha$ ali pa je $q_{k+1}>n$. Po izreku~\ref{izrek:D} velja $2^{\frac{k-1}{2}}\leq q_k \leq n$, torej smo naredili najve"c $O(log(n))$ korakov. Naj bo $x_K$ zadnji izra"cunan pribli"zek in $t\in \mathbb{N}_0$ maksimalen tak, da je $tq_K+q_{K-1}\leq n$. Definirajmo $$y=x_K \textrm{\ \ in\ \ } z=\frac{tp_K+p_{K-1}}{tq_K+q_{K-1}}.$$ O"citno imata $y$ in $z$ imenovalca manj"sa ali enaka $n$. Doka"zimo, da je en izmed njiju re"sitev. Za sodi $K$ velja $y\leq \alpha\leq\frac{p_{K+1}}{q_{K+1}}$. Z razre"sitvijo ulomka in upo"stevanjem enakosti~\eqref{enacba} se enostavno preveri, da velja tudi $$\frac{p_{K+1}}{q_{K+1}}=\frac{a_{K+1}p_K+p_{K-1}}{a_{K+1}q_K+q_{K-1}}<\frac{tp_K+p_{K-1}}{tq_K+q_{K-1}}=z.$$ Torej $$y\leq \alpha< z.$$ Podobno za lihi $K$ dobimo $$z< \alpha\leq y.$$ Za zaklju"cek dokaza je torej dovolj pokazati, da med $y$ in $z$ ni racionalnega "stevila z imenovalcem manj"sim od $n$. Vzemimo poljuben ulomek $\frac{p}{q}$ , $p\in \mathbb{Z},\ q\in \mathbb{N}$, strogo med $y$ in $z$. Vemo, da je $y=[a_0; a_1,\ldots , a_K]$ in $z=[a_0; a_1,\ldots , a_K,t]$, zato po izreku~\ref{izrek:C} velja $$|y-z|=\frac{1}{q_n (tq_n+q_{n-1})}.$$ Po drugi strani pa je $$|y-z|=|y-\frac{p}{q}|+|z-\frac{p}{q}|\geq \frac{1}{qq_n}+\frac{1}{q(tq_n+q_{n-1})}=\frac{(t+1)q_n+q_{n-1}}{qq_n(tq_n+q_{n-1})}.$$ To pa pomeni, da je $$q\geq (t+1)q_n+q_{n-1}>n,$$ kar zaklju"ci dokaz izreka. \end{dokaz} \begin{posledica} Iz zgornjega dokaza je razvidno, da lahko racionalne pribli"zke z majhnim imenovalcem i"s"cemo z veri"znimi ulomki. \end{posledica} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Neskon"cni veri"zni ulomki} \label{section:nesk} Naj bo $a_0, a_1,\ldots $ neskon"cno zaporedje "stevil, kjer $a_0\in\mathbb{Z}$, $a_1, a_2,\ldots \in\mathbb{N}$. "Stevila $a_0, a_1,\ldots , a_n$ dolo"cajo navaden veri"zen ulomek $x_n=[a_0; a_1,\ldots , a_n]$. Tako dobimo novo zaporedje "stevil $(x_n)_{n=0}^\infty$. "Cleni s sodim indeksom tvorijo podzaporedje, ki po izreku~\ref{izrek:C} strogo nara"s"ca in je navzgor omejeno s poljubnim "clenom lihega indeksa, torej je konvergentno. Ozna"cimo limito z $a$. Podobno "cleni z lihim indeksom tvorijo podzaporedje, ki strogo pada in je navzdol omejeno s poljubnim "clenom sodega indeksa, torej je konvergentno. Ozna"cimo limito z $b$. Izrek~\ref{izrek:C} v kombinaciji z izrekom~\ref{izrek:D} nam pove tudi, da je $|x_n-x_{n-1}|=\frac{1}{q_nq_{n-1}}\leq \frac{1}{n(n+1)}$. Torej pridejo "cleni z lihim indeksom poljubno blizu "clenom s sodim indeksom. Sledi, da je $a=b$. Torej zaporedje $x_n$ zmeraj konvergira, kakor smo napovedali "ze v uvodu. Tako lahko zaporedju $a_0, a_1,\ldots $ priredimo veri"zni ulomek $[a_0;a_1,a_2,\ldots]$, katerega vrednost je $$a=\lim_{n\to\infty}x_n,$$ in pi"semo $a=[a_0;a_1,a_2,\ldots]$. S protislovjem doka"zimo, da je $a$ iracionalno "stevilo. Torej recimo, da je $a$ racionalno "stevilo, ki mu pripada veri"zni ulomek $[b_0;b_1,b_2,\ldots, b_n]$, $b_n\neq 1$. "Ce obstaja $a_i$, $i\leq n$, da $b_i \neq a_i$ (vzemimo takega z najmanj"sim indeksom), bodo po izreku~\ref{primerjava} vsi pribli"zki $x_j$ za $j\geq i+2$ strogo manj"si ali strogo ve"cji od $[b_0;b_1,b_2,\ldots, b_n]=a$. Ker lihi pribli"zki padajo proti $a$, bodo vsi pribli"zki $x_j$ za $j\geq i+2$ strogo ve"cji od $a$, kar pa je v protislovju s tem, da sodi pribli"zki rastejo k $a$. Torej je $b_i=a_i$ za vsak $i\leq n$. Torej je $a=x_n$. Ker pa sodi pribli"zki strogo nara"s"cajo proti $a$, lihi pa strogo padajo, noben izmed njih ne more biti enak $a$. Protislovje. Zgornje ugotovitve zdru"zimo v izrek: \begin{izrek} \label{izrek:E} Neskon"cen veri"zni ulomek $[a_0; a_1,\ldots]$ dolo"ca neko iracionalno "stevilo $a$. K temu "stevilu konvergirajo pribli"zki $[a_0; a_1,\ldots, a_n]=x_n = \frac{p_n}{q_n}$. Za vsak $n = 0,1,\ldots$ je $a$ med "steviloma $x_n$ in $x_{n+1}$ in velja ocena $$0<|a -\frac{p_n}{q_n}|<\frac{1}{q_{n+1}q_n}.$$ \end{izrek} \begin{dokaz} Izrek smo v glavnem "ze dokazali, zato poka"zimo le zadnjo neenakost. Slednja velja, ker so $x_n$ racionalni, torej: $$0<|a -x_n|<|x_{n+1}-x_n|=\frac{1}{q_{n+1}q_n}.$$ \end{dokaz} \begin{posledica} Veri"zni ulomek je kon"cen natanko tedaj, ko predstavlja racionalno "stevilo. \end{posledica} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Izrazitev iracionalnega "stevila z veri"znim ulomkom} \label{section:IRN} Naj bo $a$ iracionalno "stevilo. Definirajmo zaporedje $(v_i)_{i=0}^\infty$: $$v_0=a\mathrm{\hspace{5mm}in\hspace{5mm}} v_i=\frac{1}{v_{i-1}-\lfloor v_{i-1}\rfloor}\mathrm{\ \ za\ \ }i>0.$$ Vidimo, da velja $$a=\lfloor v_0\rfloor+\frac{1}{v_1}=[\lfloor v_0\rfloor;v_1].$$ Ker posledi"cno velja tudi $v_1=[\lfloor v_1\rfloor;v_2]$ in zato $a=[\lfloor v_0\rfloor;\lfloor v_1\rfloor,v_2]$, nam indukcija za vsk $n$ doka"ze $$a=[\lfloor v_0\rfloor;\lfloor v_1\rfloor,\lfloor v_2\rfloor,\ldots ,\lfloor v_{n-1}\rfloor, v_n].$$ \noindent Za vsak $i\in \mathbb{N}_0$ definirajmo $$a_i=\lfloor v_i \rfloor.$$ Ker je $a$ iracionalen, so vsi $v_i$ iracionalni in zato $1>v_i-\lfloor v_i\rfloor>0$. Torej so za $i\in \mathbb{N}_0$, vsi $v_{i+1}$ med 0 in 1. Zato so vsi $a_i$ naravna "stevila, $a_0$ pa je celo. Zaporedje $(a_i)_{i=0}^\infty$ torej dolo"ca neskon"cen veri"zni ulomek $[a_0;a_1,\ldots]$, katerega pribli"zke $[a_0;a_1,\ldots,a_n]$ ozna"cimo z $x_n$. Ker je $a=[\lfloor v_0\rfloor;\lfloor v_1\rfloor,\lfloor v_2\rfloor,\ldots ,\lfloor v_{n-1}\rfloor, v_n]$, so sodi $x_n$ manj"si od $a$, lihi pa ve"cji. Ker je zaporedje $(x_n)_{n=0}^\infty$ konvergentno, je $a$ njegova limita. \newline Torej smo za poljubno iracionalno "stevilo skonstruirali neskon"cen veri"zni ulomek, ki mu je enak. Poka"zimo "se, da dva neskon"cna veri"zna ulomka predstavljata isto iracionalno "stevilo natanko tedaj, ko imata enake koeficiente. Vse kar "se moramo pokazati je, da iz $[a_0;a_1,\ldots]=[b_0;b_1,\ldots]$ sledi $a_i=b_i$ za vse $i\in \mathbb{N}_0$. Doka"zimo to s protislovjem. Denimo torej, da obstaja tak najmanj"si indeks $n$, da $a_i\neq b_i$. Brez "skode za splo"snost smemo privzeti $a_i< b_i$. Ozna"cimo $x_k=[a_0;a_1,\ldots,a_k]$ in $y_k=[b_0;b_1,\ldots,b_k]$. Iz izreka~\ref{primerjava} sledi, da je za vsak $k>n+1$ $x_k>y_k$, ali pa je za vsak $k>n+1$ $x_k0.$$ \end{izrek} \begin{zgled} Pri tem postopku dobimo za $\sqrt[3]{2}$ neskon"cni veri"zni ulomek $[1; 2, 1, 5, 1,\ldots].$ \end{zgled} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Periodi"cni veri"zni ulomki} Neskon"cen veri"zni ulomek je periodi"cen, "ce ima obliko $[a_0; a_1,\ldots,a_n,b_0,\ldots, b_{k-1}, b_0,\ldots,b_{k-1},\ldots]$. Od $n+1$-vega mesta se periodi"cno ponavlja skupina naravnih "stevil $b_0,\ldots,b_{k-1}$, ki sestavljajo periodo dol"zine $k$. Notacija: $[a_0; a_1,\ldots,a_n,\overline{b_0,\ldots, b_{k-1}}].$ \begin{izrek} \label{izrek:G} "Stevilo, ki ga dolo"ca periodi"cni veri"zni ulomek, je kvadratna iracionala; torej je oblike $s + t\sqrt{m}$, kjer sta $s$ in $t$ racionalni "stevili, $m$ pa naravno "stevilo, ki ni popoln kvadrat. \end{izrek} \begin{dokaz} Poglejmo si veri"zni ulomek $b=[\overline{b_0;b_1,\ldots, b_{k-1}}]$. Vilja $b=[b_0;b_1,\ldots, b_{k-1},b]$ in izrek~\ref{izrek:B} nam za $k\geq 2$ da $$b=\frac{p_k}{q_k}=\frac{bp_{k-1}+p_{k-2}}{bq_{k-1}+q_{k-2}}.$$ Za $k=1$ velja isti izraz, "ce definiramo $p_{-1}=1$, $q_{-1}=0$. Po preoblikovanju dobimo $$q_{k-1}b^2+(q_{k-2}-p_{k-1})b-p_{k-2}=0.$$ Tu $q_{k-1}$ ne more biti $0$, saj je naravno "stevilo. Vemo torej, da je $b$ re"sitev kvadratne ena"cbe s celimi koeficienti in da je iracionalno "stevilo. Iz tega sledi, da je koren iz diskriminante zgornje ena"cbe kvadratna iracionala, kar nam zagotavlja, da je tudi $b$ kvadratna iracionala. \end{dokaz} \begin{izrek} \label{izrek:H} Neskon"cen veri"zni ulomek, ki se dobi pri razvoju kvadratne iracionale, je periodi"cen. \end{izrek} \begin{dokaz} Pri razvoju kvadratne iracionale dobimo neskon"cen veri"zni ulomek. I"s"cemo periodi"cnost. Kvadratna iracionala $\alpha =s+t\sqrt{m}$ je koren ena"cbe $(x-s-t\sqrt{m})(x-s+t\sqrt{m}) = x^2 - 2sx + s^2 - mt^2 = 0$. "Ce jo pomno"zimo s kvadratom najmanj"sega skupnega ve"ckratnika imenovalcev pri $s$ in $t$, dobimo ena"cbo $ax^2 + bx+c=0$, $a,b,c\in\mathbb{Z}$. Razvijmo $\alpha$ v neskon"cni veri"zni ulomek $\alpha = [a_0;a_1,\ldots]$. "Ce postavimo $\gamma = \gamma_n = [a_{n+1},\ldots]$, je $\alpha = [a_0;a_1,\ldots,a_n,\gamma]$ in po izreku~\ref{izrek:B} dobimo $\alpha = \frac{\gamma p_n + p_{n-1}}{\gamma q_n + q_{n-1}}$. Ker $\alpha$ re"si ena"cbo $ax^2 + bx+c=0$, je $$a(\gamma p_n + p_{n-1})^2 + b(\gamma p_n + p_{n-1})(\gamma q_n + q_{n-1})+c(\gamma q_n + q_{n-1})^2=0.$$ Odpravimo oklepaje in pi"semo:$$A_n = ap_n^2 + bp_nq_n + cq_n^2,$$ $$B_n = 2ap_n p_{n-1} +b(p_nq_{n-1}+p_{n-1}q_n)+ 2cq_nq_{n-1},$$ $$C_n =ap_{n-1}^2 + bp_{n-1}q_{n-1} + cq_{n-1}^2,$$ $A_n, B_n, C_n\in\mathbb{Z}$. Dobimo kraj"se zapisano ena"cbo: $$A_n\gamma^2 + B_n\gamma + C_n =0.$$ "Ce bi za kak"sen $n$ veljalo $A_n = 0$, bi to pomenilo, da je $ap_n^2 + bp_nq_n + cq_n^2 = 0$, torej bi $\frac{p_n}{q_n}$ bil koren ena"cbe $ax^2 + bx+c=0$. To ne gre, ker je $\frac{p_n}{q_n}$ za vsak $n$ racionalno "stevilo, korena ena"cbe pa sta iracionalna. Zato $A_n \neq 0$ in $\gamma$ je eden od korenov ena"cbe $A_ny^2 + B_ny + C_n =0.$ Le-ta ima diskriminanto: $$B_n^2 - 4A_nC_n =(b^2 -4ac)(p_nq_{n-1}-p_{n-1}q_n)^2 = b^2 -4ac.$$ Po izreku~\ref{izrek:E} je $0<|\alpha - \frac{p_n}{q_n}|<\frac{1}{q_nq_{n+1}}\leq \frac{1}{q_n^2}$. Od tod je $0<|\alpha q_n - p_n|<\frac{1}{q_n}$. Vemo, da se $p_n$ da izraziti kot $p_n=\alpha q_n+\frac{\delta_n}{q_n}$, $\delta_n\in\mathbb{R}$, za katerega velja $|\delta_n|<1$. Dobljeno ena"cbo vstavimo v ena"cbo za $A_n$ in dobimo: $A_n = (a\alpha^2 + b\alpha + c)q_n^2 + 2a\alpha \delta_n + a\frac{\delta_n^2}{q_n^2}+b\delta_n$. Ker je $\alpha$ koren ena"cbe $ax^2 + bx+c=0$, je prvi "clen na desni $0$. Zaradi $|\delta_n|<1$ in $q_n^2\geq 1$ sledi ocena: $|A_n|<2|a\alpha|+|a|+|b|.$ Ta ocena dr"zi za vsak $n > 1$. Vidimo tudi, da je $C_n = A_{n-1}$ in zato $|C_n|<2|a\alpha|+|a|+|b|$. "Se ocena za $B_n$: $B_n^2 = b^2 -4ac + 4 A_nC_n1$, so $A_n, B_n, C_n$ po absolutni vrednosti omejena cela "stevila. Zato je v zaporedju $((A_n,B_n,C_n))_{n=2}^\infty$ le kon"cno mnogo razli"cnih "clenov. Sledi: ena izmed trojic $(A_n,B_n,C_n)$ se mora najmanj trikrat ponoviti. Naj bo $A,B,C$ taka trojica; nastopi, ko je $n$ enak $n_10\}$, $f(x,y)= \frac{1}{\sqrt{3}}|\sqrt{2}x-y|$. I"s"cemo minimum te kriterijske funkcije. RE"SITEV: O"citno je $f$ pozitivna funkcija brez ni"cle na $D$. Doka"zimo, da lahko najdemo taka naravna $x$ in $y$, da bo $|\sqrt{2}x-y|$ poljubno malo. Najprej razvijmo $\sqrt{2}$ v veri"zni ulomek. Ker je kvadratna iracionala vemo, da bomo dobili periodi"cnega. $$\sqrt{2} = 1 + (\sqrt{2}-1) = 1 + \frac{1}{\frac{1}{{\sqrt{2}-1}}\cdot \frac{\sqrt{2}+1}{\sqrt{2}+1}}= 1+\frac{1}{\sqrt{2}+1}= 1+\frac{1}{2 + (\sqrt{2}-1)}.$$ Ker smo dobili enak ostanek kot na za"cetku, opazimo, da se nam bo $2$ ponavljala. Torej $\sqrt{2} = [1;\overline{2}].$ Izrazimo $p_n$ in $q_n$ eksplicitno. Re"siti moramo diferen"cni ena"cbi: $$p_0 = 1,\hspace{5mm} p_1 = 2\cdot 1 + 1=3,\hspace{5mm} p_n = 2p_{n-1} + p_{n-2}$$ \hfill ter\hfill \phantom{1} $$q_0 = 1,\hspace{5mm} q_1 = 2,\hspace{5mm} q_n = 2q_{n-1} + q_{n-2}.$$ \noindent Dobimo re"sitvi: $$p_n=\frac{1}{2}(1+\sqrt{2})^{n+1}+\frac{1}{2}(1-\sqrt{2})^{n+1}$$ \hfill ter\hfill \phantom{1} $$q_n=\frac{\sqrt{2}}{4}(1+\sqrt{2})^{n+1}-\frac{\sqrt{2}}{4}(1-\sqrt{2})^{n+1}.$$ \noindent Velja: $$|\sqrt{2}q_n-p_n|=|(1-\sqrt{2})^{n+1}|.$$ \noindent Ker je $|1-\sqrt{2}|<1$, zaporedje na desni strani enakosti konvergira proti $0$. Za vsak $n\in \mathbb{N}$ smo torej na"sli taki naravni "stevili $x=q_n$ in $y=p_n$, da je $|\sqrt{2}x-y|<|(1-\sqrt{2})^{n+1}|$, kar gre proti 0. Do istega zaklju"cka bi pri"sli tudi brez razvoja $\sqrt{2}$ v veri"zni ulomek z uporabo izrekov~\ref{izrek:D} in~\ref{izrek:E}: $$|\sqrt{2}q_n-p_n|=q_n|\sqrt{2}-x_n|\leq q_n\frac{1}{q_nq_{n+1}}<\frac{1}{n}$$ Torej gre za omejeno optimizacijsko nalogo, kjer optimum ni dose"zen. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Uporaba veri"znih ulomkov pri re"sevanju Fermatove ena"cbe} Fermatova ena"cba je ena"cba oblike $$x^2-my^2=1,$$ kjer je $m\in \mathbb{N}$. I"s"cemo re"sitve, za katere sta $x$ in $y$ naravni "stevili. Za $m$, ki ni kvadrat naravnega "stevila, je re"sitev ena"cbe neskon"cno. Znan je tudi postopek, kako iz ene re"sitve dobimo vse ostale. Pri iskanju prve re"sitve pa nam lahko pomagajo veri"zni ulolmki. Najprej navedimo izrek: \begin{izrek} Naj bo $\alpha$ iracionalno "stevilo in $a,b$ tuji celi "stevili. "Ce dr"zi ocena $$|\frac{a}{b}-\alpha|<\frac{1}{2b},$$ je $\frac{a}{b}$ pribli"zek iz razvoja "stevila $\alpha$ v neskon"cen veri"zni ulomek. \end{izrek} Dokaz najdemo v [1], str. 124. In kako nam ta izrek pomaga pri re"sevanju Fermatove ena"cbe? Naj bo $m\geq 5$ in $(x_1,y_1)$ re"sitev ena"cbe. Potem velja $$x_1^2-my_1^2=1$$ in posledi"cno $$x_1-y_1\sqrt{m}=\frac{1}{x_1+y_1\sqrt{m}}.$$ Ker je $y_1\in \mathbb{N}$, lahko z njim delimo. Dobimo $$\frac{x_1}{y_1}-\sqrt{m}=\frac{1}{y_1x_1+y_1^2\sqrt{m}}<\frac{1}{2y_1^2}.$$ "Stevilo $\sqrt{m}$ je iracionalno, zato mora $\frac{x_1}{y_1}$ biti med pribli"zki iz razvoja $\sqrt{m}$ v veri"zni ulomek. \bigskip \medskip \noindent\textbf{Literatura} \begin{itemize} \item[{[1]}] Jo"ze Grasselli, \textsl{Diofantske ena"cbe}, Dru"stvo matematikov, fizikov in astronomov, Ljubljana, 1984 \item[{[2]}] B.~H.~Korte, J.~Vygen, \textsl{Combinatorial optimization: Theory and algorithms}, 3.~izdaja, Springer, Berlin-Heidelberg, 2006 \item[{[3]}] http://demonstrations.wolfram.com/ContinuedFractions/ \item[{[4]}] http://sl.wikipedia.org/wiki/Veri"zni\_ulomek \end{itemize} \end{document}