Luận văn Về các dãy hồi quy tuyến tính

, ..., 0, 1, ..., m− 3 2 , m− 1 2 là hệ thặng dư đầy đủ, được gọi là hệ thặng dư tuyệt đối bé nhất môđulô m. 1.1.5 Định lý. Giả sử a, b, c vàm là các số nguyên,m > 0 và a ≡ b(modm). Khi đó: 1) a+ c ≡ b+ c(modm), 2) a− c ≡ b− c(modm), 3) ac ≡ bc(modm). Chứng minh. Vì a ≡ b(modm) nên m|(a− b). Do (a+ c)− (b+ c) = a− b nên m|[(a+ c)− (b− a)]: 1) được chứng minh. Tương tự 2) được suy ra từ chỗ (a− c)− (b− c) = a− b. 7 Để chứng minh 3) ta chú ý rằng ac− bc = c(a− b) nên từ m|(a− b) suy ra m|c(a− b), tức là ac ≡ bc(modm). Tuy nhiên, nói chung không thể làm phép chia hai vế của cùng một đồng dư cho một số. Chẳng hạn 2002 ≡ 4(mod6) nhưng 2002 2 = 1001 6= 2(mod6). 1.1.6 Định lý. Giả sử a, b, c và m là các số nguyên, m > 0 và ac ≡ bc(modm) và d = (c,m). Khi đó ta có a ≡ b(modm d ). Chứng minh. Giả sử ac ≡ bc(modm). Ta có m|(ac− bc) = c(a− b). Do đó tồn tại số nguyên k sao cho c(a− b) = km. Chia hai vế cho d ta được: c d (a− b) = km d . Vì ( c d , m d ) = 1 nên từ đó suy ra m d |(a− b), tức là a ≡ b(modm d ). Ví dụ: 2002 ≡ 2(mod5). Do (2, 5) = 1 nên ta có 1001 ≡ 1(mod5). Định lý sau đây là hệ quả của định lý 1.1.6. 1.1.7 Định lý. Nếu a, b, c vàm là các số nguyên, sao chom > 0, (c,m) = 1, và ac ≡ bc(modm). Khi đó a ≡ b(modm). Định lý 1.1.7 có thể mở rộng thành định lý sau đây, cho ta thấy rằng có thể làm một số phép tính số học đối với các lớp đồng dư như đối với các số nguyên. 8 1.1.8 Định lý. Nếu a, b, c, d và m là các số nguyên, m > 0, a ≡ b(modm), c ≡ d(modm). Khi đó: 1) a+ c ≡ b+ d(modm), 2) a− c ≡ b− d(modm), 3) ac ≡ bd(modm). Chứng minh. Vì a ≡ b(modm), c ≡ d(modm) nênm|(a− b),m|(c−d). Do đó tồn tại các số nguyên k và l sao cho km = a− b, lm = c− d. Để chứng minh 1), ta nhận xét rằng (a+c)−(b+d) = km+lm = (k+l)m. Do đó m|[(a+ c)− (b+ d)] tức là a+ c ≡ b+ d(modm). Để chứng minh 2) ta chú ý rằng (a− c)− (b− d) = (a− b)− (c− d) = km−lm = (k−l)m. Do đóm|[(a−c)−(b−d)], tức là a−c ≡ b−d(modm). Để chứng minh 3), ta thấy ac−bd = ac−bc+bc−bd = c(a−b)+b(c−d) = ckm+ blm, tức là m|(ac− bd). Do đó ac ≡ bd(modm). 1.1.9 Định lý. Giả sử r1, r2, ..., rm là hệ đầy đủ các thặng dư môđulô m, a là số nguyên dương và (a,m) = 1. Khi đó ar1 + b, ar2 + b, ..., arm + b cũng là một hệ thặng dư đầy đủ môđulô m. Chứng minh. Trước tiên ta chỉ ra rằng, trong các số nguyên ar1 + b, ar2 + b, ..., arm + b không có hai số nào đồng dư nhau môđulô m. Thật vậy, nếu arj + b ≡ ark + b(modm) thì arj ≡ ark(modm). Do (a,m) = 1 nên theo định lý 1.1.7 ta có rj ≡ rk(modm). 9 Vì rj 6≡ rk(modm) nếu j 6= k nên ta suy ra j = k. Do tập hợp các số nguyên trên đây gồmm số nguyên không đồng dư môđulô m nên các số nguyên đó lập thành hệ thặng dư đầy đủ môđulô m. Định lý sau cho thấy rằng, các đồng dư được bảo toàn nếu cả hai vế được nâng lên cùng một luỹ thừa nguyên dương. 1.1.10 Định lý. Giả sử a, b, k,m là các số nguyên, đồng thời k > 0, m > 0, a ≡ b(modm). Khi đó ak ≡ bk(modm). Chứng minh. Do a ≡ b(modm), ta có m|(a− b). Vì ak − bk = (a− b)(ak−1 + ak−2b+ ...+ abk−2 + bk−1) nên (a− b)|(ak − bk). Vậy m|(ak − bk), tức là ak ≡ bk(modm). Trong trường hợp các số a, b đồng dư nhau môđulô nhiều số nguyên dương khác nhau, ta có thể kết hợp lại theo định lý sau. 1.1.11 Định lý. Giả sử a ≡ b(modm1), a ≡ b(modm2), ..., a ≡ b(modmk), trong đó a, b,m1, ...,mk là các số nguyên, m1,m2, ...,mk > 0. Khi đó a ≡ b(mod[m1...mk]) trong đó [m1...mk] là bội chung nhỏ nhất của m1, ...,mk. Chứng minh. Vì a ≡ b(modm1), a ≡ b(modm2), ..., a ≡ b(modmk), nên ta có m1|(a− b),m2|(a− b), ...,mk|(a− b). Từ đó suy ra rằng [m1,m2, ...,mk]|(a− b), tức là a ≡ b(mod[m1...mk]). 10 1.1.12 Hệ quả. Giả sử a ≡ b(modm1), a ≡ b(modm2), ..., a ≡ b(modmk), trong đó a, b nguyên, m1,m2, ...,mk là các số nguyên dương nguyên tố cùng nhau từng cặp. Khi đó a ≡ b(modm1...mk). Chứng minh. Do m1,m2, ...,mk là các số nguyên dương nguyên tố cùng nhau từng cặp nên ta có [m1m2...mk] = m1m2...mk. khi đó hệ quả được suy trực tiếp từ định lý 1.1.11. 1.2 Đồng dư tuyến tính Một đồng dư dạng ax ≡ b(modm), trong đó x là một số nguyên chưa biết, được gọi là đồng dư tuyến tính một biến. Ta sẽ thấy rằng, việc nghiên cứu các đồng dư như vậy hoàn toàn tương tự việc nghiên cứu phương trình nghiệm nguyên hai biến. Trước tiên ta nhận xét rằng nếu x = x0 là một nghiệm của đồng dư ax ≡ b(modm) và nếu x1 ≡ x0(modm), thì ax1 ≡ ax0 ≡ b(modm), nên x1 cũng là một nghiệm. Như vậy, nếu một phần tử của một lớp đồng dư môđulô m nào đó là một nghiệm, thì mọi phần tử của lớp đó cũng là nghiệm. Vì thế có thể đặt câu hỏi: trong m lớp đồng dư môđulô, có bao nhiêu lớp cho nghiệm, hay một cách tương đương, có bao nhiêu nghiệm không đồng dư môđulô m. 1.2.1 Định lý. Giả sử a, b,m là các số nguyên, m > 0 và (a,m) = d. Nếu d 6 |b thì đồng dư ax ≡ b(modm) vô nghiệm. Nếu d|b thì ax ≡ b(modm) có đúng d nghiệm không đồng dư môđulô m. Chứng minh. Số nguyên x là nghiệm của đồng dư ax ≡ b(modm) nếu và chỉ nếu tồn tại số nguyên y sao cho ax −my = b. Vì d = (a,m) nên d|b. Vậy, nếu d 6 |b thì đồng dư đang xét không tồn tại nghiệm. 11 Bây giờ giả sử d|b. Vì d = (a,m) nên tồn tại các số nguyên s, t sao cho d = as+mt. Mặt khác, tồn tại số nguyên e sao cho b = de. Từ đó ta được b = a(se) +m(te). Như vậy, ta có thể lấy một nghiệm của đồng dư là x0 = se. Ta sẽ chứng tỏ rằng, các số x = x0 +m ( a d ) k, trong đó k nguyên, đều là nghiệm đồng đư đang xét. Thật vậy ax = ax0 +m ( a d ) k, mà ax0 ≡ b(modm), a d nguyên nên ax ≡ ax0 ≡ b(modm). Ngược lại, mọi nghiệm của đồng dư đều phải có dạng (1). Thật vậy, giả sử x là nghiệm tuỳ ý, ax−my = b. Ta có: a(x− se)−m(y + te) = 0 tức là a(x− se) = m(y + te). Chia hai vế cho d ta được a d (x− se) = m d (y + te). Do d = (a,m) nên ( a d , m d ) = 1, suy ra a d |(y+te). Vậy phải tồn tại số nguyên k sao cho a d k = (y+ te), tức là y = a d k− te. Do đó a(x− se) = a d mk. Vậy, x = se+ m d k = x0 + m d k. 12 Còn phải chứng minh rằng, có đúng d nghiệm không đồng dư môđulô m. Giả sử các nghiệm x1 = x0 + m d t1 và x2 = x0 + m d t2 đồng dư môđulô m: x0 + m d t1 ≡ x0 + m d t2(modm). Ta có m d t1 ≡ m d t2(modm). Vì m d |m nên (m, m d ) = m d nên theo định lý 1.1.6, t1 ≡ t2(modm) Như vậy, hệ đầy đủ các nghiệm không đồng dư nhận được bằng cách đặt x = x0 + m d t, trong đó t chạy qua hệ đầy đủ các thặng dư môđulô d. Tập hợp đó có đúng d phần tử, cho bởi t = 0, 1, 2, ..., d− 1. 1.2.2 Định nghĩa. Giả sử a,m là các số nguyên, m > 1. Nghiệm của đồng dư ax ≡ 1(modm) được gọi là nghịch đảo của a môđulô m. Đặc biệt, có những số là nghịch đảo của chính nó môđulô một số nguyên tố p. 1.2.3 Mệnh đề. Giả sử p là một số nguyên tố. Số nguyên a là nghịch đảo môđulô p của chính nó khi và chỉ khi a ≡ 1(modp) hoặc a ≡ −1(modp). Chứng minh. Nếu a ≡ 1(modp) hoặc a ≡ −1(modp) thì a2 ≡ 1(modp) nên a là nghịch đảo của chính nó. Ngược lại, giả sử a là nghịch đảo của chính nó, tức là a2 = a.a ≡ 1(modp). Khi đó p|(a2−1). Vì (a2−1) = (a−1)(a+1) mà p nguyên tố, nên p|(a−1) hoặc p|(a+ 1). Do đó, a ≡ 1(modp) hoặc a ≡ −1(modp). 13 1.3 Định lý Fécma bé 1.3.1 Định lý. (Định lý Fécma bé). Giả sử p là số nguyên tố và a là số nguyên dương với p 6 |a. Khi đó ap−1 ≡ 1(modp). Chứng minh. Xét p− 1 số nguyên a, 2a, ..., (p− 1)a. Không số nguyên nào trong các số nói trên chia hết cho p, vì p|ja với j nào đó thì p|j do (a, p) = 1. Mà ta có 1 ≤ j ≤ p − 1. Hơn nữa, không có hai số nguyên nào trong dãy trên đồng dư môđulô p. Thật vậy nếu ja ≡ ka(modp) thì do (a, p) = 1 nên suy ra j ≡ k(modp), tức là j = k, (vì 1 ≤ j ≤ p − 1). Như vậy, các số nguyên a, 2a, ..., (p− 1)a là tập hợp (p− 1) số nguyên không đồng đư 0 và không có hai số nào đồng dư nhau môđulô p, nên các thặng dư dương bé nhất của hệ đó phải là 1, 2, ..., (p− 1) xếp theo thứ tự nào đó. Từ đó suy ra a.2a...(p− 1)a ≡ 1.2...(p− 1)(modp). Vậy ap−1(p− 1)! ≡ (p− 1)!(modp). Vì ((p− 1)!, p) = 1 nên ta được ap−1 ≡ 1(modp). 1.3.2 Hệ quả. Giả sử p là số nguyên tố và a là số nguyên dương. Khi đó ap ≡ a(modp). Chứng minh. Nếu p 6 |a thì theo Định lý Fécma bé, ta có ap−1 ≡ 1(modp). Nhân hai vế với a ta được ap ≡ a(modp). Ngược lại, nếu p|a thì p|ap nên ap ≡ a ≡ 0(modp). 14 1.3.3 Hệ quả. Giả sử p là số nguyên tố và a là số nguyên tố với p 6 |a. Khi đó ap−2 là nghịch đảo của a môđulô p. Chứng minh. Giả sử p 6 |a. Khi đó theo định lý Fécma bé ta có a.ap−2 = ap−1 ≡ 1(modp). Vậy ap−2 là nghịch đảo của a môđulô p. 1.3.4 Hệ quả. Giả sử a, b là các số nguyên dương và p là số nguyên tố, p 6 |a. Khi đó nghiệm của đồng dư tuyến tính ax ≡ b(modp) là các số nguyên x sao cho x ≡ ap−2b(modp). Chứng minh. Giả sử ax ≡ b(modp). Vì p 6 |a nên ap−2 là một nghịch đảo của a(modp). Từ đó ta có: x ≡ ap−2ax ≡ ap−2b(modp). 1.4 Số giả nguyên tố Theo Định lý Fécma bé, nếu n là số nguyên tố thì với mọi số nguyên b ta có bn ≡ b(modn). Như vậy, nếu có số nguyên b sao cho bn 6≡ b(modn) thì n phải là hợp số. Tuy nhiên, Định lý Fécma bé lại không cho ta cách kiểm tra xem một số n có phải là số nguyên tố hay không. Nói cách khác, phần đảo của định lý Fécma bé không phải bao giờ cũng đúng. Ví dụ: với n = 341, b = 2 ta có: n = 11.31, 2340 = (210)34 ≡ 1(mod11); 2340 = (25)68 = 3268 ≡ 1(mod31). Từ đó suy ra 2340 ≡ 1(mod341), nhưng n = 341 là hợp số. 15 1.4.1 Định nghĩa. Giả sử b là số nguyên dương. Nếu n là một hợp số nguyên dương và bn ≡ b(modn) thì n được gọi là số giả nguyên tố cơ sở b. Ví dụ trên đây cho thấy rằng 341 là số giả nguyên tố cơ sở 2. Chú ý rằng, nếu (b, n) = 1 thì từ bn ≡ b(modn), ta suy được bn−1 ≡ 1(modn). Ta cũng thường dùng đẳng thức này để làm định nghĩa cho các số giả nguyên tố cơ sở b và nguyên tố cùng nhau với b. Các số giả nguyên tố rất "thưa", chẳng hạn trong 1010 số tự nhiên đầu tiên có 455.052.512 số nguyên tố, nhưng chỉ có 14.884 số giả nguyên tố cơ sở 2. Tuy nhiên, với mọi số nguyên b > 1, tồn tại vô hạn số giả nguyên tố cơ sở b. Ta sẽ chứng minh điều này cho trường hợp b = 2. Trước hết ta có bổ đề sau: 1.4.2 Bổ đề. Giả sử d, n là các số nguyên dương sao cho d|n. Khi đó (2d − 1)|(2n − 1). Chứng minh. Vì d|n nên tồn tại số nguyên t sao cho dt = n. Đặt x = 2d, từ khai triển xt − 1 = (x− 1)(xt−1 + xt−2 + ...+ 1) ta có: 2n − 1 = (2d − 1)(2d(t−1) + 2d(t−2) + ...+ 2d + 1), tức là (2d − 1)|(2n − 1). 1.4.3 Định lý. Tồn tại vô hạn số giả nguyên tố cơ sở 2. Chứng minh. Giả sử n là một số giả nguyên tố cơ sở 2. Ta sẽ chứng tỏ rằng, m = 2n − 1 cũng là số giả nguyên tố cơ sở 2. Theo giả thiết, n là hợp số, chẳng hạn n = dt(1 < d, t < n) và 2n−1 ≡ 1(modn). Vì (2d − 1)|(2n − 1) nên m là hợp số. Do n là số giả nguyên tố, 2n ≡ 2(modn), tức là tồn tại k sao cho 2n − 2 = kn. Ta có: 2m−1 = 22n−2 = 2(kn+2)−2 = 2kn. Do đó m = (2n − 1)|(2nk − 1) = 2m−1 − 1, tức là 2m−1 ≡ 1(modn). Vậy m là số giả nguyên tố cơ sở 2. 16 Chương 2 Các quan hệ hồi quy 2.1 Quan hệ hồi quy tổng quát 2.1.1 Định nghĩa. Quan hệ hồi quy bậc k là một công thức cho phép tính giá trị f(n+ k) qua các giá trị f(n), f(n+ 1), ..., f(n+ k − 1). Ví dụ: f(n+ 2) = n2f(n+ 1)− f(n) + f(n− 1) là quan hệ hồi quy bậc ba, f(n+ 1) = f(n) + f(n− 1) là quan hệ hồi quy bậc hai. (1) 2.1.2 Chú ý. Đối với quan hệ hồi quy bậc k, nếu cho các giá trị f(1), ..., f(k) thì các giá trị còn lại hoàn toàn được xác định. Chẳng hạn trong quan hệ (1), nếu ta cho f(1) = f(2) = 1 thì ta nhận được dãy số nổi tiếng gọi là các số Fibonacci. 2.1.3 Định nghĩa. Một dãy f(n) thỏa mãn một quan hệ hồi quy nào đó được gọi là một nghiệm của quan hệ đó. Nếu quan hệ hồi quy bậc k thì k giá trị ban đầu của dãy có thể lấy tùy ý, các giá trị tiếp theo hoàn toàn được xác định. Một nghiệm của quan hệ hồi quy bậc k được gọi là nghiệm tổng quát nếu nó phụ thuộc k hằng số tùy ý C1, ..., Ck. Ví dụ: Xét quan hệ hồi quy f(n+ 2) = 5f(n+ 1)− 6f(n). (2) 17 Dễ dàng chứng minh được f(n) = C12 n + C23 n là nghiệm của quan hệ hồi quy đang xét (2). Nghiệm tùy ý được xác định qua các giá trị f(1), f(2). Chẳng hạn nếu đặt f(1) = a, f(2) = b ta được hệ{ 2C1 + 3C2 = a 4C1 + 9C2 = b Hệ phương trình này có nghiệm C1, C2 với mọi giá trị của a, b. 2.2 Hồi quy tuyến tính hệ số hằng 2.2.1 Định nghĩa. Quan hệ hồi quy tuyến tính bậc k với hệ số hằng là quan hệ có dạng f(n+ k) = a1f(n+ k − 1) + a2f(n+ k − 2) + ...+ akf(n), trong đó a1, a2, ..., ak là các hằng số nào đó (không phụ thuộc n) Trước tiên ta xét trường hợp đơn giản: các quan hệ hồi quy tuyến tính với hệ số hằng f(n+ 2) = a1f(n+ 1) + a2f(n). (3) 2.2.2 Bổ đề. Nếu f1(n), f2(n) là các nghiệm của (3) thì với các số tùy ý A,B dãy f(n) = Af1(n) +Bf2(n) cũng là nghiệm của (3). Chứng minh. Vì f1(n), f2(n) là các nghiệm của (3) nên ta có: f1(n+ 2) = a1f1(n+ 1) + a2f1(n), f2(n+ 2) = a1f2(n+ 1) + a2f2(n) Suy ra Af1(n+2)+Bf2(n+2) = a1[Af1(n+1)+Bf2(n+1)]+a2[Af1(n)+Bf2(n)]. Vậy f(n) = Af1(n) +Bf2(n) là nghiệm của (3). 18 2.2.3 Bổ đề. Giả sử r1 là nghiệm của phương trình r2 = a1r + a2 (4). Khi đó dãy {rn} là một nghiệm của quan hệ f(n+ 2) = a1f(n+ 1) + a2f(n) (5). Chứng minh. Ta có f(n) = rn1 , f(n+ 1) = r n+1 1 , f(n+ 2) = r n+2 1 . Theo giả thiết, r1 là nghiệm của phương trình r 2 = a1r + a2 nên ta có r21 = a1r1 + a2. Suy ra a1r n+1 1 + a2r n 1 = r n 1 (a1r1 + a2) = r n 1r 2 1 = r n+2 1 . Vậy {rn} là một nghiệm của quan hệ (5). 2.2.4 Nhận xét. Dãy { rn+m1 } vớim tùy ý cũng là một nghiệm. Thật vậy, chỉ cần áp dụng Bổ đề 2.2.2 với B = 0, A = rm1 . Phương trình (4) gọi là phương trình đặc trưng của quan hệ (5). Từ các Bổ đề 2.2.2 và Bổ đề 2.2.3, ta có định lí sau: 2.2.5 Định lý. Giả sử cho quan hệ hồi quy f(n+ 2) = a1f(n+ 1) + a2f(n). (6) Giả sử phương trình đặc trưng r2 = a1r + a2 có hai nghiệm phân biệt r1 và r2. Khi đó, nghiệm tổng quát của (6) có dạng f(n) = C1r n−1 1 + C2r n−1 2 . Chứng minh. Theo Bổ đề 2.2.3, f1(n) = r n−1 1 , f2(n) = r n−1 2 là các nghiệm của quan hệ đang xét. Theo Bổ đề 2.2.2, với mọi C1, C2 tùy ý, C1r n 1 +C2r n 2 là nghiệm. Chỉ còn phải chứng minh rằng, nghiệm tùy ý của quan hệ (6) có 19 thể viết dưới dạng đã nêu trong định lí. Mỗi nghiệm của quan hệ (6) được xác định duy nhất bởi các giá trị f(1), f(2). Vì thế, chỉ cần chỉ ra rằng, hệ phương trình { C1 + C2 = a C1r1 + C2r2 = b có nghiệm với a, b tùy ý. Dễ thấy rằng, các nghiệm đó là C1 = b− ar2 r1 − r2 , C2 = ar1 − b r1 − r2 Định lí được chứng minh. Bây giờ ta chuyển sang xét trường hợp phương trình đặc trưng có nghiệm bội. Giả sử phương trình đặc trưng của quan hệ đã cho có các nghiệm trùng nhau, chẳng hạn r1 = r2. Khi đó biểu thức C1r n−1 1 + C2r n−1 2 không còn là nghiệm tổng quát nữa, vì nghiệm đó được viết dưới dạng f(n) = Crn−11 . Nói chung, không thể chọn hằng số C sao cho hai điều kiện ban đầu f(1) = a, f(2) = b được thỏa mãn. 2.2.6 Định lý. Giả sử phương trình đặc trưng r2 = a1r + a2 có nghiệm bội r1. Khi đó nghiệm tổng quát của quan hệ đang xét có dạng f(n) = rn−11 (C1 + C2n), trong đó C1, C2 là các hằng số tùy ý. Chứng minh. Vì phương trình đặc trưng có nghiệm bội nên theo Định lí Viét ta có: a1 = 2r1, a2 = −r21. Ta viết phương trình đặc trưng dưới dạng: r2 = 2r1r − r21. Như vậy quan hệ hồi quy sẽ có dạng f(n+ 2) = 2r1f(n+ 1)− r21f(n) (7). 20 Ta thử lại rằng f2(n) = nr n−1 1 là một nghiệm của quan hệ đang xét. Ta có: f2(n+ 2) = (n+ 2)r n+1 1 , f2(n+ 1) = (n+ 1)r n 1 . Thay các giá trị này vào (7) ta nhận được các đồng nhất thức: (n+ 2)rn+11 = 2(n+ 1)r n+1 1 − nrn+11 . Vậy nrn−11 đúng là một nghiệm. Theo bổ đề 2.2.2, với C1, C2 tùy ý, f(n)rn−11 (C1 + C2n) (8) cũng là nghiệm. Mặt khác, với điều kiện f(1) = a, f(2) = b tùy ý, ta luôn luôn xác định được C1, C2 sao cho (8) là một nghiệm của quan hệ đang xét. Vậy (8) cho ta công thức nghiệm tổng quát trong trường hợp phương trình đặc trưng có nghiệm bội. 2.2.7 Nhận xét. Đối với quan hệ hồi quy tuyến tính hệ số hằng cấp k tùy ý, ta cũng có kết quả hoàn toàn tương tự. Xét quan hệ hồi quy cấp k dạng f(n+ k) = a1f(n+ k − 1) + ...+ akf(n). phương trình đặc trưng tương ứng: rk = a1r k−1 + ...+ ak. Nếu r1, r2, ..., rk là các nghiệm khác nhau của phương trình đặc trưng, thì nghiệm tổng quát sẽ là f(n) = C1r n−1 1 + ...+ Ckr n−1 k . Nếu có nghiệm nào đó trùng nhau, chẳng hạn r1 = r2 = ... = rs thì nghiệm tổng quát sẽ là f(n) = rn−11 (C1 + C2n+ ...+ Csn s−1) + Cs+1rn−1s+1 + ...+ Ckr n−1 k . 21 2.2.8 Ví dụ. Xét quan hệ hồi quy f(n+ 4) = 5f(n+ 3)− 6f(n+ 2)− 4f(n+ 1) + 8f(n). Phương trình đặc trưng có dạng: r4 − 5r3 + 6r2 + 4r − 8 = 0. Các nghiệm của phương trình là r1 = 2, r2 = 2, r3 = 2, r4 = −1. Nghiệm tổng quát của quan hệ hồi quy đang xét sẽ là f(n) = 2n−1(C1 + C2n+ C3n2) + C4(−1)n−1. 2.2.9 Chú ý. Trong các lý luận trên đây, các nghiệm của phương trình đặc trưng có thể là nghiệm phức. Khi đó, để tìm nghiệm thực của quan hệ hồi quy, ta có thể sử dụng công thức eiϕ = cosϕ+ isinϕ. Ví dụ: xét quan hệ hồi quy f(n+ 2) = f(n+ 1)− f(n). Phương trình đặc trưng tương ứng là r2 − r + 1 = 0. Phương trình này có các nghiệm phức r1 = 1 + i √ 3 2 , r2 = 1− i√3 2 , hay là r1 = e ipi3 , r2 = e −ipi3 . Như vậy, nghiệm (thực) tổng quát của quan hệ hồi quy đang xét là f(n) = C1cos npi 3 + C2sin npi 3 . 22 2.3 Dãy Fibonacci Các số Fibonacci là nghiệm của một quan hệ hồi quy đơn giản, nhưng có vai trò quan trọng trong toán học. Ta sẽ nghiên cứu một số tính chất quan trọng của các số Fibonacci. Trong toàn bộ mục này ta ký hiệu F (n) là số Fibonacci thứ n. 2.3.1 Định nghĩa. Số Fibonacci là số Fn định nghĩa bởi: F1 = F2 = 1; với n = 3, 4, ... các số Fn xác định bởi quan hệ hồi quy sau đây: Fn = Fn−2 + Fn−1. Phương trình đặc trưng tương ứng của quan hệ trên là r2 − r − 1 = 0. Phương trình này có các nghiệm: r1 = 1 + √ 5 2 , r2 = 1−√5 2 Nghiệm tổng quát của quan hệ trên có dạng: f(n) = C1 ( 1 + √ 5 2 )n +C2 ( 1−√5 2 )n . (10) Khi đó các hằng số C1, C2 được tính từ hệ phương trình C1 + C2 = 0√5 2 (C1 − C2) = 1. Giải ra ta được C1 = 1√ 5 , C1 = − 1√ 5 . Vậy nghiệm tổng quát có dạng Fn = ( 1 + √ 5 2 )n − ( 1−√5 2 )n √ 5 . Công thức trên được gọi là công thức Binê (Binet). Dựa vào công thức Binê, ta có định lý sau đây cho một tính chất thú vị của các số Fibonacci. 23 2.3.2 Định lý. Số Fibonacci Fn là số nguyên gần nhất đối với số 1√ 5 ( 1 + √ 5 2 )n , tức là số hạng an của cấp số nhân với từ đầu tiên là 1√ 5 ( 1 + √ 5 2 ) và công bội là 1 + √ 5 2 . Chứng minh. Rõ ràng chỉ cần chứng minh rằng trị tuyệt đối của hiệu giữa hai số Fn và an luôn luôn bé hơn 1 2 . Ta có | Fn − an |=| r n 1 − rn2√ 5 − r n 1√ 5 |=| r n 1 − rn1 − rn2√ 5 |= | r2 | n √ 5 . Do | r2 |=| 1− √ 5 2 |< 3− 1 2 = 1 nên | Fn − an |< 1 2 . Sau đây ta sẽ chứng minh một số tính chất cơ bản của dãy số Fibonacci. 2.3.3 Mệnh đề. F1 + F2 + ...+ Fn = Fn+2 − 1. Chứng minh. Ta có: F1 = F3 + F2 F2 = F4 + F3 ... Fn−1 = Fn+1 − Fn Fn = Fn+2 − Fn+1. Cộng từng vế của đẳng thức ta có: F1 + F2 + ...+ Fn = Fn+2 − F2, mà F2 = 1. 2.3.4 Mệnh đề. F1 + F3 + ...+ F2n−1 = F2n. 24 Chứng minh. Ta có: F1 = F2 F3 = F4 − F2 F5 = F6 − F4 ... F2n−1 = F2n − F2n−2. Cộng từng vế của đẳng thức ta được công thức cần chứng minh. 2.3.5 Mệnh đề. F2 + F4 + ...+ F2n = F2n+1 − 1. Chứng minh. Từ mệnh đề 2.3.3 ta có: F1 + F2 + F3 + ...+ F2n = F2n+2 − 1. Trừ từng vế đẳng thức này cho đẳng thức trong mệnh đề 1.3.4 ta được: F2 + F4 + ...+ F2n = F2n+2 − 1− F2n = F2n+1 − 1. 2.3.6 Mệnh đề. F1 − F2 + F3 − F4 + ...+ (−1)n+1Fn = (−1)n+1Fn−1 + 1. Chứng minh. Từ các mệnh đề 2.3.4 và 2.3.5 ta được F1 − F2 + F3 − F4 + ...+ F2n−1 − F2n = −F2n−1 + 1. (1) Cộng thêm vào hai vế F2n+1 ta có: F1 − F2 + F3 − F4 + ...− F2n + F2n+1 = F2n + 1. (2) Công thức trong mệnh đề 2.3.6 chính là kết hợp của hai công thức (1) và (2) (tương ứng với n lẻ và n chẵn). 2.3.7 Mệnh đề. F1 2 + F2 2 + ...+ Fn 2 = FnFn+1. 25 Chứng minh. Ta có: FkFk+1 − Fk−1Fk = Fk(Fk+1 − Fk−1) = Fk2. Do đó F1 2 = F1F2 F 22 = F2F3 − F1F2 F 23 = F3F4 − F2F3 ... F 2n = FnFn+1 − Fn−1Fn Cộng từng vế các đẳng thức này, ta được công thức cần chứng minh. 2.3.8 Mệnh đề. Fn+m = Fn−1Fm + FnFm+1. Chứng minh. Chứng minh quy nạp theo m. Với m = 1 ta có Fn+1 = Fn−1F1 + FnF2. Vậy mệnh đề đúng với m = 1. Giả sử mệnh đề đúng với m = k. Suy ra Fn+k = Fn−1Fk + FnFk+1. Cần chứng minh mệnh đề đúng với m = k + 1. Thật vậy Fn+k+1 = Fn+k + Fn+k−1 áp dụng giả thiết quy nạp ta có Fn+k+1 = Fn−1Fk + FnFk+1 + Fn−1Fk−1 + FnFk = Fn−1(Fk + Fk−1) + Fn(Fk + Fk+1) = Fn−1Fk+1 + FnFk+2, điều phải chứng minh. 2.3.9 Mệnh đề. F2n = F 2 n+1 − F 2n−1. 26 Chứng minh. áp dụng mệnh đề 2.3.8 với n = m ta có F2n = Fn+n = Fn−1Fn + FnFn+1 = Fn(Fn−1 + Fn+1) = (Fn+1 − Fn−1)(Fn+1 + Fn−1) = F 2n+1 − F 2n−1. 2.3.10 Mệnh đề. Fn−1Fn+1 − Fn2 = (−1)n. Chứng minh. Chứng minh quy nạp theo n. Với n = 2 ta có F1F3 − F 22 = 1, vậy mệnh đề đúng với n = 2. Giả sử mệnh đề đúng với n. Ta cần chứng minh mệnh đề đúng với n+ 1. Thật vậy ta có: FnFn+2 − F 2n+1 = FnFn+2 − (Fn−1 + Fn)2 = FnFn+2 − F 2n − F 2n−1 − 2Fn−1Fn = Fn(Fn+1 + Fn)− F 2n−1 − F 2n − 2Fn−1Fn = FnFn+1 + F 2 n − F 2n−1 − F 2n − 2Fn−1Fn = FnFn+1 − F 2n−1 − 2Fn−1Fn = FnFn+1 − F 2n−1 − Fn−1Fn − Fn−1Fn = Fn(Fn+1 − Fn−1)− Fn−1(Fn−1 + Fn) = F 2n − Fn−1Fn+1 = (−1)n+1. 2.3.11 Mệnh đề. Fn+1 2 = 4FnFn−1 + Fn−22. Chứng minh. Ta có F 2n+1 = (Fn−1 + Fn) 2 = F 2n−1 + F 2 n + 2Fn−1Fn = F 2n−1 + F 2 n − 2Fn−1Fn + 4Fn−1Fn = (Fn−1 − Fn)2 + 4Fn−1Fn = 4Fn−1Fn + F 2n−2. 27 2.3.12 Mệnh đề. F(k+1)n = Fn−1Fkn + FnFkn+1. Chứng minh. Ta có F(k+1)n = Fkn+n, áp Mệnh đề 2.3.8 với m = kn ta có điều phải chứng minh. 28 Chương 3 Một số tính chất số học của số Lucas 3.1 Đặc trưng của số giả nguyên tố Lucas không chính phương 3.1.1 Định nghĩa. Số Lucas là số Ln định nghĩa bởi : 1/ L0 = 2, L1 = 1, 2/ Với n = 2, 3, ... các số Ln xác định bởi quan hệ hồi quy sau Ln = Ln−1 + Ln−2. Phương trình đặc trưng tương ứng của quan hệ trên là r2 − r − 1 = 0. Phương trình này có các nghiệm là: r1 = 1 + √ 5 2 , r2 = 1−√5 2 . Giống như dãy Fibonacci ta có công thức Binet Ln = ( 1 + √ 5 2 )n + ( 1−√5 2 )n . Theo định lý Fécma bé, với mọi số nguyên tố n ta luôn có: Ln ≡ 1(modn) (1). 3.1.2 Định nghĩa. Nếu (1) thoả mãn với n là hợp số nào đó, thì n được gọi là số giả nguyên tố Lucas (viết là LPP). 29 Cho V là tập hợp các số LPP. Một số tính chất của số LPP đã được đề cập trong [8], [9]. Tất cả các số LPP là số lẻ (số nhỏ nhất là 705) và tất cả các số LPP đã biết là không chính phương, hoặc quadratfrei (q.f) . P.Filipponi đã chỉ ra 4438 số LPP nhỏ hơn 232 (không có các phép phân tích thành nhân tử) và 1 trong 852 số LPP nhỏ hơn 108 (có phép phân tích thành nhân tử), tất cả đều là số không chính phương ([10], [11]). 3.1.3 Định nghĩa. Cho số nguyênm > 1, chu kỳ của số Lucas (modm), được ký hiệu là k(m), là số nguyên dương nhỏ nhất e sao cho Lj+e ≡ Lj(modm) với tất cả các số nguyên j. 3.1.4 Tính chất. k(m) = lcm(k(pe) : pe ‖ m). 3.1.5 Tính chất. k(m) là chẵn với mọi m > 2; k(2) = 3, k(5) = 4. Ta cần sử dụng hai Bổ đề sau (xem thêm trong [6]) để chứng minh Định lý 3.1.8 3.1.6 Bổ đề. k(m) là số nguyên dương nhỏ nhất e sao cho αe ≡ 1(modm), ở đây α = 1 2 (1 + √ 5). 3.1.7 Bổ đề. Nếu n là số lẻ và p là số nguyên tố khác 2 và 5, thì Ln ≡ 1(modp) nếu (a) αn−1 ≡ 1(mod p) hoặc (b) αn+1 ≡ −1(mod p). 3.1.8 Định lý. Nếu n ∈ V , thì với tất cả số nguyên p|n (a*) n ≡ 1(mod k(p)) hoặc (b*) n ≡ 1 2 k(p)− 1(modk(p)). Chứng minh. Giả sử n ∈ V. Ta có Ln ≡ 1(modn) và vì vậy Ln ≡ 1(modp) với tất cả số nguyên p|n. Nếu p 6= 5, áp dụng bổ đề 3.1.7 ta có: nếu αn−1 ≡ 1(modp), thì k(p)|n−1 (bổ đề 3.1.6). Vì vậy ta có n ≡ 1(modk(p)). Nếu αn+1 ≡ −1(modp), suy 30 ra α2n+2 ≡ 1(modp). Theo bổ đề 3.1.6 thì k(p)|2n+ 2, nhưng k(p) 6 |n+ 1. Vậy 2n+ 2 = (2s+ 1)k(p) với số nguyên s nào đó, hoặc n = sk(p) + 1 2 k(p)− 1. Suy ra n ≡ 1 2 k(p)− 1(modk(p)). Nếu 5|n, thì Ln ≡ 1(mod5) kéo theo n ≡ 1(mod4) có nghĩa là n ≡ 1(modk(p). Định lý được chứng minh. 3.1.9 Định lý. n là số giả nguyên tố Lucas không chính phương khi và chỉ khi n là số lẻ, hợp số, không chính phương và với mọi p|n hoặc: (a) n ≡ 1(mod k(p) hoặc (b) n ≡ 1 2 k(p)− 1(mod k(p)). Chứng minh. Nếu n là số giả nguyên tố Lucas không chính phương, thì n là số lẻ, hợp số, không chính phương. Vậy theo định lý trên suy ra (a) và (b). Ngược lại nếu n là số lẻ, hợp số, không chính phương và các điều kiện (a) và (b) thoả mãn, ta cần chỉ ra n là số giả nguyên tố Lucas không chính phương. Nếu p|n và n ≡ 1(modk(p), thì Ln ≡ L1 ≡ 1(modp). Nếu p|n và n ≡ 1 2 k(p)−1(modk(p)) thì n+1 = 1 2 rk(p) vơi số nguyên r lẻ nào đó. Suy ra α2n+2 ≡ αrk(p) ≡ 1(mod p) (theo bổ đề 3.1.6). Vậy αn+1 ≡ ±1(modp). Vì k(p) 6 |n+1, ta có αn+1 6≡ 1(modp). Vậy αn+1 ≡ −1(modp), suy ra αn ≡ β(modp), ở đây β = 12(1 − √ 5). Tương tự, βn ≡ α(modp) có nghĩa là Ln = α n + βn ≡ α + β ≡ 1(modp). 3