$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=2cdot 2cdot 2cdot 2cdot 3cdot 5$, тоді $240=2^4cdot 3cdot 5$
Тепер знайдемо НОД цих чисел, для цього виберемо ступеня з однаковою основою та з найменшим показником ступеня, тоді
$ НОД \ (180; 240) = 2 ^ 2 \ cdot 3 \ cdot 5 = 60 $
Складемо алгоритм знаходження НОД з урахуванням канонічного розкладання на прості множники.
Щоб знайти найбільший спільний дільник двох чисел за допомогою канонічного розкладання, необхідно:
- розкласти числа на прості множники у канонічному вигляді
- вибрати ступеня з однаковою основою та з найменшим показником ступеня, що входять до складу розкладання цих чисел
- Знайти добуток чисел, знайдених на кроці 2. Отримане число і буде найбільшим шуканим спільним дільником.
Приклад 4
Визначити, чи простими, взаємно простими числами числа $195$ і $336$.
$195=3\cdot 5\cdot 13$
$336=2cdot 2cdot 2cdot 2cdot 3cdot 7=2^4cdot 3cdot 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
Взаємно простими будуть такі числа a і b , найбільший загальний дільник яких дорівнює 1 , тобто . НОД (a, b) = 1 .
З цього визначення можна дійти невтішного висновку, що єдиний позитивний загальний дільник у двох взаємно простих чисел дорівнюватиме 1 . Усього два таких числа мають два спільні дільники – одиницю та мінус одиницю.
Які приклади взаємно простих чисел? Наприклад, такою парою будуть 5 та 11 . Вони мають лише один загальний позитивний дільник, що дорівнює 1 , що є підтвердженням їхньої взаємної простоти.
Якщо ми візьмемо два простих числа, то по відношенню один до одного вони будуть взаємно простими у всіх випадках, однак такі взаємні відносини утворюються також між складовими числами. Можливі випадки, коли одне число в парі взаємно простих є складовим, а друге простим, або складовими є вони обидва.
Це твердження ілюструє наступний приклад: складові числа - 9 та 8 утворюють взаємно просту пару. Доведемо це, вирахувавши їх найбільший спільний дільник. Для цього запишемо усі їхні дільники (рекомендуємо перечитати статтю про знаходження дільників числа). У 8 це будуть числа ±1, ±2, ±4, ±8, а у 9 – ±1, ±3, ±9. Вибираємо з усіх дільників той, що буде загальним та найбільшим – це одиниця. Отже, якщо НОД (8 , − 9) = 1 , то 8 і - 9 будуть взаємно простими один до одного.
Взаємно простими числами не є 500 і 45, оскільки вони мають ще один спільний дільник – 5 (див. статтю про ознаки ділимості на 5). П'ять більше одиниці та є позитивним числом. Іншою подібною парою можуть бути - 201 і 3, оскільки їх обидва можна розділити на 3, на що вказує відповідну ознаку ділимості.
Насправді досить часто доводиться визначати взаємну простоту двох цілих чисел. З'ясування цього можна звести до пошуку найбільшого спільного дільника та порівняння його з одиницею. Також зручно користуватися таблицею простих чисел, щоб не робити зайвих обчислень: якщо одне із заданих чисел є в цій таблиці, значить, воно ділиться тільки на одиницю і саме на себе. Розберемо розв'язання такого завдання.
Приклад 1
Умова:з'ясуйте, чи є взаємно простими числа 275 та 84 .
Рішення
Обидва числа мають більше одного дільника, тому відразу назвати їх взаємно простими ми не можемо.
Обчислюємо найбільший спільний дільник, використовуючи алгоритм Евкліда: 275 = 84 · 3 + 23, 84 = 23 · 3 + 15, 23 = 15 · 1 + 8, 15 = 8 · 1 + 7, 8 = 7 · 1 + 1, = 7 · 1.
Відповідь:оскільки НОД (84, 275) = 1, то дані числа будуть взаємно простими.
Як ми вже говорили раніше, визначення таких чисел можна поширити і на випадки, коли ми маємо не два числа, а більше.
Визначення 2
Взаємно простими цілі числа a 1 , a 2 , … , a k , k > 2 будуть тоді, коли вони мають найбільший спільний дільник, що дорівнює 1 .
Іншими словами, якщо ми маємо набір деяких чисел з найбільшим позитивним дільником, більшим 1 , то всі ці числа не по відношенню один до одного взаємно зворотні.
Візьмемо кілька прикладів. Так, цілі числа − 99 , 17 та − 27 – взаємно прості. Будь-яка кількість простих чисел буде взаємно простою по відношенню до всіх членів сукупності, як, наприклад, у послідовності 2, 3, 11, 19, 151, 293 і 667. А ось числа 12, − 9, 900 і − 72 взаємно простими не будуть, тому що, крім одиниці, у них буде ще один позитивний дільник, рівний 3 . Те саме стосується числа 17 , 85 і 187: крім одиниці, їх можна розділити на 17 .
Зазвичай взаємна простота чисел не є очевидною з першого погляду, цей факт потребує доказу. Щоб з'ясувати, чи будуть деякі числа взаємно простими, потрібно знайти їх найбільший спільний дільник і зробити висновок на підставі порівняння з одиницею.
Приклад 2
Умова: визначте, чи є числа 331, 463 та 733 взаємно простими.
Рішення
Звіримося з таблицею простих чисел і визначимо, що всі ці числа в ній є. Тоді їх спільним дільником може бути лише одиниця.
Відповідь:всі ці числа будуть взаємно простими стосовно один одного.
Приклад 3
Умова:наведіть доказ того, що числа − 14 , 105 , − 2 107 та − 91 не є взаємно простими.
Рішення
Почнемо з виявлення їхнього найбільшого спільного дільника, після чого переконаємося, що він не дорівнює 1 . Оскільки у негативних чисел ті ж дільники, що й у відповідних позитивних, то НОД (− 14 , 105 , 2 107 , − 91) = НОД (14 , 105 , 2 107 , 91) . Згідно з правилами, які ми привели в статті про знаходження найбільшого спільного дільника, в даному випадку НОД дорівнюватиме семи.
Відповідь:сім більше одиниці, отже, взаємно простими ці числа не є.
Основні властивості взаємно простих чисел
Такі числа мають деякі практично важливі властивості. Перерахуємо їх по порядку та доведемо.
Визначення 3
Якщо поділити цілі числа a і b на число, що відповідає їхньому найбільшому загальному дільнику, ми отримаємо взаємно прості числа. Інакше кажучи, a: НОД (a, b) і b: НОД (a, b) будуть взаємно простими.
Цю властивість ми вже доводили. Доказ можна переглянути у статті про властивості найбільшого спільного дільника. Завдяки йому ми можемо визначати пари взаємно простих чисел: достатньо лише взяти два будь-які цілі числа і виконати розподіл на НОД. У результаті ми маємо отримати взаємно прості числа.
Визначення 4
Необхідною та достатньою умовою взаємної простоти чисел a та b є існування таких цілих чисел u 0і v 0, за яких рівність a · u 0 + b · v 0 = 1буде вірним.
Доказ 1
Почнемо з доказу необхідності цієї умови. Припустимо, у нас є два взаємно прості числа, позначені a і b . Тоді за визначенням цього поняття їх найбільший спільний дільник дорівнюватиме одиниці. З властивостей НОД нам відомо, що для цілих a і b існує співвідношення Безу a · u 0 + b · v 0 = НОД (a, b). З нього отримаємо, що a · u 0 + b · v 0 = 1. Після цього нам треба довести достатність умов. Нехай рівність a · u 0 + b · v 0 = 1буде вірним, у разі, якщо НОД (a, b)ділить і a , і b , то він ділитиме і суму a · u 0 + b · v 0, І одиницю відповідно (це можна стверджувати, виходячи з властивостей ділимості). А таке можливе лише в тому випадку, якщо НОД (a, b) = 1, що доводить взаємну простоту a і b.
Справді, якщо a та b є взаємно простими, то згідно з попередньою властивістю, буде вірним рівність a · u 0 + b · v 0 = 1. Примножуємо обидві його частини на c і отримуємо, що a · c · u 0 + b · c · v 0 = c. Ми можемо розділити перший доданок a · c · u 0 + b · c · v 0на b, тому що це можливо для a · c, і другий доданок також поділяється на b, адже один із множників у нас дорівнює b. З цього укладаємо, що всю суму можна розділити на b, а оскільки ця сума дорівнює c, то можна розділити на b.
Визначення 5
Якщо два цілих числа a і b є взаємно простими, то НОД (a · c, b) = НОД (c, b).
Доказ 2
Доведемо, що НОД (a · c , b) ділитиме НОД (c , b) , а потім – що НОД (c , b) ділить НОД (a · c , b) , що буде доказом вірності рівності НОД (a · c, b) = НОД (c, b).
Оскільки НОД (a · c, b) ділить і a · c і b, а НОД (a · c, b) ділить b, то він також ділитиме і b · c. Отже, НОД (a · c , b) ділить і a · c і b · c , отже, в силу властивостей НОД він ділить і НОД (a · c , b · c) , який дорівнює c · НОД (a , b ) = c. Отже, НОД (a · c, b) ділить і b і c, отже, ділить і НОД (c, b).
Також можна сказати, що оскільки НОД (c, b) ділить і c, і b, то він ділитиме і c, і a · c. Значить, НОД (c, b) ділить і a · c і b, отже, ділить і НОД (a · c, b).
Таким чином, НОД (a · c, b) і НОД (c, b) взаємно ділять один одного, отже, вони є рівними.
Визначення 6
Якщо числа з послідовності a 1 , a 2 , … , a kбудуть взаємно простими щодо числа послідовності b 1 , b 2 , … , b m(при натуральних значеннях k і m), їх твори a 1 · a 2 · … · a kі b 1 · b 2 · … · b mтакож є взаємно простими, зокрема, a 1 = a 2 = … = a k = aі b 1 = b 2 = … = b m = b, то a kі b m- Взаємно прості.
Доказ 3
Відповідно до попередньої якості, ми можемо записати рівності наступного виду: НОД (a 1 · a 2 · … · ak, b m) = НОД (a 2 · … · ak, b m) = … = НОД (ak, b m) = 1 . Можливість останнього переходу забезпечується тим, що ak і b m взаємно прості за умовою. Отже, НОД (a 1 · a 2 · … · ak, b m) = 1 .
Позначимо a 1 · a 2 · … · a k = A і отримаємо, що НОД (b 1 · b 2 · … · b m , a 1 · a 2 · … · a k) = НОД (b 1 · b 2 · … · b m , A) = НОД (b 2 · … · b · b m , A) = … = НОД (b m , A) = 1 . Це буде справедливим через останню рівність з ланцюжка, побудованого вище. Таким чином, у нас вийшла рівність НОД (b 1 · b 2 · … · b m , a 1 · a 2 · … · a k) = 1 , за допомогою якої можна довести взаємну простоту творів a 1 · a 2 · … · a kі b 1 · b 2 · … · b m
Це все властивості взаємно простих чисел, про які ми хотіли б вам розповісти.
Поняття попарно простих чисел
Знаючи, що являють собою взаємно прості числа, ми можемо сформулювати визначення попарно простих чисел.
Визначення 7
Попарно прості числа– це послідовність цілих чисел a 1 , a 2 , … , a k , де кожне число буде взаємно простим стосовно інших.
Прикладом послідовності попарно простих чисел може бути 14, 9, 17 і − 25 . Тут всі пари (14 і 9, 14 і 17, 14 і 25, 9 і 17, 9 і 25, 17 і 25) взаємно прості. Зазначимо, що умова взаємної простоти є обов'язковою для попарно простих чисел, але взаємно прості числа будуть попарно простими далеко не у всіх випадках. Наприклад, у послідовності 8 , 16 , 5 та 15 числа не є такими, оскільки 8 та 16 не будуть взаємно простими.
Також слід зупинитись на понятті сукупності деякої кількості простих чисел. Вони завжди будуть і взаємно, і попарно простими. Прикладом може бути послідовність 71, 443, 857, 991. У випадку з простими числами поняття взаємної та попарної простоти збігатимуться.
Якщо ви помітили помилку в тексті, будь ласка, виділіть її та натисніть Ctrl+Enter
Натуральні числа 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.
Зазвичай виділяють більше властивостей, ніж тут. Крім того, властивості взаємно простих чисел формулюються по-різному. Також буває потрібно довести ці властивості (у разі докази не наводяться).
Ключові слова: теорія чисел, лекції, взаємно прості числа.
Визначення.Цілі числа 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. Розмірковуємо: Р
$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=2cdot 2cdot 2cdot 2cdot 3cdot 5$, тоді $240=2^4cdot 3cdot 5$
Тепер знайдемо НОД цих чисел, для цього виберемо ступеня з однаковою основою та з найменшим показником ступеня, тоді
$ НОД \ (180; 240) = 2 ^ 2 \ cdot 3 \ cdot 5 = 60 $
Складемо алгоритм знаходження НОД з урахуванням канонічного розкладання на прості множники.
Щоб знайти найбільший спільний дільник двох чисел за допомогою канонічного розкладання, необхідно:
- розкласти числа на прості множники у канонічному вигляді
- вибрати ступеня з однаковою основою та з найменшим показником ступеня, що входять до складу розкладання цих чисел
- Знайти добуток чисел, знайдених на кроці 2. Отримане число і буде найбільшим шуканим спільним дільником.
Приклад 4
Визначити, чи простими, взаємно простими числами числа $195$ і $336$.
$195=3\cdot 5\cdot 13$
$336=2cdot 2cdot 2cdot 2cdot 3cdot 7=2^4cdot 3cdot 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$ і самому числу, отже числа будуть простими.
