Số học mô đun

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.

Chiếc đồng hồ với mô đun bằng 12

Đồng dưSửa đổi

Cho số nguyên n > 1, hai số được gọi là đồng dư môđun n nếu n là ước của hiệu giữa hai số đó (nghĩa là tồn tại số nguyên k sao cho a - b = nk.

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

 

Dấu ngoặc được dùng để biểu thị phép toán diễn ra ở hai bên, để tránh nhầm lẫn với ký hiệu b mod n không có dấu ngoặc.

Ví dụSửa đổi

Khi xét môđun 12, ta có:   bởi vì   và 24 là bội của 12.

Tính chấtSửa đổi

Vì quan hệ đồng dư là quan hệ tương đương, nên ta có các tính chất 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)

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
  • 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)

Nếu ab (mod n), ta thường dễ nhầm cho rằng kakb (mod n). Tuy nhiên điều sau là đúng:

  • Nếu cd (mod φ(n)), với φ is Hàm phi euler, thì acad (mod n)— nếu như a nguyên tố cùng nhau với n.

Đối với việc loại bỏ phần tử ở 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)

Xem thêmSửa đổi

Chú thíchSửa đổi

Tham khảoSửa đổi

  • 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 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àiSửa đổi