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

Bài luyện tập – bài thi HSG MTCT THCS

Tìm số tự nhiên $x$ lớn nhất có 14 chữ số, biết $x$ chia cho $7741$ dư $2017$, chia cho $2017$ dư $2013$ và chia cho $2013$ dư $2011$.

 

Xét phương trình đồng dư

$$\left\lbrace\begin{array}{llll}
x & \equiv & 2017 & (\text{mod} \ 7741)& \\
x & \equiv & 2013 & (\text{mod} \ 2017)& \\
x & \equiv & 2011 & (\text{mod} \ 2013)
\end{array} \right.
$$

Áp dụng thuật toán “nghịch đảo mô-đu-lô” trong bài 1

thuattoan 1

 

ta tìm được $z_1, z_2$ và $z_3$ như sau:

  1. $\bullet\ $ ddm1a ddm1b
  2. $\bullet\ $ ddm1c ddm1d
  3. $\bullet\ $ ddm1 ddm1e

Ta có

$a_1y_1z_1=2017\times 2017\times 2013\times (-291)$
$a_2y_2z_2=2013\times 7741\times 2013\times 165$
$a_3y_3z_3=2011\times 7741\times 2017\times (-89)$
$$x \equiv a_1y_1z_1+a_2y_2z_2+a_3y_3z_3 + k n_1n_2n_3 \equiv 126598780950343+31430170761k, k \in \mathbb{Z}$$

Để $x$ lớn nhất có 14 chữ số, số nguyên $k$ lớn nhất thoả điều kiện $k \leqslant\ $ ddm1f. Vậy $k=-847$

Vậy số cần tìm là th$99.977.426.315.776$

Chia sẻ

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

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

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

TUYỂN SINH 10 – GIẢI BÀI TOÁN THỰC TẾ DẪN ĐẾN PHƯƠNG TRÌNH BẬC NHẤT

Để tránh sai số trong quá trình nhập liệu máy tính BitexEdu giới thiệu đế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