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

Теорія чисел або вища арифметика - розділ математики, що вивчає цілі числа та подібні об'єкти.

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

Теоретично чисел розглядаються як натуральні числа, а й безліч всіх цілих чисел, безліч раціональних чисел, безліч алгебраїчних чисел. Для сучасної теорії чисел характерне застосування різноманітних методівдосліджень. У сучасній теорії чисел широко користуються методами математичного аналізу.

Сучасну теоріючисел можна розбити на такі розділи:

1) Елементарна теорія чисел. До цього розділу відносять питання теорії чисел, що є безпосереднім розвиткомтеорії ділимості та питання про представність чисел в певній формі. Більше загальною є завдання розв'язання систем діофантових рівнянь, тобто рівнянь, у яких значення невідомих мають бути обов'язково цілими числами.

2) Алгебраїчна теоріячисел. До цього розділу відносять питання, пов'язані з вивченням різних класів чисел алгебри.

3) Діофантові наближення. До цього розділу належать питання, пов'язані з вивченням наближення дійсних чисел раціональними дробами. До діофантових наближень примикають тісно пов'язані з тим самим колом ідей питання вивчення арифметичної природи різних класів чисел.

4) Аналітична теорія чисел. До цього розділу відносять питання теорії чисел, вивчення яких доводиться застосовувати методи математичного аналізу.

Основні поняття:

1) Делімість - одне з основних понять арифметики та теорії чисел, пов'язане з операцією поділу. З погляду теорії множин, ділимість цілих чисел є ставленням, визначеним на багатьох цілих чисел.

Якщо деякого цілого числа a і цілого числа b існує таке ціле число q, що bq = a, то кажуть, що число a ділиться націло на b або, що b ділить a. При цьому число b називається дільником числа a, поділеним a буде кратним числа b, а число q називається приватним від поділу a на b.

2) Просте число? - це натуральне число, яке має рівно два різні натуральних дільника: одиницю та самого себе. Решта числа, крім одиниці, називаються складовими.

3) Досконале число? (ін.-грец. ἀριθμὸς τέλειος) - натуральне число, рівну сумівсіх своїх власних дільників (тобто всіх позитивних дільників, відмінних від самого? числа).

Перше досконале число – 6 (1 + 2 + 3 = 6), наступне – 28 (1 + 2 + 4 + 7 + 14 = 28). У міру того, як натуральні числа зростають, досконалі числазустрічаються все рідше.

4) Найбільшим загальним дільником (НОД) для двох цілих чисел m і n називається найбільший із їхніх спільних дільників. Приклад: для чисел 70 та 105 найбільший спільний дільникдорівнює 35.

Найбільший спільний дільник існує і однозначно визначений, якщо хоча б одне із чисел m або n не нуль.

5) Найменше загальне кратне (НОК) двох цілих чисел m та n – це найменше натуральне число, яке ділиться на m та n.

6) Числа m і n називаються взаємно-простими, якщо вони немає спільних дільників, крім одиниці. Для таких чисел НОД(m,n) = 1. Назад, якщо НОД(m,n) = 1, то числа взаємно прості.

7) Алгоритм Евкліда - алгоритм для знаходження найбільшого загального дільника двох цілих чисел або найбільшої загальної міри двох однорідних величин.

Ви також можете знайти цікаву інформацію в науковому пошуковику Otvety.Online. Скористайтеся формою пошуку:

Ще на тему №17. Основні поняття теорії чисел.

Теорія чисел - розділ математики, у якому вивчаються властивості чисел.

Основний об'єкт теорії чисел – натуральні числа (див. Число). Головна їхня властивість, яку розглядає теорія чисел, це подільність. Перше коло завдань теорії чисел – розкладання чисел на множники. Основними «цеглинами» у такому розкладі є прості числа, тобто. числа, що діляться тільки на 1 і на себе; 2, 3, 5, 7, 11, 13, 17, 19, 23, 29 - ось перші десять простих чисел(число 1 не належать до простих). Чудова теорема, звана основна теорема арифметики, говорить: всяке натуральне число розкладається на прості множники, причому єдиним способом(З точністю до порядку їх розташування). Розклавши два числа на прості множники, нескладно визначити, чи ділиться одне з них на інше чи ні. Але досі буває важко з'ясувати, чи є це велике числопростим, тобто. чи ділиться воно на якесь інше число, крім себе та одиниці.

З розкладанням чисел на прості множники пов'язаний ряд арифметичних функцій. Зазначимо деякі з них. φ(n) - функція Ейлера - кількість чисел від 1 до n, взаємно простих з числом n (тобто не мають n спільних множників, крім одиниці); α(n) кількість дільників числа n, т(п)-сума всіх дільників числа n, π(n) – функція Чебишева – кількість простих чисел, що не перевищують n. За допомогою цих функцій виражаються багато властивостей натуральних чисел. Теорема Евкліда стверджує, що простих чисел дуже багато. Це означає, що π(n)→∞ у разі зростання числа n. Вдалося з'ясувати, як швидко функція π(n) прагне нескінченності. Виявилося, що приблизно так само, як функція

Ця теорема зветься асимптотичного закону розподілу простих чисел. Вона була сформульована і в суттєвій частині доведена П. Л. Чебишевим (1849), а повністю доведена лише через 50 років.

p align="justify"> Асимптотичний закон розподілу простих чисел - це результат так званої аналітичної теорії чисел, яка широко використовує методи математичного аналізу для дослідження теоретико-числових функцій. Виявлений у другій половині ХІХ ст. факт зв'язку такого дискретного об'єкта, як цілі числа, з глибокими властивостями функцій вплинув на розвиток теорії чисел.

Розкладання чисел на множники враховує лише структуру множини натуральних чисел, пов'язану з множенням, найбільш глибокі та важкі завданнятеорії чисел виникають при порівнянні додавання та множення. До таких завдань можна віднести, наприклад, проблему Гольдбаха - чи можна всяке парне числоподати як суму двох простих; велику теоремуФерма (див. Ферма велика теорема) - чи можна n-й ступіньчисла уявити як суму n-хступенів двох будь-яких чисел тощо.

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

Класичним методом теорії чисел є метод порівнянь. Ототожнюючи між собою числа, що дають однакові залишки при розподілі на обране число, часто вдається встановити неможливість будь-якого співвідношення. Наприклад, розглядаючи залишки від розподілу на 3 (або, як кажуть, за модулем 3), легко довести нерозв'язність у натуральних числах рівняння Зх 2 + 4у 2 = 5z 2 .

Аналітичний методполягає, як ми вже говорили, у тому, що, вирушаючи від чисел, будують функції, які досліджують методами математичного аналізу. Так, радянський вчений академікІ. М. Виноградов довів варіант проблеми Гольдбаха - уявність досить великого непарного числа у вигляді суми трьох простих.

Геометричний метод теорії чисел ми проілюструємо з прикладу великої теореми Ферма. У цій теоремі йде мовапро дозвіл у цілих числах рівняння х n + у n = z n . Розділивши обидві частини рівняння на z n і замінивши x/z на м, a y/z на v, отримаємо рівняння u n + v n = 1. Це рівняння задає на площині з координатами (u, v) деяку криву. Рішення вихідного рівняння у цілих числах відповідають рішенням нового рівняння у раціональних числах. Про кожне таке рішення (u, v) можна говорити як про точку з раціональними координатами на цій площині. Тепер можемо спробувати застосувати геометричні методидо кривої u n + v n = 1 на дослідження на ній безлічі точок з раціональними координатами.

Великий розділ теорії чисел, що займається знаходженням рішень рівнянь у цілих і раціональних числах, зветься теорії діофантових рівнянь, на ім'я давньогрецького вченого Діофанта (III ст.).

До дуже старих і відомих завдань теорії чисел належить завдання представлення чисел сумами квадратів. Перерахуємо деякі з отриманих результатів:

кожне ціле число можна подати як суму чотирьох квадратів цілих чисел (наприклад: 7 = 2 2 + 1 2 + 1 2 + 1 2);

кожне просте число виду 4n + 1 можна подати у вигляді суми двох квадратів цілих чисел (наприклад: 5 = 2 2 + 1 2 , 41 = 4 2 + 5 2 тощо), а жодне ціле (не тільки просте) число виду 4n + 3 не можна уявити в такому вигляді;

кожне просте число, крім чисел виду 8n - 1, можна як суми трьох квадратів цілих чисел.

Просте алгебраїчне тотожність

(а 2 + b 2) (х 2 + у 2) = (ах + by) 2 + (ay - bx) 2

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

Чим особливо цінна теорія чисел? Адже знайти безпосереднє застосування її результатам важко. Проте завдання теорії чисел залучають як допитливих молодих людей, і вчених протягом багатьох століть. У чому тут справа? Насамперед ці завдання, як уже говорилося, дуже цікаві та красиві. У всі часи людини вражало, що на прості питанняпро числа так важко знайти відповідь. Пошуки цих відповідей часто призводили до відкриттів, значення яких перевищує рамки теорії чисел. Досить згадати про так звану теорію ідеалів німецького математикаХІХ ст. Е. Куммера, яка народилася у зв'язку зі спробами довести велику теорему Ферма.

Назва:Теорія чисел. 2008.

Основу підручника складають результати елементарної теоріїчисел, що сформувалася у працях класиків - Ферма, Ейлера, Гауса та ін. Розглядаються такі питання як прості та складові числа, арифметичні функції, теорія порівнянь, первісні корені та індекси, ланцюгові дроби, алгебраїчні та трансцендентні числа. Оглядово освітлені властивості простих чисел, теорія діофантових рівнянь, алгоритмічні аспекти теорії чисел із застосуваннями у криптографії (перевірка великих простих чисел на простоту, розкладання великих чиселна множники, дискретне логарифмування) та з використанням ЕОМ.
Для студентів вищих навчальних закладів.

Предмет вивчення теорії чисел - числа та його властивості, т. е. числа виступають тут як засіб чи інструмент, бо як об'єкт дослідження. Натуральний ряд
1,2,3,4, ...,9,10,11, ...,99,100,101, ...
- безліч натуральних чисел - є найважливішою областю досліджень, надзвичайно змістовною, важливою та цікавою.
Вивчення натуральних чисел було розпочато в Стародавню Грецію. Евклід і Ератосфен відкрили властивості ділимості чисел, довели нескінченність множини простих чисел і знайшли способи їх побудови. Завдання, пов'язані з рішенням невизначених рівняньу цілих числах були предметом досліджень Діофанта, а також вчених Стародавню Індіюта Стародавнього Китаю, країн Середньої Азії.

Зміст
Вступ
Глава 1. Про подільність чисел
1.1. Властивості ділимості цілих чисел
1.2. Найменше загальне кратне та найбільший спільний дільник
1.3. Алгоритм Евкліда
1.4. Рішення в цілих числах лінійних рівнянь

Глава 2. Прості та складові числа
2.1. Прості числа. Решето Ератосфена. Нескінченність безлічі простих чисел
2.2. Основна теорема арифметики
2.3. Теореми Чебишева
2.4. Дзета-функція Рімана та властивості простих чисел
Завдання для самостійного вирішення
Розділ 3. Арифметичні функції
3.1. Мультиплікативні функції та їх властивості
3.2. Функція Мебіуса та формули звернення
3.3. Функція Ейлера
3.4. Сума дільників та кількість дільників натурального числа
3.5. Оцінки середнього значення арифметичних функцій
Завдання для самостійного вирішення
Глава 4. Числові порівняння
4.1. Порівняння та їх основні властивості
4.2. Класи відрахувань. Кільце класів відрахувань по даному модулю
4.3. Повна та наведена системи відрахувань
4.4. Теорема Вільсона
4.5. Теореми Ейлера та Ферма
4.6. Подання раціональних чисел нескінченними десятковими дробами
4.7. Перевірка на простоту та побудову великих простих чисел
4.8. Розкладання цілих чисел на множники та криптографічні застосування
Завдання для самостійного вирішення
Глава 5. Порівняння з одним невідомим
5.1.Основні визначення
5.2.Порівняння першого ступеня
5.3.Китайська теорема про залишки
5.4. Поліноміальні порівняння з простому модулю
5.5. Поліноміальні порівняння по складовому модулю Завдання для самостійного вирішення
Глава 6. Порівняння другого ступеня
6.1. Порівняння другого ступеня за простим модулем
6.2. Символ Лежандра та його властивості
6.3. Квадратичний закон взаємності
6.4.Символ Якобі та його властивості
6.5.Суми двох та чотирьох квадратів
6.6. Подання нуля квадратичними формамивід трьох змінних
Завдання для самостійного вирішення
Глава 7. Первісні коріння та індекси
7.1. Показник числа за заданим модулем
7.2. Існування первісних коренів за простим модулем
7.3. Побудова первісних коренів за модулями рк і 2рк
7.4. Теорема про відсутність первісних коренів за модулями, відмінними від 2, 4, рк та 2рк
7.5. Індекси та їх властивості
7.6. Дискретне логарифмування
7.7. Двовічні порівняння
Завдання для самостійного вирішення
Розділ 8. Ланцюгові дроби
8.1. Теорема Діріхле про наближення дійсних чисел раціональними
8.2. Кінцеві ланцюгові дроби
8.3. Ланцюговий дріб дійсного числа
8.4. Найкращі наближення
8.5. Еквівалентні числа
8.6. Квадратичні ірраціональності та ланцюгові дроби
8.7. Використання ланцюгових дробів для вирішення деяких діофантових рівнянь
8.8.Розкладання числа е в ланцюговий дріб
Завдання для самостійного вирішення
Глава 9. Алгебраїчні та трансцендентні числа
9.1.Поле алгебраїчних чисел
9.2. Наближення алгебраїчних чисел раціональними. Існування трансцендентних чисел
9.3. Ірраціональність чисел ег і п
9.4. Трансцендентність числа е
9.5. Трансцендентність числа п
9.6.Неможливість квадратури кола
Завдання для самостійного вирішення
Відповіді та вказівки
Список літератури

Безкоштовно завантажити електронну книгуу зручному форматі, дивитися та читати:
Скачати книгу Теорія чисел - Нестеренко Ю.В. - fileskachat.com, швидке та безкоштовне скачування.

Завантажити djvu
Нижче можна купити цю книгу за найкращою ціною зі знижкою з доставкою по всій Росії.

Теорія чисел1

1. Основні поняття теорії подільності

Î п р е д о л е н ня. Число a ділиться на ненульове число b, якщо знайдеться таке ціле число c, що виконується рівність a = b · c.

Позначення:

1) a. b a ділиться на b;

2) b | a b ділить a;

3) a кратно (кратне) b, b дільника.

Поділ із залишком

Нехай дано два числа a èb ,a Z ,b N , ääZ безліч цілих чисел, а N безліч натуральних чисел. Розділимо íàb із залишком =b · q +r , äär лежить у проміжку 0≤ r< b ,q неполное частное,r остаток. Например, 7 = 2· 3 + 1.

Теорема 1. Для будь-якого цілого a і натурального уявлення

a = b · q+ r,0 ≤ r< b

єдино.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Існування.

Розглянемо нескінченна безліччисел (a − tb) , ãäåa ,b фіксовані числа,t будь-яке число,t Z . З нього ми виберемо найменше невід'ємне число r = a − q · b. Доведемо, що лежить в межах

0 ≤ r< b.

Нехай це число не належить даному проміжку. Тоді воно більше або дорівнює b. Побудуємо нове числоr ′ =r−b =a−q·b−b =a−b (q +1).

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

1) r '(a − tb);

2) r 'невід'ємний;

1 С.В.Федоренко. Вересень 2012. Курс лекцій та завдання. Розповсюджується вільно. Курс читався в СПбГУАП (1997 1999; 2008 2011) та СПбДПУ (2002 2005).

3) r ′< r .

Отже, не r , a r ′ є найменшим невід'ємним числомз множини(a − tb) , тоді припущенняr ≥ b хибне.

Існування підтверджено.

2. Єдиність.

Нехай існує інше уявлення a = bq + r , за умови, що 0≤ r ′< b ;a ,b фиксированные числа,q Z . Т.е., мы можем разделить числоa íàb двумя способами, тогдаbq +r =bq ′ +r ′ . Переносячи доданкиñq в одну сторону, а сr в іншу, одержуємо b (q − q ′ ) =r ′ − r . Видно,

÷òî (r ′ − r ) .b . Кожен із залишків менший

(r − r) . b. |r − r|< b

Отже, r − r = 0, а значить r = r q =q . Отже, довели,

що одне число можна поділити на інше єдиним способом. Теорему доведено.

Теорема 2. Якщо a .b èb .c , òîa .c , ãäåb, c ≠ 0.

a = b · q. b = c · t

Отже, a = c · qt. За визначенням видно, що .c.

Теорема 3. Нехай виконується рівність a 1 +a 2 =b 1 +b 2 та числа a 1 , a 2 , b 1 .d, тоді b 2 .d.

Ä î ê à ç à ò å ë ü ñ ò â î

a 1 = d · t 1, a 2 = d · t 2, b 1 = d · t 3 . Виразимо b 2 з умови теореми b 2 = a 1 +a 2 − b 1 =d (t 1 +t 2 − t 3 ). За визначенням ділимості видно, що b 2. d.

2. Найбільший спільний дільник

Î п е д о л е н н ня. Якщо число c є дільником чисел èb, то число c називається загальним дільником чисел èb.

Найбільше загальних дільників чисел a èb називається найбільшим загальним дільником (НОД) чиселa èb .

Позначення: (a, b ) =d , èäåa èb числа, аd найбільший загальний

дільник цих чисел.

Розглянемо приклад для чисел 12 та 9. Випишемо всі дільники 12 та всі дільники 9. Для 12: 1, 2, 3, 4, 6 та 12; для 9: 1, 3 та 9; видно, що вони є спільні дільники 1 і 3. Виберемо найбільший це 3. Отже, (12, 9) = 3.

Визначення. Два числа a èb називаються взаємно простими, якщо їх НОД дорівнює 1.

приклад. Т.к. (10,9)=1, то 10 та 9 взаємно прості числа.

Це визначення можна розповсюдити на будь-яку кількість чисел. Якщо (a, b, c, . . . ) = 1, то числа a, b, c, . . . взаємно прості. Наприклад:

Î ï ð å ä ë å í è å. (a 1 , a 2 , ...a n ) попарно взаємно прості числа, якщо НОД будь-якої пари дорівнює одиниці(a i, a j) = 1,i ≠ j.

Наприклад: 12,17,11 як взаємно прості, а й попарно взаємно прості.

Теорема 1. Якщо a.b, òî (a, b) = b.

Ä î ê à ç à ò å ë ü ñ ò â î

Число b не може ділитися на число більше за себе. Отже, b є НОДомa èb.

Теорема 2. Нехай є уявлення a = bq + r (r не обов'язково залишок), тоді (a, b) = (b, r).

Ä î ê à ç à ò å ë ü ñ ò â î

1. Розглянемо будь-який спільний дільник a èb c . Åñëèa .c èb .c , òî

за теоремою 1.3 r.c, ò.å.c є також спільним дільникомb èr. Будь-який спільний дільник èb є спільним дільникомb èr .

2. Будь-який спільний дільник b er є дільником. Отже, загальні дільники a, b, r збігаються. Це вірно і для НОД.

3. Алгоритм Евкліда

Для будь-яких чисел a èb за допомогою алгоритму Евкліда можна знайти

Нехай a, b N вхідні дані алгоритму, а (a, b) = d N вихідні.

		Bq 0	0 < r1 < b
		R 1 q 1	0 < r2 < r1
		R 2 q 2	0 < r3 < r2

	r i−2	R i−1 q i−1	0 < ri < ri− 1

	r n−2 = r n−1 q n−1 + r n		0 < rn < rn− 1
n + 1	r n−1 = r nq n

Крок 1. Ділимо a íàb із залишком =bq 0 +r 1 , ãäå 0< r 1 < b . По теореме 2.2 (a, b ) = (b, r 1 ).

Крок 2. Ділимо b íàr 1 із залишком b =r 1 q 1 +r 2 , ãäå 0< r 2 < r 1 . Ïî теореме 2.2 (b, r 1 ) = (r 1 , r 2 ).

І так доти, доки не розділиться націло. З ланцюжка рівностей

(a, b) = (b, r 1 ) = (r 1 , r 2 ) = (r 2 , r 3 ) =... = (r n−2 , r n− 1 ) = (r n− 1 , r n ) =r n

слід, що останній ненульовий залишок r n буде найбільшим загальнимдільником d = r n = (a, b). Т.к. залишки зменшуються, то алгоритм завершиться за кінцеве числокроків.

Теореми, пов'язані з алгоритмом Евкліда

Теорема 1. НОД двох чисел ділиться на будь-який спільний дільник цих

Åñëè (a, b ) =d , òî (a c , c b ) =d c , ãäå c спільний дільник èb .

Ä î ê à ç à ò å ë ü ñ ò â î

Â запису алгоритму Евкліда a, b è âñår i розділимо наc . Отримаємо

запис алгоритму Евкліда з вхідними даними a b

÷òî ÍÎÄ a		з èc. З неї видно,
÷òî ÍÎÄ a
	è c	дорівнює c.

Теорема 2. Якщо два числа розділити на НОД, то отримаємо взаємно прості числа (a d , d b ) = 1.

Ä î ê à ç à ò å ë ü ñ ò â î

Теорема 3. Якщо

Замість c (з теореми 1) підставимо d.

(a, b) = 1, òîc. b. ac. b

Ä î ê à ç à ò å ë ü ñ ò â î

Для взаємно простих чисел a èb за теоремою 7.1 існує уявлення ax +by = 1. Помножуючи цю рівність наc , маємо ac · x +byc =c ,

íî ac = bq, bqx + byc = c, b (qx + yc) = c. Отже, c.b.

НОД кількох чисел

(a1 , a2 , . . . , an ) = dn (a1 , a2 ) = d2

(d 2, a 3) = d 3

(d n− 1 , a n ) =d n

4. Найменше загальне кратне

Î п е д о л е н ня. Загальне кратне двох чисел a èb це таке число, яке ділиться на обидва ці числаa èb .

Î п е д о л е н н ня. Найменше із загальних кратних чисел a èb називається найменшим загальним кратним (НОК) чисел èb .

Нехай M .a èM .b , тоді M загальне кратне èb . Найменше загальне кратне чисел èb позначимо як .

Теорема 1. НОК двох чисел дорівнює відношеннюїх твори до

= (a, ab b).

Ä î ê à ç à ò å ë ü ñ ò â î

Позначимо деяке загальне кратне чисел a èb через M тоді M .

a èM .b. Крім того, d = (a, b), a = a d, b = b d, причому (a, b) = 1. За визначенням ділимості M = a · k, ãäåk Z




					a′dk				a′k
					b′d				b′

a ′ не ділиться на b ′, т.к. вони взаємно прості, отже k .b ′ ïî теоремі 3.3

k = b′ · t=




M = a · k =
					(a, b)

вид будь-якого загального кратного чисел a èb. Ïðèt = 1M є НОК чисел èb.

НОК кількох чисел

[a1, a2,. . . , an ] = Mn [ a1 , a2 ] = M2

M 3 =M 4

Åñëè (a, b ) = 1, òî =ab . Ïðè (a i , a j ) = 1,i ≠ j ,M =a 1 a 2 · . . . · a n.

5. Прості та складові числа

Будь-яке число ділиться на 1 і на себе. Назвемо ці дільники тривіальними.

Число називається простим, якщо воно не має нетривіальних дільників. Число називається складеним, якщо воно має нетривіальний дільник. Число 1 не є ні простим, ні складовим.

Теорема 1. Для будь-якого натурального числа a і простого числа

виконується або (a, p) = 1 èëèa .p .

Ä î ê à ç à ò å ë ü ñ ò â î

Ó простого числа p є два тривіальні дільники. Можливі

два варіанти: a .p èëèa ̸ .p . Åñëèa ̸ .p , то НОДома èp є 1. Отже, (a, p ) = 1.

Теорема 2. Найменший відмінний від одиниці дільник цілого, більшої одиниціє просте число.

Ä î ê à ç à ò å ë ü ñ ò â î

Åñëè a ≠ 1, òîa =p·q , ãäåp найменший нетривіальний дільник. Припустимо, що складове число. Це означає, що існує

таке число s , ÷òîp .s , але тодіa .s èp не є найменшим дільникомщо суперечить умові. Т.о.p просте число.

Теорема 3. Найменший нетривіальний дільник складового числане перевершує його кореня.

Ä î ê à ç à ò å ë ü ñ ò â î

a = q · b, q ≤ b, q2 ≤ bq = a, q ≤ a.

Решето Ератосфена

Запишемо безліч натуральних чисел

1 ,2 ,3 ,4 ,5 ,6 ,7 ,8 ,9 ,10 ,11 ,12 ,13 ,14 ,15 ,16 ,17 ,18 , . . .

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

Наприклад, 2 просте число, викреслюємо числа, кратні двійці, отже парних чисел не залишиться. Аналогічно вчинимо і з трійкою. Потрібно викреслити 6, 9, 12, 15, 18 і т.д. Усі числа є простими.

Теорема 4. Безліч простих чисел нескінченна. Доведення

Нехай ( 2, 3, 5, . . . , P ) кінцева безліч простих чисел і N = 2 · 3 · 5 ·. . .·P +1.N не ділиться на жодне з простих чисел, т.к. при розподілі в залишку виходить 1. Але найменший нетривіальний дільник N за теоремою 2 є простим числом 2(, 3, 5, . . . , P ). Отже, простих чисел не кінцева множина, а нескінченна.

6. Канонічна форма числа

Теорема 1 (Основна теорема арифметики). Будь-яке число, відмінне від 1, єдиним способом представляється у вигляді добутку простих чисел.

Ä î ê à ç à ò å ë ü ñ ò â î

1. Існування.

Число n за теоремою 5.2 має простий дільник 1

n n 1 = p 1 .

Аналогічні міркування справедливі і числа n 1

n2 = n 1, p 2

ãäå p 2 простий дільник n 1 . І так будемо продовжувати доти, доки не отримаємо n i = 1.

2. Єдиність.

Нехай число n має два розкладання на прості числа

n = p1 · p2 · . . . · pl = q1 · q2 · . . . · qs.

Без обмеження спільності приймемо l ≤ s. Якщо ліва частинарівності ділиться наp 1 , те й права теж ділиться наp 1 . Отже, деякеq i = p 1 . Нехай це q1 = p1. Розділимо обидві частини рівності наp 1

Аналогічно, приймемо q 2 = p 2 . Продовжуватимемо цю процедуру, поки вираз не набуде вигляду

1 = ql +1 · . . . · qs.

Åñëè l< s , то произведение простых чисел не может быть равно 1. Следовательно, предположение о двух различных разложениях числаn невер-

íî. Åñëè s =l , òîp i =q i äëÿi і два розкладання збігаються. Теорему доведено.

Будь-яке число n N можна записати у канонічній формі

n = p1 s 1 · . . . · pl s l ,

ãäå p i прості числа, s i N .

Канонічне подання дозволяє виписати всі дільники числа та визначити НОД та НОК.

Усі дільники з числаn мають вигляд

c = p1 i 1 · p2 i 2 . . . pl i l, ãäå ij.

Знаходження НОД та НОК

Нехай числа a èb представлені у вигляді

a = p1 s 1 · p2 s 2 · . . . · pl s l b = p1 t 1 · p2 t 2 · . . . · Pl t l.

Це уявлення відрізняється від канонічного тим, що деякі s i è t i можуть дорівнювати 0.

Тоді найбільший спільний дільник a èb

(a, b) = p1 min (s 1, t 1) · p2 min (s 2, t 2) · . . . · pl min (s l, t l),

а найменше загальне кратне:

[a, b] = p1 max (s 1, t 1) · p2 max (s 2, t 2) · . . . · pl max (s l, t l).

Звідси також видно, що (a, b) ділиться на будь-який спільний дільник èb.

7. Лінійні діофантові рівняння з двома невідомими

Î п р е д о л е н ня. Лінійним діофантовим рівнянням з двома невідомими називається рівняння виду

ax + by = c,

де коефіцієнти a, b, c і невідоміx, y цілі числа, аa èb не дорівнюють нулю одночасно.

Теорема 1 (Про лінійне подання НОД). Для будь-якої пари чисел (a, b ) ((a, b ) ≠ (0, 0)) існують такі x, y Z , ÷òîax +by =(a, b ).

Ä î ê à ç à ò å ë ü ñ ò â î

Розглянемо безліч чисел (ax + by) і з нього виберемо мінімальне додатне число d = ax 0 + by 0 .

Доведемо, що d є дільником b .

Нехай d не дільник b, отже, b = d · q +r, ãäå 0< r < d ,

r = b − dq= b −(ax0 + by0 ) q= a(−x0 q) + b(1 − y0 q). Видно що:

1) число r (ax + by);

2) r позитивне;

3) r< d .

Але ми припустили, що d найменше позитивне число з цієї множини, отже, наше припущення, щоr< d неверно, значитd делительb .

Аналогічно можна довести, що a.

З усього цього випливає, що d є спільним дільником èb .

a. (a, b)

Èòàê, b . (a, b) d. (a, b ), íîd спільний дільник èb , отже, d ÍÎÄ a è b .

Теорема 2. Рівняння ax +by =c має розв'язок тоді і лише тоді, колиc ділиться на (a, b).

Ä î ê à ç à ò å ë ü ñ ò â î

1. Нехайc. (a, b), тоді за теоремою 1 ax+by= (a, b). Помножимо рівняння на c

( a,b )

a · (a,xcb) + b · (a,ycb) = c.

Пара чисел ( x0 , y0 ) буде рішенням вихідного рівняння

{ x0 = (a,bxc)y0 = (a,byc).

2. Доведемо, що якщо рівняння має розв'язок, то c. (a, b).

a. (a, b) , отже, cтеж має ділитися на ( a, b).

b . ( a, b )