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

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

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

Якщо числа ${\displaystyle i}$ та ${\displaystyle j}$ взаємно прості, то класи ${\displaystyle (i+)}$ та ${\displaystyle (j+)}$ перетинаються по класу ${\displaystyle (ij+).}$ Перетин класів ${\displaystyle (i+)}$ та ${\displaystyle (j+)}$ є класом ${\displaystyle (x+)}$, де число ${\displaystyle x}$ - найменше спільне кратне ${\displaystyle i}$ та ${\displaystyle j}$. Класи є монотонними по відношенню до ділення ${\displaystyle (x+)\subset (i+),\,\,(x+)\subset (j+).}$

Приклади

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

${\displaystyle 65-1\cdot 48=17,48-2\cdot 17=14,17-1\cdot 14=3,14-4\cdot 3=2,3-1\cdot 2=1,}$ тому найбільший спільний дільник 65 та 48 дорівнює 1.

Див. також

• Подільність
• Алгоритм Евкліда