Таблицы Брадиса

Наибольшим общим делителем чисел а

Наибольшим общим делителем чисел а

Элементы математики в задачах - Г. А. Мерзон

Определение 1. Такие q и r называются, соответственно, частным и остатком при делении а на b.

Задача 2. Найдите частное и остаток при делении: а) —17 на 4; б) 23 на -7; в) —1 на -5.

Задача 3. Какие частные могут получиться при делении числа 59?

Задача 4. Найдите частное и остаток при делении: а) п2 на п + 1;

б)  п2 + п + 2 на п — 1; в) 2100 — 1 на 27 — 1; г*) 2т — 1 на 2п — 1.

Задача 5*. а) Покажите, что a2k+1 + 1 всегда делится на а + 1 без остатка.

б)  Найдите остаток от деления a2k + 1 на а + 1.

Определение 2. Наибольшим общим делителем чисел а и b называ­ется наибольшее из таких чисел d, что aid, bid. ^ Обозначение: НОД (a, b).

Задача 6. Докажите, что для любых а и b (а = 0 или b = 0) НОД(а, b) существует и единственен.

Задача 7. Докажите, что для любых а, b и с (а = 0 или b = 0): а) НОД(а, b) ^ 1; б) НОД(а, b) = |а| ^ b. а;

в)  НОД(а, са + b) = НОД(а, b).

Задача 8 (алгоритм Евклида). Рассмотрим следующий процесс.

Пусть (а, b) —пара положительных чисел такая, что а ^ b. Она заменяется на пару (b, r), где r — остаток от деления а на b. Пара (b, r) заменяется по тому же правилу и так далее. Процесс завершается, когда получается пара вида (d, 0). Покажите, что:

а)  процесс всегда завершается;

б)  d = НОД (а, b).

Задача 9. Вычислите при помощи алгоритма Евклида:

а)  НОД(91,147); б) НОД(—144, —233).

Задача 10. Пусть 0 < а < 1000, 0 < b < 1000. Верно ли, что алгоритм Евклида закончится после не более, чем: а) 14; б) 13 шагов?

Задача 11. Покажите, как при помощи алгоритма Евклида можно по произвольным а и Ь найти такие к и I, что ак + Ь1 = НОД(а, Ь).

Задача 12. Докажите, что уравнение ах + Ьу = d имеет решение в целых числах тогда и только тогда, когда d . НОД(а, Ь). В частности, НОД(а, Ь) —это наименьшее натуральное число, представимое в ви­де ах + Ьу.