Bước tới nội dung

Số học mô đun

Bách khoa toàn thư mở Wikipedia
(Đổi hướng từ Đồng dư)
Chiếc đồng hồ với mô đun bằng 12

Trong toán học, số học mô đun là một hệ thống số học dành cho số nguyên. Trong số học mô đun, các con số được viết bao quanh lấy nhau thành nhiều vòng tròn cho đến khi chạm đến giá trị đích, gọi là mô đun (tiếng Anh: modulus, số nhiều moduli). Bộ môn nghiên cứu số học mô đun hiện đại được nhà toán học người Đức, Carl Friedrich Gauss phát triển trong cuốn sách của ông có tên Disquisitiones Arithmeticae, xuất bản năm 1801.

Đồng dư

[sửa | sửa mã nguồn]

Với một số nguyên n > 1, gọi là mô đun, hai số nguyên ab được gọi là đồng dư modulo n, nếu hiệu của chúng chia hết cho n (đó là, nếu tồn tại số nguyên k sao cho ab = kn).

Đồng dư mô đun n là một quan hệ đồng dư, tức nó là một quan hệ tương đương tương thích với các phép cộng, trừ, và nhân. Đồng dư mô đun n được ký hiệu là:

Dấu ngoặc nghĩa là (mod n) áp dụng cho toàn bộ phương trình, không chỉ mỗi vế phải (b). Ký hiệu này mang ý nghĩa khác với b mod n (không có dấu ngoặc), dùng để chỉ phép toán modulo. Cụ thể hơn, b mod n ký hiệu số dư khi chia n cho b, tức số nguyên a thỏa mãn 0 ≤ a < nab (mod n).

Trong mô đun 12, ta có thể viết:

38 − 14 = 24, một bội của 12. Một cách khác để thể hiện điều này là cả 38 và 14 có cùng số dư là 2 khi chia cho 12.

Định nghĩa đồng dư cũng áp dụng cho số nguyên âm, ví dụ như:

Tính chất

[sửa | sửa mã nguồn]

Quan hệ đồng dư thỏa mãn các tính chất của một quan hệ tương đương:

  • Phản xạ: aa (mod n)
  • Đối xứng: ab (mod n) khi và chỉ khi ba (mod n) với mọi a, b
  • Bắc cầu: nếu ab (mod n)bc (mod n) thì ac (mod n)

Cộng, trừ, nhân

[sửa | sửa mã nguồn]

Nếu a1b1 (mod n)a2b2 (mod n), hoặc ab (mod n), thì:

  • a + kb + k (mod n) với mọi số nguyên k
  • k ak b (mod n) với mọi số nguyên k khác 0
  • k ak b (mod kn) với mọi số nguyên k
  • a1 + a2b1 + b2 (mod n) (bảo toàn phép cộng)
  • a1a2b1b2 (mod n) (bảo toàn phép trừ)
  • a1 a2b1 b2 (mod n) (bảo toàn phép nhân)
  • akbk (mod n) với mọi số nguyên không âm k (bảo toàn phép mũ)
  • p(a) ≡ p(b) (mod n), với mọi đa thức p(x) có hệ số nguyên (bảo toàn với đa thức)

Đối với việc khử các hệ số ở hai bên, ta có các luật sau:

  • Nếu a + kb + k (mod n), với k là số nguyên bất kì, thì ab (mod n)
  • Nếu k ak b (mod n)k nguyên tố cùng nhau với n, thì ab (mod n)
  • Nếu k ak b (mod kn) , thì ab (mod n)

Từ ab (mod n) không thể suy ra được kakb (mod n). Ví dụ, 2 ≡ 5 (mod 3), nhưng 22 ≢ 25 (mod 3). Tuy nhiên điều sau là đúng:

Nghịch đảo phép nhân

[sửa | sửa mã nguồn]

Nghịch đảo phép nhân mô đun được định nghĩa như sau:

  • Tồn tại: có một số nguyên ký hiệu là a–1 sao cho aa–1 ≡ 1 (mod n) khi và chỉ khi a nguyên tố cùng nhau với n. Số nguyên a–1 này gọi là nghịch đảo phép nhân mô đun của a modulo n.
  • Nếu ab (mod n)a–1 tồn tại, thì a–1b–1 (mod n).
  • Nếu a xb (mod n)a nguyên tố cùng nhau với n, lời giải của đồng dư thức này là xa–1b (mod n)

Nghịch đảo phép nhân xa–1 (mod n) có thể được tính bằng các giải phương trình Bézout ax + ny = 1—dùng thuật toán Euclid mở rộng.

Cụ thể hơn, nếu p là một số nguyên tố, thì a nguyên tố cùng nhau với p với mọi a thỏa 0 < a < p; do đó nghịch đảo phép nhân của a tồn tại với mọi a không chia hết cho p.

Các tính chất khác

[sửa | sửa mã nguồn]

Một số tính chất nâng cao của quan hệ đồng dư bao gồm:

  • Định lý Fermat nhỏ: Nếu số nguyên tố p không phải là ước của a thì a p–1 ≡ 1 (mod p).
  • Định lý Euler: Nếu an nguyên tố cùng nhau thì a φ(n) ≡ 1 (mod n), trong đó φhàm phi Euler.
  • Định lý Wilson: p nguyên tố khi và chỉ khi (p − 1)! ≡ −1 (mod p).
  • Định lý thặng dư Trung Hoa: Với mọi a, bm, n nguyên tố cùng nhau, tồn tại đúng một x (mod mn) sao cho xa (mod m)xb (mod n). Cụ thể hơn, xb mn–1 m + a nm–1 n (mod mn), trong đó mn−1 là nghịch đảo của m modulo nnm−1 là nghịch đảo của n modulo m.
  • Định lý Lagrange: Đồng nhất thức f (x) ≡ 0 (mod p), trong đó p nguyên tố và f (x) = an xn + ... + a0 là một đa thức có hệ số nguyên sao cho a0 ≠ 0 (mod p), có tối đa n nghiệm.
  • Căn nguyên thủy modulo n: Một số g là căn nguyên thủy n nếu, với mọi số nguyên a nguyên tố cùng nhau với n, tồn tại một số nguyên k sao cho gka (mod n). Căn nguyên thủy modulo n tồn tại khi và chỉ khi n bằng 2, 4, pk hoặc 2pk, với p là số nguyên tố lẻ và k là một số nguyên dương. Nếu một căn nguyên thủy modulo n tồn tại thì có đúng φ(φ(n)) căn nguyên thủy như thế, với φhàm phi Euler.
  • Thặng dư bình phương: Một số nguyên a là thặng dư bình phương modulo n nếu tồn tại một số nguyên x sao cho x2a (mod n). Tiêu chuẩn Euler nói rằng, nếu p là một số nguyên tố lẻ, a không là bội của p, thì a là thặng dư bình phương modulo p khi và chỉ khi a (p–1)/2 ≡ 1 (mod p).

Chú thích

[sửa | sửa mã nguồn]

Tham khảo

[sửa | sửa mã nguồn]
  • John L. Berggren. "modular arithmetic". Encyclopædia Britannica.
  • Maarten Bullynck "Modular Arithmetic before C.F. Gauss. Systematisations and discussions on remainder problems in 18th-century Germany Lưu trữ 2013-11-02 tại Wayback Machine"
  • Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 31.3: Modular arithmetic, pp. 862–868.
  • Anthony Gioia, Number Theory, an Introduction Reprint (2001) Dover. ISBN 0-486-41449-3.
  • Long, Calvin T. (1972). Elementary Introduction to Number Theory (ấn bản thứ 2). Lexington: D. C. Heath and Company. LCCN 77171950.
  • Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970). Elements of Number Theory. Englewood Cliffs: Prentice Hall. LCCN 71081766.
  • Sengadir, T. (2009). Discrete Mathematics and Combinatorics. Chennai, India: Pearson Education India. ISBN 978-81-317-1405-8. OCLC 778356123.

Liên kết ngoài

[sửa | sửa mã nguồn]