Tìm số N có 14 chữ số thỏa mãn điều kiện đồng dư

Tìm số [latex]N[/latex] 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ố [latex]7741,\,2017,\,2013[/latex] đôi một nguyên tố cùng nha, nên ta đi giải hệ phương trình đồng dư sau:

$$\begin{cases} x\equiv2017 & \text{mod}\,7741\\ x\equiv2013 & \text{mod}\,2017\\ x\equiv2011 & \text{mod}\,2013 \end{cases}\,\,\,(I)$$

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

$$x\equiv a_1.M_1.y_1+a_2.M_2.y_2+a_3.M_3.y_3$$

Trong đó [latex]a_1=2017;\,a_2=2013;\,a_3=2011[/latex]; [latex]M_1=2017\times 2013; M_2=7741 \times 2013; M_3=7741 \times 2017[/latex]; [latex]y_1=(M_1)^{-1}\,\,\text{mod}m_1; y_2=(M_2)^{-1}\,\,\text{mod}m_2; y_3=(M_3)^{-1}\,\,\text{mod}m_3[/latex].

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 7741: 7450.

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

+ Tìm nghịch đảo 769 theo modulo 2013: 1924.

Vậy nghiệm là: [latex]x=2017\times 2017 \times 2013 \times 7450+2013 \times 7741 \times 2013 \times 165 + 2011 \times 7741 \times 2017 \times 1924 = 12659878950343[/latex].
Nghiệm [latex]x[/latex] cần tìm: [latex]x \equiv 29483295796 + 31430170761a[/latex] và từ đây, dựa theo điều kiện đề bài để tìm số [latex]s[/latex] nguyên cho phù hợp.
Kết luận số cần tìm: 99977426315776.

Xem thêm hình ảnh về quá trình tìm nghịch đảo theo modulo:

THCS.26 

Chia sẻ

About TailieuCasio

TailieuCasio

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

gtln và gtnn 2019

SỬ DỤNG MÁY TÍNH CASIO FX-580VNX TÌM GTLN VÀ GTNN CỦA HÀM SỐ

Bài toán xác định GTNN và GTLN của một hàm số là một dạng toán …

×

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