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

Итак, получили частное 2тп ...

Итак, получили частное 2тп ...

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

г) Начнем делить 2т — 1 на 2п — 1 в столбик: 2т — 1 — 2т—п (2П — 1) = = 2т—п — 1. Заметим, что мы свели задачу к аналогичной для чисел т — п и п. Продолжая деление дальше, получим формулу

2т — 1 = (2т—п + 2т—2п + ... + 2т—чп)(2п — 1) + 2г — 1,

где q и г — частное и остаток от деления т на п. Итак, получили частное 2т—п + ... + 2т—^ и остаток 2г — 1.

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

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

Ш Вообще, можно показать, что остаток от деления многочлена Р(х) на многочлен х — х0 есть число Р(х0).

Решение. а) а2к+1 + 1 = (а + 1)(а2к — а2к—1 + ... +1).

б) Докажем, что остаток равен 2, то есть а2к — 1 делится на а +1. Действительно, а2к — 1 = а(а2к—1 + 1) — (а + 1). Вычитаемое делится на а +1 в силу предыдущего пункта, следовательно, и разность де­лится на а +1.

Определение 2. Наибольшим общим делителем чисел а и Ъ называ­ется наибольшее из таких чисел й, что а. й, Ъ. й.

Обозначение: НОД(а, Ъ).

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

Решение. Множество чисел, которые делят сразу и а, и Ъ, непусто, так как по крайней мере оно содержит единицу. Кроме того, среди всех таких чисел существует наибольшее, так как каждое из них не пре­восходит \Ъ\ (почему?), следовательно, их существует лишь конечное количество для каждой пары а и Ъ. Значит, перебрав их все, мы можем найти наибольшее (оно точно будет положительным).

Задача 7. Докажите, что для любых а, Ъ и с (а = 0 или Ъ = 0):

а) НОД(а, Ъ) ^ 1; б) НОД(а, Ъ) = \а\^ Ъ . а;

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

Решение. а) См. решение предыдущей задачи.

б)  Заметим, что НОД(а, Ъ) = \а\ ^ Ъ. а. Теперь докажем, что Ъ. а ^ ^ НОД(а, Ъ) = \а\. Так как Ъ . а, то \а\ —общий делитель чисел а и Ъ. Но ясно также, что большего делителя обоих чисел быть не может, так как а не может делиться на число, большее по модулю, чем \а\.