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

Означення: натур. число а назив простим, якщо воно має тільки дільники самого себе і 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`) в найб степенях.

21. Порівняння їх основні властивості. Повна та зведена система лишків. Т.Ейлера та Ферма.

Натуральне число m>1 будемо називати модулем. Озн. Два цілі числа а,b порівнюються між собою якщо при діленні на n вони дають одну і ту ж саму остачу. З означення порівнянь випливають основні властивості:1) тоді і тільки тоді, коли - просте число. Т:2. .

Властивості:1.Два порівняння за одним і тим же модулем можна почастинно додати.

2.Наслідок.

3.Порівняння за одним і тим самим mod можна почастинно віднімати.

Доведення:

4.До обох частин порівняння можна додати одне й те ж саме додатнє число с.

5.З однієї частини порівняння можна переносити в другу частину порівняння з протилежним знаком.

6.До будь-якої частини рівняння можна додати кратне модуля.

7.Два порівняння можна почастинно перемножити.

8.Обидві частини порівняння і (modm) можна домножити на одне і те ж саме натуральне число к.

9.Якщо к спільний дільник чисел a,b,(modm) то обидві частини і mod можна поділити на дане число к.

Озн: Якщо з кожного класу лишків взяти по одному представнику, то одержана множина лишків називається повною системою лишків(ПСЛ). Числа класів називаються лишками. ПСННЛ={0,1,2,3,4,5,6}

Властивість: Теорема про ПСЛ: Якщо a,m взаємно прості НСД(a,m)=1 і b будь-яке ціле число,то якщо х пробігає ПСЛ, то ах+b також пробігає ПСЛ. Доведення: Нехай є ПСЛ за тоді

покажемо, що ця множина чисел утворює повну систему лишків. Ця система містить m чисел: покажемо що числа цієї множини не порівнюються між собою за (modm).Припустимо від супротивного: так як а взаємо прості то а це суперечить умові теореми.А значить наше припущення вірне.Множина лишків,які належать різним класам і які взаємо прості з (modm)називають зведеною системою лишків(ЗСЛ).Як правило ЗСЛ ємножина найменших невід’ємних лишків.Очевидно,що ЗСЛ за (modm)містить -лишків, -функйія Ейлера.

Якщо a,m прості і х пробігає ЗСЛ,то і ах також пробігає ЗСЛ.НСД(a,m)=1.

Покажемо, що ці числа не порівнюються між собою за (modm).Припустимо, що

Це суперечить означенню ЗСЛ.

Теорема Ейлера:Якщо am взаємно прості. .

Доведення: Розглянути ЗСЛ(modm)={ }тоді згідно теореми про ЗСЛ множина також буде зведеною системою лишків. . Очевидно, що лишок з одним із лишків .

Тоді

.Очевидно, що лишки попарно прості. А значить обидві частини останнього порівняння можна скоротити. .

Теорема Ферма:є частковим випадком теореми Ейлера,якщо m просте число;m=p;φ(p)=p-1.

.