ĐẠ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
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)
nhng
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 cha 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), nhng 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 "tha", ch¼ng h¹n trong
1010 sè tù nhiªn ®Çu tiªn
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
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 trng 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 trng
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 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
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 trng
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 trng cã nghiÖm béi nªn theo §Þnh lÝ ViÐt
= 2r1 , a2 = −r12 . Ta viÕt ph¬ng tr×nh ®Æc trng 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 trng 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 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 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 -