ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
——————–o0o——————–

HOÀNG THỊ THU HIỀN

LIÊN PHÂN SỐ VỚI TỬ SỐ BẤT KỲ

THÁI NGUYÊN - 2018


ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
——————–o0o——————–

HOÀNG THỊ THU HIỀN

LIÊN PHÂN SỐ VỚI TỬ SỐ BẤT KỲ

CHUYÊN NGÀNH: PHƯƠNG PHÁP TOÁN SƠ CẤP
MÃ SỐ: 8 46 01 13

LUẬN VĂN THẠC SĨ TỐN HỌC

NGƯỜI HƯỚNG DẪN KHOA HỌC

TS. NGƠ VĂN ĐỊNH

THÁI NGUYÊN - 2018

i

Mục lục
Mở đầu

1

Chương 1. Liên phân số chính tắc
1.1 Định nghĩa . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Thuật toán biểu diễn số thực bằng liên phân số chính tắc
1.3 Liên phân số hữu hạn, liên phân số vô hạn . . . . . . . .
1.4 Dãy giản phân của số thực . . . . . . . . . . . . . . . . . .
1.5 Liên phân số của nghịch đảo . . . . . . . . . . . . . . . . .

3
3
4
4
5
6

Chương 2. Liên phân số với tử
2.1 Một số kết quả . . . . . . .
2.2 Khai triển số vô tỷ bậc hai
2.3 Phương trình Pell . . . . .

số
. .
. .
. .


.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.


nguyên dương
7
. . . . . . . . . . . . . . . . . . . . . 7
. . . . . . . . . . . . . . . . . . . . . 14
. . . . . . . . . . . . . . . . . . . . . 21

Chương 3. Liên phân số với tử số bất kỳ
3.1 Các liên phân số có dạng các hàm hữu tỷ . .
3.2 Biểu diễn, tính hội tụ và tính duy nhất . . .
3.3 Khai triển với số hữu tỷ z . . . . . . . . . . .
3.4 Khai triển tuần hoàn và số vô tỉ bậc hai giảm
√
3.5 Các khai triển tuần hoàn cho n . . . . . . .

.
.
.
.
.

.
.
.
.
.

.
.
.

.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.

.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

28
28
30

38
40
43

Kết luận

50

Tài liệu tham khảo

51


1

Mở đầu
Liên phân số là một cách viết rõ ràng cho một số thập phân bất kỳ. Một liên
phân số chính tắc có dạng
1

a0 +

1

a1 +
a2 +

.

1

a3 + · · ·

Mỗi số thực đều có thể được viết dưới dạng liên phân số chính tắc. Liên phân
số có nhiều ứng dụng thực tế (xem [1]). Năm 2011, Anselm và Weintraub [2] đã
nghiên cứu và công bố một số kết quả về liên phân số tổng quát có dạng
z

a0 +

z

a1 +
a2 +

,

z
a3 + · · ·

trong đó z là một số nguyên dương tùy ý. Năm 2017, Greene và Schmieg [3] đã
mở rộng kết quả của Anselm và Weintraub cho trường hợp z là một số thực bất
kỳ lớn hơn hay bằng 1.
Mục đích của đề tài là nghiên cứu và trình bày lại các kết quả nêu trên.
Ngồi phần mở đầu và kết luận, luận văn gồm 3 chương:
Chương 1. Liên phân số chính tắc. Mục đích của chương này là giới
thiệu sơ lược về liên phân số chính tắc.
Chương 2. Liên phân số với tử số nguyên dương. Chương 2 trình bày
lại các kết quả của Anselm và Weintraub về liên phân số với tử số nguyên dương.
Chương 3. Liên phân số với tử số không nguyên. Chương 3 trình bày
lại các kết quả của Greene và Schmieg về liên phân số với tử số là số thực bất

kỳ.
Luận văn được hoàn thành tại trường Đại học Khoa học, Đại học Thái
Nguyên. Lời đầu tiên tác giả xin được bày tỏ lòng biết ơn sâu sắc tới thầy giáo


2

TS. Ngô Văn Định. Thầy đã dành nhiều thời gian hướng dẫn cũng như giải đáp
các thắc mắc của tôi trong suốt q trình làm luận văn. Tơi xin bày tỏ lòng biết
ơn sâu sắc tới thầy.
Tác giả xin chân thành cảm ơn tồn thể các thầy cơ trong Khoa Toán - Tin,
trường Đại học Khoa học - Đại học Thái Nguyên đã tận tình hướng dẫn, truyền
đạt kiến thức trong suốt thời gian theo học, thực hiện và hoàn thành luận văn.
Cảm ơn sự giúp đỡ của bạn bè, người thân và các đồng nghiệp trong thời
gian làm luận văn.
Thái Nguyên, tháng 05 năm 2018
Người viết luận văn

Hoàng Thị Thu Hiền


3

Chương 1
Liên phân số chính tắc
Trong chương này, chúng tơi nhắc lại sơ lược về khái niệm liên phân số chính
tắc và một số tính chất của liên phân số.

1.1


Định nghĩa

Định nghĩa 1.1. Liên phân số chính tắc (hay cịn gọi là phân số liên tục chính
tắc) là biểu thức có dạng
1

x = a0 +

(1.1)

1

a1 +
a2 +

1

.
a3 + . .

trong đó a0 là một số ngun khơng âm và tất cả các số an là số nguyên dương.
Liên phân số có thể biểu diễn chính xác các số thực. Dạng tổng quát hơn của
liên phân số là
b1

x = a0 +

b2

a1 +

a2 +

b3

.
a3 + . .

trong đó bn là số nguyên dương.
Mọi số thực đều có thể biểu diễn dưới dạng liên phân số chính tắc. Cách biểu
diễn số thực dưới dạng liên phân số cho ta khá nhiều đặc trưng thú vị. Chẳng
hạn, với liên phân số dạng chính tắc như đã nêu trong định nghĩa trên, ta có x
là số hữu tỷ khi và chỉ khi dãy {an }n≥1 là dãy hữu hạn; nếu dãy {an }n≥1 là một
dãy vơ hạn tuần hồn thì x là nghiệm của một đa thức bậc hai với hệ số nguyên.


4

Để tránh phải viết công thức cồng kềnh, chúng ta thường viết liên phân số
(1.1) dưới dạng:
x = a0 +

1
1
1
+
+
+ ···
a1 + a2 + a3 +

hoặc ta còn viết x = [a0 ; a1 , a2 , a3 , ...].


1.2

Thuật tốn biểu diễn số thực bằng liên phân số
chính tắc

Cho số thực r, ký hiệu i là phần nguyên của r, f là phần thập phân của r.
Biểu diễn liên phân số của r là [i; a1 , a2 , ...], trong đó [a1 ; a2 , ...] là dạng biểu diễn
liên phân số của 1/f . Nếu như f = 0 thì thuật tốn dừng lại, trong trường hợp
f khác 0, ta lặp lại các bước trên với r thay bằng 1/f .
Ví dụ 1.2. Xét số

415
, phần nguyên của phân số này là 4, phần lẻ của nó là số
93

43
1
xấp xỉ bằng , ta muốn giữ nguyên tử số 1 và thay mẫu số 2 bằng một số
93
2
7
khác, chính xác hơn là 2 + , khi đó có thể viết
43
43
1
415
1
1
1

=4+
=4+
=4+
=4+
=4+
.
93
7
1
1
93
93
2+
2+
2+
1
43
43
43
6+
7
7

Như vậy, ta có

1.3

415
= [4; 2, 6, 7].
93


Liên phân số hữu hạn, liên phân số vô hạn

Liên phân số hữu hạn biểu diễn số hữu tỉ. Ngược lại, một số hữu tỉ bất kì có
thể biểu diễn bằng liên phân số hữu hạn theo 2 cách: cách thứ nhất, bằng thuật
toán nêu ở phần thuật toán biểu diễn số thực bằng liên phân số, ta được liên
phân số
[a0 ; a1 , a2 , . . . , an−1 , an ];

cách thứ hai, từ biểu diễn ở cách thứ nhất, ta bớt đi 1 đơn vị ở thành phần cuối,
và thêm vào sau nó một thành phần đúng bằng 1:
[a0 ; a1 , a2 , . . . , an−1 , an − 1, 1].


5

Ví dụ 1.3. Thực hiện thuật tốn nêu trong Mục 1.2, ta có:
2.25 = 2 + 1/4 = [2; 4] = [2; 3, 1],
−4.2 = −5 + 4/5 = [−5; 1, 4] = [−5; 1, 3, 1].

Như vậy, liên phân số vô hạn là số vô tỉ và hiển nhiên mọi số vô tỉ đều được
biểu diễn dưới dạng liên phân số vơ hạn. Trong đó, đáng chú ý là các liên phân
số vơ hạn tuần hồn ln là nghiệm của một đa thức bậc hai với hệ số nguyên
và ngược lại.
√

2 là nghiệm của đa thức bậc hai x2 − 2.
−27
1√
[0; 2, 3, 4, 2, 3, 4, 2, 3, 4, . . .] =

+
1093 là nghiệm của đa thức bậc hai
14
14
7x2 + 27x − 13.

Ví dụ 1.4. [1; 2, 2, 2, 2, 2, 2, . . .] =

1.4

Dãy giản phân của số thực

Cho số thực r có dạng liên phân số là [a0 ; a1 , a2 , . . . , an−1 , an , . . .] (có thể hữu
hạn hoặc vơ hạn). Từ cơng thức biểu diễn trên, có thể xây dựng một dãy số hữu
tỉ (hữu hạn hoặc vô hạn) hội tụ đến r, dãy này gọi là dãy giản phân:
a0
h0
=
k0
1
1
a0 a1 + 1
h1
= [a0 ; a1 ] = a0 +
=
k1
a1
a1
h2
a2 (a1 a0 + 1) + a0

=
k2
a2 a1 + 1
h3
a3 (a2 (a1 a0 + 1) + a0 ) + (a1 a0 + 1)
=
k3
a3 (a2 a1 + 1) + a1
..................
hn
= [a0 ; a1 , a2 , . . . , an−1 , an ]
kn
..................

Đặt rn =

hn
.
kn

Ví dụ 1.5. Dãy giản phân của 0.84375 (dạng liên phân số là [0; 1, 5, 2, 2]):
[0; 1]

[0; 1, 3]

[0; 1, 4]

[0; 1, 5]

[0; 1, 5, 2, 1]


[0; 1, 5, 2, 1]

[0; 1, 5, 2, 2]

1

3
4

4
5

5
6

11
13

16
19

27
32


6

1.5


Liên phân số của nghịch đảo

Cho số hữu tỷ dương r, nếu biết dạng liên phân số của nó là
[a0 ; a1 , a2 , a3 , . . . , an−1 , an ]

yêu cầu đặt ra là tìm dạng liên phân số của nghịch đảo 1/r.
Xét 2 trường hợp:
• nếu r > 1, tức là a0 ≥ 1 thì liên phân số của 1/r là:
[0; a0 , a1 , a2 , a3 , . . . , an−1 , an ]
• nếu 0 < r < 1, tức là a0 = 0 thì liên phân số của 1/r là:
[a1 ; a2 , a3 , . . . , an−1 , an ].

Ví dụ 1.6.
2.25 =

9
= [2; 4],
4

15
= [0; 1, 7, 2]
17

1
4
= = [0; 2, 4]
2.25
9
17
= [1; 7, 2].

15


7

Chương 2
Liên phân số với tử số nguyên
dương
Trong Mục 2.1 của chương này, chúng tơi trình bày lại kết quả cơ bản về
khai triển cfN . Ta sẽ thấy rằng mọi số thực dương x0 đều có một khai triển
cfN . Hơn nữa, nếu N > 1 thì mỗi số hữu tỷ có cả khai triển cfN hữu hạn và
vơ hạn; nếu N > 2 nó có khai triển khơng tuần hồn. Nếu N > 1, mọi số vơ
tỷ bậc hai có cả khai triển tuần hồn và khơng tuần hồn. Ở đây chúng ta sử
dụng ngơn ngữ và ký hiệu chuẩn: x0 = [a0 , a1 , a2 , . . .]N là tuần hoàn theo chu kỳ
k từ i = m nếu ai+k = ai với mọi i ≥ m, và trong trường hợp này chúng ta viết
x0 = [a0 , . . . , am−1 , am , . . . , am+k−1 ]N .
Chúng tôi cũng trình bày lại khái niệm về khai triển cfN tốt nhất của số thực
x0 , ký hiệu bởi x0 = [[a0 , a1 , a2 , . . .]]N .
Trong Mục 2.2, chúng ta sẽ thấy rằng, với N > 1, mỗi số vơ tỷ bậc hai có
khai triển tuần hoàn cfN .
Lý thuyết về các liên phân số cổ điển liên quan mật thiết đến phương trình
của Pell, và trong Mục 2.3 chúng ta trình bày lại các kết quả tương tự trong
trường hợp N > 1.

2.1

Một số kết quả

Trong mục này chúng tơi trình bày lại các kết quả của Anselm và Weintraub
[2] về liên phân số với tử số nguyên dương, tức là tổng quát của các liên phân số

chính tắc, trong đó “tử số” 1 được thay thế bằng một số nguyên dương N tùy ý.


8

Cho N là một số nguyên dương tùy ý, chúng ta xét các liên phân số dạng
N

a0 +

N

a1 +
a2 +

,

N
a3 + . . .

trong đó a0 là một số nguyên và a1 , a2 , a3 , . . . là các số nguyên dương. Chúng ta
sẽ ký hiệu liên phân số này là [a0 , a1 , a2 , a3 . . .]N và xem nó như là một khai triển
cfN . Trước tiên, sử dụng phương pháp quy nạp ta dễ dàng có được các bổ đề
sau:
Bổ đề 2.1. Cho b0 là một số thực không âm và cho b1 , . . . , bn là các số thực
dương.
(a) [b0 , b1 , . . . , bn ]N = [b0 , b1 , . . . , bk−1 , [bk , bk+1 , . . . , bn ]N ]N .
(b) [b0 , b1 , . . . , bn ]N = [b0 , b1 , . . . , bn−1 + N/bn ]N .
(c) Với số nguyên dương m bất kỳ,
[b0 , mb1 , b2 , mb3 , . . . , kbn ]mN = [b0 , b1 , . . . , bn ]N ,


trong đó k = 1 nếu n là chẵn và k = m nếu n là lẻ.
Bổ đề 2.2. Xác định dãy {pn } và {qn } quy nạp theo
p−2 = 0,
q−2 = 1/N,

p−1 = 1,
q−1 = 0,

pn = bn pn−1 + pn−2 N,

n ≥ 0,

qn = bn qn−1 + qn−2 N,

n ≥ 0.

Cho Cn = pn /qn với n ≥ 0. Thì với mọi n ≥ 0,
Cn = [b0 , b1 , . . . , bn ]N .

Bổ đề 2.3. Với giả thiết như trong Bổ đề 2.2,
pn qn−1 − qn pn−1 = (−1)n−1 N n ,

với n ≥ 1.

Định lý 2.4. Cho a0 là một số nguyên không âm và cho a1 , a2 , . . . là các số
nguyên dương. Thì
[a0 , a1 , a2 , . . .]N := lim [a0 , a1 , a2 , . . . , an ]N
n→∞


tồn tại.


9

Chứng minh. Theo Bổ đề 2.1(c), với mỗi n,
[a0 , a1 , . . . , an ]N = [b0 , b1 , . . . , bn ]1 ,

với bi = ai khi i chẵn và bi = ai /N khi i lẻ. Cho Cn = [b0 , b1 , . . . , bn ]1 . Dãy
{C0 , C2 , C4 , . . .} tăng ngặt và dãy {C1 , C3 , C5 , . . .} giảm ngặt, và mọi số hạng
trong dãy thứ nhất nhỏ hơn mọi số hạng trong chuỗi thứ hai. Như vậy dãy thứ
nhất hội tụ đến giới hạn trên nhỏ nhất là Le và chuỗi thứ hai hội tụ tới cận
dưới L0 , với Le ≤ L0 . Ta lại có Le = L0 , tức là, dãy {C0 , C1 , C2 , . . .} hội tụ khi và
chỉ khi chuỗi ∞
n=0 bi phân kỳ. Nhưng vì mỗi ai là một số nguyên, bi ≥ 1/N với
i ≥ 1, vì vậy ta thừa nhận trường hợp này.
Chúng ta dễ dàng chứng minh trực tiếp sự hội tụ của {C0 , C1 , C2 , . . .}. Chúng
ta có |L0 − Le | = L0 − Le < C2n+1 − C2n với mọi n, và từ Bổ đề 2.3 chúng ta có
C2n+1 − C2n = 1/q2n+1 q2n . Ta lại có Cn = [a0 , a1 , . . . , an ]N , bằng quy nạp chứng
minh được q2n+1 ≥ (a1 /N )(1 + 1/N )n và q2n ≥ (1 + 1/N )n , do đó 1/q2n+1 q2n → 0
khi n → ∞.
Bây giờ chúng tơi trình bày một thuật toán để tạo ra khai triển cfN .
Định lý 2.5. Cho x0 ∈ R, x0 > 0. Xét thuật toán
(1) Cho i = 0.
(2) Chọn ai ∈ N sao cho xi − N ≤ ai ≤ xi , với xi là phần nguyên của xi .
(3) Đặt ri = xi − ai .
(4) Nếu ri = 0, kết thúc. Nếu không, hãy cho xi+1 =

N
, tăng i, và đi đến bước

ri

(2).
Khi đó x0 = [a0 , a1 , a2 , . . .]N (trong đó chỉ có thể có hữu hạn ai ).
Chứng minh. Trước tiên chúng ta sẽ xác minh rằng thuật tốn này có thể được
thực hiện như mơ tả. Khó khăn duy nhất có thể nảy sinh nếu xi < 1 với một số
i > 0 vì sau đó chúng ta sẽ khơng thể chọn ai làm mơ tả thuật tốn. Chúng ta
biết rằng x0 là một số dương và vì chúng ta cho phép a0 là 0, chúng ta ln có
một sự lựa chọn hợp lệ cho i = 0 bằng cách chọn a0 = x0 . Giả sử rằng chúng
ta đã chọn ai thỏa mãn bất đẳng thức trong bước (2). Suy ra có
0 ≤ xi − xi ≤ xi − ai = ri < xi − (xi − N ) = N.


10

Nếu ri = 0, thuật toán sẽ kết thúc. Nếu không, chúng ta nhận được 0 < ri < N

N
> 1 vì vậy chúng ta có thể thực hiện một sự lựa chọn hợp lệ cho
ri
ai+1 . Do đó, bằng quy nạp, chúng ta ln có thể chọn ai như mơ tả trong bước

do đó xi+1 =

(2) nếu thuật tốn vẫn chưa chấm dứt.
Chứng minh hội tụ đến x0 tương tự như trường hợp cổ điển và chúng ta bỏ
qua nó.
Định nghĩa 2.6. Nếu trong bước (2) của thuật tốn, chúng ta chọn ai = xi ,
chúng ta gọi đây là sự lựa chọn tốt nhất cho ai . Nếu chúng ta thực hiện sự lựa
chọn tốt nhất cho mỗi ai thì chúng ta gọi khai triển liên phân số thu được là tốt

nhất.
Ta biểu thị một khai triển cfN tốt nhất là [[a0 , a1 , a2 , . . .]]N và sử dụng ký hiệu
[[x0 ]]N để biểu thị cho khai triển tốt nhất cfN của số thực x0 .
Có một tiêu chí đơn giản để quyết định khi một khai triển cfN là một khai
triển cfN tốt nhất.
Bổ đề 2.7. Một khai triển cfN vô hạn [a0 , a1 , . . .]N là khai triển cfN tốt nhất
khi và chỉ khi ai ≥ N với mọi i ≥ 1. Một khai triển cfN hữu hạn [a0 , a1 , . . . , an ]N
là một khai triển cfN tốt nhất khi và chỉ khi n = 0, hoặc n > 0 và ai ≥ N với
1 ≤ i ≤ n − 1 và an ≥ N + 1.
Chứng minh. Chúng ta chứng minh trường hợp vô hạn. Giả sử [a0 , a1 , . . .]N là
khai triển cfN tốt nhất của một số số thực x0 . Thì với mỗi i ≥ 0, ai = xi suy ra
ri < 1, và do đó ai+1 = N/ri ≥ N . Ngược lại, nếu ai+1 ≥ N , thì, vì khai triển
khơng kết thúc, ri < 1 và do đó ai = xi .
Trong trường hợp cổ điển, một số vơ tỷ dương có một khai triển liên phân số
duy nhất, và đó là một khai triển cf1 tốt nhất. Một số hữu tỷ dương khác với 1
có hai khai triển cf1 , dạng [a0 , a1 , . . . , an ]1 với an ≥ 2 và [a0 , a1 , . . . , an − 1, 1]1 , và
1 có hai khai triển cf1 [1]1 và [0, 1]1 . Trong bất kỳ trường hợp nào, khai triển cf1
tốt nhất là khai triển đầu tiên.
Định lý 2.8. Đối với N ≥ 2, mọi số vơ tỷ dương x0 có vơ số khai triển cfN vô
hạn, và vô số trong số những khai triển này là khơng tuần hồn.
Chứng minh. Cho một số khai triển của x0 , [a0 , a1 , a2 , . . .]N , chúng ta sửa đổi nó
theo cách sau: chọn một số k > 0. Thực hiện thuật toán trên x0 và tạo một
khai triển khác [a0 , a1 , a2 , . . .]N bằng cách chọn ai = ai với mọi i < k . Sau đó chọn


11

ak = xk (một lựa chọn hợp lệ). Nếu ak = ak chúng ta có thể tiếp tục chọn ai bất

kỳ và ta sẽ có một khai triển mới cho x0 . Giả sử rằng ak = ak . Nếu ak+1 = xk+1 ,

chọn ak+1 = xk+1 và ta có một khai triển mới cho x0 . Giả sử rằng ak+1 = xk+1

N
> N suy ra xk+1 − N ≤ ak+1 − 1 ≤ xk+1 .
rk
= ak+1 − 1 và chúng ta có một khai triển mới

thì rk = xk − xk < 1 suy ra xk+1 =
Vì vậy, chúng ta có thể chọn ak+1
cho x0 .

Mỗi số vơ tỷ có ít nhất một khai triển (khai triển tốt nhất) và phương pháp
trước đó cho phép chúng ta có được từ đó một khai triển mới với mọi k ∈ N.
Hơn nữa, chúng ta có thể áp dụng phương pháp này để đảm bảo rằng khai triển
cho x0 là không tuần hoàn. Đặt một số s ∈ N và thực hiện thuật toán trên x0 ,
lập nên bất kỳ sự lựa chọn hợp lệ cho mỗi ai . Bất cứ khi nào i + s là một bình
phương, tìm j < i lớn nhất sao cho xi = xj . Nếu khơng có j như vậy tồn tại,
chọn bất kỳ cho ai , nếu không chọn ai = aj hoặc ai+1 = aj+1 bởi phương pháp
mơ tả trước đó. Điều này đảm bảo rằng khơng có dãy hữu hạn các sự lựa chọn
nào sẽ được lặp lại vô hạn lần. Như vậy với mọi s chúng ta có một khai triển
khơng tuần hồn cho x0 .
Bổ đề 2.9. Khai triển cfN tốt nhất của một số hữu tỷ dương là hữu hạn.
Chứng minh. Nếu x0 là một số hữu tỷ, thì ri là số hữu tỷ với mọi i. Cho ri =

di
ei

trong đó di và ei là các số nguyên không âm với gcd(di , ei ) = 1. Nếu ta lựa chọn
khai triển tốt nhất cho x0 , thì ri < 1 với mọi i. Như vậy
ri+1 = xi+1 − ai+1 =


N ei − di ai+1
N
− ai+1 =
< 1.
ri
di

Bây giờ gcd(N ei − di ai+1 , di ) không nhất thiết phải bằng 1, nhưng trong trường
hợp bất kỳ di+1 là ước của N ei − di ai+1 . Như vậy di+1 < di , suy ra {di } là một
dãy giảm ngặt các số nguyên không âm. Do đó dj = 0 với một số j nào đó. Như
vậy rj = 0 và thuật toán kết thúc.
Đối với một số nguyên dương m, chúng ta cho mk biểu thị một dãy k số m,
và cho m∞ biểu thị một dãy vơ số số m. Bằng tính tốn trực tiếp, chúng ta có
bổ đề sau:
Bổ đề 2.10. (a) Cho N ≥ 2. Thì với k ≥ 0 bất kỳ, ta có
N = [(N − 1)k , N ]N và N = [(N − 1)∞ ]N .


12

(b) Cho N ≥ 4 là chẵn. Thì
N = [N − 2, (N − 2)/2, N ]N .

(c) Cho N ≥ 3 là lẻ. Thì
N = [N − 2, (N − 1)/2, 2N − 1, N ]N .

Định lý 2.11. Cho x0 là một số hữu tỷ dương.
(a) Đối với N ≥ 2 bất kỳ, x0 có khai triển cfN hữu hạn với độ dài dài tùy ý, và
ít nhất một sự mở rộng cfN vô hạn.

(b) Đối với N ≥ 3 bất kỳ, x0 có vơ số khai triển cfN tuần hồn khác nhau và
vơ số các khai triển cfN khơng tuần hồn khác nhau.
(c) Với N = 2, mọi khai triển cfN vơ hạn của x0 đều có dạng
[a0 , a1 , . . . , ak , 1, 1, 1, . . .]N

với một số k nào đó và các số nguyên a0 , . . . , ak bất kỳ, và chỉ có hữu hạn
các khai triển như vậy.
Chứng minh. Cho x0 có khai triển cfN tốt nhất
x0 = [[a0 , . . . , an ]]N .

Khai triển này hữu hạn bởi Bổ đề 2.9, và an ≥ N + 1 bởi Bổ đề 2.7.
(a) Sử dụng Bổ đề 2.1 và Bổ đề 2.10(a), chúng ta có
x0 = [a0 , . . . , an ]N = [a0 , . . . , an−1 , an − 1, N ]N
= [a0 , . . . , an−1 , (N − 1)k , N ]N ,

với k ≥ 0 bất kỳ

và
x0 = [a0 , . . . , an−1 , (N − 1)∞ ]N .

(b) Trong trường hợp N là chẵn, sử dụng Bổ đề 2.1 và Bổ đề 2.10(b), chúng
ta có
x0 = [a0 , . . . , an ]N = [a0 , . . . , an−1 , an − 1, N ]N
= [a0 , . . . , an−1 , N − 2, (N − 2)/2, N ]N


13

= [a0 , . . . , an−1 , N − 2, (N − 2)/2, (N − 1)k , N ]N ,


với k ≥ 0 bất kỳ.
Ngoài ra với k ≥ 0 bất kỳ chúng ta có sự khai triển tuần hoàn theo chu kỳ
k + 2 cho bởi
x0 = [a0 , . . . , an−1 , N − 2, (N − 2)/2, (N − 1)k , N − 2, (N − 2)/2, (N − 1)k , . . .]N

và đối với dãy khơng tuần hồn bất kỳ k0 , k1 , . . . của số nguyên không âm,
chúng ta có khai triển khơng tuần hồn
x0 = [a0 , . . . , an−1 , N −2, (N −2)/2, (N − 1)k0 , N −2, (N −2)/2, (N − 1)k1 , . . .]N .

Trong trường hợp N lẻ, lập luận tương tự, sử dụng Bổ đề 2.10(c).
(c) Viết x0 = a/b là một phân số trong các số hạng nhỏ nhất. Ta chứng minh
điều này bằng cách quy nạp theo b.
Giả sử b = 1, do đó x0 = a là một số nguyên. Bằng cách kiểm tra thuật
toán của chúng ta, rất dễ dàng để thấy rằng bất kỳ khai triển cf2 hữu hạn
nào của x0 phải là
a = [a]2 = [a − 1, 1k , 2]2

cho một số k ≥ 0 = [a − 2, 1]2 nếu a ≥ 2,

và khai triển cf2 vô hạn duy nhất của a là
a = [a − 1, 1∞ ]2 .

Bây giờ hãy cho x0 = a/b với b > 1. Đặt c = a/b . Thì, chỉ có các khai triển
cf2 của x0 có dạng
a/b = [c, [x1 ]2 ]2

hoặc

a/b = [c − 1, [x1 ]2 ]2 .


Trong trường hợp đầu tiên, x1 = 2b/(a − bc) và a − bc < b, do đó bằng quy
nạp chúng ta đã làm xong. Trong trường hợp thứ hai,1 < x1 < 2 và do đó
khai triển này phải có dạng
a/b = [c − 1, 1, [x2 ]2 ]2

với x2 = 2(a − b(c − 1))/(2b − (a − b(c − 1))) và 2b − (a − b(c − 1)) < b, do đó
bằng quy nạp chúng ta đã làm xong.


14

Nhận xét 2.12. Chỉ có thể có hữu hạn các chuỗi tuần hoàn a0 , a1 , . . . và một
số dương x0 bất kỳ chỉ có hữu hạn khai triển cfN tuần hồn (có thể khơng có).
Việc lập luận chéo của chứng minh Định lý 2.8 cho thấy rằng bất kỳ số vơ tỷ
x0 nào đều có vơ số các khai triển tuần hoàn cfN với N ≥ 2 bất kỳ, và việc xây
dựng trong chứng minh của Định lý 2.11 cho thấy rằng bất kỳ số hữu tỷ x0 nào
đều có vơ số các khai triển khơng tuần hoàn cfN với N ≥ 3 bất kỳ.

2.2

Khai triển số vơ tỷ bậc hai

Trong phần này, chúng tơi trình bày các kết quả về khai triển cfN của các số
vô tỷ bậc hai, tức là các số vô tỷ là nghiệm của một phương trình bậc hai với
hệ số nguyên.
Định nghĩa 2.13. Xét một khai triển cfN tùy ý [a0 , a1 , . . .]N . Mở rộng m của
khai triển này là khai triển cfmN
Im ([a0 , a1 , a2 , a3 , . . .]N ) = [a0 , ma1 , a2 , ma3 , . . .]mN .

Chú ý rằng, theo Bổ đề 2.1(c), nếu x0 = [a0 , a1 , . . .]N , thì x0 = Im ([a0 , a1 , . . .]N )

với m bất kỳ.
Định lý 2.14. Cho x0 là một số vơ tỷ bậc hai, khi đó với mọi N , x0 có một khai
triển cfN tuần hồn.
Chứng minh. Từ lý thuyết cổ điển chúng ta biết rằng x0 có khai triển cf1 tuần
hồn với chu kỳ k . Suy ra mở rộng N của khai triển này là một khai triển cfN
của x0 , tuần hoàn với chu kỳ k (hoặc, trong trường hợp ngoại lệ, k/2) nếu k là
chẵn và tuần hoàn với chu kỳ 2k (trong mọi trường hợp) nếu k là lẻ.
Chúng ta nhận thấy rằng khơng có lý do để mong đợi nói chung rằng khai
triển cfN của x0 thu được theo cách này sẽ là khai triển cfN tốt nhất của x0 .
Thực tế từ Bổ đề 2.7 chúng ta thấy rằng điều này sẽ không bao giờ xảy ra nếu
N là đủ lớn.
Tiếp theo đây, chúng ta sẽ thấy một số họ các khai triển cfN tuần hoàn tốt
nhất cho những số vơ tỷ bậc hai dưới đây, và một số ví dụ cụ thể của các ví dụ
cfN tuần hồn tốt nhất về các số vô tỷ bậc hai.


15

Giả sử E là một số nguyên dương mà không phải là một số chính phương,
√
D=
E , và a = E − D2 , suy ra E = D2 + a với 1 ≤ a ≤ 2D. Ngoài ra, N được
cho là nhỏ (đối với E ) nếu N ≤ 2D và lớn (đối với E ) trong trường hợp cịn lại
(lưu ý rằng N = 1 ln là nhỏ).
Bổ đề 2.15. Giả sử rằng a là ước của 2DN . Thì
√
E = [D, 2DN/a, 2D]N ,

tuần hồn theo chu kỳ 2 nếu a = N và chu kỳ 1 nếu a = N . Đây là khai triển
√

cfN tốt nhất của E khi và chỉ khi a và N đều nhỏ so với E .
Chứng minh. Tính trực tiếp cho thấy rằng đây luôn luôn là một khai triển cfN
√
của E , và nó suy ra trực tiếp từ Bổ đề 2.7 rằng đó là khai triển cfN tốt nhất
√
của E chính xác khi các điều kiện nhất định được thỏa mãn.
Nhận xét 2.16. Chú ý rằng nếu a là ước của 2D, thì
[D, 2DN/a, 2D]N = IN ([D, 2DN/a, 2D]1 ).

Nhưng nếu không, khai triển cfN này không đến từ một khai triển cf1 .
Các trường hợp a = 1, a = 2, hoặc a = 4 và D chẵn được dề cập đến trong
Bổ đề 2.15. Trong trường hợp a = 4 và D lẻ ta có những điều sau đây.
Sử dụng Bổ đề 2.7 ta có thu được hai bổ đề sau đây:
Bổ đề 2.17. Cho D > 1 là lẻ, và cho E = D2 + 4. Sau đó
√

E = [[D, (D − 1)/2, 1, 1, (D − 1)/2, 2D]]1 ,

tuần hoàn theo chu kỳ 5,

và
√
E = [[D, (D2 − 1)/2, D, 2D2 + 2, D, (D2 − 1)/2, 2D]]D ,

tuần hoàn theo chu kỳ 6.

Bổ đề 2.18. (a) Với D > 1, nếu a = 2D − 1, thì
√

E = [D, 1, D − 1, 1, 2D]1


theo chu kỳ 4

và
√

E = [[D, D + 1, 2D3 + 2D2 − 2D, D + 1, 2D]]D ,

theo chu kỳ 4 .


16

(b) Với D ≥ 4 chẵn, nếu a = 2D − 3, thì
√

và

√

E = [D, 1, (D − 2)/2, 2, (D − 2)/2, 1, 2D]1

theo chu kỳ 6

E = [[D, D + 2, (D2 − 2D)/2, D + 2, 2D]]D ,

theo chu kỳ 4

khi D = 6 và theo chu kỳ 2 khi D = 6.
(c) Với D ≥ 5 lẻ, nếu a = 2D − 3, thì

√

E = [D, 1, (D − 3)/2, 1, 2D]1

theo chu kỳ 4 .

(d) Với D ≥ 3 lẻ, nếu a = 2D, thì
√

và

E = [[D, 2D + 2, 8D3 + 16D2 + 6D, 2D + 3]]2D+1
√

E = [[D, 2D + 3, 4D2 + 4D, 2D + 4]]2D+2

theo chu kỳ 2

theo chu kỳ 2

Nhận xét 2.19. (a) Bổ đề 2.18(c) cho D = 3 được đề cập đến trong Bổ đề
√
2.15, phân tích 12 = [3, 2, 6]1 = [3, 6]3 .
(b) Với D ≥ 5 lẻ và a = 2D − 3, bằng chứng số học cho thấy khai triển cfD tốt
√
nhất của E khơng phải ln ln tuần hồn.
√

(c) Nếu a = 2D và N là nhỏ, tức là, N ≤ 2D, sau đó E được đề cập đến trong
Bổ đề 2.15, vì vậy hai trường hợp được đưa ra trong Bổ đề 2.18 (d) là hai

trường hợp đầu tiên với N lớn. Có vẻ như khơng có kết quả tương tự với
N = 2D + 3, và điều này có thể là một trường hợp khơng tuần hồn.
Ví dụ 2.20. Cho a = 3 và N = 2. Nếu D chia hết cho 3 thì
trong Bổ đề 2.15. Nếu khơng chúng ta có

√

E được đề cập đến

√
7 = [[2, 3, 20, 3, 4]]2 tuần hoàn theo chu kỳ 4,
√
19 = [[4, 5, 3, 4, 34, 4, 3, 5, 8]]2 tuần hoàn theo chu kỳ 8,
√
28 = [[5, 6, 2, 6, 10]]2 tuần hoàn theo chu kỳ 4,
√
52 = [[7, 9, 4, 9, 14]]2 tuần hoàn theo chu kỳ 4,
√
67 = [[8, 10, 2, 3, 2, 3, 6, 2, 2, 2, 64, 2, 2, 2, 6, 3, 2, 3, 2, 10, 16]]2 tuần hoàn theo chu kỳ 20,
√
103 = [[10, 13, 4, 3, 9, 3, 4, 13, 20]]2 tuần hoàn theo chu kỳ 8,


17
√
124 = [[11, 14, 2, 3, 17, 6, 4, 15, 2, 2, 2, 3, 5, 59, 71, 8, 3, . . .]]2 có thể khơng tuần hồn,
√
172 = [[13, 17, 4, 2, 7, 7, . . . , 7, 7, 2, 4, 17, 26]]2 tuần hoàn theo chu kỳ 38,
√
487 = [[22, 29, 5, 7, 16, . . . , 16, 7, 5, 29, 44])2 tuần hoàn theo chu kỳ 136.

√

Ví dụ 2.21. Các ví dụ sau đây cho ta trường hợp N > 1 và [[ E]]N có chu kỳ
lẻ:
√
√
√
√

22 = [[4, 2, 2, 8]]2 có chu kỳ 3,
162 = [[12, 2, 2, 2, 2, 24]]2 có chu kỳ 5,
241 = [[15, 3, 2, 4, 4, 2, 3, 20]]2 có chu kỳ 7,
393 = [[19, 2, 4, 2, 2, 9, 9, 2, 2, 2, 9, 9, 2, 2, 4, 2, 38]]2 có chu kỳ 11.
√

√

√

Ngồi ra, [[ 457]]2 có chu kỳ 9, [[ 139]]3 có chu kỳ 5, [[ 331]]3 có chu kỳ 9,
√
√
√
[[ 181]]4 có chu kỳ 5, [[ 1997]]4 có chu kỳ 35, và [[ 524]]8 có chu kỳ 3.
Bổ đề sau đây cho ta một số họ các chu kỳ lẻ:
Bổ đề 2.22. (a) Với j ≥ 1 bất kỳ, cho D = 3j + 1, a = 6j, E = D2 + a =
9j 2 + 12j + 1. Thì
√

E = [[D, 2(D − 1)/3, 2(D − 1)/3, 2D]]2(D−1)/3 ,


theo chu kỳ 3 .

(b) Với j ≥ 1 bất kỳ, cho D = 3j + 1, a = 4j + 2, E = D2 + a = 9j 2 + 10j + 3. Thì
√
E = [[D, 2, 2, 2D]]2 ,

theo chu kỳ 3 .

Định nghĩa 2.23. Một số vô tỷ bậc hai x là N -giảm nếu x > N và −1 < x < 0,
trong đó x là liên hợp Galois của x, tức là nghiệm còn lại của đa thức tối tiểu
của x.
Khi đó, bằng tính tốn, ta có bổ đề sau:
Bổ đề 2.24. (a) Cho x là N -giảm. Cho A = x và y = N/(x − A). Thì y là
N -giảm và −N/y = A.
(b) Cho x là N -giảm. Khi đó, y = −N/x là N -giảm.
Định lý 2.25. Cho x0 là N -giảm và giả sử rằng [[x0 ]]N là tuần hồn theo chu
kỳ k . Thì [[x0 ]]N = [a0 , a1 , . . . , ak−1 ]N , nghĩa là chu kỳ bắt đầu từ a0 .


18

Chứng minh. Chúng ta có x0 = [x0 ]N = [a0 , x1 ]N = [a0 , a1 , x2 ]N = . . . và từ Bổ đề
2.24 chúng ta có xi là N -giảm với mọi i ≥ 0. Bây giờ theo giả thiết chúng ta có,
với một số j ,
x0 = [a0 , a1 , . . . , aj−1 , aj , . . . , aj+k−1 ]N .

Đặt z = xj = xj+k . Suy ra z = xj = N/(xj−1 − aj−1 ) và tương tự z = xj+k =
N/(xj+k−1 − aj+k−1 ). Như vậy
xj−1 = aj−1 + N/z,


xj+k−1 = aj+k−1 + N/z,

xj−1 = aj−1 + N/z,

xj+k−1 = aj+k−1 + N/z,

và do đó xj−1 − xj+k−1 = aj−1 − aj+k−1 . Nhưng −1 < xi < 0 với mọi i, vì vậy
−1 < xj−1 − xj+k−1 < 1. Nhưng aj−1 và aj+k−1 là hai số ngun, vì vậy ép
xj−1 = xj+k−1 và do đó aj−1 = aj+k−1 . Thực hiện theo cách quy nạp đi xuống
chúng ta có được aj−2 = aj+k−2 , . . . , a0 = ak và do đó chu kỳ bắt đầu bằng a0 .
√

Hệ quả 2.26. Cho N là nhỏ. Giả sử [[ E]]N là tuần hoàn theo chu kỳ k . Khi
√
đó [[ E]]N = [a0 , a1 , . . . , ak ]N với ak = 2a0 .
√

Chứng minh. Đặt x = D + E . Suy ra [[x]]N = [2a0 , a1 , a2 , . . .]N . Nhưng x là
N -giảm vì vậy [[x]]N là tuần hoàn bắt đầu với 2a0 , theo Định lý 2.25.
√

Hệ quả 2.27. Cho N là lớn. Giả sử [[ E]]N là tuần hoàn theo chu kỳ k . Cho
√
√
h = N/(D + E) ≥ 1. Khi đó [[ E]]N = [a0 , a1 , a2 , . . . , ak+1 ]N với ak+1 = a1 + h.
Chứng minh. Cho x =
√

N

E−D

√
E . Suy ra [[x]]N = [a0 , a1 , x2 ]N với a0 = D, x1 =

N
=
x 0 − a0

√
, a1 = N/( E − D) ≥ N , và x2 = N/(x1 − a1 ). Chắc chắn x2 > N .

N
√
< 0, nên x2 < 0. Ngoài ra,
− E−D
−1/x2 = (a1 − x1 )/N > a1 /N ≥ 1, nên −1 < x2 . Như vậy x2 là N -giảm, và do đó,

Bây giờ x2 = N/(x1 − a1 ) và x1 =

theo Định lý 2.25, [[x2 ]]N = [a2 , a3 , . . .]N là tuần hoàn theo chu kỳ k bắt đầu với
a2 .
Bây giờ chúng ta áp dụng các lập luận trong chứng minh Định lý 2.25 để kết
luận rằng x1 − xk+1 = a1 − ak+1 . Vì xk+1 là N -giảm, nên −1 < xk+1 < 0. Nhưng
√
√
x1 = N/( E − D) suy ra x1 = −N/( E + D) và do đó −(h + 1) < x1 < −h, vì vậy
chúng ta phải có a1 − ak+1 = −h suy ra ak+1 = a1 + h.
Định lý sau đây cho ta thây chiều ngược lại của Định lý 2.25 cũng đúng.



19

Định lý 2.28. Giả sử [[x0 ]]N là tuần hoàn theo chu kỳ k bắt đầu từ a0 , [[x0 ]]N =
[a0 , a1 , . . . , ak−1 ]N . Thì, x0 là N -giảm.
Chứng minh. Đầu tiên quan sát thấy rằng x0 > a0 = ak ≥ N .
x0 pk−1 + N pk−2
, chỉ ra rằng x0 là một nghiệm của đa
x0 qk−1 + N qk−2
thức f (x) = x2 qk + (qk−1 N − pk )x − pk−1 N = 0. Bây giờ f (0) = −pk−1 N < 0 và

Bây giờ x0 = xk =

f (−1) = qk − qk−1 N + pk − pk−1 N = (ak − N )qk−1 + qk−2 + (ak − N )pk−1 + pk−2 > 0

khi ak ≥ N . Do đó nghiệm cịn lại của đa thức này, đặt là x0 , phải nằm giữa −1
và 0.
Bổ đề 2.29. Cho [[x0 ]]N = [a0 , . . . , ak−1 ]N tuần hoàn theo kỳ k bắt đầu với a0 , và
cho y0 = −N/x0 . Thì [[y0 ]]N = [ak−1 , . . . , a0 ]N .
Chứng minh. Viết x0 = [x0 ]N = [a0 , x1 ]N = [a0 , a1 , x2 ]N = . . .. Lưu ý rằng, theo
Định lý 2.28, x0 là N -giảm, và do đó theo Bổ đề 2.24, mỗi xi là N -giảm. Ngoài
ra, theo Bổ đề 2.24, y0 là N -giảm. Suy ra
x0 = a0 + N/x1 ,

x1 = a1 + N/x2 ,

...,

xk−1 = ak−1 + N/xk


hoặc tương đương
−N/x1 = a0 − x0 ,

...,

−N/xk = ak−1 − xk−1 .

Đặt zk−i = −N/xi , i = 0, . . . , k . Thì ta có
z0 = ak−1 − xk−1 ,

z1 = ak−2 − xk−2 ,

...,

zk−1 = a0 − x0 .

Nhưng 0 < −xi < 1 và zi+1 = N/(zi − ak−1−i ) với mọi i, vì vậy chúng ta thấy rằng
z0 = [z0 ]N = [ak−1 , z1 ]N = [ak−1 , ak−2 , z2 ]N = . . . = [ak−1 , . . . , a0 , zk ]N .

Nhưng xk = x0 nên zk = z0 và do đó
z0 = [[ak−1 , . . . , a0 ]]N ,

đây là khai triển tốt nhất khi ai ≥ N với mọi i. Nhưng theo định nghĩa, y0 = z0 .
(Ngoài ra, nếu y0 = [y0 ]N = [ak−1 , y1 ]N = [ak−1 , ak−2 , y2 ]N = . . ., chúng ta có yi = zi
với mọi i.)
√

Định lý 2.30. Cho N là nhỏ và giả sử rằng [[ E]]N là tuần hoàn theo chu kỳ
k . Thì
√

[[ E]]N = [a0 , a1 , . . . , ak−1 , 2a0 ]N với ai = ak−i , i = 1, . . . , k − 1.


20

Chứng minh. Như chúng ta đã thấy
√
[[ E + D]]N = [2a0 , a1 , . . . , ak−1 ]N

vì thế

√
[[ E − D]]N = [0, a1 , . . . , ak−1 , 2a0 ]N

và do đó

√
N/( E − D) = [a1 , . . . , ak−1 , 2a0 ]N .
√
√
Nhưng nếu x0 = N/( E − D), y0 = −N/x0 = E + D, thì
√
[[ E + D]]N = [2a0 , ak−1 , . . . , a1 ]N
√
và so sánh hai biểu thức cho [[ E + D]]N suy ra định lý trên.

Định nghĩa 2.31. Một dãy các số nguyên c1 , . . . , ck là dãy đối xứng (palindromic) nếu nó đọc từ phải sang trái giống như đọc từ trái sang phải, nghĩa là
nếu ci = ck+1−i với i = 1, . . . , k . Một dãy là dãy nửa đối xứng (semipalindromic)
của loại (j, k ) nếu nó là sự ghép nối của một dãy đối xứng (palindromic) chiều
dài j theo sau là một dãy đối xứng (palindromic) chiều dài k , nghĩa là, nếu nó

có dạng c1 , . . . , cj , d1 , . . . , dk với c1 , . . . , cj và d1 , . . . , dk là các dãy đối xứng.
Nhận xét 2.32. Theo Định lý 2.30, chúng ta thấy rằng đối với N nhỏ, nếu
√
[[ E]]N tuần hoàn theo chu kỳ k với phần tuần hoàn cho bởi a1 , . . . , ak (ln
ln đúng với N = 1), thì hoặc ta có k = 1 hoặc a1 , . . . , ak là nửa đối xứng loại
(k − 1, 1).
√

Bây giờ giả sử rằng N là lớn và [[ E]]N tuần hoàn theo chu kỳ k với phần
tuần hoàn cho bởi a2 , . . . , ak+1 . Trong trường hợp này tình huống phức tạp hơn.
Ví dụ 2.33. (a) Các khai triển cfN trong Bổ đề 2.18(d) là nửa đối xứng loại
(1, 1).
(b) Ta có khai triển nửa đối xứng
√
8 = [[2, 9, 12, 44, 12, 10]]8 loại (3, 1),
√
53 = [[7, 399, 132, 132, 406]]112 loại (2, 1),
√
65 = [[8, 2312, 149, 702, 184, 341, 180, 341, 184, 702, 149, 2320]]144 loại (9, 1).

(c) Ta có khai triển nửa đối xứng
√
√

7 = [[2, 15, 20, 17, 65, 17]]10 loại (1, 3),
23 = [[4, 55, 152, 60, 18568, 60]]44 loại (1, 3).


21


(d) Ta có khai triển nửa đối xứng
√
13 = [[3, 196, 231, 247996, 231, 214, 7854, 214]]119 loại (3, 3),
√
129 = [[11, 108, 39, 176, 204, 176, 39, 109, 52, 98, 42, 98, 52, 109]]39 loại (5, 7).

(e) Các khai triển dưới đây không là nửa đối xứng
√
31 = [[5, 22, 14, 26, 56, 23]]13 ,
√
187 = [[13, 85, 60, 63, 232, 84, 332, 87]]58 ,
√
215 = [[14, 116, 480, 77, 128, 429, 112, 118]]77 .

2.3

Phương trình Pell
√

Cho khai triển cfN bất kỳ của x0 = E , ta có hội tụ thứ i của nó Ci = pi /qi
trong đó pi và qi được đưa ra bởi đệ quy trong Định lý 2.2. Trong trường hợp
cổ điển, điều này liên quan mật thiết đến các cách giải phương trình của Pell
p2 − Eq 2 = 1. Trong mục này, chúng ta sẽ thấy một số tính chất tương tự trong
trường hợp N bất kỳ.
√

Bổ đề 2.34. Cho [ E]N = [x0 ]N = [a0 , x1 ]N = [a0 , a1 , x2 ]N = . . . là khai triển cfN
√
bất kỳ của E . Khi đó
√

xi =

ui + N i E
,
vi

với các số nguyên ui , vi được định nghĩa quy nạp bởi
u0 = 0,

v0 = 1,

ui+1 = N (ai vi − ui ),
vi+1 =

N 2i+2 E − (ui+1 )2
.
N 2 vi

Chứng minh. Theo định nghĩa, xi = ai +

N
N
, tức là, xi+1 =
và tính tốn
xi+1
x i − ai

đơn giản cho thấy
xi+1


√
√
N (ai vi − ui ) + N i+1 E
ui+1 + N i+1 E
=
=
.
vi+1
N 2i E − (ai vi − ui )2
vi

Rõ ràng ui+1 là một số nguyên. Ta đi chứng minh rằng vi+1 là một số nguyên
bằng quy nạp. Lưu ý rằng u1 = N a0 , v1 = E − a20 nên v0 và v1 là các số nguyên.
Suy ra vi+1 ∈ Z ⇔ vi |N 2i E − (ai vi − ui )2 ⇔ vi |N 2i E − u2i .


22
N 2i Eu2i
N 2i E − u2i
∈ Z theo quy nạp, nên
= N 2 vi−1 ∈ Z như yêu
Nhưng vi =
N 2 vi−1
vi

cầu.
√

Bổ đề 2.35. Cho [ E]N = [x0 ]N = [a0 , x1 ]N = [a0 , a1 , x2 ]N = . . . là khai triển cfN
√

bất kỳ của E . Khi đó p2i − Eqi2 = (−1)i+1 vi+1 .
Chứng minh. Ta chứng minh bằng quy nạp theo i. Với i = −1, p2i − Eqi2 = (1)2 −
E(0)2 = 1 = v0 . Với i = 0, p2i − Eqi2 = a20 − E(1)2 = −(E − a0 )2 = −v1 .
Giả sử đúng với i. Suy ra
√
[ E]N = [a0 , . . . , ai , xi+1 ]N

vì thế

√
xi+1 pi + N pi−1
E=
.
xi+1 qi + nqi−1

Nhưng
xi+1

√
ui+1 + N i+1 E
=
.
vi+1

Thay vào, ta được
N i+1 Eqi = ui+1 pi + pi−1 vi+1 N,

(2.1)

ui+1 qi + qi−1 vi+1 N = N i+1 pi .


(2.2)

Lấy pi (2.2)−qi (2.1) ta được
N i+1 (p2i − Eqi2 ) = N vi+1 (pi qi−1 − pi−1 qi ).

Nhưng chúng ta biết rằng pi qi−1 − pi−1 qi = (−1)i−1 N i và thay thế và khử ta được
p2i − Eqi2 = (−1)i+1 vi .
√

Định lý 2.36. Cho N là nhỏ và giả sử rằng [[ E]]N là tuần hoàn. Trong trường
√
√
√
hợp này, [[ E]]N là tuần hoàn bắt đầu với a1 . Cho [[ E]]N có chu kỳ k, [[ E]]N =
[a0 , a1 , . . . , ak ]N . Trong trường hợp này, ak = 2a0 = 2D. Thì vk = N k , tức là,
2
p2k−1 − Eqk−1
= (−N )k , và uk = a0 N k = DN k .
√
Ngược lại, nếu vk = N k và uk chia hết cho N k , thì [[ E]]N là tuần hoàn theo
chu kỳ k với a1 , và ak = 2a0 .
√

Chứng minh. Giả sử [[ E]]N tuần hoàn theo chu kỳ k . Suy ra x1 = [a1 , . . . , ak ]N
nên
[a0 , x1 ]]N = [[a0 , a1 , . . . , ak , x1 ]]N = [[a0 , a1 , . . . , ak , xk+1 ]]N

và do đó xk+1 = x1 .