Luận văn: VỀ CÁC DÃY HỒI QUY TUYẾN TÍNH

Chia sẻ: Greengrass304 Greengrass304 | Ngày: | Loại File: PDF | Số trang:35

Thêm vào BST

Báo xấu

140
lượt xem 25
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Lý thuyết các dãy hồi quy tuyến tính là một trong những hướng nghiên cứu truyền thống của số học. Nhiều dãy số quan trọng được định nghĩa qua các dãy hồi quy. Nổi tiếng nhất trong số các dãy số như vậy là các số Fibonacci, các số Lucas. Mặc dù có lịch sử phát triển lâu đời, các số Fibonacci và Lucas vẫn chứa đựng nhiều tính chất thú vị chưa được biết đến, và luôn luôn là một trong những đề tài trọng tâm của lý thuyết số hiện đại....

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn: VỀ CÁC DÃY HỒI QUY TUYẾN TÍNH

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM Hoàng Thanh Nghị VỀ CÁC DÃY HỒI QUY TUYẾN TÍNH LUẬN VĂN THẠC SĨ TOÁN HỌC Thái Nguyên – 2008 S ố hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc -tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC SƯ PHẠM HOÀNG THANH NGHỊ VỀ CÁC DÃY HỒI QUY TUYẾN TÍNH Chuyên ngành: Đại số và lý thuyết số Mã số: 60.46.05 LUẬN VĂN THẠC SĨ TOÁN HỌC NGƯỜI HƯỚNG DẪN KHOA HỌC: GS.TSKH Hà Huy Khoái THÁI NGUYÊN - 2008
Lêi nãi ®Çu Lý thuyÕt c¸c d·y håi quy tuyÕn tÝnh lµ mét trong nh÷ng híng nghiªn cøu truyÒn thèng cña sè häc. NhiÒu d·y sè quan träng ®îc ®Þnh nghÜa qua c¸c d·y håi quy. Næi tiÕng nhÊt trong sè c¸c d·y sè nh vËy lµ c¸c sè Fibonacci, c¸c sè Lucas. MÆc dï cã lÞch sö ph¸t triÓn l©u ®êi, c¸c sè Fibonacci vµ Lucas vÉn chøa ®ùng nhiÒu tÝnh chÊt thó vÞ cha ®îc biÕt ®Õn, vµ lu«n lu«n lµ mét trong nh÷ng ®Ò tµi träng t©m cña lý thuyÕt sè hiÖn ®¹i. B¶n luËn v¨n nµy nh»m giíi thiÖu vÒ lý thuyÕt c¸c d·y håi quy tuyÕn tÝnh nãi chung, mét sè tÝnh chÊt cæ ®iÓn cña d·y sè Fibonacci, còng nh mét sè tÝnh chÊt ®îc ph¸t hiÖn rÊt gÇn ®©y (2007) cña c¸c sè Lucas. Bè côc cña luËn v¨n nh sau: Ch¬ng 1 "Lý thuyÕt ®ång d" dµnh ®Ó giíi thiÖu c¸c kh¸i niÖm, c¸c tÝnh chÊt c¬ b¶n vÒ lý thuyÕt ®ång d, ®ång d tuyÕn tÝnh, ®Þnh lý FÐcma bÐ, sè gi¶ nguyªn tè, nh»m phôc vô cho c¸c chøng minh sau. Ch¬ng 2 "C¸c quan hÖ håi quy" ®· ®a ra c¸c kh¸i niÖm vÒ c¸c quan hÖ håi quy, ph¬ng tr×nh ®Æc trng cña c¸c quan hÖ håi quy tuyÕn tÝnh hÖ sè h»ng råi tõ ®ã ®a ra nghiÖm tæng qu¸t cho c¸c trêng hîp ph¬ng tr×nh ®Æc trng cã nghiÖm béi vµ kh«ng cã nghiÖm béi. Ngoµi ra trong ch¬ng nµy còng tr×nh bµy kh¸i niÖm d·y sè Fibonacci vµ mét sè tÝnh chÊt cæ ®iÓn cña d·y sè nµy. Ch¬ng 3 "Mét sè tÝnh chÊt sè häc cña sè Lucas" nh»m tr×nh bµy mét sè kÕt qu¶ gÇn ®©y cña d·y Lucas. Cô thÓ lµ §Þnh lý vÒ sù tån t¹i c¸c sè chÝnh ph¬ng trong d·y Lucas vµ sù ®Æc trng cña c¸c sè Lucas gi¶ nguyªn tè kh«ng chÝnh ph¬ng. LuËn v¨n ®îc hoµn thµnh díi sù híng dÉn tËn t×nh cña GS. TSKH. Hµ Huy Kho¸i. Nhê ThÇy t«i ®· bíc ®Çu lµm quen vµ say mª víi To¸n häc. Nh©n dÞp nµy, t«i xin bµy tá lßng biÕt ¬n s©u s¾c tíi ThÇy. T«i xin tr©n träng c¶m ¬n ban l·nh ®¹o khoa To¸n, khoa Sau §¹i häc - 4
§¹i häc S ph¹m Th¸i Nguyªn, c¸c thÇy c« gi¸o ®· trang bÞ kiÕn thøc, t¹o ®iÒu kiÖn cho t«i trong thêi gian häc tËp t¹i ®©y. T«i rÊt biÕt ¬n BGH Trêng C§ Kinh tÕ Kü thuËt §iÖn Biªn vµ c¸c ®ång nghiÖp ®· t¹o ®iÒu kiÖn thuËn lîi cho t«i thùc hiÖn kÕ ho¹ch häc tËp cña m×nh. T«i xin c¶m ¬n ngêi th©n, b¹n bÌ ®· cæ vò ®éng viªn t«i trong qu¸ tr×nh lµm luËn v¨n. 5
Ch¬ng 1 Lý thuyÕt ®ång d 1.1 Kh¸i niÖm c¬ b¶n Gi¶ sö a, b lµ c¸c sè nguyªn. Ta nãi r»ng a ®ång d víi b 1.1.1 §Þnh nghÜa. m«®ul« m nÕu m|(a − b). Khi a ®ång d víi b m«®ul« m, ta viÕt a ≡ b(modm). NÕu a kh«ng ®ång d b m«®ul« m, ta viÕt a ≡ b(modm). a ≡ b(modm) a b NÕu vµ lµ c¸c sè nguyªn th× khi vµ chØ 1.1.2 MÖnh ®Ò. k a = b + km. khi tån t¹i sè nguyªn sao cho Gi¶ sö a ≡ b(modm). Khi ®ã m|(a − b), tøc lµ a − b = km víi Chøng minh. sè nguyªn k nµo ®ã. Ngîc l¹i, nÕu tån t¹i sè nguyªn k sao cho a = b + km th× m|(a − b), tøc lµ a ≡ b(modm). m lµ mét sè nguyªn d¬ng. Quan hÖ ®ång d m«®ul« Gi¶ sö 1.1.3 MÖnh ®Ò. m tho¶ m·n c¸c tÝnh chÊt sau ®©y: a lµ mét sè nguyªn, th× 1) (TÝnh chÊt ph¶n x¹). NÕu a ≡ a(modm). a b 2) (TÝnh chÊt ®èi xøng). Gi¶ sö vµ lµ c¸c sè nguyªn. Khi ®ã, nÕu a ≡ b(modm) th× b ≡ a(modm). 6
a, b vµ c lµ c¸c sè nguyªn. Khi ®ã, nÕu 3) (TÝnh chÊt b¾c cÇu). Gi¶ sö a ≡ b(modm), b ≡ c(modm) th× a ≡ c(modm). 1) Ta cã a ≡ a(modm) v× m|(a − a). Chøng minh. 2) Gi¶ sö a ≡ b(modm), tøc lµ m|(a − b). Khi ®ã, m|(b − a) vµ b ≡ a(modm). 3) NÕu a ≡ b(modm), b ≡ c(modm) th× m|(a − b) vµ m|(b − c). Do ®ã, m|(a − c) v× (a − c) = (a − b) + (b − c). Nhê tÝnh chÊt trªn, víi mçi sè nguyªn d¬ng m, ta cã thÓ chia tËp hîp c¸c sè nguyªn thµnh c¸c líp ®ång d m«®ul« m. Hai sè nguyªn cïng thuéc vµo mét líp ®ång d m«®ul« m khi vµ chØ khi chóng ®ång d víi nhau m«®ul« m. Mét hÖ thÆng d ®Çy ®ñ m«®unl« m lµ mét tËp hîp c¸c 1.1.4 §Þnh nghÜa. sè nguyªn sao cho mçi sè nguyªn tuú ý ®Òu ®ång d m«®unl« m víi ®óng mét sè cña tËp hîp. VÝ dô: 1) TËp hîp c¸c sè 0, 1, ..., m − 1 lµ mét hÖ thÆng d ®Çy ®ñ m«®ul« m. HÖ nµy gäi lµ hÖ thÆng d kh«ng ©m bÐ nhÊt m«®ul« m. 2) Gi¶ sö m lµ mét sè nguyªn lÎ. Khi ®ã tËp hîp c¸c sè nguyªn m−1 m−3 m−3 m−1 − ,− , ..., 0, 1, ..., , 2 2 2 2 lµ hÖ thÆng d ®Çy ®ñ, ®îc gäi lµ hÖ thÆng d tuyÖt ®èi bÐ nhÊt m«®ul« m. a, b, c vµ m lµ c¸c sè nguyªn, m > 0 vµ a ≡ b(modm). Gi¶ sö 1.1.5 §Þnh lý. Khi ®ã: a + c ≡ b + c(modm), 1) a − c ≡ b − c(modm), 2) ac ≡ bc(modm). 3) V× a ≡ b(modm) nªn m|(a − b). Do (a + c) − (b + c) = a − b Chøng minh. 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) nhng 2002 = 1001 = 2(mod6). 2 Gi¶ sö a, b, c vµ m lµ c¸c sè nguyªn, m > 0 vµ 1.1.6 §Þnh lý. ac ≡ bc(modm) vµ d = (c, m). Khi ®ã ta cã m a ≡ b(mod ). d Gi¶ sö ac ≡ bc(modm). Ta cã m|(ac − bc) = c(a − b). Do ®ã Chøng minh. tån t¹i sè nguyªn k sao cho c(a − b) = km. Chia hai vÕ cho d ta ®îc: c m (a − b) = k . d d cm m V× = 1 nªn tõ ®ã suy ra |(a − b), tøc lµ , dd d m a ≡ b(mod ). 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. a, b, c vµ m lµ c¸c sè nguyªn, sao cho m > 0, (c, m) = 1, NÕu 1.1.7 §Þnh lý. ac ≡ bc(modm). Khi ®ã a ≡ b(modm). vµ §Þ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
m > 0, a ≡ b(modm), a, b, c, d m NÕu vµ lµ c¸c sè nguyªn, 1.1.8 §Þnh lý. c ≡ d(modm). Khi ®ã: a + c ≡ b + d(modm), 1) a − c ≡ b − d(modm), 2) ac ≡ bd(modm). 3) V× a ≡ b(modm), c ≡ d(modm) nªn m|(a − b), m|(c − d). Do Chøng minh. ®ã 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). r1 , r2 , ..., rm m, a Gi¶ sö lµ hÖ ®Çy ®ñ c¸c thÆng d m«®ul« 1.1.9 §Þnh lý. (a, m) = 1. Khi ®ã lµ sè nguyªn d¬ng vµ ar1 + b, ar2 + b, ..., arm + b m. còng lµ mét hÖ thÆng d ®Çy ®ñ m«®ul« Tríc tiªn ta chØ ra r»ng, trong c¸c sè nguyªn Chøng minh. 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 ≡ rk (modm) nÕu j = k nªn ta suy ra j = k . Do tËp hîp c¸c sè nguyªn trªn ®©y gåm m 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. a, b, k, m lµ c¸c sè nguyªn, ®ång thêi k > 0, Gi¶ sö 1.1.10 §Þnh lý. m > 0, a ≡ b(modm). Khi ®ã ak ≡ bk (modm). Do a ≡ b(modm), ta cã m|(a − b). V× Chøng minh. ak − bk = (a − b)(ak−1 + ak−2 b + ... + abk−2 + bk−1 ) (a − b)|(ak − bk ). VËy m|(ak − bk ), tøc lµ ak ≡ bk (modm). nªn 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. a ≡ b(modm1 ), a ≡ b(modm2 ), ..., a ≡ b(modmk ), Gi¶ sö 1.1.11 §Þnh lý. a, b, m1 , ..., mk m1 , m2 , ..., mk > 0. Khi ®ã trong ®ã lµ c¸c sè nguyªn, a ≡ b(mod[m1 ...mk ]) [m1 ...mk ] lµ béi chung nhá nhÊt cña m1 , ..., mk . trong ®ã V× a ≡ b(modm1 ), a ≡ b(modm2 ), ..., a ≡ b(modmk ), nªn ta Chøng minh. 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
a ≡ b(modm1 ), a ≡ b(modm2 ), ..., a ≡ b(modmk ), Gi¶ sö 1.1.12 HÖ qu¶. a, b nguyªn, m1 , m2 , ..., mk trong ®ã lµ c¸c sè nguyªn d¬ng nguyªn tè cïng nhau tõng cÆp. Khi ®ã a ≡ b(modm1 ...mk ). Do m1 , m2 , ..., mk lµ c¸c sè nguyªn d¬ng nguyªn tè cïng Chøng minh. nhau tõng cÆp nªn ta cã [m1 m2 ...mk ] = m1 m2 ...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 cha 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. a, b, m m>0 (a, m) = d. Gi¶ sö lµ c¸c sè nguyªn, vµ NÕu 1.2.1 §Þnh lý. d |b th× ®ång d ax ≡ b(modm) v« nghiÖm. d|b th× ax ≡ b(modm) cã NÕu d nghiÖm kh«ng ®ång d m«®ul« m. ®óng Sè nguyªn x lµ nghiÖm cña ®ång d ax ≡ b(modm) nÕu vµ Chøng minh. 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 |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è a x = x0 + m k, d trong ®ã k nguyªn, ®Òu lµ nghiÖm ®ång ® ®ang xÐt. ThËt vËy a ax = ax0 + m k, d a mµ ax0 ≡ b(modm), nguyªn nªn d 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 m (x − se) = (y + te). d d am a Do d = (a, m) nªn ( , ) = 1, suy ra |(y + te). VËy ph¶i tån t¹i sè nguyªn dd ad a a k sao cho k = (y + te), tøc lµ y = k − te. Do ®ã a(x − se) = mk . VËy, d d d m m x = se + k = x0 + k. d d 12
Cßn ph¶i chøng minh r»ng, cã ®óng d nghiÖm kh«ng ®ång d m«®ul« m. m m Gi¶ sö c¸c nghiÖm x1 = x0 + t1 vµ x2 = x0 + t2 ®ång d m«®ul« m: d d m m x0 + t1 ≡ x0 + t2 (modm). d d Ta cã m m t1 ≡ t2 (modm). d d m m m V× |m nªn (m, ) = nªn theo ®Þnh lý 1.1.6, d d d t1 ≡ t2 (modm) Nh vËy, hÖ ®Çy ®ñ c¸c nghiÖm kh«ng ®ång d nhËn ®îc b»ng c¸ch ®Æt m t, trong ®ã t ch¹y qua hÖ ®Çy ®ñ c¸c thÆng d m«®ul« d. TËp x = x0 + d hîp ®ã cã ®óng d phÇn tö, cho bëi t = 0, 1, 2, ..., d − 1. Gi¶ sö a, m lµ c¸c sè nguyªn, m > 1. NghiÖm cña ®ång 1.2.2 §Þnh nghÜa. 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. p a Gi¶ sö lµ mét sè nguyªn tè. Sè nguyªn lµ nghÞch ®¶o 1.2.3 MÖnh ®Ò. p cña chÝnh nã khi vµ chØ khi m«®ul« a ≡ 1(modp) hoÆc a ≡ −1(modp). a ≡ 1(modp) hoÆc a ≡ −1(modp) th× a2 ≡ 1(modp) nªn NÕu Chøng minh. 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Ð p lµ sè nguyªn tè vµ a lµ sè nguyªn (§Þnh lý FÐcma bÐ). Gi¶ sö 1.3.1 §Þnh lý. p |a. Khi ®ã ap−1 ≡ 1(modp). d¬ng víi XÐt p − 1 sè nguyªn a, 2a, ..., (p − 1)a. Kh«ng sè nguyªn nµo Chøng minh. 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). p a Gi¶ sö lµ sè nguyªn tè vµ lµ sè nguyªn d¬ng. Khi ®ã 1.3.2 HÖ qu¶. ap ≡ a(modp). NÕu p |a th× theo §Þnh lý FÐcma bÐ, ta cã Chøng minh. ap−1 ≡ 1(modp). Nh©n hai vÕ víi a ta ®îc ap ≡ a(modp). p|a th× p|ap nªn ap ≡ a ≡ 0(modp). Ngîc l¹i, nÕu 14
p |a. p a Gi¶ sö lµ sè nguyªn tè vµ lµ sè nguyªn tè víi Khi 1.3.3 HÖ qu¶. ap−2 a m«®ul« p. ®ã lµ nghÞch ®¶o cña Gi¶ sö p |a. Khi ®ã theo ®Þnh lý FÐcma bÐ ta cã Chøng minh. a.ap−2 = ap−1 ≡ 1(modp). VËy ap−2 lµ nghÞch ®¶o cña a m«®ul« p. a, b lµ c¸c sè nguyªn d¬ng vµ p lµ sè nguyªn tè, p |a. Gi¶ sö 1.3.4 HÖ qu¶. Khi ®ã nghiÖm cña ®ång d tuyÕn tÝnh ax ≡ b(modp) x sao cho x ≡ ap−2 b(modp). lµ c¸c sè nguyªn ax ≡ b(modp). V× p |a nªn ap−2 lµ mét nghÞch ®¶o Gi¶ sö Chøng minh. cña a(modp). Tõ ®ã ta cã: x ≡ ap−2 ax ≡ ap−2 b(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 ≡ 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), nhng n = 341 lµ hîp sè. 15
Gi¶ sö b lµ sè nguyªn d¬ng. NÕu n lµ mét hîp sè nguyªn 1.4.1 §Þnh nghÜa. 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. (b, n) = 1 th× tõ bn ≡ b(modn), ta suy ®îc bn−1 ≡ Chó ý r»ng, nÕu 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. 1010 sè tù nhiªn ®Çu tiªn C¸c sè gi¶ nguyªn tè rÊt "tha", ch¼ng h¹n trong cã 455.052.512 sè nguyªn tè, nhng 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: d, n lµ c¸c sè nguyªn d¬ng sao cho d|n. Khi ®ã Gi¶ sö 1.4.2 Bæ ®Ò. (2d − 1)|(2n − 1). d|n nªn tån t¹i sè nguyªn t sao cho dt = n. §Æt x = 2d , tõ V× Chøng minh. xt − 1 = (x − 1)(xt−1 + xt−2 + ... + 1) ta cã: khai triÓn 2n − 1 = (2d − 1)(2d(t−1) + 2d(t−2) + ... + 2d + 1), (2d − 1)|(2n − 1). tøc lµ Tån t¹i v« h¹n sè gi¶ nguyªn tè c¬ së 2. 1.4.3 §Þnh lý. Gi¶ sö n lµ mét sè gi¶ nguyªn tè c¬ së 2. Ta sÏ chøng tá r»ng, Chøng minh. m = 2n − 1 còng lµ sè gi¶ nguyªn tè c¬ së 2. Theo gi¶ thiÕt, n lµ hîp sè, n = dt(1 < d, t < n) vµ 2n−1 ≡ 1(modn). V× (2d − 1)|(2n − 1) ch¼ng h¹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 nªn n − 2 = kn. Ta cã: 2m−1 = 22 −2 = 2(kn+2)−2 = 2kn . Do ®ã sao cho 2n 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 Quan hÖ håi quy bËc k lµ mét c«ng thøc cho phÐp tÝnh 2.1.1 §Þnh nghÜa. gi¸ trÞ f (n + k ) qua c¸c gi¸ trÞ f (n), f (n + 1), ..., f (n + k − 1). VÝ dô: f (n + 2) = n2 f (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) §èi víi quan hÖ håi quy bËc k , nÕu cho c¸c gi¸ trÞ f (1), ..., f (k ) 2.1.2 Chó ý. 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. Mét d·y f (n) tháa m·n mét quan hÖ håi quy nµo ®ã ®îc 2.1.3 §Þnh nghÜa. 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) = C1 2n + C2 3n 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Ö 2C 1 + 3 C 2 = a 4C 1 + 9 C 2 = 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 Quan hÖ håi quy tuyÕn tÝnh bËc k víi hÖ sè h»ng lµ quan 2.2.1 §Þnh nghÜa. hÖ cã d¹ng f (n + k ) = a1 f (n + k − 1) + a2 f (n + k − 2) + ... + ak f (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) = a1 f (n + 1) + a2 f (n). (3) f1 (n), f2 (n) lµ c¸c nghiÖm cña (3) th× víi c¸c sè tïy ý A, B NÕu 2.2.2 Bæ ®Ò. f (n) = Af1 (n) + Bf2 (n) còng lµ nghiÖm cña (3). d·y V× f1 (n), f2 (n) lµ c¸c nghiÖm cña (3) nªn ta cã: Chøng minh. f1 (n + 2) = a1 f1 (n + 1) + a2 f1 (n), f2 (n + 2) = a1 f2 (n + 1) + a2 f2 (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
r1 Gi¶ sö lµ nghiÖm cña ph¬ng tr×nh 2.2.3 Bæ ®Ò. r2 = a1 r + a2 (4). {rn } lµ mét nghiÖm cña quan hÖ Khi ®ã d·y f (n + 2) = a1 f (n + 1) + a2 f (n) (5). f (n) = r1 , f (n + 1) = r1 +1 , f (n + 2) = r1 +2 . n n n Ta cã Chøng minh. Theo gi¶ thiÕt, r1 lµ nghiÖm cña ph¬ng tr×nh r 2 = a1 r + a2 nªn ta cã 2 r1 = a1 r1 + a2 . Suy ra a1 r1 +1 + a2 r1 = r1 (a1 r1 + a2 ) = r1 r1 = r1 +2 . n n n n2 n {rn } lµ mét nghiÖm cña quan hÖ (5). VËy r1 +m víi m tïy ý còng lµ mét nghiÖm. ThËt vËy, chØ n D·y 2.2.4 NhËn xÐt. m cÇn ¸p dông Bæ ®Ò 2.2.2 víi B = 0, A = r1 . Ph¬ng tr×nh (4) gäi lµ ph¬ng tr×nh ®Æc trng cña quan hÖ (5). Tõ c¸c Bæ ®Ò 2.2.2 vµ Bæ ®Ò 2.2.3, ta cã ®Þnh lÝ sau: Gi¶ sö cho quan hÖ håi quy 2.2.5 §Þnh lý. f (n + 2) = a1 f (n + 1) + a2 f (n). (6) Gi¶ sö ph¬ng tr×nh ®Æc trng r 2 = a1 r + a2 r1 r2 . Khi ®ã, nghiÖm tæng qu¸t cña (6) cã d¹ng cã hai nghiÖm ph©n biÖt vµ f (n) = C1 r1 −1 + C2 r2 −1 . n n = r1 −1 , f2 (n) = r2 −1 lµ c¸c nghiÖm n n Theo Bæ ®Ò 2.2.3, f1 (n) Chøng minh. n n cña quan hÖ ®ang xÐt. Theo Bæ ®Ò 2.2.2, víi mäi C1 , C2 tïy ý, C1 r1 + C2 r2 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 C 1 r1 + C 2 r2 = b cã nghiÖm víi a, b tïy ý. DÔ thÊy r»ng, c¸c nghiÖm ®ã lµ b − ar2 ar1 − b C1 = , C2 = r1 − r2 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 trng cã nghiÖm béi. Gi¶ sö ph¬ng tr×nh ®Æc trng cña quan hÖ ®· cho cã c¸c nghiÖm trïng = r2 . Khi ®ã biÓu thøc C1 r1 −1 + C2 r2 −1 kh«ng cßn lµ n n nhau, ch¼ng h¹n r1 f (n) = Cr1 −1 . n nghiÖm tæng qu¸t n÷a, v× nghiÖm ®ã ®îc viÕt díi d¹ng 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. Gi¶ sö ph¬ng tr×nh ®Æc trng 2.2.6 §Þnh lý. r 2 = a1 r + a2 r1 . Khi ®ã nghiÖm tæng qu¸t cña quan hÖ ®ang xÐt cã d¹ng cã nghiÖm béi f (n) = r1 −1 (C1 + C2 n), n C1 , C2 trong ®ã lµ c¸c h»ng sè tïy ý. V× ph¬ng tr×nh ®Æc trng cã nghiÖm béi nªn theo §Þnh lÝ ViÐt Chøng minh. 2 ta cã: a1 = 2r1 , a2 = −r1 . Ta viÕt ph¬ng tr×nh ®Æc trng díi d¹ng: r2 = 2r1 r − r1 . 2 Nh vËy quan hÖ håi quy sÏ cã d¹ng 2 f (n + 2) = 2r1 f (n + 1) − r1 f (n) (7). 20
= nr1 −1 lµ mét nghiÖm cña quan hÖ ®ang xÐt. n Ta thö l¹i r»ng f2 (n) Ta cã: f2 (n + 2) = (n + 2)r1 +1 , f2 (n + 1) = (n + 1)r1 . n n Thay c¸c gi¸ trÞ nµy vµo (7) ta nhËn ®îc c¸c ®ång nhÊt thøc: (n + 2)r1 +1 = 2(n + 1)r1 +1 − nr1 +1 . n n n nr1 −1 ®óng lµ mét nghiÖm. n VËy Theo bæ ®Ò 2.2.2, víi C1 , C2 tïy ý, f (n)r1 −1 (C1 + C2 n) n (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 trng cã nghiÖm béi. §èi víi quan hÖ håi quy tuyÕn tÝnh hÖ sè h»ng cÊp k tïy ý, 2.2.7 NhËn xÐt. 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 ) = a1 f (n + k − 1) + ... + ak f (n). ph¬ng tr×nh ®Æc trng t¬ng øng: rk = a1 rk−1 + ... + ak . NÕu r1 , r2 , ..., rk lµ c¸c nghiÖm kh¸c nhau cña ph¬ng tr×nh ®Æc trng, th× nghiÖm tæng qu¸t sÏ lµ f (n) = C1 r1 −1 + ... + Ck rk −1 . n n 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) = r1 −1 (C1 + C2 n + ... + Cs ns−1 ) + Cs+1 rs+1 + ... + Ck rk −1 . n −1 n n 21