1. Означення простого та взаємно-простого числа. Деякі теореми про прості числа

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

Число 1 має тільки один дільник, а саме 1, а кожне натуральне число а, відмінне від 1, має принаймні два дільники: 1 і а (тут і далі мова йде тільки про додатні дільники).

Означення 1.1 Відмінне від 1 натуральне число а називають простим, якщо воно не має дільників, відмінних від 1 і а. Його називають складеним, якщо воно має дільники, відмінні від 1 і а.

Простими є, наприклад, числа 2, 7, 13; числа 4, 9, 15 - складені. Число 1 не належить ні до простих, ні до складених чисел.

Доведемо кілька важливих теорем про прості числа.

Теорема 1.1 Всяке натуральне число а або ділиться на дане просте число р, або взаємно просте з р.

Справді, найбільший спільний дільник (а, р) як дільник числа р може дорівнювати або р, або 1. У першому випадку a ділиться на р, у другому а і р - взаємно прості числа.

Теорема 1.2 Якщо добуток кількох натуральних чисел ділиться на просте число р, то принаймні один із співмножників ділиться на р.

Справді, внаслідок попередньої теореми, кожен із співмножників або взаємно простий з р, або ділиться на р. Але якби всі множники були взаємно прості з р, то за теоремою їх добуток був би взаємно простий з р. Тому хоч один з множників ділиться на р.

Теорема 1.3 Найменший відмінний від 1 дільник більшого від 1 натурального числа а є число просте.

Нехай q - найменший дільник натурального числа а > 1. Якби q було числом складеним, то воно мало б дільник q₁, такий, що 1< q₁< q. Але тоді а ділилося б на q₁ і q не було б найменшим дільником числа а.

Теорема 1.4 Найменший відмінний від 1 дільник складеного числа а не більший за .

Нехай найменшим відмінним від 1 дільником числа а є q. Тоді а = q * a₁ де а₁ - деяке натуральне число, причому а₁ ? q, бо в противному разі q не було б найменшим додатним дільником числа а. Отже, а * a₁ ? qa₁ * q і тому а ? q², q ? .