Простые числа

Натуральное число р > 1 называется простым, если оно не имеет других на­туральных делителей, кроме 1 и p. Простым числом будет наименьший, отлич­ный от единицы делитель целого а, а > 1.

Теорема (Евклид). Существует бесконечно много простых чисел.

Отметим еще несколько свойств простых чисел (р – простое).

Свойство 1. (р,а)¹1=> р|а.

Свойство 2. p|ab=> р|а либо р|b.

Свойство легко обобщается на слу­чай нескольких чисел а, b, с,...

Теорема 2. Всякое целое, больше единицы, разложимо в произведе­ние простых множителей. Это разложение единственно с точностью до порядка следования множителей. В разложении некоторые множители могут повторяться. Если объединить повторения, то получается каноническое разложение числа а на простые множители:

.

3.1.6. Сравнения

Будем рассматривать целые числа в связи с остатками от их деления на натуральное т, называемое модулем. Если два целых а и b имеют одинаковые остатки от деления на т, то они называются сравнимыми по модулю т. Сравнимость чисел а и b записывают в виде

a º b(mod m).

Отметим следующие легко доказываемые либо очевидные свойства.

Свойство 1. a º b(mod m) Û m|a–b.

Свойство 2. a º b(mod m), b º c(mod m) => a º c(mod m).

Свойство 3. Сравнения можно почленно складывать.

Пусть а₁º b₁(mod m), а₂º b₂(mod m). Тогда (а₁+а₂)º(b₁ +b₂)(mod m).

Свойство 4. Сравнения можно почленно перемножать.

Аналогично предыдущему, (а₁а₂)º(b₁b₂)(mod m).

Свойство 5. К обеим частям сравнения можно прибавить одно и то же число.

Свойство 6. Обе части сравнения можно умножить на одно и то же число.

Свойство 7. Обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем.

Свойство 8. Обе части сравнения и модуль можно сокращать на их общий делитель.

Свойство 9. а º b(mod m₁), а º b(mod m₂)=> а º b(mod [m₁, m₂]).

Свойство 10. а º b(mod m), d|b, d|m, =>d|a.

Свойство 11. а º b(mod m), => (a,m)=(b,m).