modulo - Phần 1


Trong bài này chúng ta sẽ học về khái niệm modulo. Hai số $a$ và $b$ được gọi là bằng nhau modulo $n$ nếu $a$ và $b$ có cùng số dư khi chia cho $n$. Hay nói cách khác, là $(a-b)$ chia hết cho $n$. Chúng ta sẽ viết $a = b \pmod{n}$.

Ví dụ như, $5 = 9 \pmod{2}$, $-1 = 3 \pmod{2}$, $-2 = -8 \pmod{2}$. Rõ ràng theo modulo 2 thì một số $a$ bất kỳ sẽ hoặc là $a=0 \pmod{2}$ khi nó là số chẳn, hoặc là $a=1 \pmod{2}$ khi nó là số lẽ. 


Sau đây là một vài ví dụ khác:
$$0 = 3 = 6 = 9 = 12 = -3 = -6 \pmod{3},$$ $$1 = 4 = 7 = -2 = -5 \pmod{3},$$ $$2 = 5 = 8 = -1 = -4 \pmod{3},$$ $$0 = 4 = 8 = -4 \pmod{4},$$ $$1 = 5 = -3 = -7 \pmod{4},$$ $$2 = 6 = -2 = - 6 \pmod{4},$$ $$-2 = -14 \pmod{6}, ~~~7 = -14 \pmod{7}, ~~~5 = -3 \pmod{8}, ~~~16 = -2 \pmod{9}, ...$$

Chúng ta nhắc lại định nghĩa, chúng ta nói $a = b \pmod{n}$ khi mà $a-b$ chia hết cho n và đọc là $a$ bằng $b$ modulo $n$.

Bây giờ chúng ta xem các tính chất của phép modulo này.

Công thức cộng:
Nếu $a = b \pmod{n}$ và $x = y \pmod{n}$ thì $a +x = b + y \pmod{n}$.

Cái này giống như phép cộng chúng ta vẫn thường làm, tức là nếu $a=b$ và $x=y$ thì $a+x = b+y$. Ở đây, ta chỉ việc bỏ thêm cái đuôi modulo $n$ vào mà thôi. Ví dụ, từ $13 = 1 \pmod{4}$ và $2 = 6 \pmod{4}$ chúng ta có $15 = 7 \pmod{4}$.

Chứng minh tính chất này thì thật đơn giản, chúng ta chỉ việc dùng định nghĩa. Bởi vì $a = b \pmod{n}$ cho nên $a-b$ chia hết cho $n$, tương tự, vì $x = y \pmod{n}$ nên $x-y$ chia hết cho $n$. Cộng hai số chia hết cho $n$ sẽ được số chia hết cho $n$, do đó $(a-b)+(x-y)$ sẽ chia hết cho $n$. Chúng ta có $(a-b)+(x-y) = (a+x) - (b+y)$, như vậy vì số $(a+x) - (b+y)$ chia hết cho $n$ cho nên theo định nghĩa, chúng ta sẽ có $a +x = b + y \pmod{n}$. Như vậy là chúng ta đã chứng minh xong công thức cộng. Bây giờ chúng ta sẽ phát biểu các tính chất khác.


Công thức cộng (trường hợp đặc biệt): 
Nếu $a = b \pmod{n}$ thì $a + z = b + z \pmod{n}$.

Trường hợp đặt biệt này là từ công thức cộng mà ra khi ta áp dụng $a = b \pmod{n}$ và $z = z \pmod{n}$ để được $a + z = b + z \pmod{n}$.

Công thức trừ:
Nếu $a = b \pmod{n}$ và $x = y \pmod{n}$ thì $a - x = b - y \pmod{n}$.


Công thức trừ (trường hợp đặc biệt): 
Nếu $a = b \pmod{n}$ thì $a - z = b - z \pmod{n}$.

Công thức nhân:
Nếu $a = b \pmod{n}$ và $x = y \pmod{n}$ thì $a x = b y \pmod{n}$.


Công thức nhân (trường hợp đặc biệt): 
Nếu $a = b \pmod{n}$ thì $a z = b z \pmod{n}$.


Công thức luỹ thừa:
Nếu $a = b \pmod{n}$  thì $a^k = b^k \pmod{n}$.


Công thức luỹ thừa là từ công thức nhân mà ra. Chúng ta có $a = b \pmod{n}$ và $a = b \pmod{n}$, nên theo công thức nhân chúng ta có $a^2 = b^2 \pmod{n}$. Tiếp tục áp dụng công thức nhân đối với $a^2 = b^2 \pmod{n}$ và $a = b \pmod{n}$, chúng ta có $a^3 = b^3 \pmod{n}$. Và cứ thế đối với mọi số tự nhiên $k$ thì $a^k = b^k \pmod{n}$.



Bài tập về nhà: chứng minh công thức trừ và công thức nhân.

Hẹn gặp lại các bạn tại "modulo - Phần 2" khi chúng ta sẽ xem các ứng dụng của phép modulo.






4 nhận xét:

  1. cam on ban da dang nhieu phan toan bo ich, ban co the dang nhieu hon duoc khong, ban co facebook chu de minh co the ket ban voi ban

    Trả lờiXóa
  2. rất hay. xin cám ơn tác giả

    Trả lờiXóa
  3. bạn ơi, a^-1 mod a = ?
    giúp mình vơi

    Trả lờiXóa
  4. rất bổ ích! cảm ơn tác giả

    Trả lờiXóa