ФЭНДОМ


Prime.jpg Эта статья является статьёй проекта «Простые числа»
Вы можете помочь проекту, развив и дополнив её.
Wikipedia.png Это — материал из Википедии.


Основная теорема арифметики утверждает:

Каждое натуральное число n>1 представляется в виде n=p_1\cdot\dots\cdot p_k, где p_1,\dots,p_k — простые числа, причём такое представление единственно с точностью до порядка следования сомножителей.

Единицу можно также считать произведением нулевого количества простых чисел, «пустым произведением».

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

n = p_1^{d_1} \cdot p_2^{d_2} \cdot \dots \cdot p_k^{d_k}, где p_1 < p_2 < \dots < p_k — простые числа, и d_1,\dots,d_k — некоторые натуральные числа.

Такое представление числа n называется его каноническим разложением на простые сомножители.

Следствия Править

  • Основная теорема арифметики даёт элегантные выражения для наибольшего общего делителя и наименьшего общего кратного.

Доказательство Править

Доказательство основной теоремы арифметики опирается на лемму Евклида:

Если простое число p делит без остатка произведение двух целых чисел x \cdot y, то p делит x или y.


Существование. Пусть n — наименьшее натуральное число, неразложимое в произведение простых чисел. Оно не может быть единицей по формулировке теоремы. Оно не может быть и простым, потому что любое простое число является произведением одного простого числа — себя. Если n составное, то оно — произведение двух меньших натуральных чисел. Каждое из них можно разложить в произведение простых чисел, значит, n тоже является произведением простых чисел. Противоречие.

Единственность. Пусть n — наименьшее натуральное число, разложимое в произведение простых чисел двумя разными способами. Если оба разложения пустые — они одинаковы. В противном случае, пусть p — любой из сомножителей в любом из двух разложений. Если p входит и в другое разложение, мы можем сократить оба разложения на p и получить два разных разложения числа n/p, что невозможно. А если p не входит в другое разложение, то одно из произведений делится на p, а другое — не делится (как следствие из леммы Евклида, см. выше), что противоречит их равенству.

История Править

В «Началах» Евклида эта теорема отсутствует. Вероятно тогда (и позднее) она воспринималась как самоочевидный факт. Первая её точная формулировка и доказательство приводятся в книге К. Ф. Гаусса «Арифметические исследования», изданной в 1801 году.

Обнаружено использование расширения AdBlock.


Викия — это свободный ресурс, который существует и развивается за счёт рекламы. Для блокирующих рекламу пользователей мы предоставляем модифицированную версию сайта.

Викия не будет доступна для последующих модификаций. Если вы желаете продолжать работать со страницей, то, пожалуйста, отключите расширение для блокировки рекламы.

Также на ФЭНДОМЕ

Случайная вики