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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Взаємна простота великих чисел може бути перевірена і доведена чи спростована за допомогою алгоритму Евкліда.

Якщо числа та взаємно прості, то класи та перетинаються по класу Перетин класів та є класом , де число - найменше спільне кратне та . Класи є монотонними по відношенню до ділення

Приклади

[ред. | ред. код]
  • Числа 9 та 24 не є взаємно простими, оскільки обидва числа діляться на 3.
  • Для перевірки взаємної простоти 7 і 91 зазначимо, що 7 — просте число. Оскільки 91 ділиться на 7, 91/7=13, ці числа не є взаємно простими.
  • Числа 10 та 9 — взаємно прості, тому що будь-який їх спільний дільник мусить також ділити їх різницю 10-9=1.
  • Також взаємно простими є 65 та 48, в чому можна пересвідчитися за допомогою алгоритму Евкліда:
тому найбільший спільний дільник 65 та 48 дорівнює 1.

Див. також

[ред. | ред. код]