1. Thuật toán Euclid và Đẳng thức Bezout
Định nghĩa 1.1 (Tính chia hết): Cho \(a, b\) là hai số nguyên. Ta nói rằng \(a\) chia hết cho \(b\) nếu tồn tại một số nguyên \(c \in \mathbb{Z}\) sao cho \(a = bc\).
Mệnh đề 1.2 (Phép chia Euclid): Cho \(a\) là một số nguyên, \(b\) là một số nguyên dương. Khi đó tồn tại duy nhất hai số nguyên \(q, r \in \mathbb{Z}\) sao cho:
\[a = qb + r \quad \text{và} \quad 0 \le r < b\]Định lý 1.3 (Định lý Bezout): Cho \(a\) và \(b\) là hai số nguyên. Khi đó tồn tại hai số nguyên \(m, n \in \mathbb{Z}\) sao cho:
\[\text{UCLN}(a, b) = am + bn\]Chứng minh Định lý 1.3:
Đặt \(d = \text{UCLN}(a, b)\). Khi đó với mọi \(m, n \in \mathbb{Z}\) ta luôn có \(d\) là ước của \(am + bn\).
Xét tập hợp \(D := \{e = am + bn \in \mathbb{Z} \mid m, n \in \mathbb{Z}\}\). Theo khẳng định trên ta luôn có \(d\) là ước của \(e\) với mọi \(e \in D\).
Đặt \(D_+ = \{e \in D \mid e > 0\}\). Với \(a, b\) cho trước ta luôn có thể chọn được \(m, n \in \mathbb{Z}\) sao cho \(am + bn > 0\), nên \(D_+\) là một tập con khác rỗng của tập các số nguyên dương. Vì thế nó tồn tại phần tử nhỏ nhất. Gọi \(d_+ = am_+ + bn_+\) là phần tử nhỏ nhất đó. Khi đó \(d \mid d_+\) (do \(d_+\) cũng là một phần tử của \(D\)).
Ta sẽ chứng minh rằng \(d_+ \mid d\). Điều này tương đương với việc chứng minh rằng \(d_+ \mid a\) và \(d_+ \mid b\).
Giả sử phản chứng \(a\) không chia hết cho \(d_+\), khi đó áp dụng phép chia Euclid cho \(a\) và \(d_+\) ta được \(a = q d_+ + r\) với \(0 < r < d_+\). Từ đó ta có:
\[r = a - q d_+ = (1 - qm_+)a + (-qn_+)b \in D\]Ta vừa chỉ ra rằng \(r\) là một phần tử nhỏ hơn \(d_+\) và cũng thuộc \(D_+\) (mâu thuẫn với giả thiết \(d_+\) là số nhỏ nhất). Vậy \(d_+\) phải là ước của \(a\). Chứng minh tương tự ta cũng có \(d_+\) phải là ước của \(b\).
Vậy \(d = d_+ = am_+ + bn_+\).
2. Đồng dư thức và Vành các lớp đồng dư
Hệ quả 1.4: Cho \(a\) và \(b\) là hai số nguyên. Khi đó \(a\) và \(b\) nguyên tố cùng nhau khi và chỉ khi tồn tại hai số nguyên \(m\) và \(n\) thỏa mãn:
\[am + bn = 1\]Định nghĩa 1.5 (Đồng dư): Cho \(n \in \mathbb{N}_+\) là một số nguyên dương. Ta nói \(a \equiv b \pmod{n}\) khi và chỉ khi \(a - b\) chia hết cho \(n\).
Áp dụng phép chia Euclid cho cặp các số nguyên \((a_1, n)\) và \((a_2, n)\) ta được:
\[a_1 = q_1 n + r_1, \quad 0 \le r_1 < n\]\[a_2 = q_2 n + r_2, \quad 0 \le r_2 < n\]Điều này dẫn đến \(a_1 \equiv a_2 \pmod{n} \iff r_1 = r_2\). Ta quan tâm đến tập hợp các lớp đồng dư của \(n\), ký hiệu là \(\mathbb{Z}/n\mathbb{Z}\).
- Tập \(\mathbb{Z}/n\mathbb{Z}\) có đúng \(n\) phần tử.
- Ví dụ 1.6: Với \(n = 5\), ta có \(\mathbb{Z}/5\mathbb{Z} = \{[0], [1], [2], [3], [4]\}\).
- Trên tập \(\mathbb{Z}/n\mathbb{Z}\) ta có thể cộng các lớp đồng dư, nhân các lớp đồng dư. Cụ thể:
Định lý 1.7 (Gauss): Tập hợp \(\mathbb{Z}/n\mathbb{Z}\) cùng với phép toán cộng và nhân ở trên lập thành một vành giao hoán (có tính chất giống như \(\mathbb{Z}, \mathbb{Q}, \mathbb{R}, \dots\)).