Необходимые сведения из элементарной теории чисел

1. Простым числомназывается натуральное число, имеющее только два неравных натуральных делителя.

2. Каждое натуральное число единственным образом, с точностью до порядка записи сомножителей, представляется в виде произведения степеней простых чисел.

3. Наибольшим общим делителемдвух целых чиселНОД(a,b)(или(a,b)) называется наибольшее целое, на которое без остатка делится какa,так иb.

4. Пусть a > b и d = (a,b). Тогда существуют целые x и у, являющиеся решением уравнения xa + yb = d. Если d = 1, то a и b называются взаимно простыми.

5. Наибольший общий делитель двух чисел можно найти с помощью алгоритма Эвклида. Для этого aделится с остатком наb, т.е.а = q₁b + r₁. Далее вместоaиb, рассматриваем соответственноbиr₁:b = q₂r₁+ r₂.На следующем шаге роль b и r₁, играют r₁ и r₂: r₁ = q₃r₂ + r₃ и т.д. Процесс заканчивается на некотором шаге k+1, для которого r_k+1= 0. Тогда НОД(a,b) = r_k. Рассмотрим пример.

Найти НОД(1547, 560) 1547 = 2 ^х560 + 427 560 = 1^х427 + 133 427 = 3^х133 + 28 133 = 4^х28 + 21 28 = 1^х21 + 7 21 = 3^х7 + 0 НОД(1547,560)=7

6. Для решения уравнения xa + yb = dможно использовать данные, полученные в каждом шаге алгоритма Эвклида, двигаясь снизу вверх, с помощью выражения остатка через другие элементы, используемые в соответствующем шаге. Например, изr₂ = q₄r₃ + r₄следуетr₄ = r₂ +q₄r₃.В последнем равенстве r₃ можно заменить, исходя из соотношения r₁ = q₃r₂ + r₃, т.е.r₄ = r₂ – q₄(q₃r₂ – r₁). Поэтомуr₄ = (1 – q₄q₃)r₂ + q₄r₁.Таким образом, мы выразили r₄ в виде целочисленной комбинации остатков с меньшими номерами, которые, в свою очередь, могут быть выражены аналогично. Продвигаясь “снизу вверх”, в конце концов, мы выразим r4 через исходные числа a и b. Если бы мы начали не с r₄, а с r_k, то получили бы r_k= xa + yb = d. Рассмотрим пример.

Решить 1547х + 560y = 7

7 = 28 – 1 ^х 21 = 28 – 1 ^х(133 — 4^х28) = 5^х 28 - 1^х 1ЗЗ = = 5^х (427 - 3^х 133) — 1^х 13З = 5^х 427 – 16^х (560 - 1^х 427)=

= 21 ^х 427 - 16^х 560 = 21^х (1547 - 2^х 560) - 16^х 560 = = 21^х547 - 58^х560

Решение: x = 21, y = -58

7. Число a сравнимо с числом b по модулю n, если a – b делится на n. Запись данного утверждения имеет следующий вид: а = b(mod n). Наименьшее неотрицательное число а, такое, что а = A(mod n) называется вычетом числа A по модулю n. Если (a,n) = 1, то существует x, такое, что x = a^-1 (mod n).

Действительно, (a,n) = 1 = d = ax + ny, поэтому ax = 1(mod n). Такое число x называется обратным к а по модулю n и записывается в виде a^-1 (mod n).

8. Пусть функция (n), гдеn— натуральное число, равна количеству натуральных чисел, меньшихn,для которых(а,n)=1. Такая функция называетсяфункцией Эйлера. Для чиселnвида n = (p_i— простое) функция Эйлера определяется какφ(n) = .

9. Теорема Эйлера. Пусть(а,n) = 1. Тогда a^φ(n) = 1(mod n).

Следствие. Еслиed = 1(mod φ(n))и(a, n) = 1, то(а^e)^d = а(mod n).

10. Для большинства вычетов по модулю n = pqпоказатель степени в соотношенииa^φ(n) = 1(mod n) может быть уменьшен, но в этом случае он зависит отa. Наименьший показательk(a),для которогоa^k(a) = 1(mod n), называетсяпорядком числа a по модулю nи обозначается какоrd_n(a). Для любогоaзначениеоrd_n(a)является делителем значения функции Эйлераφ(n).