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
Sử dụng định lý phần dư Trung Hoa (CRT)
- 16/07/2025
- 523 lượt xem
 |
|
|
Phần 3. Sử dụng định lý phần dư Trung Hoa
để tìm dư của phép chia $\boldsymbol{a^n}$ cho $\boldsymbol{b}$. |
 |
Định lý phần dư Trung Hoa không phải là lợi thế để tìm dư của phép chia $a^n$ cho $b$ nhưng đây là một kênh tham khảo dành cho giáo viên phụ trách đội tuyển. Hơn nữa Định lý này còn áp dụng để giải một số bài toán phức tạp sau này. |
|
Ta xét lại bài toán: Tìm dư của phép chia số $x=29^{376}$ cho $1975$. |
| Ta có $1975=25\times 79$, trong đó $25$ và $79$ nguyên tố cùng nhau. Ta sẽ tìm dư của các phép chia số $x=29^{376}$ cho $25$ và cho $79$. Sau đó “tổ hợp 2 nghiệm” ta sẽ được dư của phép chia $x=29^{376}$ cho $1975$. |
Thực hành: Ta tìm $a_1$ sao cho $x \equiv a_1 \ (\text{mod}\ 25 )$.
Vì $25$ và $29$ nguyên tố cùng nhau 
nên theo Định lý Euler $29^{\varphi(25)} \equiv 1 \ (\text{mod}\ 25)$.
Ta có $\varphi (25)=20$ nên $29^{20} \equiv 1 \ (\text{mod}\ 25 )$.
$29^{376}=29^{20.18+16}=\left(29^{20}\right)^{18}.29^{16} \equiv 29^{16} \ (\text{mod}\ 25)$.
$29^{16}=(29^4)^4$ 
,
nhập biểu thức 
sau đó nhấn $\fbox{OK}$ 2 lần 
.
Vậy $x \equiv 21 \ (\text{mod}\ 25 )$.
Hoàn toàn tương tự vì $79$ và $29$ nguyên tố cùng nhau nên $29^{\varphi(79)} =29^{78} \equiv 1 \ (\text{mod}\ 79 )$. Khi đó $29^{376}=29^{78.4+64}=\left(29^{78}\right)^4.29^{64} \equiv ((29^{4})^4)^4\ (\text{mod}\ 79 )$.
, nhập biểu thức 
sau đó nhấn $\fbox{OK}$ 3 lần 
.
Vậy $x \equiv 9 \ (\text{mod}\ 79)$.
Ta có hệ phương trình $$\left\lbrace\begin{array}{ll} x \equiv 21 \ &(\text{mod}\ 25 )\\
x \equiv 9 \ &(\text{mod}\ 79 )\end{array} \right. $$
“Tổ hợp 2 nghiệm” ta có: 
Kết luận: $x \equiv 246\ (\text{mod}\ 1975)$.
 Định lý Euler. Nếu $a$ và $n$ nguyên tố cùng nhau (nghĩa là $\text{gcd}(a,n)=1 $) thì $a^{\varphi(n)} \equiv 1 \ (\text{mod}\ n)$, |
trong đó $\varphi(n)$ được xác định như sau:
Ví dụ: $25=5^2 ⇒ \varphi(25)=25\times \left(1-\dfrac15\right)=20$.
Đặc biệt nếu $n$ là số nguyên tố thì $\varphi(n)=n-1$.
 Định lý phần dư Trung Hoa cho hệ hai phương trình đồng dư. Nếu $a_1, a_2$ nguyên tố cùng nhau thì hệ phương trình $$\left\lbrace\begin{array}{ll}x \equiv a_1 &(\text{mod}\ m_1)\\ x \equiv a_2 &(\text{mod}\ m_2)\end{array} \right. $$ có nghiệm duy nhất $$x \equiv a_1m_2y_2+a_2m_1y_1\ (\text{mod}\ m_1m_2)$$ |
trong đó
$\bullet\quad y_2=(m_2)^{-1}\ (\text{mod}\ m_1)\qquad $ (đọc là $y_2$ là nghịch đảo của $m_2$ theo mô-đu-lô $m_1$)
$\bullet\quad y_1=(m_1)^{-1}\ (\text{mod}\ m_2)\quad $ ($y_1$ là nghịch đảo của $m_1$ theo mô-đu-lô $m_2$), nghĩa là
Nếu bài toán sẽ gặp không quá phúc tạp thì $y_2$ và $y_1$ được tìm như sau:
Lập bảng giá trị cho hai hàm số $f(x)=\dfrac{m_2x-1}{m_1}\ , g(x)=\dfrac{m_1x-1}{m_2}$ với $x$ nguyên chạy từ $1$ đến $30$ nếu kết quả của phép chia là số nguyên thì $x$ tương ứng chính là $y_2, y_1$ cần tìm.
 Minh họa bằng hệ phương trình đã cho ở trên.
|
Xét lại hệ phương trình $$\left\lbrace\begin{array}{llll} x \equiv 21 \ &(\text{mod}\ 25 ) & \times\quad y_1 & (\text{nghịch đảo của $25$ theo mô-đu-lô $79$}) \\
x \equiv 9 \ &(\text{mod}\ 79 )& \times\quad y_2 & (\text{nghịch đảo của $79$ theo mô-đu-lô $25$})\end{array} \right. $$
Lập bảng giá trị cho hai hàm số 
kết quả 
.
Vì $f(x)$ là số nguyên với $x=19$ nên $y_1=19$, $g(x)$ là số nguyên với $x=19$ nên $y_2=19$ (ngẫu nhiên $y_1=y_2=19$, các bài toán khác $y_1\ne y_2$).
Vậy $x\equiv \underbrace{21\times 79\times 19}_{a_1m_2y_2}+\underbrace{9\times 25\times 19}_{a_2m_1y_1}\quad (\text{mod}\ 25\times 79 ) ⇔ \quad \fbox{$ x \equiv 246\quad (\text{mod}\ 1975 )$}$
About TS. Nguyễn Thái Sơn
