Периодичность позволяет продолжить последовательность в обе стороны, определив как = a(8modf) (рИ всяком целом г (в том числе и отрицательном.)

Следствие 33.19

В конечной группе (S, ф) с единицей е для всякого а £ S выполняется равенство as = е. Доказательство

По теореме Лагранжа ord(a) \ \S\, откуда 15*1 = 0 (mod t), где t = ord(a). Упражнения 33.3-1

Напишите таблицы для групповых операций в группах (Z£, +4) и (Z*,, -5). Докажите, что эти группы изоморфны, то есть постройте взаимно-однозначное соответствие а между их элементами, удовлетворяющее следующему свойству: равенство а + Ь = с (mod 4) должно выполняться одновременно с равенством а (а) а(Ь) = а (с) (mod 5).

33.3-2

Докажите теорему 33.14 33.3-3

Пусть р - простое число, к - положительное целое число. Докажите, что <р(рк) =рк~г(р- 1). 33.3-4

Пусть п > 1 и а £ Z*. Докажите, что функция fa : Z* -> Z*, определяемая равенством fa(x) = ах mod п является перестановкой множества Z*.

33.3-5

Выпишите все подгруппы групп Zg и Z*3.

33.4. Решение линейных диофантовых уравнений

Нас будут интересовать целочисленные решения уравнения

ах = Ь (mod га),(33.22)

(здесь а, Ь и га - целые числа; такие уравнения называют «линейными диофантовыми уравнениями»). Ясно, что здесь ва- жен лишь остаток от деления х на га, так что решением (33.22) естественно называть не целое число, а элемент группы Ъп (класс чисел, дающих один и тот же остаток при делении на га). Таким образом, можно сформулировать задачу так: есть элементы а, Ь £ Zra, мы ищем все х £ Zra, для которых ах = Ь (mod га).

Напомним, что через (а) обозначается порождённая элементов а подгруппа (в данном случае подгруппа группы Zra). По определению (а) = {а : х > 0} = {ах mod га : х > 0}, поэтому уравнение

(33.22) имеет хотя бы одно решение тогда и только тогда, когда Ь £ (а). Сколько элементов вПо теореме Лагранжа (33.15)

это число является делителем га. Теорема 33.20

Для любых положительных целых а и га

(а) = (d) = {0, d,2d,..., ((n/d) - l)d},(33.23)

и

I (а) I = n/d,

где d = gcd (а, ra). Доказательство

Расширенный алгоритм Евклида в применении капп даёт тройку (d,x,yr), для которой d = gcd(a,ra) и ах + пу = d. Тогда ах = d (mod га), и потому d £ (а). С другой стороны, d есть делитель а, и потому а £ (d). Следовательно, (a) = (d) = {0,d,2d,... , ((n/d) - l)d}

Следствие 33.21

Уравнение ах = Ь (mod га) разрешимо относительно х тогда и только тогда, когда НОД(а, га) Ь. Следствие 33.22

Уравнение ах = Ь (mod га) имеет <i = gcd(a,ra) различных решений в Ъп или не имеет их вовсе.

Доказательство Если уравнение ах = Ь (mod га) имеет решение, то Ь £ (а). Согласно следствию 33.18, последовательность ах mod га (а и га фиксированы, ж = 0,1,...) периодична с периодом \{а)\ = n/d. Если Ь £ (а), то 6 встречается ровно один раз среди первых n/d членов рассматриваемой последовательности. При изменении г от 0 до га - 1 этот набор из n/d чисел проходится d раз и элемент Ь встречается d раз; соответствующие значения ж служат решениями уравнения ах = Ь (mod га).

Теорема 33.23

Пусть d = gcd (а, га) = ах Л-пу, где ж и у - целые числа (например, выдаваемые процедурой Extended-Euclid). Если d \ Ь, то число жо = x(b/d) (mod га) является решением уравнения ах = Ь (mod га).

Доказательство

По условию ах = <i (mod га), поэтому ажо = ax(b/d) = d(b/d) = 6 (mod га).

Теорема 33.24

Пусть уравнение ах = Ь (mod га) разрешимо, и жо является его решением. Тогда уравнение имеет d = gcd(a,6) решений в Ъп, задаваемых формулой Xi = жо + i(n/d), где г = 0,1, 2,... , га - 1.

Доказательство

Начав с жо и двигаясь с шагом n/d, мы сделаем d шагов, прежде чем замкнём круг. При этом все эти числа будут оставаться решениями уравнения ах = Ь (mod га), так как при увеличении ж на

n/d произведение ах увеличивается на n(a/d), то есть на кратное га. Таким образом, мы перечислили все d решений.

В соответствии со сказанным напишем процедуру, которая по целым числам а, 6 и га > 0 даёт все решения уравнения ах = Ь (mod га).

Modular-Linear-Equation-Solver(a,b,п)

1(d,x,у)\gets Extended-Euclid(a,n)

2if d b

3then x 0 \gets x (b/d) \bmod n

4for i \gets 0 to d-1

5do print (x 0+i(n/d)) \bmod n

6else print "нет решений"

Например, для уравнения 14ж = 30 (mod 100) (а = 14, 6 = 30 и га = 100) вызов процедуры Extended-Euclid в строке 1 даёт (d, х, у) = (2, -7,1). Поскольку 2 30, в строке 3 вычисляется жо = ( - 7) • (15) mod 100 = 95, и в строках 4-5 печатаются числа 95 и 45.

Процедура Modular-Linear-Equation-Solver (а, га) выполняет 0(lg п-\-НОД(а, га)) арифметических операций (O(lgra) в строке 1 и О (gcd (а, га)) в остальных строках).

Следствие 33.25

Пусть га > 1. Если gcd (а, га) = 1, то уравнение ах = Ь (mod га) имеет единственное решение (в Ъп).

Случай 6=1 особенно важен - при этом мы находит обратный к х элемент по модулю га (multiplicative inverse modulo га), то есть обратный в группе Z* элемент.

Следствие 33.26

Пусть га > 1. Если gcd (а, га) = 1, то уравнение

ах = 1 (mod га)(33.24)

имеет единственное решение в Ъп. При gcd (а, га) > 1 это уравнение решений не имеет.

Тем самым мы научились вычислять обратный элемент в группе Z* за О (lgra) арифметических операций.

Упражнения

33.4-1

Решите уравнение 35ж = 10 (mod 50). 33.4-2

Докажите, что если gcd(a,ra) = 1, то из ах = ay (mod га) следует уравнение ж = у (mod га). Покажите на пример, что условие gcd(a,ra) = 1 существенно.

33.4-3

Будет ли работать процедура Modular-Linear-Equation-Solver, если строку 3 в ней заменить на

3 then х 0 \gets х (b/d) \bmod (n/d)