1. Суміжні класи, та їх властивості. Теорема Лагранжа та наслідки

1. Суміжні класи, та їх властивості. Теорема Лагранжа та наслідки.

Нехай G – мультиплікативна група, Н – підгрупа групи G, введемо на моножині G бінарне відношення конгруентності за підгрупою H,

a,b є G (a

b (mod H)

b^-1 є H). Дане відношення очевидно є відношенням еквівалентності, оскільки воно рефлексивне, симетричне і транзетивне.

1. Рефлексивність a

a^-1=e є H → a

a (mod H)

2. Симетричність a

b (mod H) → a

b^-1 є H → (a

b^-1)=b

a^-1 є H → b

a (mod H)

3. Транзетивність a

(mod H) b

c (mod H) → a

b^-1, b

c^-1 є H → a

b^-1 b

c^-1=a

c^-1 є H → a

c (mod H)

Як відомо будь-яке відношення еквівалентності проводить розбиття множини на якій воно задано на класи еквівалентності. Надалі класи еквівалентності групи G за підгрупою H називатимемо правими суміжніми класами групи G за підгрупою H.

Означення: порядком мультиплікативної групи називається к-сть елементів цієї групи.

Теорема (Лагранжа): порядок довільної підгрупи скінченої групи є дільником порядку групи.
3. Фактор-група

Нехай G мультиплікативна група А, В

G. А

В={a

b | a є А

b є B}.Твердження: Нехай G/H множина суміжних класів групи G по нормальному дільнику H. Тоді добуток 2-х суміжних класів є також суміжним класом із мн. G/H. Причому Ha

Hb=Hab. Доведемо рівність Ha

Hb=Hab. Нехай ha і h₁b – довільні елементи відповідних класів Ha і Hb. Так як ha

h₁b=h

h₁a^-1)ab=(h

h₂)ab є Hab. Оскільки h₂=ah₁a^-1 є H, так як H

G, отже Ha

Hab. Нехай h(ab) є Hab – hab=(ha)(e

b) є Ha

Hb, Hab

Hb, таким чином Ha

Hb=Hab, а це означає, що визначена операція множення суміжних класів групи G за нормальним дільником H є алгебраїчною на множині G/H.

Теорема: Мн. cуміжних класів G/Hразом з визначеною на ній бінарною алгебрагічною операцією множення суміжних класів Ha

Hb=Habутв. мультиплікативну групу. Доведення: ми показали, що множення є бінарною алгебраїчною операцією на G/H задається правилом Ha

Hb=Hab,

ab є G, перевіримо аксіоми групи.

Нехай a,b,c – довільні елементи групи G, оскільки (aH

bH)cH=(abH)(cH)=abcH, aH(bH

cH)=aH(bc)H=abcH, то (aH

bH)cH=aH(bH

cH), отже асоціативність виконується. Одиничним елеентом є сама підгрупа H=He, Ha

He=H(ae)=Ha, або He

Ha=Ha=H(ea)=Ha. Кожний елемент a групи G має обернений a^-1. Оберненим до Ha буде Ha^-1. Оскільки Ha

Ha^-1=Haa^-1=He=H або Ha^-1 Ha=Ha^-1a=He=H.

Означення:Алгебра називається фактор-групою групи G за підгрупою H.

34. Ознака Паскаля

Нехай потрібно визначити ознаку подільності цілого числа a натуральне число n. Будемо співставляти число f(a) з таким розрахунком, щоб f(a) було менше, або значно менше a, і числа a і f(a) однозначно поділялись на m, або не поділялись.

Для визначення ознак подільності скористаємося функцією f(a), яка була запропонована Паскалем і носить назву функції Паскаля.

Число a в десятковій системі числення має вигляд: a=(a_na_n_-1…a₁a₀)₁₀=a_n10ⁿ+a_n_-110ⁿ^-1+…+a₁10¹+a₀, де a_n≠0 і 0≤a_i≤9.

Нехай r_i найменший лишок за абсолютною величиною, який відповідає класу 10ⁱ (modm), тобто r_i – це або остача при діленні 10ⁱ на m, або число, яке одержиться, якщо від цієї остачі відняти модуль m (з цих двох чисел треба вибрати менше за абсолютною величиною).

Співставивши числу f(a)=a_nr_n+a_n_-1r_n_-1+…+a₁r₁+a₀ ми одержимо функцію Паскаля f(a) для числа a. За властивістю 6 числових конгруенцій a

f(a)(modm), а тому a

mf(a)

m, а тому заміняючиa на f(a) ми можемовстановитиознакиподільності для різнихm.

5. Основна теорема про гомоморфізм груп

Лема: Якщо f – гомоморфізм групи G в групу G`, H= Ker f – ядро цього гомоморфізму, то для довільних a,b є G з умови f(a)=f(b) слідує Ha=Hb.

Доведення: f(ab^-1)=f(a)f^-1(b)=f(a)f^-1(a)=e`. ab^-1 є H = Ker f, a

b (mod H), звідки Ha=Hb.

Теорема: якщо f – гомоморфізм групи G на групу G`, H=Ker f – ядро гомоморфізму f, то фактор-група G/H ізоморфна групі G`.

Доведення: фактор-групу G/H складають суміжні класи групи G за нормальним дільником H. Задамо відображення φ:G/H→G`, таким чином φ(Ha)=f(a),

a є G. Оскільки Н – ядро гомоморфізму, то кожному суміжному класу На ставитиметься у відповідність єдиний елемент групи G`, який не залежатиме від вибору представника класу. Покажемо, що φ – гомоморфізм. Нехай На і Нb – два довільні суміжні класи з G/H, оскільки φ(Ha

Hb)=φ(Hab)=f(ab)=f(a)

f(b)=φ(Ha)

φ(Hb), то φ – гомоморфізм G/H в G`.

Покажемо, що відображення φ є відображенням на групу G`. Нехай a` є G`, оскільки f – гомоморфізм на G`, то існує a є G, таке, що f(a)=a`.

Отже, Ha – прообраз a` при відображенні φ. Звідки φ – сюр’єктивне відображення G/H на G`. На завершення доведення покажемо, що φ також ін’єктивне відображення. Припустимо, що φ(Ha)=φ(Hb). Тоді скориставшись лемою маємо Ha=Hb, так як попередня рівність рівносильна рівності f(a)=f(b).

32. Індекси за простим модулем і їх властивості.

За допомогою первісних коренів можна побудувати теорію, що нагадує теорію логарифмів. Нехай ε – первісний корінь за модулем p₁, тоді числа ε, ε², … ε^p^-1 утворюють ЗСЛ за модулем p, а тому будь-яке ціле число, яке не поділяється на p буде конгруентне за модулем p деякому із чисОл εⁱ. Число i називається індексом a за модулем p при основі ε, і позначається ind_εa або inda.

Означення: індексом числа aназивається таке ціле число i, для якого a

εⁱ(modp).

Аналогічно як з означення логарифма випливає основна логарифмічна тотожність, так і з означення індекса випливає конгруенція

(modp).

Із властивості 3 порядку числа за даним модулем слідує, що з умови a

b(modp) слідує ind_εa

ind_εb(modp-1). Оскільки p_pε=p-1.

Властивості індексів:

Нехай ε – первісний корінь за модулем p, цілі числа aі b не діляться на p, тоді мають місце такі властивості:

1.indab

ind a + ind b (mod p-1).

Доведення: ab

(modp). Проіндексувавши при основі ε дістанемо indab

inda + indb (modp-1).

2.ind aⁿn ind a (mod p-1), n є N.

Доведення: a

(mod), aⁿ(mod p), а далі індексуємо при основі ε і отримуємо: indaⁿn ind a(mod p-1)

3.Якщо a

b, то ind

ind a - ind b (mod p-1). Доведення аналогічне до властивості 1.

4.ind_εε

1(modp-1).

5.ind_ε1

0(modp-1)
30. Порядок числа і класу лишків та його властивості.

Означення: порядком числа aза модулем m називається таке найменше натуральне d, для якого a^d(modm).

З властивостей числових конгруенцій слідує, що конгруентні за модулем mчисла мають один і той же порядок. a

b(modm)→a^db^d(modm). Отже, можна говорити про порядок класу лишків за модулем m, як порядок будь-якого лишку з цього класу.

Властивості порядку числа за модулем:

1) якщо P_m(a)=d, то числа a, a², …,a^d є попарно неконгруентні за модулем m. Нехай 1≤kk

(modm), так як (a, m)=1, то скоротивши на a^k дістанемо

1(modm), де d>

-k≥1. Існування

-kсуперечить тому, що d – порядок a за модулемm, отже a^k (modm). Властивість доведена.

2) Якщо P_m(a)=d, то aⁿ1(modm) тоді і тільки тоді, коли n

d.

Доведення: нехай n

d, тоді n=dq. aⁿa^dq(a^d)^q1^q1 (modm), звідки aⁿ1 (modm).

Навпаки, нехай aⁿ1 (modm), покажемо, що n

d. Спочатку розділимо n на dз остачею, n=dq+r, 0≤rn

(modm) одержуємо (a^d)^qa^r1(modm), звідки a^r1(modm). Так як dнайменше натуральне число для якого a^d1(modm),то r=0, а тому n=dq₁ → n

d.

Наслідок: якщо P_m(a)=d, то φ(m)

d.

Доведення: за теоремою Ейлера a^φ⁽^m⁾1(modm), за властивістю 2 φ(m)

d.

3)Якщо P_m(a)=d, то a^sa^t (mod m) тоді і тільки тоді, коли s

t (mod d).

Доведення: a^sa^t (mod m)a^s-t1(mod m) (s-t)

d s

t(mod d).
7. Циклічні групи

Нехай G – мультиплікативна група.

Означення: Група G називається циклічною, якщо кожний її елемент є степенем одного і того ж елемента цієї групи, який називається твірним елементом групи.

Теорема: Довільна підгрупа циклічної групи є циклічною.

Доведення: Нехай G – циклічна група з твірними елементами a. H – підгрупа групи G. Покажемо, що H – також циклічна. Якщо H={e} – одинична підгрупа, то очевидно вона циклічна. Нехай H≠{e}. Так як всі елементи групи G мають вигляд a^k, k є Z, то і підгрупа H складається з таких елементів. Якщо a^k є H, то і обернений елемент a^-^k=H. А тому можна вважати k>0, тобто, що підгрупа H, яка не є одиничною завжди містить додатній степінь елемента a. Нехай s – найменше натуральне число, для якого a^s є H. Покажемо, що a^s – твірний елемент H.

Нехай a^k є H, розділимо k на s з остачею, тоді k=sq+r, де 0

rk, a^s є H дістанемо a^k(a^s)^-^q=a^r є H, де 0k=(a^s)^q, тобто a^s – твірний елемент групи H.

Наслідок: довільна група простого порядку є циклічною.

28. Конгруенції вищих степенів за простим модулем.Теорема про кіл-ть розв’язків конгоруенції степеня n.

Розглянемо алгебраїчну конгруенцію степеня n за простим модулем p.

a_nx^k+a_n-1x^n-1+…+a₁x+a₀0(mod p), (1), де a_n, a_n-1, …, a₁, a₀є Z, a_nне поділяється на p, p – просте число.