Основна теорема арифметики цілих невід’ємних чисел.

5. Основну теорему арифметики називають також теоремою про існування та єдиність розкладу будь-якого натурального числа на добуток простих множників. Ця теорема використовувалась ще у стародавній Греції, але була сформульована і доведена видатним німецьким математиком К.Гауссом у 1801 році.

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

Доведення: доведення складається з двох частин. У першій частині доведемо існування такого розкладу. Якщо аєN і a>1, то можливі два випадки : а) число а – просте, тоді розклад існує; б) число а – складене, тоді воно має найменший простий дільник. Нехай це буде число р₁. Виходячи із цього, маємо ар₁ і а=р₁b, де bєN, причому число 1<р₁< b.

Число b може бути або простим, або складеним. Якщо число b – просте, то ми вже можемо представити число а у вигляді добутку двох простих чисел рb, тобто розклад існує. Якщо b – складене число, то воно має простий дільник. Нехай це буде число р₂. Виходячи із цього, маємо ар₂ і а=р₁р₂с, де сєN, причому число 1<р₂<с. Отже, а=р₁·р₂·с. Знову число с може бути або простим, або складеним. Якщо число с – просте, то число а буде представлятися у вигляді добутку трьох простих чисел. Якщо число c – складене, то ми одержимо ще один простий дільник р₃. Оскільки с< b<а, то цей процес завжди буде закінчуватися, а тому завжди буде існувати розклад числа а у вигляді добутку простих множників (І).

Не виключеним є випадок, коли деякий із множників в розкладі (1) повторюється, а тому в загальному випадку розклад числа на прості множники записують так: (ІІ). Розклад (ІІ) називається канонічним розкладом натурального числа а у добуток простих множників. В цьому розкладі р₁, р₂, р₃,...,р_k – прості множники, розміщені в порядку зростання; a₁, a₂, a₃,...,a_k– це натуральні числа, які показують, скільки разів повторюється той чи інший множник. Існування доведено.

У другій частині доведемо єдиність такого розкладу методом від супротивного, припустивши, що існує два різних розклади у вигляді (І), тобто а=р₁·р₂·р₃·…·р_к (ІІ) і а=q₁·q₂·q₃·…·q_n (III). Врахуємо, що р₁<р₂<р₃<…<р_к і q₁<q₂<q₃<…<q_n. У даних розкладах р_і і q_і – різні, але серед них будуть однакові. Для визначеності припустимо, що p₁¹q₁ i p₁<q₁.

Утворимо нове число b=p₁·q₂·q₃·…·q_n (IV). Легко бачити, що число а в записі (1) ділиться націло на p₁. Оскільки , то . Використовуючи записи (III) і (IV), винесемо добуток q₂·q₃·…·q_n за дужки: (a-b)=(q₁–p₁)·q₂·q₃·...·q_n. Ми показали, що вираз . Оскільки р₁ - просте число, то вираз ((q₁-p₁) q₂· q₃· q_n)p₁. Числа q₂, q_3,…q_n - прості і жодне із них не може ділитися на р₁. Тоді на p₁ повинна ділитися різниця (q₁–p₁)р₁. Разом з тим, оскільки р₁р₁, то , бо p₁¹q₁ і ці числа прості. Отже, для того, щоб (q₁–p₁)р₁ потрібно, щоб q₁-p₁=0, тоді q₁=p₁. Ми прийшли до суперечності із вибором p₁ і q₁. Ця суперечність говорить, що наше припущення про неєдиність розкладу було хибним. Отже, якщо розклад існує, то він єдиний. Теорема доведена повністю.

Доведена теорема є теоретичною основою представлення будь-якого натурального числа у вигляді добутку простих множників. Покажемо це на прикладі такої вправи: „Представити число 1224 у канонічному розкладі, тобто розкласти в добуток простих множників”.

Розв’язання:

6. Дільники і кратні. Спільні дільники і спільні кратні. Найбільший спільний дільник (НСД) і найменше спільне кратне (НСК), їх властивості.

6.Розглянемо два натуральних числа а та b. Якщо аb, то говорять, що а кратне b.

Означення: якщо аb, то число а називається кратним до числа b.

Із означення відношення подільності відомо, що із аbÛa=b·c. Якщо записати за допомогою характеристичної властивості множину чисел, кратних числу а, то будемо мати множину {a, 2a, 3a, … na…}. У множині чисел, кратних даному числу а є найменше число і немає найбільшого. За допомогою терміна “кратне” задається відношення подільності. Нехай задано множини чисел, кратних числу 3 і числу 5, тобто А={3,6,9,…3n,…} і B={5,10,15,…5n,…}. Утворимо перетин цих множин AÇB={15,30,45,…15n,…}. Множина AÇB задає нам спільні кратні чисел 3 і 5.

Означення: Будь-яке число, кратне числам а₁, а_2, а₃,…,а_n називається спільним кратним цих чисел.

Означення: найменше із спільних кратних чисел а₁, а_2, а₃,…а_k називається найменшим спільним кратним цих чисел.

Найменше спільне кратне прийнято позначати так: НСК(а₁, а₂, а₃,…а_k) або К(а₁, а_2, а₃,…а_k). Розглянемо властивості НСК, сформулювавши відповідні теореми для випадку двох чисел.

Властивість 1: кожне спільне кратне даних чисел ділиться на їх найменше спільне кратне.

Доведення: для спрощення викладок доведення теореми проведемо для випадку двох чисел. Нехай НСК(a,b)=k і CK(a,b)=d. Доведемо, що dk. Доведення проведемо методом від супротивного, припустивши, що , тобто, згідно означення операції ділення з остачею виконуються умови: d=kq+r і 0£r<k. Звідси r=d-kq. Оскільки d є спільним кратним (СК) чисел a і b, то . Оскільки k=НСК(a,b), то . Оскільки r<k, a£ k, то r – ділиться на число, більше, ніж воно саме, тобто число r є спільним кратним чисел a і b. Отже, СК(a,b)=r. А це можливо тоді, коли d–k·q=0, r=0, а це суперечить припущенню, що . Отже, припущення хибне і теорема доведена.

Властивість 2: якщо НСК(a,b)=k, то для будь-якого сÎN НСК(ac,bc)=ck.

Ця теорема говорить, що будь-який спільний множник можна виносити за знак НСК. Ввівши в попередніх пунктах означення дільника даного числа, ми з’ясували, що кількість дільників є завжди скінченною, найменшим дільником будь-якого числа є 1, а відношення „число b є дільником числа а” є оберненим до відношення „число а кратне числу b”.

Означення: всяке число, на яке ділиться кожне із чисел а₁, а₂, а₃…а_к називається спільним дільником цих чисел.

Означення найбільший із спільних дільників чисел а₁,а₂,а₃…а_к називається найбільшим спільним дільником чисел а₁, а₂, а₃…а_к і позначається НСД(а₁,а₂,а₃…а_к) або Д(а₁,а₂,а₃…а_к).

Означення: числа а₁, а₂, а₃…а_к називаються взаємно простими, якщо їх найбільший спільний дільник дорівнює 1. .

Властивість 1: якщо , то НСК(a,b)=a, а НСД(a,b)=b.

Доведення: за умовою і , тобто СД(a,b)=b, оскільки a>b, то НСД(a,b)=b. За умовою , то число а є спільним кратним для чисел a і b. Оскільки a>b, то а=НСК(а, b). Теорема доведена.

Властивість 2: будь-який спільний дільник даних чисел є дільником їх спільного дільника.

Властивість 3: спільні дільники даних чисел можна виносити, як за знак найменшого спільного кратного, так і за знак найбільшого спільного дільника.

Властивість 4: найменше спільне кратне даних чисел дорівнює добутку цих чисел, поділеному на найбільший спільний дільник цих чисел, тобто: .

Справедливість властивостей 2-4 приймемо без доведення.