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

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}

Vấn đề ta đi tìm nghịch đảo bằng cách áp dụng thuật toán Euclid:

+Tìm nghịch đảo của 3937 theo modulo 77417450

+ Tìm nghịch đảo 1308 theo modulo 2017: 165

+ Tìm nghịch đảo 769 theo modulo 2013: 1924
Quá trình tìm nghịch đảo theo modulo:
[​IMG]

Vậy nghiệm cần tìm là:

x=2017\times 2017\times 2013\times 7450+2013\times 7741\times 2013\times 165+2011\times 7741\times 2017\times 1924=126598780950343

Nghiệm x cần tìm:

x\equiv 29483295796+31430170761a

và từ đây  dựa theo điều kiện đề bài để tìm số a nguyên cho phù hợp.

Kết luận số cần tìm:

99977426315776.

  

Chia sẻ

About casiobitex

Casiobitex

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

anh 1

XÂY DỰNG MỘT SỐ HỆ THỨC LƯỢNG TRONG TAM GIÁC

 Trong kỳ thi học sinh giỏi máy tính cầm tay cấp thành phố, đặc biệt …

×

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