Прості числа. Нескінченність множини простих чисел. Основна теорема арифметики. Застосування канонічного розкладу чисел до знаходження НСД і НСК

Означення: натур. число а назив простим, якщо воно має тільки дільники самого себе і 1.

З озн. виплив. що 1 не є простим числом, а також, що 2 – єдине парне число.

Т. кожне натур. m або ділиться націло на просте р або взаємопросте з числом р.

(два числа a,b назив. взаємопростими, якщо їх НСД = 1).

числа a1, a2, a3 ………., an назив попарно простими, якщо б – я два числа із них взаємно прості.

Дов.

Розг. НСД (m, р). так як р просте число, то воно має лише два дільники – 1 або р. отже і найб.спіл. дільн. Чисел m, р буде 1 або р.

Т. найм. простий дільник натур. числа а>1 не перевищує .

Дов.

a=p*q, p>q

ap > p*q₂

a ≥ q₂

q≤ .

на практиці дана тоер. викор і для розкладу чисел на множ. і визнач. Того чи буде дане число простим.

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

Т. множина простих чисел нескінченна.

Дов.

Методом від супротивного. Припустимо, що множ.простих чис. скінченна. Вона містить р={р1, р2 …… рn }.

Побуд.число а = р1* р2* …… *рn+1.

або число а є просте, тоді ми отрим.суперечність з припущеним.

або число а складне, тобто його дільниками є не тільки «1» або «а», але й інші числа. Якщо а – складне, то воно обов‘язково ділиться на одне із простих чисел р1, р2 …… рn.

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

Впродовж всього р-ку матем., мат всіх країн намагалися встановити ф-лу,яка би вичерпувалв собою множ простих чисел.

До цих пір не встановлена така формула, хоча відома наприкл ф-ла Ейлера, яка при N=1,…..42 дає прості числа, а для інших значень складені.

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

Кожне натур.число N≥2 можна розкласти в добуток простих множників і цей розклад єдиний з точністю до порядку запису співмножників.

Дов.

Дов спочатку можл.розкладу ММІ

n=2, 2=2

n=k

n=k+1

Якщо k+1 просте чис.,то k+1= k+1

Якщо k+1 складене, то k+1= k1 *k2

k1 <k2

k2 ≤k

згідно п.2 б-я всяке чис. яке ≤k можна представити у вигляді добутку простих монж. Ми довели можл представ. > 2 у виді добутку простих чисел.

Дов єдиність від супротивного. Припустимо, що а можна представити двома різними способами:

а = р1* р2* …… *рr.

а = q1* q2* …… *qr,

причому. р1* р2* …… *рr., q1* q2* …… *qr, прості числа

r<S, тоді р1* р2* …… *рr = q1* q2* …… *qr,

ліва частина ділиться на р1, тоді і права частина ділиться на р. так як справа є добуток простих чис. то цей доб. Ділиться націло на р1, коли одне із, q1* q2* …… *qr ділиться націло на q1, тобто = р1

не обмежуючи загальності вваж.,що q1= р1

р2* р3* …… *рr. =, q2* q3* …… *qs, р2 = q2

р3* …… *рr­ = q3* …… *qs

1 = qr+1 ….. qs

qr+1 = 1

qs =1

отримали суперечність з припущеним.

Згідно основн. теор.арифм., кожне чис.a>1 можна єдиним чином представити у виді (1)

а = р1* …… *рr.

у представлені (1) деякі множин можуть повторюватися,тоді прир. Їх об‘єднати, як степінь простих чисел

а = p1k 1* p2k2 * ….. psks (2)

Означ. Представлення натур.числа а у виді (2) назив канонічним розкладом натур.числа.

Очевидно якщо (2) конон.розклад натур.чис., то кожний дільник матиме вид:

d = p1£1 * p2£2 * ….. ps£s

0≤£1 ≤ k1

…………….

0≤£s≤ ks

Якщо ми маємо два натур чис

а = p1k1 * p2k2 * ….. psks

b = q1k * q2k * ….. qlkl

то мають місце співвідношення:

d1 = q1ß1 * q2ß2 * ….. qlßl

0≤ß1 ≤ r1

…………….

0≤ ßl≤ rs/

НСД(a,b) – це добуток спільних множників в канон. розклад (r) (r`) в найм степенях.

НСК(a,b) - це добуток спільних множників в канон. розклад (r) (r`) в найб степенях.

Поиск по сайту: