2016-06-24 01:14:00
#АПО_математика #Эйлер #ТеоремаЭйлера
И ещё одно математическое утверждение, названное в честь великого Леонарда Эйлера, на #АПО!
Теорема Эйлера - обобщение известной всякому олимпиаднику Малой теоремы Ферма. Теорема крайне полезна при решении сравнений.
Теорема Эйлера:
Пусть φ(n) - количество натуральных чисел, меньших n и взаимно простых с ним (к примеру, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4 и так далее).
Тогда для любых взаимно простых a и m верно, что a^φ(m) ≡ 1 (mod m).
Доказательство:
Обозначим k = φ(m).
Пусть x1 , … , xk — все различные натуральные числа, меньшие m и взаимно простые с ним.
Рассмотрим все возможные произведения xi*a. Поскольку a взаимно просто с m и xi взаимно просто с m, то и xi*a также взаимно просто с m, то есть xi*a ≡ xj (mod m) для некоторого j.
Отметим, что все остатки xi*a при делении на m различны. Действительно, пусть это не так, то существуют такие i1 ≠ i2, что xi1*a ≡ xi2*a (mod m), то есть (xi1 − xi2)*a ≡ 0 (mod m). Так как a взаимно просто с m, то последнее равенство равносильно тому, что xi1 − xi2 ≡ 0 (mod m) или xi1 ≡ xi2 (mod m). Это противоречит тому, что числа x1 , … , xk попарно различны по модулю m.
Перемножим все сравнения вида xi*a ≡ xj (mod m). Получим:
x1 ⋯ xk*a^k ≡ x1 ⋯ xk (mod m).
Значит,
x1 ⋯ xk*(a^k − 1) ≡ 0 (mod m).
Так как число x1 ⋯ xk взаимно просто с m, то последнее сравнение равносильно тому, что a^k − 1 ≡ 0 (mod m), то есть что a^k ≡ 1 (mod m). Вспомним, что мы обозначили k = φ(m). Тем самым, доказательство теоремы Эйлера завершено.
