$p$ називається простим числом, якщо в нього лише $2$ дільника: $1$ і воно саме.

Дільником натурального числа$a$ називають натуральне число, яке вихідне число $a$ ділиться без залишку.

Приклад 1

Знайти дільники числа $6$.

Рішення: Нам треба знайти всі числа, на які задане число 6$ ділиться без залишку. Це будуть цифри: $ 1,2,3, 6 $. Отже дільником числа $6$ будуть числа $1,2,3,6.$

Відповідь: $ 1,2,3,6 $.

Отже, щоб знайти дільники числа треба знайти все натуральні числа, куди це ділиться без залишку. Неважко помітити, що число $1$ буде дільником будь-якого натурального числа.

Визначення 2

Складнимназивають число, у якого крім одиниці та себе є інші дільники.

Прикладом простого числа може бути $13$, прикладом складового число $14.$

Примітка 1

Число $1$ має лише один дільник-саме це число, тому його не відносять ні до простих, ні до складових.

Взаємно прості числа

Визначення 3

Взаємно простими числаминазиваються ті, у яких НОД дорівнює $1$.Значить для з'ясування чи будуть числа взаємно простими необхідно знайти їх НОД і порівняти його з $1$.

Попарно взаємно прості

Визначення 4

Якщо в наборі чисел будь-які два взаємно прості, такі числа називаються попарно взаємно простими. Для двох чисел поняття «взаємно прості» та «попарно взаємно прості» збігаються.

Приклад 2

$8, 15$ - не прості, але взаємно прості.

$ 6, 8, 9 $ - взаємно прості числа, але не попарно взаємно прості.

$ 8, 15, 49 $ - попарно взаємно прості.

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

Розкладання на прості множники

Наприклад, розкладемо на прості множники число $180$:

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$

Скористаємося властивістю ступенів, тоді отримаємо,

$180=2^2\cdot 3^2\cdot 5$

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

Канонічне розкладання натурального числа у загальному вигляді

Канонічне розкладання натурального числа у загальному вигляді має вигляд:

$m=p^(n1)_1\cdot p^(n2)_2\cdot \dots \dots ..\cdot p^(nk)_k$

де $p_1,p_2\dots \dots .p_k$- прості числа, а показники ступенів-натуральні числа.

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

Приклад 3

Знайти найбільший спільний дільникчисел $180$ та $240$.

Рішення: Розкладемо числа на прості множини за допомогою канонічного розкладання

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, тоді $180=2^2\cdot 3^2\cdot 5$

$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, тоді $240=2^4\cdot 3\cdot 5$

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

$НОД \ (180; 240) = 2 ^ 2 \ cdot 3 \ cdot 5 = 60 $

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

Щоб знайти найбільший спільний дільник двох чисел за допомогою канонічного розкладання, необхідно:

1. розкласти числа на прості множники у канонічному вигляді
2. вибрати ступеня з однаковою основою та з найменшим показником ступеня, що входять до складу розкладання цих чисел
3. Знайти добуток чисел, знайдених на кроці 2. Отримане число буде шуканим найбільшим спільним дільником.

Приклад 4

Визначити, чи будуть простими, взаємно простими числами $195$ і $336$.

$195=3\cdot 5\cdot 13$

$336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$

$НОД \ (195; 336) = 3 \ cdot 5 = 15 $

Ми бачимо, що НОД цих чисел відмінний від $1$, отже числа не взаємно прості. Також ми бачимо, що до складу кожного з чисел входять множники, крім $1$ і самого числа, значить простими числа так само не будуть, а будуть складовими.

Приклад 5

Визначити, чи будуть простими, взаємно простими числами $39$ і $112$.

Рішення: Скористаємося для розкладання на множники канонічним розкладанням:

$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$

$НОД \ (39; 112) = 1 $

Ми, НОД цих чисел дорівнює $1$, отже числа взаємно прості. Також ми бачимо, що до складу кожного з чисел входять множники, крім $1$ і самого числа, значить простими числа так само не будуть, а будуть складовими.

Приклад 6

Визначити чи простими, взаємно простими числами числа $883$ і $997$.

Рішення: Скористаємося для розкладання на множники канонічним розкладанням:

$883=1\cdot 883$

$997=1\cdot 997$

$ НОД \ (883; 997) = 1 $

Ми, НОД цих чисел дорівнює $1$, отже числа взаємно прості. Також ми бачимо, що до складу кожного з чисел входять тільки множники, рівні $1$ і самому числу, значить, числа будуть простими.

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

Зауважте, наприклад, що числа 4 і 9 взаємно прості, але окремо жодне з них не є простим. А число 1 взаємно легко з будь-яким числом, зокрема і із собою.

Для цього визначення зовсім неістотно, що чисел лише два - воно буквально переноситься на будь-яку кількість натуральних чисел. Наприклад, числа 6, 10, 15 взаємно прості, хоча жодні з них взаємно простими, очевидно, є.

Властивість взаємної простотипереноситься і безліч цілих чисел. При цьому вихідне визначення – для натуральних чисел – природним чином коригується: ціле число завжди має два дільники – 1 та -1, так що два цілих числа називаються взаємно простими, якщо їх загальними дільниками є лише 1 та –1.

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

Зазначимо також, що іноді зустрічається не зовсім акуратне формулювання типу «два числа - натуральні або цілі - називаються взаємно простими, якщо вони не мають спільних дільників». І тут як би забувається про 1 і -1. Така «забудькуватість» виправдана тим, що 1 і -1 - тривіальні дільники, вони завжди є, і цю дрібницю можна для стислості лише мати на увазі.

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

Нагадаємо, що ціле число називають простим, якщо простим числом є його модуль – натуральне число. Таке узагальнення шкільного поняття простого числа є цілком природним: адже головне - це можливість розумного, нетривіального розкладання числа на множники, а з цього погляду числа, скажімо, 5 і -5 цілком рівноправні: розкладання -5 = (-5) нецікаво, нерозумно, тривіально.

Для взаємно простих цілих чисел надзвичайно важливим та корисним з погляду задач є наступний критерій взаємної простоти двох цілих чисел: цілі числа a та b взаємно прості тоді і тільки тоді, коли існують такі цілі числа u та v, що au+ bv = 1.

Ця властивість, однак, явно неправильна, якщо говорити тільки про натуральні числа: очевидно, не існує таких натуральних чисел u і v, що 2u + Зv = 1.

На підставі саме цієї властивості можна довести незалежно від основної теореми, що якщо добуток двох цілих чисел ділиться на просте число р, то хоча б одне з цих чисел ділиться на р. Справді, якщо а не ділиться на р, то а і р взаємно прості, тоді для деяких u і v виконується рівність au + рv = 1, звідки abu + bрv = bтак що b ділиться на р.

Понад те, це твердження насправді головне задля доказу основний теореми арифметики.

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

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

Ключові слова: теорія чисел, лекції, взаємно прості числа.

Визначення.Цілі числа a та b називаються взаємно простими, якщо (a, b) = 1.

Два числа a і b є взаємно простими тоді й лише тоді, коли знайдуться цілі числа u та v такі, що au + bv = 1.

Нехай X = ( x n | n = 1, 2, ...) - довільна строго зростаюча послідовність натуральних чисел (або, якщо завгодно, X - довільне підмножина натуральних чисел, впорядковане природним чином). Позначимо через ξ(N; X) число членів послідовності X, що не перевищують N .

Визначення.Число називається (верхньою асимптотичною) щільністю послідовності X = (x n | n = 1, 2, ...) у множині N .

приклад 1.Нехай x n = 2n, де n пробігає N, - Послідовність всіх парних чисел. Очевидно, що

Між іншим, це добре узгоджується з нашими інтуїтивними уявленнями про те, що парних чисел – половина.

приклад 2.Нехай x n = 2 n , де n пробігає N - геометрична прогресія. Інтуїтивно ясно, що таких чисел у натуральному ряду мало, бо чим "далі в ліс" по натуральному ряду, тим рідше зустрічається ступінь двійки. Поняття щільності підтверджує це відчуття: ξ (2 k ; ( x n )) = k , і легко перевірити, що

густина- це можливість навмання витягнути з натурального ряду число, що належить заданій послідовності.

Аналогічно визначенню густини послідовності, можна дати визначення густини множини пар натуральних чисел. Нехай є довільна множина Х упорядкованих пар натуральних чисел. Позначимо через ξ (N ; X) число пар з множини Х, кожна компонента яких не перевищує N . Корисно уявити пари чисел з множини Х як координати точок на координатній площині, тоді ξ (N ; X) є просто число точок множини Х, що потрапили в квадрат (( x , y) | 0< x ≤ N ; 0 < y ≤ N }.

Визначення.Число

називається (верхньою асимптотичною) щільністю множини пар Х у множині N 2 .

Приклад 3.Нехай Х - безліч всіх пар натуральних чисел, у яких перша компонента строго більша за другу. Безліч Х відповідають точки першої чверті координатної площини, що лежать під бісектрисою y = x. Щільність такої множини легко підрахувати:

Нехай X - безліч всіх упорядкованих пар (u, v) натуральних чисел таких, що (u, v) = 1, тобто. безліч всіх пар взаємно простих чисел.

Теорема (Чезаро).Імовірність вибрати з N пари взаємно простих чисел дорівнює 6/π 2 , Точніше Доказ. Припустимо відразу, що є можливість p того, що випадково обрані натуральні числа а і b взаємно прості. Нехай d ∈ N . Через P ( S ) позначимо, як завжди, ймовірність події S . Розмірковуємо: Р

Натуральні числа a та b називають взаємно простимиякщо їх найбільший спільний дільник дорівнює 1 (НД(a ; b ) = 1). Інакше кажучи, якщо числа a і b немає жодних спільних дільників, крім 1, всі вони взаємно прості.

Приклади пар взаємно простих чисел: 2 і 5, 13 і 16, 35 і 88 тощо. Можна вказати кілька взаємно простих чисел, наприклад, числа 7, 9, 16 – взаємно прості.

Часто взаємно прості числа позначають так: (a, b) = 1. Наприклад, (23, 30) = 1. Цей запис як би є скороченим записом позначення найбільшого загального дільника двох чисел (НД(23, 30) = 1), і свідчить, що й найбільший загальний дільник дорівнює 1.

Два сусідні натуральні числа завжди будуть взаємно прості.Наприклад, 15 і 16 - пара взаємно простих чисел, також як 16 і 17. Це легко зрозуміти, якщо взяти до уваги «правило» про те, що якщо два натуральні числа a і b діляться на те саме натуральне число більше 1 ( n > 1), те й їхня різниця також повинна ділиться на це число n (тут мається на увазі, що a, b і їхня різниця діляться націло, тобто кратні числу n). Але якщо a і b два сусідні числа (нехай a< b ), то b – a = 1; но 1 делится только на 1 (из ряда натуральных чисел). Следовательно, a и b не имеют других общих делителей, кроме 1.

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

Властивості взаємно простих чисел

• Найменше загальне кратне (НОК) пари взаємно простих чисел і їх твору.Наприклад, (3, 8) = 1 (це означає взаємно прості), отже їх НОК дорівнює 3 × 8 = 24 (НОК(3, 8) = 24). Дійсно, ви не знайдете менше, ніж 24, яке було б кратним і 3 і 8.
• Якщо числа a і b взаємно прості і число c кратне як a , і b , це число буде кратно і твору ab . Це можна записати так: якщо a і c b , то c ab . Наприклад, (3, 10) = 1, число 60 кратно як 3, і 10, і навіть кратно 30 (3 × 10).
• Якщо числа a і b взаємно прості та взято число c кратне b (c b ), то добуток ac також буде кратним b (ac b ). Наприклад, (2, 17) = 1, нехай c = 34. Число 34 кратне b = 17, тоді ac = 2 × 34 = 68. Перевіряємо: 68 ÷ 17 = 4, тобто ділиться націло, а значить 68 кратно 17.

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

$p$ називається простим числом, якщо в нього лише $2$ дільника: $1$ і воно саме.

Дільником натурального числа $a$ називають натуральне число, яке вихідне число $a$ ділиться без залишку.

Приклад 1

Знайти дільники числа $6$.

Рішення: Нам треба знайти всі числа, на які задане число 6$ ділиться без залишку. Це будуть цифри: $ 1,2,3, 6 $. Отже дільником числа $6$ будуть числа $1,2,3,6.$

Відповідь: $ 1,2,3,6 $.

Отже, щоб знайти дільники числа треба знайти все натуральні числа, куди це ділиться без залишку. Неважко помітити, що число $1$ буде дільником будь-якого натурального числа.

Визначення 2

Складнимназивають число, у якого крім одиниці та себе є інші дільники.

Прикладом простого числа може бути $13$, прикладом складового число $14.$

Примітка 1

Число $1$ має лише один дільник-саме це число, тому його не відносять ні до простих, ні до складових.

Взаємно прості числа

Визначення 3

Взаємно простими числаминазиваються ті, у яких НОД дорівнює $1$.Значить для з'ясування чи будуть числа взаємно простими необхідно знайти їх НОД і порівняти його з $1$.

Попарно взаємно прості

Визначення 4

Якщо в наборі чисел будь-які два взаємно прості, такі числа називаються попарно взаємно простими. Для двох чисел поняття «взаємно прості» та «попарно взаємно прості» збігаються.

Приклад 2

$8, 15$ - не прості, але взаємно прості.

$ 6, 8, 9 $ - взаємно прості числа, але не попарно взаємно прості.

$ 8, 15, 49 $ - попарно взаємно прості.

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

Розкладання на прості множники

Наприклад, розкладемо на прості множники число $180$:

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$

Скористаємося властивістю ступенів, тоді отримаємо,

$180=2^2\cdot 3^2\cdot 5$

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

Канонічне розкладання натурального числа у загальному вигляді

Канонічне розкладання натурального числа у загальному вигляді має вигляд:

$m=p^(n1)_1\cdot p^(n2)_2\cdot \dots \dots ..\cdot p^(nk)_k$

де $p_1,p_2\dots \dots .p_k$- прості числа, а показники ступенів-натуральні числа.

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

Приклад 3

Знайти найбільший спільний дільник чисел $180$ та $240$.

Рішення: Розкладемо числа на прості множини за допомогою канонічного розкладання

$180=2\cdot 2\cdot 3\cdot 3\cdot 5$, тоді $180=2^2\cdot 3^2\cdot 5$

$240=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 5$, тоді $240=2^4\cdot 3\cdot 5$

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

$НОД \ (180; 240) = 2 ^ 2 \ cdot 3 \ cdot 5 = 60 $

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

Щоб знайти найбільший спільний дільник двох чисел за допомогою канонічного розкладання, необхідно:

1. розкласти числа на прості множники у канонічному вигляді
2. вибрати ступеня з однаковою основою та з найменшим показником ступеня, що входять до складу розкладання цих чисел
3. Знайти добуток чисел, знайдених на кроці 2. Отримане число буде шуканим найбільшим спільним дільником.

Приклад 4

Визначити, чи будуть простими, взаємно простими числами $195$ і $336$.

$195=3\cdot 5\cdot 13$

$336=2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 7=2^4\cdot 3\cdot 5$

$НОД \ (195; 336) = 3 \ cdot 5 = 15 $

Ми бачимо, що НОД цих чисел відмінний від $1$, отже числа не взаємно прості. Також ми бачимо, що до складу кожного з чисел входять множники, крім $1$ і самого числа, значить простими числа так само не будуть, а будуть складовими.

Приклад 5

Визначити, чи будуть простими, взаємно простими числами $39$ і $112$.

Рішення: Скористаємося для розкладання на множники канонічним розкладанням:

$112=2\cdot 2\cdot 2\cdot 2\cdot 7=2^4\cdot 7$

$НОД \ (39; 112) = 1 $

Ми, НОД цих чисел дорівнює $1$, отже числа взаємно прості. Також ми бачимо, що до складу кожного з чисел входять множники, крім $1$ і самого числа, значить простими числа так само не будуть, а будуть складовими.

Приклад 6

Визначити чи простими, взаємно простими числами числа $883$ і $997$.

Рішення: Скористаємося для розкладання на множники канонічним розкладанням:

$883=1\cdot 883$

$997=1\cdot 997$

$ НОД \ (883; 997) = 1 $

Ми, НОД цих чисел дорівнює $1$, отже числа взаємно прості. Також ми бачимо, що до складу кожного з чисел входять тільки множники, рівні $1$ і самому числу, значить, числа будуть простими.