Известно, что некоторое число при делении на 3 даëт остаток 2, при делении на 4 даëт остаток 3, при делении на 6 остаток 5. Найдите самое маленькое число с такими свойствами

Задача: найти наименьшее число n такое, что

• n ≡ 2 (mod 3)
• n ≡ 3 (mod 4)
• n ≡ 5 (mod 6)

Поясним и найдём решение шаг за шагом.

1. Объяснение связей между условиями

• Из условия n ≡ 5 (mod 6 следует, что n = 5 + 6k). Посчитаем по модулю 3: 5 ≡ 2 (mod 3) и 6k ≡ 0 (mod 3), значит n ≡ 2 (mod 3).
• Следовательно условие n ≡ 2 (mod 3) является производным от условия n ≡ 5 (mod 6). Его можно учитывать автоматически.

2. Сведение к двум условиям Нам осталось удовлетворить только:

• n ≡ 3 (mod 4)
• n ≡ 5 (mod 6)

Заметим, что gcd(4, 6) = 2. Чтобы система имела решение, остатки по модулю 2 должны совпадать:

• 3 ≡ 1 (mod 2)
• 5 ≡ 1 (mod 2) Они совпадают, значит решение существует. Решение будет уникально modulo lcm(4,6) = 12.

3. Поиск решения modulo 12 Найдем n, удовлетворяющий одновременно:

• n ≡ 3 (mod 4) ⇒ n = 3, 7, 11, 15, ...
• n ≡ 5 (mod 6) ⇒ n = 5, 11, 17, 23, ...

Перепробовав, видим, что наименьшее число из второй последовательности, которое также равно 3 по модулю 4, — это 11. Проверим:

• 11 mod 4 = 3 ✓
• 11 mod 6 = 5 ✓
• 11 mod 3 = 2 ✓ (соответствует исходному условию)

4. Ответ Наименьшее число — 11.

Дополнение (общий вид решений) Все решения имеют вид n ≡ 11 (mod 12). То есть любые n = 11 + 12t, где t — неотрицательное целое число. Но минимальное положительное решение — 11.