Подільність цілих чисел

В українській програмі цієї теми в такому вигляді немає, але вона спирається на ділення з остачею (3 клас), подільність і найбільший спільний дільник (6 клас). Лінійне зображення НСД вивчають у гуртках та в поглибленому курсі.

Кажуть, що a ділиться націло на b (b — дільник числа a), якщо існує ціле число q, для якого a = bq. Це записують a⋮b. Наприклад, 21⋮7, бо 21 = 7·3.

Якщо a не ділиться націло на b, є остача. Для будь-яких цілих a і b (b ≠ 0) існує рівно одна неповна частка q і одна остача r, для яких a = bq + r, де r не менша за 0 і менша за b. Це ділення з остачею.

Якщо a і c обидва діляться на b, то й кожне число ax + cy ділиться на b (x і y — будь-які цілі числа).

Якщо пройти кроки алгоритму Евкліда у зворотному порядку, найбільший спільний дільник (НСД) двох чисел можна записати як ax + by. Є й обернене твердження: рівняння ax + by = c має цілі розв'язки лише тоді, коли НСД чисел a і b ділить c.

У кожній місії працюй на аркуші ділення або у віконці відповіді; якщо застряг, прочитай підказку.