Continued fraction expansion of irrational numbers

In this section we use continued fractions for expansion of irrational numbers.

Theorem 1. Let $\displaystyle (x_n)_{n\geq 0}$ be a sequence of intergers with $\displaystyle x_i>0$ for every $\displaystyle i>0$ . Then the sequence $\displaystyle (p_n/q_n)_{n\geq 0}$ is a convergent sequence, and the its limit is an irrational number. We denote this limit by $\displaystyle [x_0;x_1,x_2,\ldots]$ .

Proof. From [1] we have $\displaystyle q_1\geq q_0=1>0$ and for all $\displaystyle n>1$ , $\displaystyle q_n=x_nq_{n-1}+q_{n-2},$ hence by induction on $\displaystyle n$ , $\displaystyle q_{n+1}>q_n$ for every $\displaystyle n\geq 1$ . Therefore $\displaystyle\lim_{n\to \infty}q_n=\infty$ .

By the Proposition 4 in [1], for all $\displaystyle n\geq 0$ ,

$\displaystyle \frac{p_n}{q_n}-\frac{p_{n+1}}{q_{n+1}}=\frac{(-1)^{n-1}}{q_nq_{n+1}},\quad\quad (1)$

hence $\displaystyle \frac{p_n}{q_n}-\frac{p_{n+2}}{q_{n+2}}=\frac{(-1)^{n-1}(q_{n+2}-q_n)}{q_nq_{n+1}q_{n+2}},\quad \forall n\geq 0.$ Therefore

$\displaystyle \frac{p_1}{q_1}>\frac{p_3}{q_3}>\frac{p_5}{q_5}>\ldots>\frac{p_0}{q_0}$

and

$\displaystyle \frac{p_0}{q_0}<\frac{p_2}{q_2}<\frac{p_4}{q_4}<\ldots<\frac{p_1}{q_1},$

hence $\displaystyle (p_{2n}/q_{2n})_{n\geq 0}$ and $\displaystyle (p_{2n+1}/q_{2n+1})_{n\geq 0}$ are convergent sequences. By (1) and $\displaystyle q_n\to\infty$ we have

$\displaystyle\lim_{n\to\infty}\frac{p_{2n}}{q_{2n}}=\lim_{n\to\infty}\frac{p_{2n+1}}{q_{2n+1}},$ so $\displaystyle (p_n/q_n)_{n\geq 0}$ is a convergent sequence.

Now we prove $\displaystyle \displaystyle \alpha:=\lim_{n\to\infty}\frac{p_n}{q_n}$ is an irrational number. We have

$\displaystyle \frac{p_{2m}}{q_{2m}}<\alpha<\frac{p_{2n+1}}{q_{2n+1}},\quad\forall m,n\geq 0.$

Thus, by (1),

$\displaystyle\left|\alpha-\frac{p_{2n}}{q_{2n}}\right|\leq \frac{1}{q_{2n}q_{2n+1}}<\frac{1}{q_{2n}^2},\quad\forall n\geq 1.$

By the Proposition 2 in [1], $\displaystyle p_{2n}$ and $\displaystyle q_{2n}$ are coprime integers for every $\displaystyle n\geq 1$ , hence there are infinite rational numbers $\displaystyle r/s$ , with $\displaystyle s>0$ and $\displaystyle (r,s)=1$ , such that

$\displaystyle \left|\alpha-\frac{r}{s}\right| <\frac{1}{s^2}.\quad\quad (2)$

Assume that $\displaystyle \alpha$ is rational and write $\displaystyle \alpha=p/q$ , where $\displaystyle p$ and $\displaystyle q>0$ are coprime integers. For all positive integers $\displaystyle s$ , at most two integers $\displaystyle r$ satisfy the equation (2), hence there are coprime integers $\displaystyle r_0$ and $\displaystyle s_0>q$ such that

$\displaystyle\left|\frac{p}{q}-\frac{r_0}{s_0}\right| <\frac{1}{s_0^2}.$

From the inequality we have $\displaystyle \mid ps_0-qr_0\mid <1$ , hence $\displaystyle ps_0=qr_0$ , a contradiction. Therefore $\displaystyle \alpha$ is an irrational number. $\Box$

Theorem 2. Let $\displaystyle \alpha$ be an irrational number. Then there is a unique sequence of integers $\displaystyle (a_n)_{n\geq 0}$ such that

(1) $\displaystyle a_i>0$ for every $\displaystyle i>0$ .

(2) $\displaystyle \alpha =[a_0;a_1,a_2,\ldots]$ .

Proof. In this proof, $\displaystyle [x]$ is the integer part of $\displaystyle x$ . Because $\displaystyle \alpha$ is an irrational number, we have $\displaystyle [\alpha]<\alpha<[\alpha]+1$ , hence there is a real number $\displaystyle u_1>1$ such that

$\displaystyle \alpha=[\alpha]+\frac{1}{u_1}.$

Because $\displaystyle \alpha$ is an irrational and $\displaystyle [\alpha]$ is an integer, $\displaystyle u_1$ is an irrational number. Hence there is an irrational number $\displaystyle u_2>1$ such that

$\displaystyle u_1=[u_1]+\frac{1}{u_2},$

and so on. Therefore we have real numbers $\displaystyle u_0:=\alpha$ , $u_1>1$ , $\displaystyle u_2>1$ , $\displaystyle \ldots$ such that $\displaystyle u_i$ is irrationals for every $\displaystyle i>0$ and

$\displaystyle u_k=[u_k]+\frac{1}{u_{k+1}},\quad\forall k\geq 0.$

We claim that $\displaystyle \alpha=[[u_0];[u_1],[u_2],\ldots]$ . Fix a $\displaystyle k>2$ . We have

$\displaystyle \alpha=[[u_0];[u_1],\ldots, [u_k],u_{k+1}].$

Hence, by Proposition 4 in [1],

$\displaystyle \left|\alpha-\frac{p_k}{q_k}\right|=\frac{1}{q_k(u_{k+1}q_{k}+q_{k-1})}<\frac{1}{q_k^2},$

so $\displaystyle \lim_{n\to\infty}\frac{p_n}{q_n}=\alpha$ . Now assume that

$\displaystyle \alpha =[a_0;a_1,a_2,\ldots]=[b_0;b_1,b_2,\ldots],$

where $\displaystyle (a_n)_{n\geq 0}$ and $\displaystyle (b_n)_{n\geq 0}$ are two sequences of integers such that $\displaystyle a_i>0$ and $\displaystyle b_i>0$ for every $\displaystyle i>0$ .

Because

$\displaystyle [a_0;a_1,a_2,\ldots,a_{n}]=a_0+\frac{1}{[a_1;a_2,\ldots,a_n]},\quad\forall n\geq 0,$

we have

$\displaystyle [a_0;a_1,a_2,\ldots]=a_0+\frac{1}{[a_1;a_2,\ldots]}.$

Hence $\displaystyle a_0=b_0=[\alpha]$ and $\displaystyle [a_1;a_2,a_3,\ldots] = [b_1;b_2,b_3,\ldots]$ . Similarly, $\displaystyle a_1=b_1$ and

$\displaystyle [a_2;a_3,a_4,\ldots] = [b_2;b_3,b_4,\ldots],$

and so on. Therefore $\displaystyle a_i=b_i$ for every $i$ . $\Box$

The equality in the theorem is called an expansion of $\displaystyle \alpha$ into a infinite continued fraction. In that expansion we will call $\displaystyle [a_0;a_1,a_2,\ldots,a_i]$ is the $\displaystyle i-$ th convergent of the continued fraction, or $\displaystyle i-$ th convergent of $\displaystyle \alpha$ . The theorem says that for every irrational number has an expansion into a infinite continued fraction, and this expansion is unique.

Example 1. $\displaystyle \sqrt{2}=[1;2,2,\ldots]$ .

Example 2. The golden ratio $\displaystyle\varphi:=\frac{1+\sqrt{5}}{2}=[1;1,1,\ldots]$ .

Example 3. $\displaystyle e=[2;1,2,1,1,4,1,1,6,1,1,8,\ldots]$ .

A sequence $\displaystyle (a_n)_{n\geq 0}$ is called eventually periodic if $\displaystyle a_{n+T}=a_n$ for some positive integer $\displaystyle T$ and sufficiently large $\displaystyle n$ . A real number is called quadratic irrational number, if there is a polynomial $\displaystyle P(x)$ is of degree two with rational coefficients such that $\displaystyle P(x)$ is an irreducible polynomial (see [3]) over the rational numbers and $\displaystyle \alpha$ is a root of $\displaystyle P(x)$ .

Theorem 3. Let $\displaystyle \alpha$ be an irrational number and $\displaystyle \alpha =[a_0;a_1,a_2,\ldots]$ is the expansion of $\displaystyle\alpha$ into a infinite continued fraction. Then $\displaystyle (a_n)_{n\geq 1}$ is eventually periodic if and only if $\displaystyle \alpha$ is a quadratic irrational.

References

[1] https://nttuan.org/2008/10/12/continued-fractions-the-basics/

[2] https://nttuan.org/2008/11/14/continued-fraction-expansion-of-rational-numbers/

[3] https://nttuan.org/2009/01/11/poly02/

Continued fraction expansion of rational numbers

In this section we use continued fractions ([2]) for expansion of rational numbers. If $\displaystyle x_0$ , $\displaystyle x_1$ , $\displaystyle \ldots$ , are integer nunbers with $\displaystyle x_i>0$ for every $\displaystyle i>0$ then $\displaystyle [x_0;x_1,x_2,\ldots,x_n]\in\mathbb{Q},\quad\forall n\geq 0.$

Conversly, we have the theorem

Theorem 1. Let $\displaystyle r$ and $\displaystyle s$ be coprime integers with $\displaystyle s>0$ . Then there are non negative integer $\displaystyle n$ and integers $\displaystyle a_0$ , $\displaystyle a_1$ , $\displaystyle \ldots$ , $\displaystyle a_n$ such that

(1) $\displaystyle a_i>0$ for every $\displaystyle i=1,2,\ldots,n$ .

(2) $\displaystyle r/s=[a_0;a_1,a_2,\ldots,a_n]$ .

Proof. Let us proceed by induction on $\displaystyle s$ . The case $\displaystyle s=1$ is trivial. Now suppose that the assertion is true for all positive integers up to $\displaystyle s-1$ ( $\displaystyle s>1$ ). Because $\displaystyle (r,s)=1$ and $\displaystyle s>1$ , we have $\displaystyle s\nmid r$ . Hence by the Division Algorithm ([1]), there are integers $\displaystyle a$ and $\displaystyle b$ such that

$\displaystyle r=sa+b,\quad 1\leq b<s.\quad\quad (1)$

By the hypothesis of the induction, there are integers $\displaystyle m>0$ , $\displaystyle a_1$ , $\displaystyle a_2>0$ , $\displaystyle \ldots$ , $\displaystyle a_m>0$ such that

$\displaystyle \frac{s}{b}=[a_1;a_2,a_3,\ldots,a_m].\quad\quad (2)$

Because $\displaystyle s>b$ , we have $\displaystyle a_1>0$ . From (1) and (2) we have

$\displaystyle \frac{r}{s}=a+\frac{1}{s/b}=a+\frac{1}{[a_1;a_2,a_3,\ldots,a_m]}=[a;a_1,a_2,\ldots,a_m],$ completing the induction step. $\Box$

The equality in the theorem is called an expansion of $\displaystyle r/s$ into a finite continued fraction. In that expansion we will call $\displaystyle [a_0;a_1,a_2,\ldots,a_i]$ is the $i-$ th convergent of the continued fraction, or $i-$ th convergent of $\displaystyle r/s$ .

Example 1. Find an expansion of $\displaystyle 43/5$ into a finite continued fraction.

Solution. By the Division Algorithm, we have

$\displaystyle 43=5\cdot 8+3\quad\quad\frac{43}{5}=8+\frac{3}{5}=8+\frac{1}{5/3},$ and

$\displaystyle 5= 3\cdot 1 +2\quad\quad\frac{5}{3}=1+\frac{2}{3}=1+\frac{1}{3/2},$ and $\displaystyle \frac{3}{2}=1+\frac{1}{2}$ . Therefore $\displaystyle 43/5=[8;1,1,2]$ . $\Box$

The theorem says that for every rational number has an expansion into a finite continued fraction. But this expansion is not unique.

Example 2. $\displaystyle 13/5=[2;1,1,2]=[2;1,1,1,1]$ . $\Box$

Theorem 2. Let $\displaystyle \alpha$ be an integer number. Then $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction.

Proof. By the theorem 1, we can write

$\displaystyle \alpha=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . If $\displaystyle n=0$ then $\displaystyle \alpha=a_0$ and $\displaystyle \alpha=[\alpha]$ is an expansion of $\displaystyle \alpha$ . If $\displaystyle n=1$ then $\displaystyle \alpha=a_0+\frac{1}{a_1}$ , hence $\displaystyle \frac{1}{a_1}$ is an integer, so $\displaystyle a_1=1$ . Therefore $\displaystyle \alpha=[\alpha-1;1]$ is an expansion of $\displaystyle \alpha$ .

Now assume that $\displaystyle n\geq 2$ . We have

$\displaystyle \alpha-a_0=\frac{1}{[a_1;a_2,\ldots,a_n]}$

is an integer number and $\displaystyle [a_1;a_2,\ldots,a_n]>0$ , hence $\displaystyle [a_1;a_2,\ldots,a_n]\leq 1$ . This claim is false because $\displaystyle n\geq 2$ and $\displaystyle a_i\geq 1$ for every $\displaystyle i=1,2,\ldots,n$ . $\Box$

Theorem 3. Let $\displaystyle \alpha$ be a rational number but not an integer. Then $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction.

Proof. Assume that $\displaystyle \alpha=\alpha=r/s$ , where $\displaystyle r$ and $\displaystyle s>1$ are coprime integers. We prove by induction on $\displaystyle s$ that $\displaystyle \alpha$ has exactly two expansions into a finite continued fraction

$\displaystyle \alpha=[a_0;a_1,\ldots,a_n]=[a_0;a_1,\ldots,a_n-1,1],$

where $\displaystyle a_n>1$ . If $\displaystyle s=2$ , because $\displaystyle (r,s)=1$ there is an integer $\displaystyle k$ such that $\displaystyle r=2k+1$ . By the theorem 1, we can write

$\displaystyle \alpha=k+\frac{1}{2}=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . We have $n>0$ and $a_0=k$ , hence $\displaystyle 2=[a_1;a_2,\ldots,a_n]$ . By the theorem 2, we have $2$ has exactly two expansions into a finite continued fraction, those are $2=[2]$ and $2=[1;1]$ , therefore $\alpha$ has exactly two expansions $\displaystyle \alpha=[k;2]=[k;1,1],$ hence the claim is true for $\displaystyle s=2$ . Now suppose that the claim is true for $\displaystyle 2$ , $\displaystyle 3$ , $\displaystyle \ldots$ , $\displaystyle s-1$ ( $\displaystyle s>2$ ). By the theorem 1, we can write

$\displaystyle \alpha=[a_0;a_1,a_2,\ldots,a_n],$

where $a_0$ , $a_1$ , $\ldots$ , $a_n$ are integers such that $a_i>0$ for every $i=1,2,\ldots,n$ . We have $n>0$ and $a_0=[\alpha]$ (integer part of $\alpha$ ), hence $\displaystyle \frac{1}{\alpha-[\alpha]}=[a_1;a_2,\ldots,a_n].$ By the Division Algorithm, there is an integer $\displaystyle a$ such that $\displaystyle r=s[\alpha]+a$ and $1\leq a<s$ , then

$\displaystyle \frac{s}{a}=[a_1;a_2,\ldots,a_n].$

If $a=1$ then $a_1>1$ and by the theorem 2, we have $s/a$ has exactly two expansions are $s/a=[a_1]$ and $\displaystyle s/a=[a_1-1;1]$ . If $\displaystyle a>1$ then by the hypothesis of the induction (note that $\displaystyle s$ and $\displaystyle a$ are coprime integers), $\displaystyle s/a$ has exactly two expansions are

$\displaystyle \frac{s}{a}=[a_1;b_2,\ldots,b_n]=[a_1;b_2,\ldots,b_n-1,1],$

where $\displaystyle b_n>1$ . Therefore $\displaystyle \alpha$ has exactly two expansions, and the claim is true for $\displaystyle s$ . $\Box$

References

[1] https://nttuan.org/2020/01/14/divisibility/

[2] https://nttuan.org/2008/11/14/continued-fraction-expansion-of-rational-numbers/

Perfect rulers

Giả sử ta có một cái thước kẻ dài $\displaystyle 6$ , trên đó đã đánh dấu các điểm $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 2$ , $\displaystyle 3$ , $\displaystyle 4$ , $\displaystyle 5$ , $\displaystyle 6$ . Sử dụng chiếc thước này ta có thể tạo mọi đoạn có độ dài thuộc $\displaystyle [6]$ , nhưng ta không cần đánh dấu trên thước nhiều điểm như thế để đạt được điều này. Ta có thể đánh dấu $\displaystyle 0$ , $\displaystyle 1$ , $\displaystyle 4$ , $6$ là đủ (đoạn độ dài $2$ được đo giữa hai điểm $4$ và $6$ , đoạn độ dài $3$ được đo giữa $1$ và $4$ , đoạn độ dài $4$ được đo giữa $0$ và $4$ , đoạn độ dài $5$ được đo giữa $1$ và $6$ ). Vì $C_4^2=6$ nên hoàn cảnh này là hoàn hảo.

Bài toán. Cho một số nguyên $n$ lớn hơn $4$ . Chứng minh rằng không tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Lời giải. Giả sử ngược lại, tồn tại $n$ số tự nhiên phân biệt $a_1$ , $a_2$ , $\ldots$ , $a_n$ sao cho mọi số nguyên dương không vượt quá $C_n^2$ đều có dạng $a_i-a_j$ .

Xét đa thức $\displaystyle A(z) = \sum_i z^{a_i}$ . Theo tính chất của các số $a_1$ , $a_2$ , $\ldots$ , $a_n$ , ta có

$\displaystyle A(z) \cdot A\left(\frac{1}{z}\right)=\sum_{k=-C_n^2}^{C_n^2} z^k+n-1,\quad \forall z\in\mathbb{C}\setminus \{0\}.$

Continue reading →

A nonnegative trigonometric polynomial

Bài toán. Cho số tự nhiên $n$ . Chứng minh rằng với mỗi số thực $x$ , ta có

$\displaystyle\frac{1}{2}+\frac{\cos x}{2}+\frac{\cos 2x}{3}+\cdots+\frac{\cos nx}{n+1}\geq 0.$

Lời giải. Dễ thấy khi $\displaystyle n<3$ thì khẳng định là đúng. Bây giờ ta xét $\displaystyle n\geq 3.$ Vế trái là hàm số chẵn, tuần hoàn với chu kỳ $\displaystyle 2\pi$ , và bất đẳng thức đúng với $\displaystyle x=0$ . Vì thế ta chỉ cần chứng minh bất đẳng thức khi $\displaystyle 0<x\leq \pi.$ Sử dụng số phức ta chứng minh được kết quả sau:

Bổ đề. $\displaystyle \frac{1}{2}+\sum_{k=1}^n\cos kx=\frac{\sin (2n+1)\frac{x}{2}}{2\sin \frac{x}{2}}$ , và $\displaystyle \sum_{k=0}^n\frac{\sin (2k+1)\frac{x}{2}}{2\sin\frac{x}{2}}=\frac{\sin^2(n+1)\frac{x}{2}}{2\sin^2 \frac{x}{2}}.$

Gọi vế trái của bất đẳng thức là $\displaystyle f_n(x).$ Dùng biến đổi Abel hai lần và bổ đề, ta có $\displaystyle 2\sin^2(x/2)f_n(x)=\sum_{k=0}^{n-2}\frac{2\sin^2(k+1)(x/2)}{(k+1)(k+2)(k+3)}+\frac{\sin^2n(x/2)}{n(n+1)}$

$\displaystyle +\frac{\sin (2n+1)(x/2)\sin (x/2)}{n+1}.\quad (1)$

Nếu $\displaystyle (2n+1)\frac{x}{2}\leq \pi$ thì dễ có điều cần chứng minh, bây giờ ta xét trường hợp còn lại, khi đó $\displaystyle n+1>\frac{2\pi+x}{2x}.\quad (2).$

Từ $\displaystyle (1)$ và $\displaystyle n\geq 3$ , bằng cách dùng hai số hạng đầu trong tổng, ta có bất đẳng thức

$\displaystyle 2\sin^2(x/2)f_n(x)\geq \frac{\sin^2(x/2)}{3}+\frac{\sin^2x}{12}-\frac{\sin (x/2)}{n+1}.$

Vì thế, bài toán sẽ được giải nếu ta chứng minh được $\displaystyle n+1\geq \frac{6}{\sin \frac{x}{2}(3+\cos x)}:=g(x).\quad (3)$

Bây giờ ta xét hai trường hợp:

Trường hợp 1: $\displaystyle 0<x\leq \pi/3.$

Hàm số $\displaystyle y=\sin t/t$ nghịch biến trên $\displaystyle (0;\pi/6]$ nên $\displaystyle \sin\frac{x}{2}\geq \frac{3x}{2\pi},$ suy ra $\displaystyle g(x)\leq \frac{4\pi}{x(3+\cos x)},$ mà $\displaystyle \cos t\geq 1-\frac{t^2}{2}$ với mọi $\displaystyle t$ không âm nên $\displaystyle g(x)\leq \frac{8\pi}{x(8-x^2)}.\quad (4)$

Vì $\displaystyle 0<x\leq \pi/3$ nên $\displaystyle x^2+2\pi x<8,$ suy ra $\displaystyle \frac{8\pi}{x(8-x^2)}<\frac{2\pi+x}{2x}.$ Kết hợp với $\displaystyle (2)$ ta có $\displaystyle (3)$ đúng.

Trường hợp 2: $\pi/3<x\leq \pi.$

Bằng cách chuyển về biến $\displaystyle t=\sin x/2$ ta chứng minh được $\displaystyle g(x)<4\leq n+1,$ và có $\displaystyle (3)$ lại đúng.

Pell’s equation I

Trong bài này chúng tôi sẽ giới thiệu một số định lí của Dirichlet về xấp xỉ số thực bởi số hữu tỉ, và áp dụng các định lí đó vào lý thuyết phương trình Pell.

Định lí 1 (Dirichlet). Cho số thực $\theta$ và số nguyên dương $Q$ . Khi đó có số nguyên dương $q$ và số nguyên $a$ thỏa mãn $q\leq Q$ và $\displaystyle \left|\theta-\frac{a}{q}\right|\leq\dfrac{1}{q(Q+1)}.$

Chứng minh. Phân hoạch nửa đoạn $[0;1)$ thành $Q+1$ nửa đoạn

$\displaystyle I_k=\left[\frac{k}{Q+1};\frac{k+1}{Q+1}\right),\quad k=0,1,\ldots,Q.$

Xét $Q$ số $\{1.\theta\},\{2.\theta\},\ldots,\{Q.\theta\}$ .

Nếu $I_0$ chứa ít nhất một số trong dãy trên, chẳng hạn $\{m.\theta\}$ , ta chọn $q=m$ . Nếu $I_{Q}$ chứa ít nhất một số trong dãy trên, chẳng hạn $\{n.\theta\}$ , ta chỉ cần chọn $q=n$ . Nếu hai khoảng trên không chứa số nào thì tồn tại một khoảng $I_i$ chứa ít nhất hai số $\{j.\theta\},$ $\{k.\theta\}$ $(j<k)$ trong dãy, ta chọn $q=k-j$ . $\Box$

Như vậy mọi số thực có thể được xấp xỉ bởi một số hữu tỉ có mẫu bị chặn với độ chính xác phụ thuộc vào chặn trên của mẫu. Sau đây là một áp dụng đẹp đẽ của định lí trên:

Hệ quả. Mọi số nguyên tố dạng $4k+1$ có thể viết thành tổng của hai số chính phương.

Chứng minh. Theo định lí Wilson, tồn tại số nguyên dương $c$ sao cho $c^2+1\equiv 0\pmod{p}.$ Theo định lí Dirichlet, tồn tại các số nguyên $a,b$ sao cho $1\leq b\leq [\sqrt{p}]$ và

$\displaystyle \left|\frac{c}{p}-\frac{a}{b}\right|\leq\frac{1}{b([\sqrt{p}]+1)}<\frac{1}{b\sqrt{p}}. \quad (*)$

Từ $(*)$ ta có $|cb-ap|<\sqrt{p}$ , suy ra $0<(cb-ap)^2+b^2<2p$ , mà $(cb-ap)^2+b^2\equiv b^2(c^2+1)\equiv 0\pmod{p},$ suy ra $(cb-ap)^2+b^2=p.$ $\Box$

Định lí 2 (Dirichlet). Cho số vô tỷ $\alpha$ . Khi đó có vô hạn số hữu tỷ $\displaystyle\frac{a}{q}$ sao cho $q>0$ và $\displaystyle \left|\alpha-\frac{a}{q}\right|<\frac{1}{q^2}.$ Hơn nữa ta có thể chọn $q$ lớn tùy ý.

Chứng minh. Ta sẽ xây dựng dãy hữu tỷ thỏa mãn bằng quy nạp.

Với số nguyên $Q\geq 1$ bất kỳ, theo định lí 1, tồn tại phân số $\displaystyle\frac{a}{q}$ sao cho $1\leq q\leq Q$ và

$\displaystyle \left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q(Q+1)}.$

Bằng cách thu gọn $\displaystyle\frac{a}{q}$ nếu cần, ta có thể xem phân số này tối giản. Do $Q+1>q$ nên từ bất đẳng thức trên ta có

$\displaystyle \left|\alpha-\frac{a}{q}\right|\leq\frac{1}{q(Q+1)}<\frac{1}{q^2}.$

Giả sử ta đã xây dựng được dãy các phân số tối giản đôi một khác nhau $\displaystyle\frac{a_1}{q_1},\frac{a_2}{q_2},\ldots,\frac{a_m}{q_m}$ thỏa mãn bất đẳng thức trong định lí. Vì $\alpha$ là số vô tỷ nên $|\alpha-a_i/q_i|>0\,\forall i$ , bởi thế nên ta có thể chọn được số nguyên dương $Q$ để $Q>\max \{|\alpha-a_i/q_i|^{-1}\}.$ Dùng định lí 1 cho số $Q$ này ta tìm được phân số tối giản $\displaystyle\frac{a_{m+1}}{q_{m+1}}$ sao cho $1\leq q_{m+1}\leq Q$ và