Тексти лекцій

3
Зміст Вступ. 5
Розділ I. ТЕОРІЯ ПОДІЛЬНОСТІ В КІЛЬЦІ ЦІЛИХ ЧИСЕЛ ..................................................................... Тема 1. Відношення подільності, його властивості .......................................................................... 6
1. Теорема про ділення з остачею ......................................................................................................... 6
2.
Найбільший спільний дільник (НСД) двох чисел і алгоритм Евкліда. Властивості НСД двох чисел .......................................................................................................................................................... 8
3.
Найбільший спільний дільник кількох чисел ..................................................................................11
4.
Взаємно прості числа Тема 2. Системні числа ........................................................................................................................16
1. Позиційні і непозиційні системи числення. Суть позиційного принципу запису чисел ............16
2.
Арифметичні операції над системними числами ...........................................................................19
3.
Переведення цілих чисел з однієї позиційної системи числення в іншу.....................................20
Тема 3. Прості і складені числа ...........................................................................................................23
1.
Прості числа.
Нескінченність множини простих чисел. Решето Ератосфена .....................................................23
3. Основна теорема арифметики ..........................................................................................................24
4.
Канонічний розклад складеного числа ............................................................................................25
5.
Числові функції. Число і сума натуральних дільників...................................................................27
6. Прості числа в арифметичних прогресіях Тема 4. Ланцюгові дроби ......................................................................................................................30
1.
Запис раціональних чисел у вигляді скінченних ланцюгових дробів .........................................30
2.
Запис ірраціональних чисел у вигляді нескінченних ланцюгових дробів Тема 5. Підхідні дроби ланцюгового дробу .......................................................................................36
1. Правило утворення підхідних дробів ...............................................................................................36
2.
Властивості підхідних дробів ............................................................................................................38
3.
Розв’язування в цілих числах лінійного рівняння з двома невідомими .....................................41
Розділ II. ГРУПИ І КІЛЬЦЯ Тема 6. Групи та підгрупи. Циклічні групи і підгрупи. Розклад групи за підгрупою .....................44
1. Групи .....................................................................................................................................................44
2. Підгрупи ................................................................................................................................................45
3. Циклічні групи і підгрупи ....................................................................................................................45
4. Суміжні класи Тема 7. Нормальні дільники групи. Фактор-групи. Гомоморфізми груп ........................................50
1. Нормальні дільники групи .................................................................................................................50
2. Фактор-групи........................................................................................................................................52
3. Гомоморфізми груп Тема 8. Кільце. Область цілісності. Ідеали кільця. Гомоморфізми кілець ....................................56
1. Елементарні відомості про кільця. Область цілісності. Поле часток ..........................................56
2. Ідеали кільця та операції над ними. Конгруенції і класи лишків за ідеалом. Фактор-кільце ...................................................................61
4. Гомоморфізми та ізоморфізми кілець. Теорема про гомоморфізми кілець Тема 9. Кільця головних ідеалів та евклідові кільця. Характеристика кільця ..............................66
1. Подільність в області цілісності .......................................................................................................66
2. Кільця головних ідеалів .....................................................................................................................68
3. Евклідові кільця ..................................................................................................................................70
4. Характеристика кільця з одиницею ..................................................................................................71
Розділ III. ТЕОРІЯ КОНГРУЕНЦІЙ Тема 10. Конгруенції в кільці цілих чисел та їхні властивості ........................................................73
1. Властивості конгруенцій при незмінному модулі ...........................................................................73
2. Властивості конгруенцій за різними модулями ..............................................................................76
3. Класи лишків за даним модулем. Фактор-кільце класів лишків Тема 11. Повна і зведена системи лишків. Функція Ейлера ............................................................80
1. Повна система лишків ........................................................................................................................80
2.
Зведена система лишків. Функція Ейлера .......................................................................................80
3. Властивості функції Ейлера ..............................................................................................................82
4. Теореми Ейлера і Ферма Тема 12. Лінійні конгруенції з одним невідомим. Конгруенції го степеня ..................................86
1. Розв’язок конгруенції. Рівносильні конгруенції. Число розв’язків конгруенції го степеня з одним невідомим ....................................................................................................................................86

4
2. Способи розв'язування конгруенцій го степеня ..........................................................................88
3. Конгруенції вищих степенів з одним невідомим .............................................................................89
4. Число розв’язків конгруенції го степеня.......................................................................................91
Тема 13. Квадратичні лишки і нелишки ......................................................................................93
1. Лишки і нелишки ..................................................................................................................................93
2. Критерій Ейлера ..................................................................................................................................94
3. Символ Лежандра Тема 14. Числа і класи чисел, які належать до даного показника ..................................................97
1. Показники за модулем ........................................................................................................................97
2. Властивості показників за модулем .................................................................................................98
3. Первісні корені ....................................................................................................................................99
4. Індекси за простим модулем ...........................................................................................................100
5. Основні властивості індексів Тема 15. Деякі арифметичні застосування теорії конгруенцій .....................................................103
1. Виведення ознак подільності ..........................................................................................................103
2. Визначення довжини періоду при перетворенні звичайного дробу в десятковий ..................105
Література ..............................................................................................................................................108
Предметний покажчик .........................................................................................................................109

6
Розділ I. ТЕОРІЯ ПОДІЛЬНОСТІ В КІЛЬЦІ ЦІЛИХ ЧИСЕЛ Тема 1. Відношення подільності, його властивості
1. Теорема про ділення з остачею
Відомо, що множина цілих чисел


,...
2
,
1
,
0
,
1
,
2
...,



Z
з введеними в ній операціями додавання і множення утворює кільце, тобто таку алгебраїчну структуру, для якої виконуються умови:
1) вона є абелевою групою відносно додавання;
2) операція множення асоціативна;
3) операція множення дистрибутивна справа і зліва відносно додавання.
Це кільце називається кільцем цілих чисел, причому воно є комутативним кільцем, оскільки операція множення цілих чисел комутативна. У цьому кільці, як і в будь-якому іншому, здійсненна операція віднімання. Щодо операції ділення, то вона не завжди здійсненна в Z, тобто існують цілі числа, частка яких не є цілим числом. Тому перейдемо до розгляду питання про подільність цілих чисел.
Означення. Якщо для цілих чисел а і b в кільці цілих чисел Z існує таке ціле число q, щ то кажуть, що а ділиться на b»або«b ділить а»і пишуть відповідно
a
b
b
a
/
,

. Число а при цьому називають кратнимчисла b, b –
дільником числа а, а q – часткою.
Зрозуміло, якщо то число q також є дільником числа а.
Якщо в кільці Z не існує числа q такого, що то кажуть, що а не ділиться на b»або«b не ділить а. З означення випливають такі властивості подільності цілих чисел.
1.
a
Z
a

0


, бо
0 0


a
2.
)
1
(
1
)
(











a
a
a
a
a
a
Z
a
, бо
)
1
(
)
(
,
1






a
a
a
a
3.
)
(
)
(
)
(
)
(
b
a
b
a
b
a
b
a
Z
a













, бо


bq
a
q
b
a
q
b
a
q
b
a
)
(
)
(
)
(
)
(
)
)(
(












4.
c
a
c
b
b
a
Z
c
b
a







,
,
, бо




2 1
cq
b
bq
a
c
a
q
q
c
q
cq
bq
a






)
(
)
(
1 2
1 2
1 5.
c
b
a
c
b
a
c
b
c
a
Z
c
b
a




)
(
)
(
,
,







, бо




2 1
cq
b
cq
a
c
b
a
q
q
c
b
a
q
q
c
b
a

)
(
)
(
)
(
2 1
2 1










6.
b
ac
b
a
Z
c
b
a





,
,
, бо
)
(
)
(
qc
b
c
bq
ac
bq
a




7.






c
a
c
a
c
a
Z
b
a
b
a
b
a
n
n
n



,
,...,
,
,
,
2 1
2 2
1 1
c
b
a
b
a
b
a
n
n

)
(
2 2
1 1




(це випливає з властивостей 5,6).
8.
b
a
a
b
b
a
Z
b
a








,
Важливу роль у теорії подільності цілихчисел відіграє така теорема

7 Теорема 1 (про ділення цілих чисел з остачею). Які б не були ціле число а і натуральне число b, завжди існує єдина пара цілих чисел q і r така, що
,
r
bq
a


(1)
0
b
r


(2) Число q називають неповною часткою, r – остачею. Доведен н я. Доведемо спочатку, що числа q і r, які задовольняють умови (1) і (2), існують.
Якщо ціле число а ділиться на натуральне число b, тобто
bc
a

, де с – деяке ціле число, то числа
c
q

і
0

r
задовольняють умови (1) і (2).
Припустимо, що число а не ділиться на b. Тоді можливі такі два випадки:
2
;
1
b
a
b
a


Розглянемо кожен з цих випадків.
1. Нехай
b
a

. Якщо при цьому
0

a
, то з рівності
a
b
a



0
випливає, що числа
a
r
q


,
0
задовольняють умови теореми. Якщо ж
0

a
, то і тому з рівності
)
(
)
1
(
b
a
b
a




випливає, що умови теореми задовольняють числа
b
a
r
q




,
1
.
Отже, в першому випадку завжди існує пара чисел q і r, яказадовольняє умови (1) і (2).
2. Нехай тепер
b
a

. Якщо при цьому
0

a
, то з рівності
)
(
1
b
a
b
a




випливає, що існують ціле число
1

q
і натуральне число
b
a
r


, такі, що
r
bq
a


Якщо ж
0

a
, то
0
)
(



a
a
b
(оскільки а не ділиться на
N
b

, то
1

b
і
0 1


b
, крім того,
0


a
, тому
0
)
1
)(
(



b
a
, тобто
0
)
(



a
a
b
) і зрівності
]
)
(
[
a
a
b
a
b
a





випливає, що рівність (1) справджується для цілого числа і натурального числа
a
a
b
r



)
(
Отже, у другому випадку завжди існують ціле число q і натуральне число r, які задовольняють умову (1).
Нехай М – множина всіх тих і тільки тих натуральних чисел r, для кожного з яких при належному виборі цілого числа q справджується рівність (1). За принципом найменшого числа, у множині натуральних чисел М є найменше число. Нехай цим найменшим числом є
1
r
. Тоді
1 1
r
bq
a


, де
1
r
– деяке натуральне число. Покажемо, що
b
r

1
. Справді, припустимо, що
b
r

1
. Тоді
2 1
r
b
r


, де
2
r
– деяке натуральне число, і
2 1
2 1
1 1
)
1
(
r
q
b
r
b
bq
r
bq
a








,тобто
2 1
)
1
(
r
q
b
a



, причому
1 2
r
r

. Отже, числа
1 1


q
q
і
2
r
r

задовольняють умову (1) і тому
M
r

2
,чого не може бути, оскільки
1
r
– найменше з чисел множини М. Якщо припустити, що то
)
1
(
1 1




q
b
b
bq
a
, тобто а ділиться на а це суперечить умові. Тому
b
r

1
Отже, і в другому випадку існує пара чисел q і r, яказадовольняє умови теореми. Таким чином, в усіх можливих випадках існує пара чисел q і r,така, що
b
r
r
bq
a




0
,