Вычисление мультипликативных обратных элементов по заданному модулю — различия между версиями

Материал из Модулярная арифметики
Перейти к: навигация, поиск
(Новая страница: «Рассмотрим вопрос о мультипликативных обратных элементов по заданному модулю в фактор-…»)
 
Строка 2: Строка 2:
  
 
Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.
 
Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.
 +
 +
 +
'''Определение'''
 +
 +
Функция Эйлера <math>phi (n)</math> — это количество чисел от <math>1</math> до <math>n</math>, взаимно простых с <math>n</math>.
 +
 +
 +
Т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с <math>n</math> равен единице.
 +
 +
 +
'''Tеоремa Эйлера'''
 +
 +
Если <math>a</math> и <math>p</math> взаимно просты, то <math>a^{phi(p)} \equiv 1 \pmod p</math>, где <math>phi (n)</math> - функция Эйлера.
 +
 +
 +
Доказательство.
 +
 +
Пусть <math>x_1, \dots, x_{\varphi(p)}</math> — все различные натуральные числа, меньшие <math>p</math> и взаимно простые с ним.
 +
 +
Рассмотрим все возможные произведения <math>x_i a</math> для всех <math>i</math> от <math>1</math> до <math>\varphi(p)</math>.
 +
 +
Поскольку <math>a</math> взаимно просто с <math>p</math> и <math>x_i</math> взаимно просто с <math>p</math>, то и <math>x_i a</math> также взаимно просто с <math>p</math>, то есть <math>x_i a \equiv x_j\pmod p</math> для некоторого <math>j</math>.
 +
 +
Отметим, что все остатки <math>x_i a</math> при делении на <math>p</math> различны. Действительно, пусть это не так, то существуют такие <math>i_1 \neq i_2</math>, что
 +
: <math>x_{i_1} a \equiv x_{i_2} a\pmod p</math>
 +
или
 +
: <math>(x_{i_1} - x_{i_2}) a \equiv 0\pmod p</math>.
 +
 +
Так как <math>a</math> взаимно просто с <math>p</math>, то последнее равенство равносильно тому, что
 +
: <math>x_{i_1} - x_{i_2} \equiv 0\pmod p</math> или <math>x_{i_1} \equiv x_{i_2}\pmod p</math>.
 +
Это противоречит тому, что числа <math>x_1, \dots, x_{phi(p)}</math> попарно различны по модулю <math>p</math>.
 +
 +
Перемножим все сравнения вида <math>x_i a \equiv x_j\pmod p</math>. Получим:
 +
: <math>x_1 \cdots x_{phi(p)} a^{phi(p)} \equiv x_1 \cdots x_{phi(p)}\pmod p</math>
 +
или
 +
: <math>x_1 \cdots x_{phi(p)} (a^{phi(p)}-1) \equiv 0\pmod p</math>.
 +
Так как число <math>x_1 \cdots x_{phi(p)}</math> взаимно просто с <math>p</math>, то последнее сравнение равносильно тому, что
 +
: <math>a^{phi(p)}-1 \equiv 0\pmod p</math>
 +
или
 +
:<math>a^{phi(p)} \equiv 1\pmod p</math>.
 +
 +
 +
В частном случае, когда <math>p</math> простое, теорема Эйлера превращается в так называемую малую теорему Ферма:
 +
 +
'''Малая теорема Ферма'''
 +
 +
Если <math>p</math> - простое число и <math>a</math> - произвольное целое число, не делящееся на <math>p</math>, то <math>a^{p-1} \equiv 1 \pmod p </math>.

Версия 17:15, 4 сентября 2014

Рассмотрим вопрос о мультипликативных обратных элементов по заданному модулю в фактор-кольце Z_p.

Рассмотрим два способа вычисления обратных мультипликативных элементов. Первый способ основан на рассмотренном выше алгоритме Евклида, второй – на теореме Эйлера.


Определение

Функция Эйлера phi (n) — это количество чисел от 1 до n, взаимно простых с n.


Т.е. это количество таких натуральных чисел из отрезка [1; n], наибольший общий делитель (НОД) которых с n равен единице.


Tеоремa Эйлера

Если a и p взаимно просты, то a^{phi(p)} \equiv 1 \pmod p, где phi (n) - функция Эйлера.


Доказательство.

Пусть x_1, \dots, x_{\varphi(p)} — все различные натуральные числа, меньшие p и взаимно простые с ним.

Рассмотрим все возможные произведения x_i a для всех i от 1 до \varphi(p).

Поскольку a взаимно просто с p и x_i взаимно просто с p, то и x_i a также взаимно просто с p, то есть x_i a \equiv x_j\pmod p для некоторого j.

Отметим, что все остатки x_i a при делении на p различны. Действительно, пусть это не так, то существуют такие i_1 \neq i_2, что

x_{i_1} a \equiv x_{i_2} a\pmod p

или

(x_{i_1} - x_{i_2}) a \equiv 0\pmod p.

Так как a взаимно просто с p, то последнее равенство равносильно тому, что

x_{i_1} - x_{i_2} \equiv 0\pmod p или x_{i_1} \equiv x_{i_2}\pmod p.

Это противоречит тому, что числа x_1, \dots, x_{phi(p)} попарно различны по модулю p.

Перемножим все сравнения вида x_i a \equiv x_j\pmod p. Получим:

x_1 \cdots x_{phi(p)} a^{phi(p)} \equiv x_1 \cdots x_{phi(p)}\pmod p

или

x_1 \cdots x_{phi(p)} (a^{phi(p)}-1) \equiv 0\pmod p.

Так как число x_1 \cdots x_{phi(p)} взаимно просто с p, то последнее сравнение равносильно тому, что

a^{phi(p)}-1 \equiv 0\pmod p

или

a^{phi(p)} \equiv 1\pmod p.


В частном случае, когда p простое, теорема Эйлера превращается в так называемую малую теорему Ферма:

Малая теорема Ферма

Если p - простое число и a - произвольное целое число, не делящееся на p, то a^{p-1} \equiv 1 \pmod p .

Источник — «https://vscripts.ru/w/index.php?title=Вычисление_мультипликативных_обратных_элементов_по_заданному_модулю&oldid=981»