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

То есть пусть аЪ .

То есть пусть аЪ .

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

Задача 14. Докажите, что если р — простое, то либо а делится на р, либо найдутся такие х и у, что ах + ру = 1.

~0~                  Решение. Если р — простое и а не делится на р, то это означает, что                    ~і

аир взаимно просты (т. е. их НОД равен единице), а отсюда и из задачи 11 следует, что найдутся такие х и у, что ах + ру = 1.

Задача 15. Пусть р — простое число. Докажите, что если аЪ. р, то а.р или Ъ . р .

Решение. Предположим противное. То есть пусть аЪ . р, но а . р и Ъ/р. Тогда по предыдущей задаче найдутся такие х1, х2, уг и у2, что будет выполнено следующее: ахг + рух = 1, Ъх2 + ру2 = 1. Те­перь перемножим левые и правые части этих равенств и получим: аЪх1 х2 + ру1Ъх2 + ру2ах1 + р2уху2 = 1; так как аЪ . р, то левая часть делится на р, а правая — не делится. Получили противоречие.

Задача 16. Докажите основную теорему арифметики (задача 16в листка «Целые числа 1»).

Решение. Напомним, что в предыдущем листочке мы свели доказа­тельство основной теоремы арифметики к следующему факту. Пусть у нас есть два разложения числа на простые множители:

х = р1 ■ р2 •• . •• рп = 41 ■ 42 •• . •• 4т

168                     Целые числа 2. Алгоритм Евклида

(где р1, р2, ..., рп, q1, q2, • ••, qn —необязательно различные простые множители), тогда каждый простой множитель из левой части обязательно присутствует в правой и наоборот.

Докажем, например, что р1 присутствует в правой части. Так как q1 ■ q2 ■ . ■ qn = q1 ■ (q2 ■ • • • ■ qn). Рі, то по задаче 15 либо q1. р1 (и тогда q1 = р1, так как оба числа простые), либо q2 ■ ... ■ qn = q2 ■ (qз ■... ■ qn). . р1. Опять, воспользовавшись задачей 15, получаем, что либо q2 . р1 (и тогда q2 = р1, так как оба числа простые), либо q3 ■ ... ■ qn = = q3 ■ (q4 ' ••• ' qn). р1. Применяя вышеописанную процедуру, мы рано или поздно получаем, что р1 совпадет с одним из множителей qi.