Question

Доказать теорему : если целые числа m и n взаимно просты,то найдется такое натуральное k ,что (m^k)-1 делится на n.

Answer 1

Ответ:

Пошаговое объяснение:

можно воспользоваться теоремой Эйлера, которая гласит:

если m и n - взаимно простые числа, и φ(n) - количество натуральных чисел взаимно простых с n и меньших чем n, то m^(φ(n)) - 1 делится на n.

значит, для любого n, при k = φ(n) - существует и удовлетворяет условию.

Что и требовалось доказать

Само доказательство теоремы Эйлера нет смысла переписывать. Его легко можно найти.

так же φ(n) называется функцией Эйлера