Мультипликативное число?

[timsand]

Добрый вечер. Помогите пожалуйста, очень нужно.

Нужно умножить число 1129 на мультипликативное обратное 588 по модулю 881
Я не понимаю как это посчитать.
Но есть ответ. Т.е. 1129 * 442 mod 881 = 372
Как получили число 442?

какое число называется мультипликативно обратными к числу по модулю ?
Пример: Вычисляется число $d$, мультипликативно обратное к числу $e$ по модулю $q$, то есть число, удовлетворяющее условию:
$ de = 1 (\mod q)$ или: $de=1+kq$. где $k$ некоторое целое число.

[ИСН]

Да ладно посчитать. Понять бы. Слова-то какие страшные. Мультипликативное, обратное... Что они значат?

[timsand]

http://ru.wikipedia.org/wiki/Мультипликативная_функция

обратное это:
например число 550 обратное для этого числа 1\550

[Toucan]

Тема едет в Карантин до тех пор пока автор не даст определение, какое число называется мультипликативно обратным к числу $A$ по модулю $B$.

После того как исправите сообщение, напишите в Сообщение в карантине исправлено, чтобы кто-нибудь из модераторов вернул Вашу тему в учебный раздел.

[Toucan]

Вернул

[Maslov]

Ну а теперь осталось только воспользоваться расширенным алгоритмом Евклида...

[Joker_vD]

Вам надо найти $u, v$ такие, что $588u + 881v = 1$, тогда $u$ и будет "мультипликативно обратным". Ну, воспользуйтесь алгоритмом Евклида.

[timsand]

я посчитал. u=-439
v=293

по теории моё u должно быть равно 442. или я что-то путаю?

[ИСН]

Так это одно и то же. Тут не только операции понимаются в особенном смысле; тут само понятие одинаковых чисел - - -

[VAL]

Joker_vD в сообщении #366207 писал(а):

Вам надо найти $u, v$ такие, что $588u + 881v = 1$, тогда $u$ и будет "мультипликативно обратным". Ну, воспользуйтесь алгоритмом Евклида.

Я всегда (до появления мат. пакетов) предпочитал решать сравнения т.н. комбинированным методом, а не алгоритмом Евклида (или применением теоремы Эйлера). Как правило, вычислений на порядок меньше.
Например, в нашем случае имеем: $588x\equiv 1(881)$
Умножив обе части сравнения на 3 (взаимно простое с 881), получим $2x\equiv 3(881)$. Значит, $2x\equiv 3+884(881)$, откуда $x\equiv 442(881)$.

[timsand]

Мужики, я комбинированный метод не понимаю... объясните тупому пожалуйста как по Евклиду решить.

[Joker_vD]

timsand
Так вы же уже посчитали: $u = -439 \pmod{881}$.

[VAL]

timsand в сообщении #366238 писал(а):

Мужики, я комбинированный метод не понимаю... объясните тупому пожалуйста как по Евклиду решить.

Может так понятнее будет?
Вы получили:
$1=-439\cdot 588+293\cdot 881=-439\cdot 588+881\cdot 588-588\cdot 881+293\cdot 881=(881-439)588+(293-588)881=442\cdot 588-295\cdot 881$

[timsand]

Огромное всем спасибо! Я всё понял! )) Оказывается, не всё так сложно... ))