Олимпиадная задача по алгебре 8 класс на арифметику остатков. У Пети есть тринадцать карточек с числами от 1 до 13. Он хочет взять как можно больше из них так, чтобы их произведение давало остаток 9 при делении на 14. Сколько чисел он возьмёт? Введите все числа, которые он возьмёт.

Число 7 брать нельзя, потому что тогда произведение будет делиться на 14 и даст остаток 0.

Кроме того, итоговый остаток 9 — нечётный. Значит, произведение тоже должно быть нечётным, поэтому нельзя брать ни одного чётного числа:

Остаются числа:

Их произведение по модулю 14:

Удобно сгруппировать:

Поэтому произведение всех шести чисел равно

Нужно получить остаток 9. Уберём число 3:

так как $3\cdot5=15\equiv1\pmod{14}$.

Проверим:

Максимально Петя возьмёт 5 чисел: