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

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

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

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

Приклади[ред. | ред. код]

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

Див. також[ред. | ред. код]