ОСНОВНЫЕ СВЕДЕНИЯ ИЗ ТЕОРИИ

7. 1. Теорема 1.

Если аÎZ, тÎN, т >1 и (а; т) = 1 , – то в бесконечной последовательности степеней а¹, а², а³, ... , а^s, … , а^t, … найдутся хотя бы две степени с показателями s и t (s < t) такие, что . (*)

7. 2. Замечание. Обозначив t – s = k > 0, из (*) получим: . Возводя обе части этого сравнения в степень nÎN , получим: (**). Это означает, что существует бесконечное множество степеней числа a, удовлетворяющих сравнению (**). Но как найти эти показатели? Каков наименьший показатель, удовлетворяющий сравнению (**) ? На первый вопрос отвечает теорема Эйлера (1707 – 1783).

7. 3. Теорема Эйлера.

Если аÎZ, тÎN, т >1 и (а; т) = 1, – то . (13)

Пример. Пусть а = 2, т = 21, (а; т) = (2; 21) = 1. Тогда . Так как j (21) = 12, то 2¹² º 1(mod 21). В самом деле: 2¹² = 4096 и (4096 – 1) 21. Тогда очевидно, что 2²⁴ º 1(mod 21), 2³⁶ º 1(mod 21) и так далее. Но является ли показатель степени 12 – наименьшим, удовлетворяющим сравнению 2ⁿ º 1(mod 21) ? Оказывается, нет. Наименьшим показателем будет п = 6: 2⁶ º 1(mod 21), ибо 2⁶ – 1 = 63, а 63 21. Заметим, что наименьший показатель следует искать только среди делителей числа j(т) (в данном примере – среди делителей числа j(21) = 12 ).

7. 4. Малая теорема Ферма (1601 – 1665).

Для любого простого числа р и любого числа аÎZ, не делящегося на р, имеет место сравнение . (14)

Пример. Пусть а = 3, р = 5, где 3 не 5. Тогда или .

7. 5. Обобщёння теорема Ферма.

Для любого простого числа р и произвольного числа аÎZ имеет место сравнение (15)

ТИПОВЫЕ ЗАДАЧИ

1. Докажите, что 38 ⁷³ º 3(mod 35).

Решение.

1) Так как (38; 35) = 1, то по теореме Эйлера ; j(35) = 24, значит,

(1).

2) Из сравнения (1) по следствию 2 свойства 5⁰ числовых сравнений имеем:

(2) .

3) Из сравнения (2) по следствию 1 свойства 5⁰ сравнений: 38⁷²×38 º 1×38 (mod 35) Þ Þ38 ⁷³ º38 º 38–35 = 3(mod 35) Þ 38 ⁷³ º 3 (mod 35), что и требовалось доказать.

2. Дано: а = 4, т = 15. Найти наименьший показатель степени k, удовлетворяющий сравнению (*)

Решение.

1) Так как (a; m) = (4; 25) = 1, то по теореме Эйлера , j(25) = 20, поэтому .

2) Является ли найденный показатель степени – число 20 – наименьшим натуральным числом, удовлетворяющим сравнению (*)? Если существует показатель степени, меньший 20, то он должен быть делителем числа 20. Значит, искомый наименьший показатель k надо искать среди множества чисел n = {1, 2, 4, 5, 10, 20}– делителей числа 20.

3) При п = 1: ;