Алёна решила сделать табличку степеней остатков по модулю 77 . В первой строке она выписала все остатки, взаимно простые с 77 , во второй строке — их квадраты, далее — кубы и т. д. В какой строке она впервые получит изначальную строку?
Остатки от деления на 77, взаимно простые с 77, образуют множество из 60 чисел: из 77 чисел выкидывается 7 кратных 11 и 10 оставшихся кратных 7 (10 потому что 0 не выкидываем дважды)
Если возвести любой из этих остатков в 60ю степень, то по модулю 77 результат будет равен 1 (теорема Эйлера).
Но минимальная степень, в которую можно возвести любой из этих остатков и получить 1 определяется функцией Кармайкла λ(77). Ее значение может быть меньше количества остатков, но обязательно является его делителем. Для числа 77 λ(77)=30
Значит в 30й строке Алена получит все 1, а в 31-й - вновь исходную строку. В 60й и 61й строке будет то же самое, но это уже будет не первый раз, а второй.
Ответ: в 31й строке
1 votes Thanks 0
reygen
Впервые слышу о такой функции, а как вы определили что λ(77)=30, есть определенная формула, или табличка по которой вы поняли что там 30
Amalgamma143
Формулы, как и для функции Эйлера боюсь нет, а табличка есть, да
reygen
Боюсь что на олимпиаде у вас такой таблички не будет, намного лучше решить данную задачу с использованием функции Эйлера и малой теоремы ферма
Amalgamma143
Если при этом можно получить 31 а не 61, то почему бы и нет
Answers & Comments
Остатки от деления на 77, взаимно простые с 77, образуют множество из 60 чисел: из 77 чисел выкидывается 7 кратных 11 и 10 оставшихся кратных 7 (10 потому что 0 не выкидываем дважды)
Если возвести любой из этих остатков в 60ю степень, то по модулю 77 результат будет равен 1 (теорема Эйлера).
Но минимальная степень, в которую можно возвести любой из этих остатков и получить 1 определяется функцией Кармайкла λ(77). Ее значение может быть меньше количества остатков, но обязательно является его делителем. Для числа 77 λ(77)=30
Значит в 30й строке Алена получит все 1, а в 31-й - вновь исходную строку. В 60й и 61й строке будет то же самое, но это уже будет не первый раз, а второй.
Ответ: в 31й строке