ДЕЛИМОСТЬ И ПРОСТЫЕ ЧИСЛА

259

как само соотношение (1) показывает, что d делится на любое

число, служащее общим делителем чисел а и Ь.

Заметим, наконец, что весь этот круг вопросов, в особенности

если присоединить к нему то, что будет по этому поводу изло-

жено в главе III, в связи с алгорифмом Евклида, может служить

превосходным — нетрудным и вместе с тем увлекательным — мате-

риалом для работы математического кружка средней школы.

Воспользуемся теперь теоремой 1 для доказательства следующего

очень важного предложения теории делимости (известного уже

Евклиду):

Теорема 2. Если числа а н Ь взаимно просты, а произведе-

ние ас Делится на Ь, то н цисло с делится на Ь.

В самом деле, в силу теоремы 1 целые числа х и у могут быть

выбраны так, что

откуда

асх — Ьсу с.

Так как по условию ас делится на Ь, то пусть

К— целод число; мы получаем:

с асх — Ьсу Ь,'гх — Ьсу Ь (Кх — су),

откуда и видно, что с делится на Ь.

где

Пусть теперь р — простое число и а— любое натуральное

число; очевидно, что тогда возможно только одно из двух: либо а

делится на р, либо а взаимно просто с р. В самом деле, если а

не взаимно просто с р, то а и р имеют общего делителя 1;

но р, будучи числом простым, делится только на 1 и р; поэтому

и а делится на р.

Это простое замечание позволяет вывести из теоремы 2 сле-

дующее важное

Сл е д ст в и е. Если произведение ab Делится на простое число

р, то по женьшей мере один из сомножителей Делится на р.

В самом деле, если, например, а не делится на р, то в силу

только что сделанного замечания а взаимно просто с р; но тогда

из делимости произведения ab на р в силу теоремы 2 вытекает,

что Ь делится на р, что и требовалось доказать.

Это правило, доказанное нами для произведения двух сомножи-

телеИ, легко способом индукции распространить и на любое число

сомножителей. Пусть, например, произведение abc делится на

простое число р; если а не делится на р, то согласно доказан-

ному произведение Ьс должно делиться на р, а тогда, как мы

знаем, либо Ь, либо с делится на р. В конечном счёте, следова-

тельно, из делимости на простое число р произведения abc вытекает

делимость на р по меньшей мере одного из сомножителей. Таким

же путем от трех сомножителей можно, очевидно, перейти к четырём,

37$