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

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

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

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

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

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

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