2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Мультипликативное число?
Сообщение25.10.2010, 19:24 
Добрый вечер. Помогите пожалуйста, очень нужно.

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

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

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

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 19:33 
http://ru.wikipedia.org/wiki/Мультипликативная_функция

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

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 19:40 
Аватара пользователя
 i  Тема едет в Карантин до тех пор пока автор не даст определение, какое число называется мультипликативно обратным к числу $A$ по модулю $B$.

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

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 20:53 
Аватара пользователя
Вернул

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 21:08 
Ну а теперь осталось только воспользоваться расширенным алгоритмом Евклида...

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

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 21:34 
я посчитал. u=-439
v=293

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

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 21:37 
Аватара пользователя
Так это одно и то же. Тут не только операции понимаются в особенном смысле; тут само понятие одинаковых чисел - - -

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 21:41 
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)$.

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 21:59 
Мужики, я комбинированный метод не понимаю... объясните тупому пожалуйста как по Евклиду решить.

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 22:20 
timsand
Так вы же уже посчитали: $u = -439 \pmod{881}$.

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 22:48 
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$

 
 
 
 Re: Мультипликативное число?
Сообщение25.10.2010, 23:58 
Огромное всем спасибо! Я всё понял! )) Оказывается, не всё так сложно... ))

 
 
 [ Сообщений: 14 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group