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 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} .

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. (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}} koji dobro aproksimira zadani iracionalni 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 \alpha} .

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

No, ovo je prilično gruba aproksimacija. Za bolju, dijelit ćemo segment 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 I} na sve više dijelova, tj. podintervala. Recimo da smo 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 I} podijelili na točno 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 \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 $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 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 1 \leq q \leq Q = 100} slijedi 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} \leq \frac{1}{q} } . Zato 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 |q\sqrt{2} - p| \leq \frac{1}{100} < \frac{1}{q}. }

Evidentno je da, uz to, mora biti 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|| = |q\sqrt{2} - p| \leq \frac{1}{100}.}

Slično, ako je pak 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 1 < Q < Q' < Q + 1 } očito 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 \frac{1}{Q'} < \frac{1}{Q} } pa teorem vrijedi i u tom slučaju.

Jasno je da je nejednakost 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\sqrt{2} - p| \leq \frac{1}{100} < \frac{1}{q}, } ekvivalentna s 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 |\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.