CHƯƠNG 1: CƠ SỞ TOÁN HỌC 1.1 Số học trên modulo 1.1 Định nghĩa modulo Cho một số nguyên a và số nguyên dương n bất kỳ, thực hiện phép chia a cho n thì thu được thương số q và phần dư r thỏa mãn mối quan hệ sau: a = q.x +r 0≤r<n Ví dụ minh họa trên bảng 1. Minh họa thương số và phần dư khi thực hiện phép chia a cho n a = 13 n=4 13 = 3 x 4 + 1 q=3 r=1 a = -13 n=4 -13 = (-4) x 4 + q = -4 r=3 3 Tóm lại, cho một số nguyên a và số nguyên dương n thì ta định nghĩa a mod n là phần dư của phép chia a cho n. Ví dụ: 13 mod 4 = 1 và -13 mod 4 = 3 Hai số nguyên a và b được gọi là đồng dư modulo với n nếu (a mod n) = (b mod n) và được ký hiệu như sau: a ≡ b (mod n) Ví dụ: 13 ≡ 5 (mod 4) vì 13 mod 4=1 và 5 mod 4 = 1 7 ≡ −13 (mod 4) vì 7 mod 4 = 3 và −13 mod 4 = 3 1.2 Ước số 8 Ta nói rằng a chia hết cho số b khác không nếu tồn tại số m nào đó để a = m.b, trong đó m, a, b là các số nguyên. a chia hết cho b được kí hiệu là b|a và b được gọi là ước số của a.
Ví dụ các ước số dương của 15 là 1, 3, 5 và 15.3 Các phép toán trên modulo (A + B) % C = ((A % C) + (B % C)) % C (A - B) % C = ((A % C) - (B % C)) % C (A * B) % C = ((A % C) * (B % C)) % C (A / B) % C = ((A % C) * (B-1 % C)) % C Nếu (a + b) ≡ (a + c) mod n thì b ≡ c mod n.c) mod n, thì b ≡ c mod n, khi a là nguyên tố cùng nhau với n. Ví dụ: (11 * 19) mod 7 = (11 mod 7 * 19 mod 7) mod 7 = 20 mod 7 = 6 Bảng 1.2 sau minh họa phép toán số học cộng, nhân, số đối và số nghịch đảo trên modulo 8. Số đối của số nguyên x là số nguyên y sao cho (x + y) mod 8 = 0, số nghịch đảo của số nguyên x là số nguyên y sao cho (x. Như vậy, để tìm các số đối của các số nguyên ở cột bên trái bảng cộng bằng cách quét lần lượt các phần từ trong dòng để tìm phần tử 0 và khi đó phần tử ở dòng đầu tiên ứng với cột này là số đối.
Tương tự, để tìm giá trị nghịch đảo của số bên trái của bảng nhân bằng cách quét lần lượt các phần tử trong dòng để tìm phần tử 1 và khi đó phần tử đầu tiên ứng với cột này là số nghịch đảo. Các phép toán số học trên modulo 8 + 0 1 2 3 4 5 6 7 X 0 1 2 3 4 5 6 7 0 0 1 2 3 4 5 6 7 0 0 0 0 0 0 0 0 0 1 1 2 3 4 5 6 7 0 1 0 1 2 3 4 5 6 7 2 2 3 4 5 6 7 0 1 2 0 2 4 6 0 2 4 6 3 3 4 5 6 7 0 1 2 3 0 3 6 1 4 7 2 5 4 4 5 6 7 0 1 2 3 4 0 4 0 4 0 4 0 4 9 5 5 6 7 0 1 2 3 4 5 0 5 2 7 4 1 6 3 6 6 7 0 1 2 3 4 5 6 0 6 4 2 0 6 4 2 7 7 0 1 2 3 4 5 6 7 0 7 6 5 4 3 2 1 x -x x-1 0 0 - 1 7 1 2 6 - 3 5 3 4 4 - 5 3 5 6 2 - 7 1 7 1.4, Ước chung lớn nhất (GCD) - Khái niệm: Ước chung lớn nhất của 2 số nguyên dương a và b là số lớn nhất mà cả a và b cùng chia hết. 10 ● Giải thuật Euclid Ví dụ: Tìm GCD(4864, 3458) = ? 4864 = 1*3458 + 1406 3458 = 2*1406 + 646 1406 = 2*646 + 76 646 = 5*114 + 38 76 = 2*38 + 0 Vậy GCD(4864, 3458) = 38 Thuật toán trên có thể được mở rộng để không những chỉ tính được GCD của 2 số nguyên a, b mà còn tính được các số nguyên x và y thỏa mãn ax + by = d Giải thuật Euclid mở rộng Giải thuật Euclid mở rộng được sử dụng để giải một phương trình vô định nguyên (còn được gọi là phương trình Đi-ô-phăng) có dạng: ax + by = c (a, b, c ∈ Z; x, y ∈ Z là ẩn) Điều kiện cần và đủ để phương trình này có nghiệm (nguyên) là 𝐺𝐶𝐷(𝑎,𝑏) là ước của c ₋ Khẳng định này dựa trên mệnh đề: Nếu d = gcd(a, b) thì tồn tại các số nguyên x, y sao cho: a.y = d ₋ Thuật toán: Input: Hai số nguyên không âm a và b với a ≥ b 11 Output: d = GCD(a, b) và các số nguyên x và y thỏa mãn ax + by = d Hình 1. Thuật toán euclid mở rộng VD: Bảng sau chỉ ra các bước của thuật toán với giá trị vào a= 814 và b= 187 Bảng 1.
Minh họa thuật toán Euclid mở rộng Vậy, gcd(814, 187) = 11, và (814) * 3 + (187) * (-13) = 11 12 1.2 Một số thuật toán trên Zn 1.1 Tìm số nghịch đảo Định nghĩa: Phần tử nghịch đảo + Cho a e Zn + Phần tử nghịch đảo (ngược theo phép nhân) của a mod n là một số nguyên xe Z, sao cho: ax = 1 mod n) + Nếu x tồn tại thì nó là duy nhất, a được gọi là khả nghịch. Phần tử nghịch đảo của a được ký hiệu là a-. (2) Nếu d > 1 thì a-1 mod n không tồn tại. Ngược lại return(x).
* Các bước tính a-1 mod n: 13 14 Ví dụ 1: n = 173, a = 1024 Dòng r0 r1 r2 q t0 t1 0 1024 173 159 5 0 1 1 173 159 14 1 1 1019 2 159 14 5 11 1019 6 3 14 5 4 2 6 953 4 5 4 1 1 953 148 5 4 1 0 4 148 805 15 Bảng 1. Minh họa cho ví dụ tính phần tử nghịch đảo Vậy 173-1 = 805 (trong Z1024) 1.2 Ak mod n Tính giá trị biểu thức z = Ak mod n ₋ Thuật toán “bình phương và nhân” ₋ Biểu diễn k dạng nhị phân bibi - 1bi - 2…b1b0, bi ∈ {0, 1} Hình 1. Các bước của thuật toán bình phương và nhân Ví dụ: Bảng sau chỉ ra các bước tính toán ak mod n, với a = 7, k = 560 = 1000110000, n = 561 Bảng 1. Các bước tính của thuật toán bình phương và nhân Giá trị f cuối cùng = 1, là đáp số cần tìm 1.3 Lý thuyết số 16 ● Các số nguyên tố Như chúng ta đã biết số nguyên tố là các số nguyên dương chỉ có ước số là 1 và chính nó.
Chúng không thể được viết dưới dạng tích của các số khác. I là số nguyên tố, nhưng không quan tâm đến nó. Xét các số nhỏ hơn 10 ta có: 2, 3, 5, 7 là số nguyên tố, vì chúng không có ước số khác 1 và chính nó; 4, 6, 8, 9, 10 không phải là số nguyên tổ. Có thể nói 2 là số chẵn duy nhất là số nguyên tố.
Các số nguyên tố là trung tâm của lý thuyết số. Số các số nguyên tố là vô hạn. Sau đây là danh sách các số nguyên tố nhỏ hơn 200: 2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97 101 103 107 109 113 127 131 137 139 149 151 157 163 167 173 179 181 191 193 197 199 ● Phân tích thừa số nguyên tố ₋ Một trong những bài toán cơ bản của số học là phân tích ra thừa số nguyên tố số a, tức là viết nó dưới dạng tích của các số nguyên tố. Lưu ý rằng phân tích là bài toán khó hơn rất nhiều so với bài toán nhân các số để nhận được tích.
₋ Ta có kết luận, mọi số nguyên dương đều có phân tích duy nhất thành tích các lũy thừa của các số nguyên tố; Ví dụ: 91 = 7 * 13; 3600 = 24 * 32 * 52 17 ₋ Thông thường để tìm phân tích trên, ta phải kiểm tra tính chia hết cho các số nguyên tố từ nhỏ đến lớn và thực hiện phép chia liên tiếp cho các số nguyên tố, rồi gộp thành lũy thừa của các số nguyên tố. ● Số nguyên tố cùng nhau và GCD ₋ Hai số nguyên dương a và b không có ước chung nào ngoài 1, được gọi là nguyên tố cùng nhau. ₋ Ví dụ: 8 và 15 là nguyên tố cùng nhau, vì ước của 8 là 1, 2, 4, 8, còn ước của 15 là I, 3, 5, 15. Chỉ có 1 là ước chung của 8 và 15.
₋ Ngược lại có thể xác định ước chung lớn nhất bằng cách trong các phân tích ra thừa số của chúng, tìm các thừa số nguyên tố chung và lấy bậc lũy thừa nhỏ nhất trong hai phân tích của hai số đó. Ta có phân tích: 300 = 21 * 31 * 52 và 18 = 21 * 32. ₋ Hay với mọi số nguyên tốp và số nguyễn a không là bội của p, ta luôn có: ap = a mod p ₋ Công thức trên luôn đúng, nếu p là số nguyên tố, còn a là số nguyên dương nhỏ hơn 18 Ví dụ. Vi 5 và 7 là các số nguyên tố.
2 và 3 không là bội tương ứng của 7 và 5, nên theo định lý Fermat ta có: 27 - 1 mod 7 = 1 (= 26 mod 7 = 64 mod 7 = 1) 35 - 1 mod 5 = 1 (= 34 mod 5 = 81 mod 5 = 1) (-2)11 - 1 mod 11 = 1 (= 210 mod 11 = 1024 mod 11 = 1) ₋ Kết quả trên được dùng trong khoa công khai. Nó cũng được sử dụng để kiểm tra tính nguyên tố của một số nguyên p nào đó, bằng cách lấy ngẫu nhiên các số a và kiểm tra xem có tính chất nêu trên không, kết luận là p nguyên tố cảng thuyết phục nếu phép thử trên dùng với nhiều lần chọn ngẫu nhiên các số a. ● Hàm Euler ₋ Cho n là một số nguyên dương.