Навчання / Бібліотека / Головоломки

Спільні остачі

ГоловоломкиСереднє

Знайдіть найменше додатне ціле число, яке дає остачу $3$ при діленні на $7$ , остачу $5$ при діленні на $8$ і остачу $1$ при діленні на $9$ .

Для перевірки відповіді потрібен JavaScript. Підказка й розв’язок відкриваються і без нього.

Підказка

Випишіть числа, що дають остачу $1$ при діленні на $9$ , і залиште лише ті, що задовольняють інші умови, крокуючи на добуток уже врахованих модулів.

Розв’язок

Числа з остачею $1$ за модулем $9$ мають вигляд $9 k + 1$ , і $9 k + 1$ дає остачу $5$ за модулем $8$ рівно тоді, коли $k$ дає остачу $4$ за модулем $8$ , тож перший кандидат — $37$ , а решта — $37 + 72 t$ .
За модулем $7$ маємо $37 \equiv 2$ і $72 \equiv 2$ , тож $37 + 72 t \equiv 2 + 2 t$ , і потрібно, щоб це було $3$ за модулем $7$ .
Це означає $2 t \equiv 1$ за модулем $7$ , отже $t \equiv 4$ за модулем $7$ , а найменше значення — $t = 4$ .
Число дорівнює $37 + 72 \times 4 = 325$ .

Відповідь: $325$