Đăng ký Đăng nhập
Trang chủ Về các dãy hồi quy tuyến tính...

Tài liệu Về các dãy hồi quy tuyến tính

.PDF
35
53
113

Mô tả:

ĐẠ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Þ 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. 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 tr­ng 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 tr­ng 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 tr­ng 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 1.1.1 §Þnh nghÜa. m«®ul« Khi Gi¶ sö a, b lµ c¸c sè nguyªn. Ta nãi r»ng a ®ång d­ víi b m nÕu m|(a − b). 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 6≡ b(modm). NÕu a vµ khi tån t¹i sè nguyªn k sao cho 1.1.2 MÖnh ®Ò. Chøng minh. sè nguyªn th× Gi¶ sö b lµ c¸c sè nguyªn th× a ≡ b(modm) khi vµ chØ a = b + km. a ≡ b(modm). Khi ®ã m|(a − b), tøc lµ a − b = km víi k nµo ®ã. Ng­îc l¹i, nÕu tån t¹i sè nguyªn k sao cho a = b + km m|(a − b), tøc lµ a ≡ b(modm). 1.1.3 MÖnh ®Ò. Gi¶ sö m lµ mét sè nguyªn d­¬ng. Quan hÖ ®ång d­ m«®ul« m tho¶ m·n c¸c tÝnh chÊt sau ®©y: 1) (TÝnh chÊt ph¶n x¹). NÕu a lµ mét sè nguyªn, th× a ≡ a(modm). 2) (TÝnh chÊt ®èi xøng). Gi¶ sö a ≡ b(modm) th× b ≡ a(modm). 6 a vµ b lµ c¸c sè nguyªn. Khi ®ã, nÕu 3) (TÝnh chÊt b¾c cÇu). Gi¶ sö a, b vµ c lµ c¸c sè nguyªn. Khi ®ã, nÕu a ≡ b(modm), b ≡ c(modm) th× a ≡ c(modm). Chøng minh. 2) Gi¶ sö 1) Ta cã a ≡ a(modm) v× m|(a − a). 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 hîp c¸c sè nguyªn thµnh c¸c líp ®ång d­ m«®ul« thuéc vµo mét líp ®ång d­ m«®ul« m«®ul« m, ta cã thÓ chia tËp m. Hai sè nguyªn cïng m khi vµ chØ khi chóng ®ång d­ víi nhau m. 1.1.4 §Þnh nghÜa. Mét hÖ thÆng d­ ®Çy ®ñ m«®unl« m lµ mét tËp hîp c¸c 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« 1.1.5 §Þnh lý. Gi¶ sö m. 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. nªn V× a ≡ b(modm) nªn m|(a − b). Do (a + c) − (b + c) = a − b 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 ra ac − bc = c(a − b) nªn tõ m|(a − b) suy 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 1.1.6 §Þnh lý. 2002 = 1001 6= 2(mod6). 2 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(mod Chøng minh. Gi¶ sö tån t¹i sè nguyªn m ). d ac ≡ bc(modm). Ta cã m|(ac − bc) = c(a − b). Do ®ã k sao cho c(a − b) = km. Chia hai vÕ cho d ta ®­îc: c m (a − b) = k . d d   c m m V× , = 1 nªn tõ ®ã suy ra |(a − b), tøc lµ d d 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. 1.1.7 §Þnh lý. vµ NÕu a, b, c vµ m lµ c¸c sè nguyªn, sao cho m > 0, (c, m) = 1, 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ªn m|(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) Do ®ã = km+lm = (k+l)m. 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ö lµ sè nguyªn d­¬ng vµ r1 , r2 , ..., rm lµ hÖ ®Çy ®ñ c¸c thÆng d­ m«®ul« (a, m) = 1. Khi ®ã ar1 + b, ar2 + b, ..., arm + b còng lµ mét hÖ thÆng d­ ®Çy ®ñ m«®ul« Chøng minh. m. 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 m, a 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å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. 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−2 b + ... + 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ý. trong ®ã Gi¶ sö a ≡ b(modm1 ), a ≡ b(modm2 ), ..., a ≡ b(modmk ), 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. cã V× a ≡ b(modm1 ), a ≡ b(modm2 ), ..., a ≡ b(modmk ), nªn ta 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¶. trong ®ã Gi¶ sö a ≡ b(modm1 ), a ≡ b(modm2 ), ..., a ≡ b(modmk ), 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ã [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 ®ã biÕn. x lµ mét sè nguyªn ch­a biÕt, ®­îc gäi lµ ®ång d­ tuyÕn tÝnh mét 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, d 6 |b th× ®ång d­ ax ≡ b(modm) v« nghiÖm. ®óng m>0 NÕu vµ (a, m) = d. NÕu d|b th× ax ≡ b(modm) cã 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 VËy, nÕu y sao cho ax − my = b. V× d = (a, m) nªn d|b. 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µ r»ng, c¸c sè x0 = se. Ta sÏ chøng tá   a x = x0 + m k, d trong ®ã k nguyªn, ®Òu lµ nghiÖm ®ång ®­ ®ang xÐt. ThËt vËy   a k, ax = ax0 + m 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 m a (x − se) = (y + te). d d a m a Do d = (a, m) nªn ( , ) = 1, suy ra |(y +te). VËy ph¶i tån t¹i sè nguyªn d d a a d 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ã V× m m t1 ≡ t2 (modm). d d m m m |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 d hîp ®ã cã ®óng d phÇn tö, cho bëi t = 0, 1, 2, ..., d − 1. x = x0 + 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 ®Ò. m«®ul« Gi¶ sö p lµ mét sè nguyªn tè. Sè nguyªn a lµ nghÞch ®¶o 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) hoÆc = (a − 1)(a +1) mµ p nguyªn tè, nªn p|(a − 1) 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ý. d­¬ng víi (§Þnh lý FÐcma bÐ). Gi¶ sö p lµ sè nguyªn tè vµ a lµ sè nguyªn 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) 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 suy ra = 1. ja ≡ ka(modp) th× do (a, p) = 1 nªn 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« nhÊt cña hÖ ®ã ph¶i lµ p, nªn c¸c thÆng d­ d­¬ng bÐ 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¶. ®ã ap−2 Gi¶ sö p lµ sè nguyªn tè vµ lµ nghÞch ®¶o cña Chøng minh. Gi¶ sö a lµ sè nguyªn tè víi p 6 |a. Khi a m«®ul« p. 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 1.3.4 HÖ qu¶. Gi¶ sö a m«®ul« p. 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 Chøng minh. cña x sao cho x ≡ ap−2 b(modp). ax ≡ b(modp). V× p 6 |a nªn ap−2 lµ mét nghÞch ®¶o Gi¶ sö 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 cã bn th× n lµ sè nguyªn tè th× víi mäi sè nguyªn b ta ≡ b(modn). Nh­ vËy, nÕu cã sè nguyªn b sao cho bn 6≡ b(modn) 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. d­¬ng vµ bn Gi¶ sö b lµ sè nguyªn d­¬ng. NÕu n lµ mét hîp sè nguyªn ≡ 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 Gi¶ sö 1.4.2 Bæ ®Ò. 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 ®ã (2d − 1)|(2n − 1). Chøng minh. khai triÓn V× d|n nªn tån t¹i sè nguyªn t sao cho dt = n. §Æt x = 2d , tõ 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ý. Chøng minh. Tån t¹i v« h¹n sè gi¶ nguyªn tè c¬ së 2. 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ªn n = dt(1 < d, t < n) vµ 2n−1 ≡ 1(modn). V× (2d − 1)|(2n − 1) 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 = 22 n −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. gi¸ trÞ Quan hÖ håi quy bËc k lµ mét c«ng thøc cho phÐp tÝnh 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. 2.1.2 Chó ý. (1) §è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 nã phô thuéc k ®­îc gäi lµ nghiÖm tæng qu¸t nÕu 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). 17 (2) 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Ö  2C1 + 3C2 = a 4C1 + 9C2 = b HÖ ph­¬ng tr×nh nµy cã nghiÖm 2.2 C1 , C2 víi mäi gi¸ trÞ cña a, b. 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) = 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). 2.2.2 Bæ ®Ò. d·y NÕu (3) f1 (n), f2 (n) lµ c¸c nghiÖm cña (3) th× víi c¸c sè tïy ý A, B 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) = 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 2.2.3 Bæ ®Ò. Gi¶ sö r1 lµ nghiÖm cña ph­¬ng tr×nh r2 = a1 r + a2 Khi ®ã d·y (4). {rn } lµ mét nghiÖm cña quan hÖ f (n + 2) = a1 f (n + 1) + a2 f (n) Chøng minh. Ta cã (5). f (n) = r1n , f (n + 1) = r1n+1 , f (n + 2) = r1n+2 . Theo gi¶ thiÕt, r1 lµ nghiÖm cña ph­¬ng tr×nh r 2 = a1 r + a2 nªn ta cã r12 = a1 r1 + a2 . Suy ra a1 r1n+1 + a2 r1n = r1n (a1 r1 + a2 ) = r1n r12 = r1n+2 . {rn } lµ mét nghiÖm cña quan hÖ (5).  n+m 2.2.4 NhËn xÐt. D·y r1 víi m tïy ý còng lµ mét nghiÖm. ThËt vËy, chØ VËy cÇn ¸p dông Bæ ®Ò 2.2.2 víi B = 0, A = r1m . 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) = a1 f (n + 1) + a2 f (n). (6) Gi¶ sö ph­¬ng tr×nh ®Æc tr­ng r 2 = a1 r + 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) = C1 r1n−1 + C2 r2n−1 . Chøng minh. Theo Bæ ®Ò 2.2.3, f1 (n) = r1n−1 , f2 (n) = r2n−1 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 ý, C1 r1n + C2 r2n 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  cã nghiÖm víi C1 + C2 = a C 1 r1 + C 2 r2 = b a, b tïy ý. DÔ thÊy r»ng, c¸c nghiÖm ®ã lµ C1 = b − ar2 ar1 − b , 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 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 C1 r1n−1 + C2 r2n−1 kh«ng cßn lµ 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è f (n) = Cr1n−1 . 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 r 2 = a1 r + 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) = r1n−1 (C1 + C2 n), trong ®ã C1 , C2 Chøng minh. ta cã: a1 lµ c¸c h»ng sè tïy ý. V× ph­¬ng tr×nh ®Æc tr­ng cã nghiÖm béi nªn theo §Þnh lÝ ViÐt = 2r1 , a2 = −r12 . Ta viÕt ph­¬ng tr×nh ®Æc tr­ng d­íi d¹ng: r2 = 2r1 r − r12 . Nh­ vËy quan hÖ håi quy sÏ cã d¹ng f (n + 2) = 2r1 f (n + 1) − r12 f (n) 20 (7). Ta thö l¹i r»ng f2 (n) = nr1n−1 lµ mét nghiÖm cña quan hÖ ®ang xÐt. Ta cã: f2 (n + 2) = (n + 2)r1n+1 , f2 (n + 1) = (n + 1)r1n . Thay c¸c gi¸ trÞ nµy vµo (7) ta nhËn ®­îc c¸c ®ång nhÊt thøc: (n + 2)r1n+1 = 2(n + 1)r1n+1 − nr1n+1 . VËy nr1n−1 ®óng lµ mét nghiÖm. Theo bæ ®Ò 2.2.2, víi C1 , C2 tïy ý, f (n)r1n−1 (C1 + C2 n) còng lµ nghiÖm. MÆt kh¸c, víi ®iÒu kiÖn lu«n x¸c ®Þnh ®­îc (8) f (1) = a, f (2) = b tïy ý, ta lu«n 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 ta còng cã kÕt qu¶ hoµn toµn t­¬ng tù. XÐt quan hÖ håi quy cÊp k tïy ý, k d¹ng f (n + k) = a1 f (n + k − 1) + ... + ak f (n). ph­¬ng tr×nh ®Æc tr­ng 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 tr­ng, th× nghiÖm tæng qu¸t sÏ lµ f (n) = C1 r1n−1 + ... + Ck rkn−1 . 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µ n−1 f (n) = r1n−1 (C1 + C2 n + ... + Cs ns−1 ) + Cs+1 rs+1 + ... + Ck rkn−1 . 21
- Xem thêm -

Tài liệu liên quan