Необходимые сведения из элементарной теории чисел
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, т.е. а = q1b + r1. Далее вместо a и b, рассматриваем соответственно b и r1: b = q2r1+ r2. На следующем шаге роль b и r1, играют r1 и r2: r1 = q3r2
+ r3 и т.д. Процесс заканчивается на некотором шаге k+1, для которого rk+1= 0. Тогда НОД(a,b) = rk. Рассмотрим пример.
Найти НОД(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 можно использовать данные, полученные в каждом шаге алгоритма Эвклида, двигаясь снизу вверх, с помощью выражения остатка через другие элементы, используемые в соответствующем шаге. Например, из r2 = q4r3
+ r4 следует r4 = r2 +q4r3. В последнем равенстве r3 можно заменить, исходя из соотношения r1
= q3r2 + r3, т.е. r4 = r2 – q4(q3r2
– r1). Поэтому r4 = (1 – q4q3)r2
+ q4r1. Таким образом, мы выразили r4 в виде целочисленной комбинации остатков с меньшими номерами, которые, в свою очередь, могут быть выражены аналогично. Продвигаясь “снизу вверх”, в конце концов, мы выразим r4 через исходные числа a и b. Если бы мы начали не с r4, а с rk, то получили бы rk
= 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. Пусть функция j(n), где n — натуральное число, равна количеству натуральных чисел, меньших n, для которых (а,n)=1. Такая функция называется функцией Эйлера. Для чисел n вида
n = (pi — простое) функция Эйлера определяется как ?(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), для которого ak(a) = 1(mod n), называется порядком числа a по модулю n и обозначается как оrdn(a). Для любого a значение оrdn(a) является делителем значения функции Эйлера ?(n).
