Делимость, признаки делимости

Основная теорема арифметики, формулировка, доказательство.


В этой статье дана теоретическая основа разложения чисел на простые множители - основная теорема арифметики. Здесь мы дадим ее формулировку и приведем доказательство основной теоремы арифметики.


Вспомогательные теоремы

Основная теорема арифметики утверждает возможность разложения любого целого числа, которое больше единицы, на простые множители. Прежде чем сформулировать и доказать ее, рассмотрим две вспомогательные теоремы.

Теорема.

Любое целое положительное и отличное от единицы число a либо делится на простое число p, либо a и pвзаимно простые числа.

Доказательство.

Наибольший общий делитель чисел a и p делит p. Так как p – простое число по условию, то его положительными делителями являются лишь 1 и p, следовательно, НОД(a, p) равен либо 1, либо p. В первом случае НОД(a, p)=1, откуда следует, что числа a и p – взаимно простые. Во втором случае НОД(a, p)=p, а так как a делится на НОД(a, p), то a делится на p.

Теорема.

Если произведение нескольких целых положительных и отличных от единицы множителей делится на простое число p, то хотя бы один множитель делится на p.

Доказательство.

Каждый из множителей согласно предыдущей теореме либо взаимно прост с числом p, либо делится на p. Если бы все множители были взаимно просты с p, то произведение этих множителей было бы взаимно просто с p в силу свойств взаимно простых чисел. Поэтому, хотя бы один из множителей делится на p.

Основная теорема арифметики


Теперь мы обладаем необходимым арсеналом знаний, позволяющим провести доказательство основной теоремы арифметики.

Теорема.

Любое целое число, которое больше 1, можно разложить на произведение простых множителей, причем это разложение единственно, если не учитывать порядок следования множителей.

Доказательство.

Пусть a – целое число, большее единицы.

Сначала докажем возможность разложения числа a на простые множители.

Пусть p1 – наименьший положительный и отличный от 1 делитель числа a. В силу теоремы, доказанной в разделе таблица простых чисел, число p1 – простое. Тогда по определению делимости существует такое целое число a1, что a=p1·a1. Если a1 больше единицы, то существует его наименьший простой делитель p2, откуда a1=p2·a2 и a=p1·p2·a2. Если a2 больше единицы, то существует его наименьший простой делитель p3, поэтому a2=p3·a3, откуда a=p1·p2·p3·a3. И так продолжаем этот процесс, пока не получим an=1, что неизбежно, так как a, a1, a2, … - последовательность убывающих целых положительных чисел. Итак, мы всегда можем получить разложение числа a на простые множители вида a=p1·p2·…·pn (при n=1 имеем a=p1, это разложение соответствует случаю, когда число a простое).

Осталось доказать единственность полученного разложения.

Предположим, что помимо разложения a=p1·p2·…·pn существует еще одно разложение числа a на простые множители q1, q2, …, qm вида a=q1·q2·…·qm. Тогда должно быть справедливо равенство p1·p2·…·pn=q1·q2·…·qm. Покажем, что при n≠m это равенство невозможно, a при n=m произведения p1·p2·…·pn и q1·q2·…·qm тождественно равны.

Правая часть последнего равенства делится на q1, тогда в силу предыдущей теоремы хотя бы один из множителей p1, p2, …, pn должен делиться на q1. Допустим, на q1 делится p1, но так как числа p1 и q1 простые, то p1 делится на q1 только тогда, когда q1=p1. Это позволяет нам сократить обе части равенства p1·p2·…·pn=q1·q2·…·qm на q1=p1, получаем p2·…·pn=q2·…·qm. Рассуждая аналогично про p2 и q2, придем к равенству p3·…·pn=q3·…·qm. И так действуем дальше, пока в какой либо части равенства не сократятся все множители. При n≠m мы получим или равенство 1=qn+1·…·qm, или равенство pm+1·…·pn=1, которые невозможны для простых чисел qn+1, …, qm и pm+1, …, pn. Если же n=m, то мы получим тождество 1=1, которое указывает на тождественное равенство разложений a=p1·p2·…·pn и a=q1·q2·…·qm. Этим доказана единственность разложения числа на простые множители.

В заключение отметим, что основную теорему арифметики часто называют теоремой о разложении чисел на простые множители.

Материал этой статьи продолжает тема разложение чисел на простые множители, способы и примеры разложения.

Список литературы.

  • Виленкин Н.Я. и др. Математика. 6 класс: учебник для общеобразовательных учреждений.
  • Виноградов И.М. Основы теории чисел.
  • Михелович Ш.Х. Теория чисел.
  • Куликов Л.Я. и др. Сборник задач по алгебре и теории чисел: Учебное пособие для студентов физ.-мат. специальностей педагогических институтов.

Некогда разбираться?

Закажите решение

Профиль автора статьи в Google+