Основная теорема арифметики
До доказательства основной те-
оремы сделаем еще один шаг — до-
кажем лемму.
Лемма 3. Если произведение
ab делится на с, причем числа
b и с взаимно просты, то а де-
лится на с.
Страница переведена на новый сайт https://myeducation.su/ : страница
ФИЗИКО-МАТЕМАТИЧЕСКИЙ ЖУРНАЛ Квант (6 июнь 1972)
Действительно, поскольку у нас
НОД F, с) — 1, то но лемме 2 най-
дутся такие целые числа х и у, что
I ~ Ьх -г су. Умножая обе части ра-
венства на а, получаем, что а =
= abx -г асу. Так как по условию ab
делится на с, то и abx, и, разумеется,
асу делятся на с, а значит, и их сум-
ма а делится на с.
Лемма 3 очень часто используется
при решении задач, причем иногда
совсем «незаметно». Мы, например,
опирались на нее в предыдущем пунк-
те при выводе формул, дающих все
решения уравнения I19.V+ 13л/ —- 1
(там мы выделили соответствующую
фразу курсивом).
Задача ’20. Докажите, что если’чис-
ло и делится па взаимно простые числа & не,
то и делится на be.
Задача 21. Какие из следующих
утверждений перны:
а) если ««делится па 15, то хотя бы один
из сомножителей делится на 15;
Г>) если ab делится на 17, от хотя бы один
из сомножителей делится на 17;
в) если а делится на 6, а & делится на 10,
то ab делится на 15;
г) если ab делится на 60, а Ь взаимно прос-
то с 10, то с делится на 20.
Напомним теперь, что натуральное
число р называется простым, если
оно имеет ровно два делителя: р
и 1.
34 Основная теорема арифметики
Если р просто, то для любого
целого числа а верно одно из двух
утверждений: либо а делится на р,
либо аир взаимно просты (потому
что НОД (а, р) может равняться толь-
ко р или I).
Лемму 3 можно сформулировать
в частном случае так:
если произведение ab делится
на простое число р, то или чис-
ло а, или число b делится на
число р.
Отсюда сразу выводится основная
теорема арифметики.
Каждое число разлагается на
простые множители и притом
единственным образом.
Действительно, пусть число рас-
кладывается на несколько множите-
лей и хотя бы один нз них не является
простым числом, тогда этот множи-
тель сам разлагается на множители;
если среди его множителей снова
имеется не простой множитель, он
опять разлагается на множители, и так
далее. Поскольку каждый множи-
тель числа меньше самого числа, та-
кой процесс не может продолжаться
бесконечно, и мы обязательно придем
к разложению числа на простые мно-
жители.
Докажем теперь, что не может
быть двух различных разложений
числа на простые множители. Пред-
положим, что имеются два разло-
жения числа а : а — рхр., . . . рг =-
— <7i<7-> ¦ ¦ ¦ Яп {r^k), где»/?,- и qi —
простые числа. Так как левая часть
равенства делится на plf то и пра-
вая его часть должна делиться на
/>,, и значит, одно нз чисел qt
должно делиться на р1. Но qt —
простое число, значит, qt — p,. Со-
кратив равенство на общий множи-
тель qt -~ р,, обратимся к множи-
телю р., и установил! аналогично, что
он равен некоторому множителю qt.
Сократив равенство на р.> — qt, об-
ратимся к множителю р3 и так далее.
В конце концов слева сократятся все
множители и останется 1, а так как
qi — целые положительные числа,
то и справа не может остаться ниче-
го, кроме 1. Итак, числа pt и qt
будут соответственно равны и оба
разложения тождественны.
Задача 22. Разложите числа 1971,
1972 и 1973 на простые множители.
Задача 23. а) Докажите, что если
т и п взаимно просты и am ¦= bn, то существу-
ет такое целое it. что a— kn. b ¦¦= km.
б) Докажите, что если т и п взаимно
просты и хт — у», то найдется такое целое
число г, что х — г», а у — г'».
ШКОЛЬНИКИ
РАСЧИЩАЮТ КАТОК
Группа школьников рясчн-
щает лопатами каток, по-
крытый ровным слоем снега.
Действуя оптимальным об-
разом, ош1 расчищают круг-
лый каток радиусом 10 .«
(рис. I) за I ч. Зп сколько
времени они смогут расчи-
стить клток радиусом 20 м?
Что школьмнкн расчистят
быстрее — этот каток или
хоккейную площадку, имею-
щую форму прямоугольника
20 м X Ь4 ‘.« * рис. 2). по-
крытую таким же слоем
снега? Считается, что время
затрачивается на работу
против сил трения.
(Ответ смотрите на стр. 50)
В. М. Фшиман
35 Основная теорема арифметики
