Взаємно прості числа
З Вікіпедії, безкоштовно encyclopedia
Взаємно прості числа — натуральні або цілі числа, які не мають спільних дільників більших за 1, або, інакше кажучи, якщо їх найбільший спільний дільник дорівнює 1. Таким чином, 2 і 3 — взаємно прості, а 2 і 4 — ні (діляться на 2). Будь-яке натуральне число взаємно просте з 1.Натуральні числа називають взаємно простими, якщо їх найбільший спільний дільник дорівнює 1. Якщо — просте, а
— довільне ціле число, то вони взаємно прості і тільки тоді, коли
не ділиться на
Взаємна простота великих чисел може бути перевірена і доведена чи спростована за допомогою алгоритму Евкліда.
Якщо числа та
взаємно прості, то класи
та
перетинаються по класу
Перетин класів
та
є класом
, де число
- найменше спільне кратне
та
. Класи є монотонними по відношенню до ділення