Элементы теории чисел. Функция Эйлера. Теорема Ферма.

· При разработке алгоритмов шифрования используется ряд понятий теории чисел и модулярной арифметики. Теория чисел, или высшая арифметика, изучает свойства целых чисел. Как наука она оформилась, начиная с открытий П. Ферма. Под целыми числами понимают числа …, -4, -3, -2, -1, 0, 1, 2, 3, 4, … Особое место среди целых чисел занимают натуральные числа – целые положительные числа 1, 2, 3, 4, … Высшая арифметика — дедуктивная наука, основанная на законах арифметики. Целые числа образуют бесконечный ряд (множество) Z, где выполняются основные арифметические операции: сложение, вычитание и умножение. Частное от деления целых чисел не всегда является целым числом. Поэтому множество целых чисел образует кольцо. Мы назовём одно число a делителем другого числа b, если b = a ⋅ c для некоторого числа c. Примем обозначение a / b, означающее, что a делит b нацело, или a является делителем b. Если число a не является делителем другого числа b, то используем обозначение: a не делит b. Натуральное число p называется простым, если p > 1 и не имеет положительных делителей, отличных от 1 и p. Натуральное число N называется составным, если N > 1 и имеет, по крайней мере, один положительный делитель, отличный от 1 и N.

· Функция Эйлера φ(n) — мультипликативная арифметическая функция, равная количеству натуральных чисел, меньших n и взаимно простых с ним. При этом полагают, что число 1 взаимно просто со всеми натуральными числами, и φ(1) = 1.

Например, для числа 24 существует 8 взаимно простых с ним чисел (1, 5, 7, 11, 13, 17, 19, 23), поэтому φ(24) = 8.

Названа в честь Эйлера, который впервые использовал её в 1760 году в своих работах по теории чисел для доказательства малой теоремы Ферма, а затем и для доказательства более общего утверждения — теоремы Эйлера. Позднее функцию использовал Гаусс в своем труде «Арифметические исследования» (Disquisitiones Arithmeticae (англ.)), вышедшем в свет в 1801 году. Гаусс ввёл ставшее стандартным обозначение φ(n).

Функция Эйлера находит применение в вопросах, касающихся теории делимости и вычетов, теории чисел, криптографии. Функция Эйлера играет ключевую роль в алгоритме RSA.

Функция Эйлера показывает, сколько натуральных чисел из отрезка имеют c только один общий делитель - единицу. Функция Эйлера определена на множестве натуральных чисел, и значения ее лежат в множестве натуральных чисел.

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

· Ма́лая теоре́ма Ферма́ — классическая теорема теории чисел, которая утверждает, что

Если p — простое число, и а не делится на р, то а^р-1 = 1 (mod p). Другими словами, а^р-1 при делении нацело на р даёт в остатке 1.

Равносильная формулировка:

Для любого простого р и целого а:

(а^р-а) делится на р

Если — простое число, а и — такие положительные целые числа, что , тогда . Это утверждение используется в системе шифрования с открытым ключом RSA.

Если — простое число, отличное от 2 и 5, то число , запись которого состоит из одних девяток, делится на . Отсюда легко следует, что для любого целого числа , которое не делится на 2 и на 5, можно подобрать число, состоящее только из девяток, которое делится на . Этот факт используется в теории признаков делимости и периодических дробей.

Малая теорема Ферма является частным случаем теоремы Эйлера, которая, в свою очередь, является частным случаем теорем Кармайкла и Лагранжа для конечных циклических групп.