Нахождение длины группы вычетов для заданного числа

Всё, что не упомянуто выше.

Нахождение длины группы вычетов для заданного числа

Сообщение Гость » Чт июн 13, 2019 7:26 pm

День добрый, столкнулся с проблемой при решении задачи.
Есть задача:
Задаём два числа: A и N (2 ≤ A < N ≤ 109).
к примеру: 7 и 20. Далее множим единицу на А, берём модуль N и называем это Z[1], множим Z[1] на А, берём модуль N и называем это Z[2] и так далее.
Начинаем считать остатки:
Z[1] = (1*7) modulo 20 = 7,
Z[2] = (7*7) modulo 20 = 9,
Z[3] = (9*7) modulo 20 = 3
Z[4] = (3*7) modulo 20 = 1

Необходимо найти номер остатка, который будет равен единице.
Есть ли способ для любой пары чисел найти длину группы вычетов (по сути вектора, в котором по порядку расположены остатки)?
Я понимаю, что длина расположена от 1 до значения функции эйлера от модуля N.
Гость
 

Re: Нахождение длины группы вычетов для заданного числа

Сообщение Гость » Чт авг 08, 2019 11:48 pm

"Вот то ли я дурак, то ли лыжи не едут?!"
Из условия задачи, очевидно, что N - число положительное, интервал для N[2;109) - вот зачем первым делом брать модуль этого числа!?
Как-то и вникать дальше - не интересно!
Гость
 


Вернуться в Алгебра