Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгебра, теория чисел
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.74/19: Рейтинг темы: голосов - 19, средняя оценка - 4.74
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
#1

Mod с отрицательной степенью

23.04.2014, 17:59. Просмотров 3470. Ответов 20
Метки нет (Все метки)

Как высчитать мод с отрицательной степенью? Например: X^-y mod Z. По подробней, пожалуйста, если Вас не затруднит Спс !!
P.S.
"^" - степень. Т.е. X в степени -y. (На всякий случай )
0
Лучшие ответы (1)
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
23.04.2014, 17:59
Ответы с готовыми решениями:

1.Докажите, что если a ≡ b (mod n) и c ≡ d (mod n), то:
1.Докажите, что если a ≡ b (mod n) и c ≡ d (mod n), то:

Матрица в отрицательной степени
Здравствуйте. 1. Как возвести матрицу в степень -4? 2. Чтобы найти...

я в тупике. корень из чисел с отрицательной степенью
√(10^(-16)) какая степень будет??

X mod 3 = 2; x mod 5 = 3; x mod 15 = ?
x mod 3 = 2; x mod 5 = 3; x mod 15 = ? mod - остаток от деления

Что означает mod?
Что значит "M^e mod n" в шифровании RSA? Что означает mod? Извиняюсь если...

20
Alex5
1122 / 783 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
23.04.2014, 19:09 #2
Лучший ответ Сообщение было отмечено _MOHAX_ как решение

Решение

Если z простое, то для вычисления x-y mod z можно воспользоваться малой теоремой Ферма.
( Если x не делится на простое число p, то xp-1 = 1 (mod p). )

Пример.
316 = 1 ( mod 17 )
3-10 = 3-10 316 = 3-10+16 = 36 (mod 17 )

Добавлено через 14 минут
Другой способ.
Находим наибольший общий делитель x, z, применяя алгоритм Евклида
Если x , z взаимно просты, то 1 = НОД(x,z) = u x + v z, следовательно 1 = u x ( mod z ).
Пример.
3 = 23 - 5*4,
5 - 3 = -23 + 5*5 = 2,
3 - 2 = 2*23+(-9)*5 = 1.

(-9)*5 = 1 ( mod 23 ), 5-1 = -9 ( mod 23 ).
5
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
23.04.2014, 19:58  [ТС] #3
а от куда взяли "p"? Из первого примера.
0
helter
Эксперт по математике/физике
3756 / 2782 / 301
Регистрация: 12.03.2013
Сообщений: 5,126
23.04.2014, 21:20 #4
Я чего-то не понял: в сравнениях стоят настоящие числа, а не классы вычетов, а, скажем, 3-10 - не особо целое-то.
0
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
23.04.2014, 21:30  [ТС] #5
Предложите свой вариант решения? Мне было бы интересно)
0
helter
Эксперт по математике/физике
3756 / 2782 / 301
Регистрация: 12.03.2013
Сообщений: 5,126
23.04.2014, 21:35 #6
Если как в арифметике рассматривать сравнения только на целых числах, о каком решении может идти речь, задача не имеет смысла. А если работать в http://www.cyberforum.ru/cgi-bin/latex.cgi?{\mathbb R}/{\mathbb Z}, при целом Z задача становится тривиальной. Короче, формулировка бредова.
0
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
23.04.2014, 21:41  [ТС] #7
Позвольте спросить, причем здесь вообще сравнение? Что мы с чем сравниваем? Речь идет о решении непосредственно x^-y mod z уравнения и подобное ему. Я, конечно, ни чего не утверждаю, что вы сказали не в тему, но если опираться на данное уравнение, на мой взгляд, сравнения здесь не должно быть ни какого. Может я не прав...
0
Байт
Эксперт C
18100 / 11957 / 2483
Регистрация: 24.12.2010
Сообщений: 24,089
23.04.2014, 23:01 #8
Цитата Сообщение от _MOHAX_ Посмотреть сообщение
причем здесь вообще сравнение? Что мы с чем сравниваем?
Такова терминология. Уравнение x = y (mod z) называется во многих уважаемых работах сравнением по модулю z

Добавлено через 11 минут
ИМХО, когда эти уважаемые авторы говорили на эту тему, у них еще не поворачивался язык назвать это "уравнением над кольцом, или над полем". Хотя интуитивно они прекрасно понимали о чем идет речь, но термины "кольцо" и "поле" появились через несколько веков после ихних соображений "на полях". И опасаясь быть непонятыми коллегами, они свои уравнения называли сравнениями, дабы не вызывать ненужных ассоциаций.
Столбовая дорога математики вымощена не слишком удачной терминологией.
0
helter
Эксперт по математике/физике
3756 / 2782 / 301
Регистрация: 12.03.2013
Сообщений: 5,126
23.04.2014, 23:01 #9
_MOHAX_, дайте-ка для начала определение mod, которым вы пользуетесь.
0
Alex5
1122 / 783 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
24.04.2014, 14:29 #10
Цитата Сообщение от helter Посмотреть сообщение
Я чего-то не понял: в сравнениях стоят настоящие числа, а не классы вычетов
В сравнениях стоят именно классы вычетов.
Например, 5-2 по модулю 14 - это класс вычетов x (если такой существует),
для которого выполняется соотношение 52 x = 1 ( mod 14 ).

Добавлено через 13 минут
Цитата Сообщение от _MOHAX_ Посмотреть сообщение
а от куда взяли "p"? Из первого примера.
p обозначает произвольное простое число.
Если x не делится на 2, то x-1 делится на 2.
Если x не делится на 3, то x2-1 делится на 3.
Если x не делится на 5, то x4-1 делится на 5.
Если x не делится на 7, то x6-1 делится на 7.
...

Добавлено через 13 минут
Цитата Сообщение от _MOHAX_ Посмотреть сообщение
Позвольте спросить, причем здесь вообще сравнение? Что мы с чем сравниваем?
Сравнение по модулю натурального числа...
1
helter
Эксперт по математике/физике
3756 / 2782 / 301
Регистрация: 12.03.2013
Сообщений: 5,126
24.04.2014, 14:38 #11
Цитата Сообщение от Alex5 Посмотреть сообщение
В сравнениях стоят именно классы вычетов.
Это где вы такое вычитали?
0
Alex5
1122 / 783 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
24.04.2014, 17:33 #12
Цитата Сообщение от helter Посмотреть сообщение
Это где вы такое вычитали?
Используя сравнения по модулю n, мы тем самым отождествляем числа, отличающиеся на n.
(mod 5 ) -4 = 1 = 1+5 = 1+5+5 = ...
И значит 1, 6, 11,... можно рассматривать как обозначения одного объекта (класса вычетов [1] в кольце Z5).
1
helter
Эксперт по математике/физике
3756 / 2782 / 301
Регистрация: 12.03.2013
Сообщений: 5,126
24.04.2014, 20:16 #13
Цитата Сообщение от Alex5 Посмотреть сообщение
Используя сравнения по модулю n, мы тем самым отождествляем числа, отличающиеся на n.
(mod 5 ) -4 = 1 = 1+5 = 1+5+5 = ...
И значит 1, 6, 11,... можно рассматривать как обозначения одного объекта (класса вычетов [1] в кольце Z5).
Я всё же настаиваю, что запись a ≡ b (mod c) применяется только в том случае, когда a, b, c ― целые числа, а не классы вычетов. Аналогично, если J - идеал кольца R, для a, b ∈ R запись a ≡ b (mod J) означает, что a - b ∈ J. Если вы знаете литературу, в которой запись с mod использовалась для вычетов, прошу поделиться.
0
Alex5
1122 / 783 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
25.04.2014, 22:49 #14
Цитата Сообщение от helter Посмотреть сообщение
Я всё же настаиваю, что запись a ≡ b (mod c) применяется только в том случае, когда a, b, c ― целые числа, а не классы вычетов.
Так, с этим я вполне согласен. Когда я написал
Цитата Сообщение от Alex5 Посмотреть сообщение
В сравнениях стоят именно классы вычетов.
я имел в виду, что операции (умножения и сложения) в сравнении по модулю m эквивалентны
операциям (умножения и сложения) в кольце классов вычетов Zm.

И эту эквивалентность можно использовать для такого определения отрицательной степени по модулю m:
a-1 - это целое число, соответствующее элементу [a]m-1 кольца Zm. (x-1 обозначает элемент, обратный элементу x.)

В кольце Z5: [2]5 [3]5 = [1]5, и [2]5 = [3]5-1.
В соответствии с этим, 2*3 = 1 (mod 5), 2 = 3-1 (mod 5).

См. здесь пример в разделе Решение сравнений .
Modular Inverse (Ссылка взята из Modular multiplicative inverse )
0
helter
Эксперт по математике/физике
3756 / 2782 / 301
Регистрация: 12.03.2013
Сообщений: 5,126
25.04.2014, 23:06 #15
Ладно, обозначение само по себе кривое, но кто-то его использует (по крайней мере на сайтах), куда деваться. По моему мнению, хорошо и правильно так: либо использовать для вычетов скобки, черту или ничего вообще (пояснив, что действия выполняются в Z5, и поэтому 4 + 2 = 1 и 3-1 = 2.), при этом писать знак равенства и никаких mod. Либо же использовать для вычетов представителей и при этом писать знак сравнения и mod, а знаки действий имеют обычные значения, так что при этом 4 + 2 ≡ 1 (mod 5), а http://www.cyberforum.ru/cgi-bin/latex.cgi?3^{-1} = 1/3 вообще не включается в рамки теории. При сём и останусь. :P
0
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
27.04.2014, 14:47  [ТС] #16
Не совсем конечно понятно, можете показать эти 2 способа решения на примере? Например 5^-1 mod 8? Как решить этот пример по вашим способам?
0
Байт
Эксперт C
18100 / 11957 / 2483
Регистрация: 24.12.2010
Сообщений: 24,089
27.04.2014, 16:25 #17
Можно подбором
5*5 = 25 = 1 (mod 8) => 5-1 = 5 (mod 8)
Кстати, кольцо вычетов по модулю 8 обладает интересным свойством. Все элементы, имеющие обратные. (а это все нечетные) обратны самим себе.
2
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
27.04.2014, 18:29  [ТС] #18
Alex5, Не совсем конечно понятно, можете показать эти 2 способа решения на примере? Например 5^-1 mod 8? Как решить этот пример по вашим способам?
0
Alex5
1122 / 783 / 232
Регистрация: 12.04.2010
Сообщений: 2,012
28.04.2014, 17:47 #19
Цитата Сообщение от _MOHAX_ Посмотреть сообщение
Alex5, Не совсем конечно понятно
Чтобы получше понять, полезно самому попрактиковаться. Попробуйте, например, вычислить

http://www.cyberforum.ru/cgi-bin/latex.cgi?\;3^1(mod 5), \;3^2(mod 5), \;3^3(mod 5), \;3^4(mod 5), \;3^5(mod 5), \;

http://www.cyberforum.ru/cgi-bin/latex.cgi?\;3^0(mod 5), \;3^{-1}(mod 5), \;3^{-2}(mod 5) \;

Ещё упражнение. Чему равен НОД(10,6)? При каких x, y выполняется равенство НОД(10,6) = 10x + 6y ?
0
_MOHAX_
7 / 7 / 3
Регистрация: 22.06.2013
Сообщений: 173
28.04.2014, 17:57  [ТС] #20
Я тут нашел в книжке одной такой тип решения:
3^-1 mod 40
Решение:
40 1 0
3 0 1 q=13
1 1 -13

3^-1 mod 40 = 13
Вам знаком такой метод решения?
0
28.04.2014, 17:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.04.2014, 17:57

Решить уравнение (с mod)
1296x=1105(mod 2413)

док-ть что p mod 6 = 1 или 5
док-ть что p mod 6 = 1 или 5; p - простое >=5;

уравнение с дробной степенью
Требуется найти решение уравнения: (a+x)^{1.4}=k(2a-x) x - искомая...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2018, vBulletin Solutions, Inc.
Рейтинг@Mail.ru