какие остатки могут получится при делении различных чисел на 17?

Цель: понять, какие остатки могут получиться при делении на 17.

Ключевые идеи:

• При делении целого числа a на 17 существует целое q и остаток r такие, что a = 17q + r и 0 ≤ r < 17.
• Следовательно, возможные остатки при делении на 17 — это все числа от 0 до 16 включительно: {0, 1, 2, ..., 16}.

Почему так:

• Любое число можно представить как кратное 17 плюс остаток r, где r выбирается так, чтобы он был меньше 17 и неотрицателен.
• Для любого r из 0..16 можно подобрать число a = 17k + r (например, a = r), которое даёт остаток r при делении на 17. Значит, все эти остатки реально встречаются.

Примеры остатков:

• 0 делится на 17 → остаток 0
• 17 делится на 17 → остаток 0
• 18 на 17 даёт остаток 1
• 33 на 17 даёт остаток 16 (поскольку 33 = 17·1 + 16)
• 100 на 17 даёт остаток 15 (потому что 100 = 17·5 + 15)
• Для отрицательных чисел остаток все ещё выбирается из 0..16, например -1 ≡ 16 (по модулю 17)

Итог:

• Возможные остатки при делении на 17: 0, 1, 2, ..., 16.
• Любой из этих остатков может появиться для некоторых чисел.