Question

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

Answer 1

Ответ:

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

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

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

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

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

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

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

Answer 2

Для доказательства данной теоремы, мы будем использовать малую теорему Ферма, которая гласит следующее:

Если p - простое число, а a - целое число, которое не делится на p, то (a^(p-1)) ≡ 1 (mod p).

Теперь, давайте докажем вашу теорему:

Пусть m и n - взаимно простые целые числа. Это означает, что gcd(m, n) = 1, где gcd обозначает наибольший общий делитель.

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

(m^k) ≡ 1 (mod n).

Мы хотим, чтобы это уравнение выполнялось. Давайте рассмотрим целое число k такое, что:

k = φ(n),

где φ(n) обозначает функцию Эйлера (функцию Эйлера от n), которая представляет количество натуральных чисел от 1 до n-1, взаимно простых с n.

Теперь мы видим, что по малой теореме Ферма:

(m^(φ(n))) ≡ 1 (mod n).

Таким образом, (m^(φ(n)) - 1) делится на n, что и требовалось доказать.

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