Định lý thặng dư Trung Hoa và áp dụng - bài 1

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 đó

  1. $\bullet\ $ $ y_i=\dfrac{N}{n_i}, i=1,2,\dots, k$.
  2. $\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$ :
thuattoan 1
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)$

Chia sẻ

About TS. Nguyễn Thái Sơn

BQT Toán Casio
nguyên trưởng Khoa Toán-Tin học ĐHSP TP HCM (1999-2009). nguyên Giám đốc- Tổng biên tập NXB ĐHSP TP HCM (2009-2011). nguyên Tổng thư ký Hội Toán học TP HCM (2008-2013). Giảng viên thỉnh giảng ĐHSP TP HCM.

Bài Viết Tương Tự

CÁC BÀI TOÁN THỰC TẾ THEO CHƯƠNG TRÌNH TOÁN LỚP 8

Bài 1. Xe 1 đi từ A đến B với vận tốc $30km/h$. Sau đó …

×

Sai số! tác hại to lớn của việc sử dụng máy tính Casio giả và cách phòng tránh Chi tiết