Dirichletov teorem

Dirichletov teorem je jedan od najvažnijih rezultata u teoriji brojeva, a izniče u njenoj disciplini pod nazivom diofantske aproksimacije, nazvane po starogrčkom matematičaru Diofantu.

Iskaz teorema glasi ovako.

Ako su $\alpha ,Q$ realni brojevi i $Q>1$, tada postoje cijeli brojevi $p,q$ takvi da vrijedi $1\leq q<Q$ te $||q\alpha ||=|q\alpha -p|\leq {\frac {1}{Q}}$.

Oznaka $||q\alpha ||$ predstavlja udaljenost od $q\alpha$ do njemu najbližeg cijelog broja. Dakle, općenito vrijedi $||\alpha ||={\text{min}}(\{{\alpha }\},1-\{{\alpha }\})$ gdje je $\{{\alpha }\}=\alpha -\left\lfloor \alpha \right\rfloor$ razlomljeni dio od $\alpha$.

Ovaj je teorem prvi dokazao njemački matematičar Dirichlet još 1842. godine.

Motivacija

Jedno od glavnih pitanja diofantskih aproksimacija je naći racionalan broj Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle {\frac {p}{q}}} koji dobro aproksimira zadani iracionalni broj $\alpha$.

Osnovni postupak koji bismo mogli učiniti je da lociramo između koja dva prirodna broja se nalazi iracionalan broj $\alpha$. Jasno je da su ta dva tražena prirodna broja $\left\lfloor \alpha \right\rfloor ,\left\lfloor \alpha +1\right\rfloor$ pa se $\alpha$ očito nalazi u segmentu $I=[\left\lfloor \alpha \right\rfloor ,\left\lfloor \alpha +1\right\rfloor ]$.

No, ovo je prilično gruba aproksimacija. Za bolju, dijelit ćemo segment $I$ na sve više dijelova, tj. podintervala. Recimo da smo $I$ podijelili na točno Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle q\in \mathbb {N} } jednakih dijelova.

Pitamo se koji je od racionalnih brojeva Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\lfloor\alpha\right\rfloor + \frac{1}{q},\left\lfloor\alpha\right\rfloor + \frac{2}{q}, ..., \left\lfloor\alpha\right\rfloor + \frac{q}{q} = \left\lfloor\alpha\right\rfloor + 1 } najbliži broju Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} . Neka je to Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \left\lfloor\alpha\right\rfloor + \frac{k}{q} = \frac{p}{q}} .

Očigledno je onda Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\alpha - \frac{p}{q}| < \frac{1}{2} \cdot \frac{1}{q} } jer je svaki podsegment duljine Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{q}} pa Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} mora biti udaljen od rubne točke podsegmenta u kojem pripada za manje od polovice njegove duljine. Valja uočiti da treba biti stroga nejednakost jer Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} ne može biti udaljen od Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{p}{q}} za točno pola duljine posegmenta, odnosno Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{2q}} , jer je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha} iracionalan.

Vidimo da ovime birajući broj Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} generiramo točno jedan Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} tako da je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d(\alpha, \frac{p}{q}) < \frac{1}{2q}} .

No, ovo nije naročito dobra aproksimacija. Na primjer, ako želimo da bude Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d < \frac{1}{10000} } trebamo za nazivnik uzeti čak Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q = 5000 } da bi ova aproksimacija uspjela.

Dirichletov će nam teorem dati puno bolje aproksimacije, Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\alpha - \frac{p}{q}| < \frac{1}{q^2}} , ali za manje parova Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (p, q)} . Naime, želimo li da bude Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d(\alpha, \frac{p}{q}) < \frac{1}{10 000}} , Dirchletov teorem kaže da će postojati barem jedan broj Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} za koji će ta aproksimacija uspjeti i to za nazivnike Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle q} manje ili jednake Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 100.}

Dokazat ćemo Dirichletov teorem u ekvivalentnom (skaliranom) obliku, dakle Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |q\alpha - p| < \frac{1}{q}.}

Pomoćna lema

Neka imamo dva realna broja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x < y. } Tada je s brojevnog pravca očito da vrijedi Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x - y| = |\left\lfloor x \right\rfloor - \left\lfloor y \right\rfloor| \pm |\{x\} - \{y\}|.}

Dakle, vidimo da na udaljenosti Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |\{x\} - \{y\}| } od Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x - y|} postoji prirodni broj, i to s obje strane broja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle |x - y|.}

Primjer i dokaz

Uzmimo Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha = \sqrt{2}, Q = 100} .

Dakle, želimo dokazati da među brojevima u skupu Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = \{0, \sqrt{2}, 2\sqrt{2}, 3\sqrt{2},..., 100\sqrt{2}\}} postoji barem jedan koji je udaljen od nekog cijelog broja za manje od Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{1}{Q} = \frac{1}{100} } .

Jasno je da je dovoljno promatrati razlomljene (decimalne) dijelove brojeva u skupu Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S.}

U tu svrhu, promotrimo skup $S'=\{0,\{{\sqrt {2}}\},\{2{\sqrt {2}}\},...,\{100{\sqrt {2}}\}\}.$

Kako su svi članovi skupa $S'$ u segmentu $[0,1)$, podijelimo taj segment na 100 podintervala. Dobivamo $[0,{\frac {1}{100}}),[{\frac {1}{100}},{\frac {2}{100}}),...,[{\frac {99}{100}},1).$

Prema Dirichletovom principu je očito da barem dva broja (ili više) $\{x{\sqrt {2}}\},\{y{\sqrt {2}}\}$ iz Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle S} pripadaju istom podintervalu.

Prema tome, postoje barem dva $x,y\in \{0,1,2,...,100\},x\neq y$ takvi da je $0\leq |\{x{\sqrt {2}}\}-\{y{\sqrt {2}}\}|<{\frac {1}{100}}$.

Prema pomoćnoj lemi slijedi da na udaljenosti $|\{x{\sqrt {2}}\}-\{y{\sqrt {2}}\}|$ od broja $x{\sqrt {2}}-y{\sqrt {2}}={\sqrt {2}}(x-y)$ postoji $p\in \mathbb {Z}$.

Kako je $1\leq |x-y|\leq Q=100$ stavimo $q=|x-y|$. (Postojanje brojeva $x,y$ očito dokazuje postojanje broja $q.$)

Ovime smo dokazali da postoje $p,q\in \mathbb {Z} ,1\leq q\leq 100$ takvi da je $|q{\sqrt {2}}-p|<{\frac {1}{Q}}={\frac {1}{100}}.$

Zbog toga što je $1\leq q\leq Q=100$ slijedi ${\frac {1}{Q}}={\frac {1}{100}}\leq {\frac {1}{q}}$. Zato vrijedi $|q{\sqrt {2}}-p|\leq {\frac {1}{100}}<{\frac {1}{q}}.$

Evidentno je da, uz to, mora biti $||q\alpha ||=|q{\sqrt {2}}-p|\leq {\frac {1}{100}}.$

Slično, ako je pak $1<Q<Q'<Q+1$ očito je ${\frac {1}{Q'}}<{\frac {1}{Q}}$ pa teorem vrijedi i u tom slučaju.

Jasno je da je nejednakost $|q{\sqrt {2}}-p|\leq {\frac {1}{100}}<{\frac {1}{q}},$ ekvivalentna s $|{\sqrt {2}}-{\frac {p}{q}}|\leq {\frac {1}{100q}}<{\frac {1}{q^{2}}},$ čime smo pokazali Dirichletov teorem u aproksimacijskom obliku sličnom uvodnom primjeru.

Analogno se pokazuje za bilo koji Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha \geq 0, Q > 1, } a onda očito i za Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha < 0} .

Zanimljivosti

Dirichlet je u svome dokazu ovog teorema, po prvi puta koristio elementarnu i jednu od najvažnijih metoda u kombinatorici, poznatu pod nazivom Dirichletov princip (u nas još poznatu kao princip kutija ili pak u stranoj literaturi kao “princip pretinaca” i “princip golubinjaka”), koja upravo zato nosi njegovo ime.