BITEXEDU Chuyên trang chia sẻ tài liệu, kinh nghiệm ứng dụng giải toán trên máy tính cầm tay
Định lý thặng dư Trung Hoa và áp dụng - bài 1
- 22/08/2021
- 1,209 lượt xem
Ta xét một hệ phương trình đồng dư theo các modulo nguyên tố cùng nhau.
Một ví dụ là tìm một số có dư là 1 khi chia cho 2, có dư là 2 khi chia cho 3 và có dư là 3 khi chia cho 5.
Cho các số $ n_i, i=1,2\dots, k$ đôi một nguyên tố cùng nhau và đặt $ N=n_1.n_2.\dots. n_k$
Định lý: Hệ phương trình đồng dư:
$$ \left\lbrace\begin{array}{llll}x &\equiv &a_1 & (\mod \ n_1), \\ x &\equiv &a_2 & (\mod \ n_2), \\ \dots & && \\ \dots &&& \\ x &\equiv &a_k & (\mod \ n_k)\end{array}\right.$$
có nghiệm duy nhất theo mô-đun $ M$ là
$$ x \equiv \displaystyle \sum_{i=1}^{k}a_iy_iz_i\quad (\mod M)$$
trong đó
- $\bullet\ $ $ y_i=\dfrac{N}{n_i}, i=1,2,\dots, k$.
- $\bullet\ $ $ z_i$ là nghịch đảo của $ y_i\quad (\mod n_i)$, nghĩa là $ y_iz_i \equiv 1\quad (\mod n_i)$.
Ví dụ: 8 là nghịch đảo của 7 theo modulo 11 vì $ 8\times 7 \equiv 1 (\mod 11)$
Khi $ y_i$ bé thì có thể tính nhẩm được. Đặc biệt khi $ y_1 \equiv 1$ thì $ z_i=1$.
Khi $ y_i$ khá lớn ta áp dụng thuật toán trên máy tính casio FX-580 VNX sau đây để tính $ z_i$ :
Khi bấm CALC máy tính sẽ hỏi A ta nhập $ n_i$, hỏi y ta nhập $ y_i$, hỏi C ta nhập 0, hỏi D ta nhập 1, hỏi E ta nhập thương của phép chia A cho y, hỏi F ta nhập dư của phép chia A cho y. Sau đó nhấn Enter (=) nhiều lần cho đến khi vào thấy dư R=1 thì dừng lại, nhấn enter (=) sẽ thấy $ z_i$.
Ví dụ: Tìm nghịch đảo của 3937 theo modulo 7741.
Vậy nghịch đảo của 3937 theo modulo 7741 là $-291+7741=7450$.
Ta trở lại ví dụ ở trên:
$$\left\lbrace\begin{array}{lll}x &\equiv 1& (\mod 2)\\ x &\equiv 2&(\mod 3)\\ x &\equiv 3 &(\mod 5)\end{array}\right.$$
$a_1=1, y_1=15\equiv 1\ \text{mod}\ 2 \Rightarrow z_1=1$
$a_2=2, y_2=10\equiv 1 \ \text{mod}\ 3\Rightarrow z_2=1$
$a_3=3, y_3=6\equiv 1 \ \text{mod}\ 5 \Rightarrow z_3=1$
Vậy $x \equiv 53 \ (\text{mod}\ 30)$
About TS. Nguyễn Thái Sơn
