Bài giảng Toán rời rạc - Chương 4: Số nguyên

TOÁN RỜI RẠC - HK1 - NĂM 2015 -2016
Chương 4
SỐ NGUYÊN
lvluyen@hcmus.edu.vn
∼luyen/trr
FB: fb.com/trr2015
Trường Đại Học Khoa học Tự nhiên TP Hồ Chí Minh
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 1/15
Nội dung
Chương 4. SỐ NGUYÊN
1. Phép chia
2. Ước chung lớn nhất và bội chung nhỏ nhất
3. Nguyên tố cùng nhau
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 2/15
4.1. Phép chia
Định nghĩa. Cho hai số nguyên a và b 6= 0. Ta gọi a chia hết cho b
nếu tồn tại số nguyên m sao cho a = mb, ký hiệu a
... b. Khi đó
a được gọi là bội của b,
b được gọi là ước của a, ký hiệu b |a
Ví dụ. 12
... 3, 15 6 ... 2, 4 | 20, 5 6 | 21.
Định lý. Cho a 6= 0, b và c là các số nguyên. Khi đó
(i) Nếu a | b và a | c, thì a | (b+ c);
(ii) Nếu a | b, thì a | bc;
(iii) Nếu a | b và b | c, thì a | c.
Hệ quả. Cho a 6= 0, b và c là các số nguyên thỏa a | b và a | c. Khi đó
a |mb+ nc với m,n là số nguyên.
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 3/15
Bổ đề. Cho hai số nguyên a và b với b > 0. Khi đó tồn tại duy nhất
cặp q, r ∈ Z sao cho
a = qb+ r với 0 ≤ r < b.
Ví dụ. Cho a = −102 và b = 23. Khi đó −102 = −5× 23 + 13
Ví dụ.(tự làm) Làm tương tự như ví dụ trên trong trường hợp:
a = 121; b = 15.
a = 214; b = 23
Định nghĩa. Trong bổ đề trên, q được gọi là phần thương , r được
gọi là phần dư . Ký hiệu q = a div b, r = a mod b.
Ví dụ.
13 ÷ 4 = 3, 13 mod 4 = 1, − 23 div 5 = −5, − 23 mod 5 = 2.
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 4/15
Đồng dư
Định nghĩa. Cho m là số nguyên dương. Hai số nguyên a và b được
gọi đồng dư với nhau theo modulo m, nếu a và b chia m có cùng phần
dư. Ký hiệu a ≡ b (mod m)
Ví dụ. 27 ≡ 43 (mod 4); 47 ≡ 92 (mod 5); 124 ≡ 58 (mod 6).
Bổ đề. a ≡ b (mod m) khi và chỉ khi a− b chia hết cho m.
Tính chất.
(i) Với mọi số nguyên a, ta có a ≡ a (mod m)
(ii) Nếu a ≡ b (mod m) thì b ≡ a (mod m)
(iii) Nếu a ≡ b (mod m) và b ≡ c (mod m) thì a ≡ c (mod m)
Tính chất. Nếu a ≡ b (mod m) và c ≡ d (mod m) thì
a+ c ≡ b+ d (mod m) và ac ≡ bd (mod m)
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 5/15
4.2. Ước chung lớn nhất và bội chung nhỏ nhất
Định nghĩa. Số nguyên U > 0 được gọi là ước chung lớn nhất (ký
hiệu UCLN) của hai số nguyên a, b nếu thỏa hai điều kiện sau:
1 U là một ước chung của a, b
2 Nếu số nguyên V là một ước chung của a, b thì V là ước của U .
Định nghĩa. Số nguyên B > 0 được gọi là bội chung nhỏ nhất (ký
hiệu BCNN) của hai số nguyên a, b nếu thỏa hai điều kiện sau:
1 U là một bội chung của a, b
2 Nếu số nguyên V là một bội chung của a, b thì V là bội của B.
Ví dụ. UCLN của 15 và 25 là 5, BCNN của chúng là 75.
Định lý. Ước chung lớn nhất (tương ứng bội chung nhỏ nhất) của a, b
là duy nhất, ký hiệu (a; b), (tương ứng [a; b]).
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 6/15
Mệnh đề. Với mọi số tự nhiên m,n ta có mn = (m;n) [m;n]
Nhận xét.
1 (a; b) = (±a;±b) và [a; b] = [±a;±b]. Do đó, từ đây về sau ta giả
sử a, b ≥ 0.
2 Nếu a | b thì (a; b) = a và [a; b] = b.
Ví dụ.
(15; 20) = (−15; 20) = (−15;−20) = (15,−20) = 5
[15; 20] = [−15; 20] = [−15;−20] = [15,−20] = 60
(15, 60) = 15; [15, 60] = 60
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 7/15
Thuật toán Euclide tìm UCLN d của a, b
Nếu b là ước của a, thì d = b;
Nếu không, ta lần lượt thực hiện các phép chia:
a = q1b+ r1 0 ≤ r1 < b
b = q2r1 + r2 0 ≤ r2 < r1
r1 = q3r2 + r3 0 ≤ r3 < r2
Do b > r1 > r2 > · · · ≥ 0 nên phép chia như trên sẽ dừng sau một
số hữu hạn bước. Gọi rn+1 là số dư đầu tiên bằng 0. Ta có
rn−2 = qnrn−1 + rn 0 ≤ rn < rn−1
rn−1 = qn+1rn + 0
Khi đó rn là UCLN của a và b.
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 8/15
Ví dụ. Tìm UCLN và BCNN của a = 2322, b = 654.
Giải. Ta có
2322 = 3× 654 + 360
654 = 1× 360 + 294
360 = 1× 294 + 66
294 = 4× 66 + 30
66 = 2× 30 + 6
30 = 5× 6
Như vậy (2322; 654) = 6 và [2322; 654] =
2322× 654
6
= 253098.
Ví dụ.(tự làm) Tìm UCLN và BCNN 1638 và 16457?
Đáp án. (1638; 16457) = 7 và [1638; 16457] = 3850938.
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 9/15
Định lý. Giả sử d là UCLN của a và b. Khi đó tồn tại m,n ∈ Z sao
cho: d =ma+ nb.
Ví dụ. Tìm UCLN d và BCNN e của a = 114 và b = 51? Từ đó tìm:
a) hai số m,n ∈ Z sao cho d = ma+ nb?
b) hai số u, v ∈ Z sao cho 1
e
=
u
a
+
v
b
?
Giải. Ta có
114 = 2× 51 + 12
51 = 4× 12 + 3
12 = 4× 3.
Suy ra (114; 51) = 3. Hơn nữa
3 = 51− 4× 12
= 51− 4× (114− 2× 51)
= −4× 114 + 9× 51.
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 10/15
Ta có e =
ab
d
= 1938. Như vậy
a) m = −4, n = 9
b) Ta có d = ma+ nb. Chia 2 vế cho ab, ta được
d
ab
=
m
b
+
n
a
⇔ 1
e
=
n
a
+
m
b
(vì ab = de).
Như vậy u = 9, v = −4.
Ví dụ.(tự làm) Tìm UCLN d và BCNN e của a = 1638 và b = 16457?
Từ đó tìm:
a) hai số m,n ∈ Z sao cho d = ma+ nb?
b) hai số u, v ∈ Z sao cho 1
e
=
u
a
+
v
b
?
lvluyen@hcmus.edu.vn Chương 3. Số nguyên 14/12/2015 11/15
4.3. Nguyên tố cùng nhau
Định ngh