Question

Алёна решила сделать табличку степеней остатков по модулю 77 . В первой строке она выписала все остатки, взаимно простые с 77 , во второй строке — их квадраты, далее — кубы и т. д. В какой строке она впервые получит изначальную строку?

Answer 1

Остатки от деления на 77, взаимно простые с 77, образуют множество из 60 чисел: из 77 чисел выкидывается 7 кратных 11 и 10 оставшихся кратных 7 (10 потому что 0 не выкидываем дважды)

Если возвести любой из этих остатков в 60ю степень, то по модулю 77 результат будет равен 1 (теорема Эйлера).

Но минимальная степень, в которую можно возвести любой из этих остатков и получить 1 определяется функцией Кармайкла λ(77). Ее значение может быть меньше количества остатков, но обязательно является его делителем. Для числа 77 λ(77)=30

Значит в 30й строке Алена получит все 1, а в 31-й - вновь исходную строку. В 60й и 61й строке будет то же самое, но это уже будет не первый раз, а второй.

Ответ: в 31й строке

Answer 2

Чтобы найти строку, в которой Алёна впервые получит изначальную строку, нужно рассмотреть остатки, взаимно простые с 77, и последовательно вычислять их степени по модулю 77, пока не получится изначальная строка. Начнем с первой строкой, где уже выписаны остатки, взаимно простые с 77. Эти остатки будут следующими:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76.

Теперь начнем вычислять их степени по модулю 77, пока не получится изначальная строка:

1. Квадраты: 1, 4, 9, 16, 25, 36, 49, 64, 1, 9, 21, 34, 49, 1, 25, 51, 2, 30, 60, 13, 46, 2, 36, 71, 18, 66, 25, 76, 37, 1, 64, 29, 96, 61, 28, 97, 66, 37, 8, 81, 54, 29, 4, 81, 58, 37, 18, 1, 84, 67, 52, 37, 24, 11, 84, 61, 40, 21, 4, 87, 70, 55, 42, 29, 16, 5, 94, 83, 74.

2. Кубы: 1, 8, 27, 64, 125, 216, 343, 512, 1, 27, 1331, 79507, и так далее.

Таким образом, изначальная строка (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, и так далее) повторяется во второй строке (квадраты) на пятом месте (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76).

Таким образом, Алёна впервые получит изначальную строку во второй строке (квадраты) на пятом месте.