Skip to main content
LibreTexts - Ukrayinska

5.6: Фундаментальна теорема арифметики

  1. Last updated
  2. Save as PDF
  • Page ID
    64113

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

    Прості числа - це натуральні числа, які не мають належного дільника, крім 1. Прості числа можна розглядати як будівельні блоки всіх цілих чисел щодо множення.

    Теорема\(\PageIndex{1}\): Fundamental Theorem of Arithmetic

    Задано будь-яке ціле число\(n\geq 2\), існують\(p_1 \leq p_2 \leq \cdots \leq p_s\) такі прості числа, що\(n = p_1 p_2 \ldots p_s\). Крім того, ця факторизація є унікальною, в тому сенсі, що якщо\(n = q_1 q_2 \ldots q_t\) для деяких простих чисел\(q_1 \leq q_2 \leq \cdots \leq q_t\), то\(s=t\) і\(p_i = q_i\) для кожного\(i\),\(1\leq i\leq s\).

    Доказ

    Спочатку доведено існування факторизації. \(S\)Дозволяти множина цілих чисел\(n\geq2\), які не можна виразити як добуток простих чисел. Оскільки продукт може містити лише одне просте,\(S\) не містить жодного простого. Припустимо\(S\neq\emptyset\), тоді принцип добре впорядкованості має на увазі, що\(S\) має найменший елемент\(d\). Оскільки\(S\) не містить простих чисел,\(d\) є складовим, тому\(d=xy\) для деяких цілих чисел\(x\) і\(y\), де\(2\leq x,y<d\). Мінімалізм\(d\) означає, що\(x,y\not\in S\). Так що обидва\(x\) і\(y\) можуть бути виражені як добуток простих чисел, то\(d=xy\) є ще й добутком простих чисел, що є протиріччям, тому що\(d\) належить\(S\). Отже, що означає\(S=\emptyset\), що кожне ціле число\(n\geq2\) може бути виражено як добуток простих чисел.

    Далі ми доведемо, що факторизація унікальна. Припустимо, що є два способи фактора\(n\), скажімо\(n = p_1 p_2 \ldots p_s = q_1 q_2 \ldots q_t\). Без втрати спільності ми можемо припустити\(s\leq t\). Припустимо, існує найменший\(i\), де\(1\leq i\leq s\), такий що\(p_i \neq q_i\). Потім\[p_1 = q_1, \quad p_2 = q_2, \quad \cdots \quad p_{i-1} = q_{i-1}, \quad\mbox{but}\quad p_i \neq q_i. \nonumber\] випливає, що\[p_i p_{i+1} \cdots p_s = q_i q_{i+1} \cdots q_t, \nonumber\] в яких обидві сторони мають як мінімум два фактори (чому?). Без втрати спільності ми можемо припустити\(p_i < q_i\). Оскільки\(p_i \mid q_i q_{i+1} \cdots q_t\), і\(p_i\) є основним, Лема Евкліда передбачає, що\(p_i \mid q_j\) для деяких\(j\), де\(i < j \leq t\). Оскільки\(q_j\) є простим, ми повинні мати\(p_i = q_j \geq q_i\), що суперечить припущенню, що\(p_i < q_i\). Тому не існує жодного,\(i\) для чого\(p_i\neq q_i\). Це засіб\(p_i=q_i\) для кожного\(i\), і як наслідок, ми повинні мати\(s=t\).

    Цікаво, що ми можемо використовувати сильну форму індукції, щоб довести існування частини фундаментальної теореми арифметики.

    Доказ

    (Існування) Індукт на\(n\). Позов, очевидно, тримається за\(n=2\). Припустимо, що він тримає\(n=2,3,\ldots,k\) для деякого цілого числа\(k\geq2\). Ми хочемо показати, що це також стосується\(k+1\). Якщо\(k+1\) це просте, ми закінчили. В іншому випадку,\(k+1=\alpha\beta\) для деяких цілих чисел\(\alpha\) і\(\beta\), обидва менше ніж\(k+1\). Так як\(2\leq \alpha,\beta \leq k\), обидва\(\alpha\) і\(\beta\) можуть бути виражені у вигляді добутку простих чисел. Склавши ці прості числа разом, а при необхідності мітки та переставляючи їх, ми бачимо, що\(k+1\) це також можна виразити як добуток простих чисел у бажаному нам вигляді. На цьому індукція закінчена.

    Наступний результат - одна з найдавніших теорем в математиці, численні докази можна знайти в літературі.

    Теорема\(\PageIndex{2}\)

    Є нескінченно багато простих чисел.

    Доказ

    Припустимо, існує лише кінцева кількість простих чисел\(p_1, p_2, \ldots, p_n\). Розглянемо ціле.\[x = 1 + p_1 p_2 \cdots p_n. \nonumber\] Очевидно, що\(x\neq p_i\) для будь-якого\(i\). Оскільки\(p_1, p_2, \ldots, p_n\) вважаються єдиними простими числами, ціле число\(x\) має бути складене, отже, може бути враховано у добуток простих чисел. \(p_k\)Дозволяти бути одним з цих простих множників, так що\(x=p_kq\) для деякого цілого числа\(q\). Тоді\[\begin{array}{r c l} 1 &=& x-p_1 p_2 \cdots p_n \\ &=& p_kq-p_1 p_2 \cdots p_n \\ &=& p_k(q-p_1p_2\cdots p_{k-1} p_{k+1} \cdots p_n), \end{array} \nonumber\] що неможливо. Це протиріччя доводить, що простих чисел нескінченно багато.

    Деякі з простих чисел, перерахованих в Фундаментальній теоремі арифметики, можуть бути ідентичними. Якщо згрупувати однакові прості числа разом, то отримаємо канонічну факторизацію або факторизацію правої степені цілого числа.

    Теорема\(\PageIndex{3}\)

    Всі цілі числа\(n\geq 2\) можуть бути однозначно виражені у вигляді\(n = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}\) для деяких різних простих\(p_i\) і натуральних чисел\(e_i\).

    Як тільки ми знайдемо факторизацію двох цілих чисел, їх найбільший спільний дільник можна легко отримати.

    Приклад\(\PageIndex{1}\label{eg:FTA-01}\)

    З факторизацій\(246 = 2\cdot 3\cdot 41\) і зрозуміло\(426 = 2\cdot 3\cdot 79\), що\(\gcd(246,426) = 2\cdot3 = 6\).

    практичні вправи\(\PageIndex{1}\label{he:FTA-01}\)

    Знайдіть факторизації 153 та 732 та використовуйте їх для обчислення\(\gcd(153,732)\).

    Хоча множина простих чисел, які ділять два різних натуральних числа\(a\) і\(b\) можуть бути різними, ми могли б все ж записати обидва\(a\) і\(b\) як добуток степеней всіх простих чисел, що беруть участь. Наприклад, поєднуючи прості множники,\[12300 = 2^2\cdot 3\cdot 5^2\cdot 41, \quad\mbox{and}\quad 34128 = 2^4\cdot 3^3\cdot 79, \nonumber\] ми могли б записати їх так, як\[12300 = 2^2\cdot 3^1\cdot 5^2\cdot 41^1\cdot 79^0, \quad\mbox{and}\quad 34128 = 2^4\cdot 3^3\cdot 5^0\cdot 41^0\cdot 79^1. \nonumber\] випливає, що\[\gcd(12300,34128) = 2^2\cdot 3^1\cdot 5^0\cdot 41^0\cdot 79^0 = 12. \nonumber\] узагальнення є негайним.

    Теорема\(\PageIndex{4}\)

    Якщо\(a = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}\) і\(b = p_1^{f_1} p_2^{f_2} \cdots p_t^{f_t}\) для деяких окремих простих чисел\(p_i\), де\(e_i, f_i\geq0\) для кожного\(i\), то\(\gcd(a,b) = p_1^{\min(e_1,f_1)} p_2^{\min(e_2,f_2)} \cdots p_t^{\min(e_t,f_t)}\).

    У цій теоремі ми дозволяємо показникам дорівнювати нулю. У звичайній факторизації прайм-влада показники повинні бути позитивними.

    практичні вправи\(\PageIndex{2}\label{he:FTA-02}\)

    Обчислити\(\gcd(2^3\cdot5\cdot7\cdot11^2, 2^2\cdot3^2\cdot5^2\cdot7^2)\).

    Визначення: найменш поширене кратне

    Найменше спільне кратне цілих чисел\(a\) і\(b\), позначається\(\mathrm{ lcm }(a,b)\), є найменшим додатним спільним кратним обох\(a\) і\(b\).

    Теорема\(\PageIndex{5}\)

    Якщо\(a = p_1^{e_1} p_2^{e_2} \cdots p_t^{e_t}\) і\(b = p_1^{f_1} p_2^{f_2} \cdots p_t^{f_t}\) для деяких окремих простих чисел\(p_i\), де\(e_i, f_i\geq0\) для кожного\(i\), то\(\mathrm{ lcm }(a,b) = p_1^{\max(e_1,f_1)} p_2^{\max(e_2,f_2)} \cdots p_t^{\max(e_t,f_t)}\).

    практичні вправи\(\PageIndex{3}\label{he:FTA-03}\)

    Обчислити\(\mathrm{ lcm }(2^3\cdot5\cdot7\cdot11^2, 2^2\cdot3^2\cdot5^2\cdot7^2)\).

    Слідство\(\PageIndex{6}\)

    Для будь-яких натуральних чисел\(a\) і\(b\), у нас є\(ab = \gcd(a,b)\cdot \mathrm{ lcm }(a,b)\).

    Доказ

    Для кожного\(i\) одне з двох чисел\(e_i\) і\(f_i\) є мінімальним, а іншим є максимальним. Отже,\[e_i + f_i = \min(e_i,f_i) + \max(e_i,f_i), \nonumber\] з якого ми отримуємо\[p_i^{e_i} p_i^{f_i} = p_i^{e_i+f_i} = p_i^{\min(e_i,f_i)+\max(f_i,f_i)} = p_i^{\min(e_i,f_i)} p_i^{\max(e_i,f_i)}. \nonumber\] Отже,\(ab\) дорівнює добутку\(\gcd(a,b)\) і\(\mathrm{ lcm }(a,b)\).

    Приклад\(\PageIndex{1}\label{eg:FTA-02}\)

    З тих пір\(12300 = 2^2\cdot 3^1\cdot 5^2\cdot 41^1\cdot 79^0\)\(34128 = 2^4\cdot 3^3\cdot 5^0\cdot 41^0\cdot 79^1\), і, випливає\(\gcd(12300,34128)=12\), що\[\mathrm{ lcm }(12300,34128) = 2^4\cdot 3^3\cdot 5^2\cdot 41^1\cdot 79^1 = 34981200. \nonumber\] Ми бачили це, і ми маємо\(12\cdot 34981200 = 12300\cdot 34128\).

    практичні вправи\(\PageIndex{4}\label{he:FTA-04}\)

    Знаючи\(\gcd(246,426)=6\), що, як би ви обчислили значення\(\mathrm{ lcm }(246,426)\)?

    Приклад\(\PageIndex{3}\label{eg:FTA-03}\)

    Коли ми додаємо два дроби, ми спочатку беремо спільний знаменник, як у\[\frac{7}{8} + \frac{5}{12} = \frac{7}{8}\cdot\frac{3}{3} + \frac{5}{12}\cdot\frac{2}{2} = \frac{21+10}{24} = \frac{31}{24}. \nonumber\] Clear досить, найменш спільний знаменник точно найменш спільний кратний двом знаменникам.

    Приклад\(\PageIndex{4}\label{eg:FTA-04}\)

    Панель управління автомата має два сигнальних ліхтарі, один червоний і один синій. Червоне світло блимає раз в 10 секунд, а синє світло блимає раз в 14 секунд. При включенні машини обидва ліхтарі блимають одночасно. Через скільки секунд вони будуть блимати в один і той же час знову?

    Рішення

    Ця проблема ілюструє типове застосування найменш поширених множинних. Червоне світло блимає на 10, 20, 30,... секундах, тоді як синє світло блимає на 14, 28, 42,... секундах. Загалом, червоне світло блимає в\(t\) секундах, якщо\(t\) кратне 10, а синє світло блимає, коли\(t\) кратне 14. Тому обидва ліхтарі блимають разом,\(t\) коли кратні як 10, так і 14. Наступного разу це станеться через\(\mathrm{ lcm }(10,14)=70\) секунди.

    практичні вправи\(\PageIndex{5}\label{he:FTA-05}\)

    Дві комети подорожують по фіксованих орбітах навколо землі. Один з них повертається на Землю кожні 35 років, інший - кожні 42 роки. Якщо вони обидва з'являться в 2012 році, коли наступного разу вони повернуться на Землю в тому ж році?

    практичні вправи\(\PageIndex{6}\label{he:FTA-06}\)

    Задано відносно прості натуральні числа\(m\) і\(n\), які можливі значення\(\mathrm{ lcm }(4m-6n,6m+4n)\)?

    Приклад\(\PageIndex{5}\label{eg:FTA-05}\)

    Що\(2\mathbb{Z}\cap3\mathbb{Z}\) дорівнює?

    Рішення

    Припустимо\(x\in 2\mathbb{Z}\cap3\mathbb{Z}\), потім\(x\in2\mathbb{Z}\) і\(x\in3\mathbb{Z}\). Це означає\(x\), що кратне як 2, так і 3. Отже,\(x\) є кратним\(\mathrm{ lcm }(2,3)=6\), що означає\(x\in6\mathbb{Z}\). Тому,\(2\mathbb{Z}\cap3\mathbb{Z} \subseteq 6\mathbb{Z}\).

    Далі, припустимо\(x\in 6\mathbb{Z}\),\(x\) то кратна 6. Отже,\(x\) є кратним 2, а також кратним 3. Це означає\(x\in2\mathbb{Z}\), і\(x\in3\mathbb{Z}\). Як результат,\(x\in 2\mathbb{Z}\cap3\mathbb{Z}\). Тому,\(6\mathbb{Z} \subseteq 2\mathbb{Z}\cap3\mathbb{Z}\). Разом з\(2\mathbb{Z}\cap3\mathbb{Z} \subseteq 6\mathbb{Z}\), робимо висновок, що\(2\mathbb{Z}\cap3\mathbb{Z} = 6\mathbb{Z}\).

    практичні вправи\(\PageIndex{7}\label{he:FTA-07}\)

    Що\(4\mathbb{Z}\cap6\mathbb{Z}\) дорівнює?

    Резюме та огляд

    • Є нескінченно багато простих чисел.
    • Будь-яке натуральне число\(n>1\) може бути однозначно враховано у добуток простих степенів.
    • Прості числа можна розглядати як будівельні блоки (шляхом множення) всіх натуральних чисел, що перевищують одиницю.
    • Дано два натуральних числа\(a\) і\(b\), їх найменше спільне кратне позначається як\(\mathrm{ lcm }(a,b)\).
    • Для будь-яких натуральних чисел\(a\) і\(b\), у нас є\(ab = \gcd(a,b)\cdot\mathrm{ lcm }(a,b)\).

    Вправа\(\PageIndex{1}\label{ex:FTA-01}\)

    Знайти факторизацію цих цілих чисел на прості степені.

    1. 4725
    2. 9702
    3. 180625
    4. 166 2405

    Вправа\(\PageIndex{2}\label{ex:FTA-02}\)

    Знайдіть найменше спільне кратне кожній з наступних пар цілих чисел.

    1. 27, 81
    2. 24, 84
    3. 120, 615
    4. 412, 936
    5. 1380, 3020
    6. 1122, 3672

    Вправа\(\PageIndex{3}\label{ex:FTA-03}\)

    Річард дотримується дуже жорсткої рутини. Він замовляє піцу на обід кожні 10 днів, а вечеряє з батьками кожні 25 днів. Якщо він замовить піцу на обід і сьогодні вечеряє з батьками, коли він знову зробить обидва в той же день?

    Вправа\(\PageIndex{4}\label{ex:FTA-04}\)

    Обчислити\(\gcd(15\cdot50,25\cdot21)\), і\(\mathrm{ lcm }(15\cdot50,25\cdot21)\).

    Вправа\(\PageIndex{5}\label{ex:FTA-05}\)

    Що\(10\mathbb{Z}\cap15\mathbb{Z}\) дорівнює? Доведіть свою претензію.

    Вправа\(\PageIndex{6}\label{ex:FTA-06}\)

    \(n\)Дозволяти\(m\) і бути натуральними числами. Що\(m\mathbb{Z}\cap n\mathbb{Z}\) дорівнює? Доведіть свою претензію.

    Вправа\(\PageIndex{7}\label{ex:FTA-07}\)

    \(p\)Дозволяти бути непарним простим. Покажіть, що

    • \(p\)має форму\(4k+1\) або форму\(4k+3\) для деякого невід'ємного цілого числа\(k\).
    • \(p\)має форму\(6k+1\) або форму\(6k+5\) для деякого невід'ємного цілого числа\(k\).

    Вправа\(\PageIndex{8}\label{ex:FTA-08}\)

    Наведіть три приклади\(p\) непарного простого для кожної з наступних форм

    1. \(4k+1\)
    2. \(4k+3\)
    3. \(6k+1\)
    4. \(6k+5\)

    Вправа\(\PageIndex{9}\label{ex:FTA-09}\)

    Доведіть, що будь-який\(3n+1\) простий форми також форми\(6k+1\).

    Вправа\(\PageIndex{10}\label{ex:FTA-10}\)

    Доведіть, що якщо\(n\) натуральне число має вигляд\(3k+2\), то він має простий множник тієї ж форми.

    Підказка

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

    Вправа\(\PageIndex{11}\label{ex:FTA-11}\)

    Доведіть, що 5 є єдиним простим у формі\(n^2-4\).

    Підказка

    Розглянемо факторизацію\(n^2-4\).

    Вправа\(\PageIndex{12}\label{ex:FTA-12}\)

    Скористайтеся результатом «Будь-яке\(p\) непарне просте число має форму\(6k+1\) або форму\(6k+5\) для деякого невід'ємного цілого числа\(k\)», щоб довести наступні результати.

    • Якщо\(p\geq5\) є простим, то\(p^2+2\) є складовим.
    • Якщо\(p\geq q\geq5\) прості числа, то\(24\mid(p^2-q^2)\).