Пошаговое объяснение:
можно воспользоваться теоремой Эйлера, которая гласит:
если m и n - взаимно простые числа, и φ(n) - количество натуральных чисел взаимно простых с n и меньших чем n, то m^(φ(n)) - 1 делится на n.
значит, для любого n, при k = φ(n) - существует и удовлетворяет условию.
Что и требовалось доказать
Само доказательство теоремы Эйлера нет смысла переписывать. Его легко можно найти.
так же φ(n) называется функцией Эйлера
