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

Фундаментальная теорема арифметики (также называемая теоремой об уникальной факторизации) - это теорема теории чисел. Теорема гласит, что каждое целое положительное число больше 1 можно записать в виде произведения простых чисел (или целое число само является простым). Теорема также утверждает, что существует только один способ записать число. Если два человека нашли два разных способа записать число, единственное, что может отличаться, - это порядок, в котором записаны простые числа. Например, мы можем написать:

6936 = 23 - 3 - 172 или 1200 = 24 - 3 - 52

и если кто-то другой найдет другой способ записать 6936 или 1200 как произведение простых чисел, мы можем расположить эти простые числа в правильном порядке и выяснить, что они совпадают с тем, что мы имеем здесь. Нахождение простых чисел называется факторизацией.

Эта теорема может быть использована в криптографии.

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

Первым, кто доказал теорему, был Евклид. Первое подробное и правильное доказательство было приведено в "Disquisitiones Arithmeticae" Карла Фридриха Гаусса.

Некоторые люди могут подумать, что теорема верна везде. Однако теорема не верна в более общих системах счисления, таких как алгебраические целые числа. Впервые об этом упомянул Эрнст Куммер в 1843 году в своей работе о последней теореме Ферма. Для получения дополнительной информации об этом: читайте алгебраическую теорию чисел.

Доказательство состоит из двух частей: сначала мы покажем, что каждое число можно записать в виде произведения простых чисел; затем мы покажем, что если мы запишем число в виде произведения простых чисел во второй раз, то два списка простых чисел должны совпасть.

Первая часть доказательства

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

Итак, посмотрим, что произойдет, если кто-то скажет, что знает целое положительное число, большее 1, которое нельзя записать в виде произведения простых. В этом случае мы попросим его назвать все числа, большие 1, которые не могут быть записаны в виде произведения простых. Одно из этих чисел должно быть наименьшим: назовем его n. Конечно, это число n не может быть 1. Кроме того, оно не может быть простым числом, потому что простое число является "произведением" одного простого: самого себя. Поэтому оно должно быть произведением чисел. Таким образом -

n = ab

где a и b - целые положительные числа, которые, конечно, меньше n. Но: n было наименьшим числом, которое нельзя записать как произведение простых. Значит, можно записать a и b как произведение простых, потому что они оба меньше n. Но тогда произведение

n = ab

также можно записать как произведение простых. Это невозможно, потому что мы говорили, что n не может быть записано как произведение простых.

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

Вторая часть доказательства

Теперь мы должны доказать, что существует только один способ записать положительное число больше 1 в виде произведения простых чисел.

Для этого мы используем следующую лемму: если простое число p делит произведение ab, то оно делит a или делит b (лемма Евклида). Сначала мы докажем эту лемму. Предположим, что p не делит a. Тогда p и a - простые числа, и мы имеем тождество Безута, которое говорит, что должны существовать целые числа x и y такие, что

px + ay = 1.

Умножение всего на b дает

pbx + aby = b,

Помните, что ab может делиться на p. Итак, теперь в левой части у нас есть два члена, которые делятся на p. Значит, член в правой части также делится на p. Теперь мы доказали, что если p не делит a, то оно должно делить b. Это доказывает лемму.

Сейчас мы докажем, что целое число, большее 1, можно записать только одним способом - как произведение простых чисел. Возьмем два произведения простых чисел A и B, которые имеют одинаковый результат. Таким образом, мы знаем, что A = B. Возьмем любое простое число p из первого произведения A. Оно делит A, поэтому оно также делит B. Используя несколько раз лемму, которую мы только что доказали, мы можем увидеть, что p должно делить по крайней мере один фактор b из B. Но все факторы являются простыми, поэтому b также является простым. Но мы знаем, что p также простое, поэтому p должно быть равно b. Теперь мы делим A на p и B на p. И получаем результат A* = B*. И снова мы можем взять простое число p из первого произведения A* и выяснить, что оно равно некоторому числу в произведении B*. Продолжая в том же духе, в конце мы увидим, что простые коэффициенты двух произведений должны быть совершенно одинаковыми. Это доказывает, что целое положительное число можно записать в виде произведения простых только одним единственным способом.

Вопросы и ответы

В: Что такое фундаментальная теорема арифметики?


О: Фундаментальная теорема арифметики - это теорема теории чисел, которая утверждает, что каждое целое положительное число больше 1 может быть записано как произведение простых чисел, и существует только один способ записать это число.

В: Как можно использовать эту теорему?


О: Эта теорема может быть использована в криптографии.

В: Что произойдет, если два человека найдут два разных способа записать одно и то же число?


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

В: Что такое факторизация?


О: Факторизация - это нахождение всех простых чисел, из которых состоит данное число.

В: Является ли 6936 примером простого числа?


О: Нет, 6936 не является простым числом; его можно записать как 23 - 3 - 172.
Нет, 6936 не является простым числом; его можно записать как 23 - 3 - 172.

AlegsaOnline.com - 2020 / 2023 - License CC3