Question

[Dương Đình Khang]

tìm số tự nhiên nhỏ nhất thỏa mãn:

• Chia cho 29 dư 5.
• Chia cho 31 dư 28.

Answer 1

[Lê Đình Hải Anh]

Để tìm số tự nhiên nhỏ nhất thỏa mãn hai điều kiện:

• Chia cho 29 dư 5, tức là \(x \equiv 5 \left(\right. m o d 29 \left.\right)\)
• Chia cho 31 dư 28, tức là \(x \equiv 28 \left(\right. m o d 31 \left.\right)\)

Ta có thể sử dụng phương pháp sắp xếp đồng dư (Chinese Remainder Theorem).

Bước 1: Biểu diễn bài toán dưới dạng hệ đồng dư

Ta có hệ đồng dư sau:

\(x \equiv 5 \left(\right. m o d 29 \left.\right)\) \(x \equiv 28 \left(\right. m o d 31 \left.\right)\)

Bước 2: Giải hệ đồng dư

Ta sẽ giải hệ đồng dư này bằng cách thay thế \(x\) từ đồng dư đầu tiên vào đồng dư thứ hai.

Giả sử \(x = 29 k + 5\) (vì \(x \equiv 5 \left(\right. m o d 29 \left.\right)\)).

Thay vào đồng dư thứ hai:

\(29 k + 5 \equiv 28 \left(\right. m o d 31 \left.\right)\) \(29 k \equiv 23 \left(\right. m o d 31 \left.\right)\)

(Ở đây \(28 - 5 = 23\)).

Bước 3: Giải phương trình đồng dư

Ta cần giải phương trình \(29 k \equiv 23 \left(\right. m o d 31 \left.\right)\). Để làm điều này, ta tìm nghịch đảo của 29 modulo 31.

Sử dụng thuật toán Euclid mở rộng để tìm nghịch đảo của 29 modulo 31:

\(31 = 1 \times 29 + 2\) \(29 = 14 \times 2 + 1\) \(2 = 2 \times 1 + 0\)

Dừng lại khi còn dư 0. Giải ngược lại ta có:

\(1 = 29 - 14 \times 2 = 29 - 14 \times \left(\right. 31 - 1 \times 29 \left.\right) = 15 \times 29 - 14 \times 31\)

Vậy nghịch đảo của 29 modulo 31 là 15.

Bước 4: Tính giá trị của \(k\)

Nhân hai vế của phương trình \(29 k \equiv 23 \left(\right. m o d 31 \left.\right)\) với 15:

\(k \equiv 15 \times 23 \left(\right. m o d 31 \left.\right)\)

Tính \(15 \times 23 = 345\), và \(345 \div 31 = 11\) dư 4, nên:

\(k \equiv 4 \left(\right. m o d 31 \left.\right)\)

Bước 5: Tính giá trị của \(x\)

Vậy \(k = 31 m + 4\) với \(m\) là một số nguyên. Thay vào \(x = 29 k + 5\):

\(x = 29 \left(\right. 31 m + 4 \left.\right) + 5 = 29 \times 31 m + 116 + 5 = 899 m + 121\)

Do đó, \(x = 899 m + 121\). Số tự nhiên nhỏ nhất là khi \(m = 0\), tức là:

\(x = 121\)

Kết luận:

Số tự nhiên nhỏ nhất thỏa mãn các điều kiện là 121.

Answer 2

[Vũ Trung Nhân]

a)Gọi số cần tìm là x

=>x-5 chia hết cho 29

x=29+5=34

Vậy x=34

b)Gọi số đó là y

=>y-28 chia hết cho 31

y=31+28=59

Vậy y=59