Делимость целых чисел

В российской программе этой темы нет (деление с остатком изучают в 3–5 классах, а алгоритм Евклида — в углублённом курсе 7 класса), но на ней видно, как устроена делимость. Говорят, что a делится на b, если существует целое число 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, то на b делится и любое число вида ax + cy (x и y — любые целые).

Если пройти шаги алгоритма Евклида в обратном порядке, НОД двух чисел можно записать в виде ax + by. Верно и обратное: уравнение ax + by = c имеет целые решения только тогда, когда НОД чисел a и b делит c.

Работай на листе деления уголком или в окошке для ответа в каждом задании; если не получается, прочитай подсказку.