Download miễn phí Luận văn Về các dãy hồi quy tuyến tính
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.
Để tải bản Đầy Đủ của tài liệu, xin Trả lời bài viết này, Mods sẽ gửi Link download cho bạn sớm nhất qua hòm tin nhắn.
Ai cần download tài liệu gì mà không tìm thấy ở đây, thì đăng yêu cầu down tại đây nhé:
Nhận download tài liệu miễn phí
Tóm tắt nội dung tài liệu:
, ..., 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) hay 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)
hay p|(a+ 1). Do đó, a ≡ 1(modp) hay a ≡ −1(modp).
13
1.3 Định lý Fécma bé
1...