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

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

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

,

где p₁, …, p_k – простые числа.

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

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

,

где p₁ < p₂ < … < p_k – простые числа, а α₁, …, α_k – некоторые натуральные числа.

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

Доказательство основной теоремы арифметики заслуживает отдельного разговора. Однако пока что мы с Вами примем эту теорему без доказательства.

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

Возьмем, к примеру, число 882. Перебираем последовательно простые числа, начиная с двойки. 882 делится на 2. Следовательно, в разложении числа 882 на произведение простых сомножителей будет двойка как минимум в первой степени. Разделим 882 на 2. Получим 441. Число 441 на 2 не делится, но делится на 3. Тогда мы можем утверждать, что в разложении числа 882 должна присутствовать и тройка (снова же – как минимум в первой степени). Разделив 441 на 3, получаем 147. Продолжаем этот процесс, пока не получим единицу. Кратко это записывается в таком виде:

882	2
441	3
147	3
49	7
7	7
1

Исходя из схемы, теперь несложно записать искомое разложение (записываем сомножители в порядке возрастания, сверху вниз): 882 = 2 ∙ 3² ∙ 7².

Рассмотрим несколько примеров составления такого разложения.

Примеры.

270 2 135 3 45 3 15 3 5 5 1 270 = 2 ∙ 33 ∙ 5

415 5 83 83 1 415 = 5 ∙ 83

549 3 183 3 61 61 1 549 = 32 ∙ 61

693 3 231 3 77 7 11 11 1 693 = 32 ∙ 7 ∙ 11

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

К примеру, число 1323 = 3³ ∙ 7² будет делиться нацело на 63 = 3² ∙ 7 (поскольку 2 < 3 и 1 < 2), но не будет делиться на 567 = 3⁴ ∙ 7 (поскольку 4 > 3).

Задачи.

1. Делится ли 2⁹ ∙ 3 на 2?

Решение. Да, так как 2 входит в разложение этого числа на простые множители.

2. Делится ли 2⁹ ∙ 3 на 5?

Решение. Нет, потому что в разложении этого числа на простые множители нет простого числа 5.

3. Делится ли 2⁹ ∙ 3 на 8?

Решение. Да, поскольку 8 = 2³, а в разложение данного числа на простые множители двойка входит 9 раз (9 > 3).

4. Делится ли 2⁹ ∙ 3 на 9?

Решение. Нет, так как в разложение данного числа на простые множители тройка входит лишь один раз, а в разложение числа 9 – дважды.

5. Делится ли 2⁹ ∙ 3 на 6?

Решение. Да, потому что 6 = 2 ∙ 3, а 2 и 3 входят в разложение данного числа на простые.

6. Верно ли, что если натуральное число делится на 4 и на 3, то оно делится на 12?

Решение. Да. В разложение на простые множители числа, делящегося на 4, двойка входит по крайней мере 2 раза. Поскольку число делится и на 3, то в его разложение входит и тройка. Поэтому оно делится на 12.

7. Верно ли, что если натуральное число делится на 4 и на 6, то оно делится на 24?

Решение. Нет. Например, число 12. Дело в том, что если число делится на 4, то в его разложение на простые множители по крайней мере дважды входит число 2; из делимости числа на 6 следует, что в его разложении есть 2 и 3. Таким образом, заведомо в это разложение входят две (не три!) двойки и одна тройка, и можно утверждать лишь то, что число делится на 12.

8. Число a не делится на 3. Может ли на 3 делиться число 2a?

Решение. Нет, поскольку тройка не входит в разложение на простые множители числа a, а значит, не входит и в разложение числа 2a.

9. Число a – четно. Верно ли, что 3a делится на 6?

Решение. Да, так как 2 и 3 входят в разложение числа 3a на простые множители.

10. Число 5a делится на 3. Верно ли, что a делится на 3?

Решение. Да, потому что в разложение числа 5a на простые множители тройка входит, а в разложение простого числа 5 – нет.

11. Число 15a делится на 6. Верно ли, что a делится на 6?

Решение. Нет. Например, a = 2. Дело в том, что тройка, входящая в разложение числа 6, входит и в разложение числа 15. Поэтому можно утверждать лишь то, что в разложении числа a обязательно есть двойка.

Определение 3. Два числа называются взаимно простыми, если у них нет общих делителей, отличных от единицы.

Упражнение. Докажите, что любые два разных простых числа всегда являются взаимно простыми.