Bài toán tổng quát về hệ phương trình đồng dư

08/11/2017
1,708 lượt xem
casiobitex

Bài toán tổng quát về hệ phương trình đồng dư

Đề bài: Tìm số $N$ có 14 chữ số, biết rằng $N$ chia 7741 dư 2017, chia 2017 dư 2013, chia 2013 dư 2011.

Bài giải:

Vì các số 7741, 2017, 2013 đôi một nguyên tố cùng nhau, nên ta đi giải hệ phương trình đồng dư sau:

$\left\{\begin{matrix} x\equiv 1\left ( mod7741 \right ) & & \\ x\equiv 2013\left ( mod2017 \right ) & & \\ x\equiv 2011\left ( mod2013 \right )& & \end{matrix}\right.$

$\left ( I \right )$

Thì hệ có nghiệm duy nhất theo modulo $M=7741\times 2017\times 2013$ là:

$x\equiv a_{1}.M_{1}.y_{1}+a_{2}.M_{2}.y_{2}+a_{3}.M_{3}.y_{3}$

Trong đó

$a_{1}=2017; a_{2}=2013; a_{3}=2011; M_{1}=2017\times 2013; M_{2}=7741\times 2013; M_{3}=7741\times 2017; y_{1}=\left ( M_{1} \right )^{-1}modm_{1}; y_{2}=\left ( M_{2} \right )^{-1}modm_{2}; y_{3}=\left ( M_{3} \right )^{-1}modm_{3}$