Мультипликативное обратное как найти – Сайт, где вы сможете решить свои вопросы

Обратное по модулю целого a — это такое целое число x, что произведение ax сравнимо с 1 по модулю m^[1]. В стандартных обозначениях модульной арифметики эта эквивалентность записывается как:

${displaystyle axequiv 1{pmod {m}},}$

что является сокращённым способом записи утверждения, что m делит (без остатка) величину ax − 1, или, выражаясь другим способом, остаток от деления ax на целое m равен 1. Если a имеет обратный по модулю m, то имеется бесконечное количество решений этой эквивалентности, которые образуют класс вычетов для этого модуля. Более того, любое целое, которое эквивалентно a (то есть из класса эквивалентности a) будет иметь любой элемент класса эквивалентности x в качестве обратного элемента. Используя обозначения $overline {w}$ для класса эквивалентности, содержащего $w$ , утверждение выше может быть записано следующим образом: обратный элемент по модулю класса эквивалентности ${overline {a}}$ есть класс эквивалентности $overline{x}$ , такой что

${displaystyle {overline {a}}cdot _{m}{overline {x}}={overline {1}},}$

где символ ${displaystyle cdot _{m}}$ означает умножение классов эквивалентности по модулю m^[2]. Такой вид записи представляет аналог обычной концепции обратного числа в множестве рациональных или вещественных чисел, если заменить числа классами эквивалентности и должным образом определения бинарных операций.

Фундаментальное использование этой операции — решение линейной эквивалентности вида:

${displaystyle axequiv b{pmod {m}}.}$

Нахождение модульного обратного имеет практическое приложение в области криптографии, например, криптосистема с открытым ключом и алгоритм RSA ^[3]^[4]^[5]. Преимущество для реализации этих приложений в том, что существует очень быстрый алгоритм (расширенный алгоритм Евклида), который может быть использован для вычисления модульных обратных.

Модульная арифметика[править | править код]

Говорят, что для данного положительного числа m два целых числа a и b сравнимы по модулю m, если m делит их разность. Это бинарное отношение обозначается как

${displaystyle aequiv b{pmod {m}}.}$

Это является отношением эквивалентности на множестве целых чисел $mathbb {Z}$ , и классы эквивалентности называются классами вычетов по модулю m. Пусть ${overline {a}}$ означает класс эквивалентности, содержащий целое число a^[6], тогда

${displaystyle {overline {a}}={bin mathbb {Z} mid aequiv b{pmod {m}}}.}$

Линейное сравнение — это сравнение по модулю вида

${displaystyle axequiv b{pmod {m}}.}$

В отличие от линейных уравнений в целых числах, линейное сравнение может иметь ноль, одно или несколько решений. Если x является решением линейного сравнения, то любой элемент из $overline{x}$ также является решением, так что, если говорится о количестве решений линейного сравнения, подразумевается количество различных классов эквивалентности, которые содержат эти решения.

Если d является наибольшим общим делителем чисел a и m, то линейное сравнение ${displaystyle axequiv b{pmod {m}}}$ имеет решения тогда и только тогда, когда d делит b. Если d делит b, то существует ровно d решений^[7].

Модульное обратное целого числа a по модулю m — это решение линейного сравнения

${displaystyle axequiv 1{pmod {m}}.}$

Ранее говорилось, что решение существует тогда и только тогда, когда наибольший общий делитель a и m равен 1, то есть a и m должны быть взаимно простыми числами. Более того, если это условие выполняется, существует ровно одно решение, то есть, если решение существует, модульное обратное единственно^[8].

Если ${displaystyle axequiv 1{pmod {m}}}$ имеет решение, оно обозначается часто следующим образом

${displaystyle xequiv a^{-1}{pmod {m}},}$

однако это можно считать злоупотреблением^[en], поскольку может неверно интерпретироваться как обычное обратное числа $a$ (которое, в отличие от модульного обратного, не является целым за исключением случаев, когда a равно 1 или -1). Обозначение было бы приемлемым, если бы a интерпретировался как обозначение для класса вычетов ${overline {a}}$ , поскольку обратный элемент класса вычетов снова является классом вычетов с операцией умножения, определённой в следующем разделе.

Целые по модулю m[править | править код]

Отношение эквивалентности по модулю m разбивает множество целых чисел на m классов эквивалентности. Операции сложения и умножения можно определить на этих объектах следующим образом: для сложения или умножения классов эквивалентности сначала любым способом выбираются представители этих классов, затем осуществляется обычная операция над отобранными целыми числами и, наконец, результат операции лежит в классе вычетов, являющемся результатом операции над классами. В символической форме, с ${displaystyle +_{m}}$ и ${displaystyle cdot _{m}}$ представляющими операции над классами вычетов, эти определения можно записать как

${displaystyle {overline {a}}+_{m}{overline {b}}={overline {a+b}}}$

${displaystyle {overline {a}}cdot _{m}{overline {b}}={overline {ab}}.}$

Эти операции вполне определены (что означает, что конечный результат не зависит от выбора представителей).

Классы вычетов по m с этими двумя операциями образуют кольцо, называемое кольцом целых чисел по модулю m. Имеется несколько обозначений, используемых для этих алгебраических объектов, наиболее часто используется $mathbb{Z}/mmathbb{Z}$ или ${displaystyle mathbb {Z} /m}$ , однако некоторые элементарные учебники и приложения используют упрощённое обозначение $mathbb {Z} _{m}$ , если не возникает противоречие с другими алгебраическими объектами.

Классы вычетов целых чисел по модулю m были традиционно известны как классы остатков по модулю m, что отражает факт, что все элементы класса эквивалентности имеют один и тот же остаток от деления на m. Любое множество из m целых, выбранных из разных классов вычетов по модулю m называется полной системой вычетов по модулю m^[9]. Деление столбиком показывает, что множество целых чисел {0, 1, 2, …, m − 1} образуют полную систему вычетов по модулю m, известную как наименьшая система вычетов по модулю m. При работе с арифметическими задачами иногда удобнее работать с полной системой вычетов и использовать язык эквивалентности, в то время как в других случаях более удобен взгляд с точки зрения классов эквивалентности кольца $mathbb{Z}/mmathbb{Z}$ ^[10].

Мультипликативная группа кольца вычетов[править | править код]

Не всякий элемент полной системы вычетов по модулю m имеет обратный элемент, например, нуль обратного не имеет. После удаления элементов полной системы вычетов, что не взаимно просты с m, оставшиеся элементы, которые называются приведённой системой вычетов, все имеют обратные. Число элементов в приведённой системе вычетов равно ${displaystyle phi (m)}$ , где $phi$ есть функция Эйлера, то есть количество положительных целых чисел меньших m, которые взаимно просты с m.

В кольце с единицей общего вида не всякий элемент имеет обратный, а те, что имеют, называются обратимыми. Поскольку произведение обратимых элементов обратимо, обратимые элементы кольца образуют группу, группу обратимых элементов кольца, и эта группа часто обозначается как ${displaystyle R^{times }}$ , если R является названием кольца. Группа обратимых элементов кольца целых чисел по модулю m называется мультипликативной группой целых по модулю m, и она изоморфна приведённой системе вычетов. В частности, её порядок (размер) равен ${displaystyle phi (m)}$ .

Когда m является простым, скажем p, то ${displaystyle phi (p)=p-1}$ и все ненулевые элементы $mathbb{Z}/pmathbb{Z}$ имеют обратные, а тогда $mathbb{Z}/pmathbb{Z}$ является конечным полем. В этом случае мультипликативная группа целых чисел по модулю p образует циклическую группу порядка p − 1.

Пример[править | править код]

Для иллюстрации вышеприведённых определений рассмотрим пример чисел по модулю 10.

Два числа эквивалентны по 10 тогда и только тогда, когда их разность делится на 10, например

${displaystyle 32equiv 12{pmod {10}}}$ поскольку 10 делит 32 − 12 = 20,

${displaystyle 111equiv 1{pmod {10}}}$ поскольку 10 делит 111 − 1 = 110.

Некоторые из классов вычетов по этому модулю:

${displaystyle {overline {0}}={cdots ,-20,-10,0,10,20,cdots }}$

${displaystyle {overline {1}}={cdots ,-19,-9,1,11,21,cdots }}$

${displaystyle {overline {5}}={cdots ,-15,-5,5,15,25,cdots }}$

${displaystyle {overline {9}}={cdots ,-11,-1,9,19,29,cdots }.}$

Линейное сравнение ${displaystyle 4xequiv 5{pmod {10}}}$ не имеет решений, поскольку целые, конгруэнтные 5 (то есть, входящие в ${displaystyle {overline {5}}}$ ) все нечётные, в то время как 4x все чётные. Однако линейное сравнение ${displaystyle 4xequiv 6{pmod {10}}}$ имеет два решения, а именно, ${displaystyle x=4}$ и ${displaystyle x=9}$ . НОД(4, 10) = 2 и 2 не делит 5, но делит 6.

Поскольку НОД(3, 10) = 1, линейное сравнение ${displaystyle 3xequiv 1{pmod {10}}}$ будет иметь решения, то есть, модульное обратное числа 3 по модулю 10 будет существовать. 7 удовлетворяет этому уравнению (21 − 1 = 20). Однако и другие целые удовлетворяют этому уравнению, например 17 и −3 (поскольку 3(17) − 1 = 50 и 3(−3) − 1 = −10). В частности, любое целое число из ${displaystyle {overline {7}}}$ будет удовлетворять уравнению, поскольку эти числа имеют вид 7 + 10r для некоторого r и ясно, что

${displaystyle 3(7+10r)-1=21+30r-1=20+30r=10(2+3r),}$

делится на 10. Это уравнение имеет только один класс вычетов в качестве решений. Решение в этом случае может быть получено просто перебором возможных классов, но для получения решения для больших модулей нужны систематические алгоритмы, и они будут представлены в следующих разделах.

Произведение классов вычетов ${displaystyle {overline {5}}}$ и ${displaystyle {overline {8}}}$ может быть получено путём выбора элемента из ${displaystyle {overline {5}}}$ , скажем 25, и элемента из ${displaystyle {overline {8}}}$ , скажем −2, и их произведение (25)(−2) = −50 находится в классе эквивалентности $overline {0}$ . Таким образом, ${displaystyle {overline {5}}cdot _{10}{overline {8}}={overline {0}}}$ . Сложение определяется аналогично. Десять классов вычетов вместе с этими операциями сложения и умножения классов вычетов образует кольцо целых чисел по модулю 10, то есть ${displaystyle mathbb {Z} /10mathbb {Z} }$ .

Полной системой вычетов по модулю 10 может быть множество {10, −9, 2, 13, 24, −15, 26, 37, 8, 9}, где каждое целое лежит в своём классе вычетов по модулю 10. Минимальной системой вычетов по модулю 10 служит {0, 1, 2, …, 9}. Приведённой системой вычетов по модулю 10 может быть {1, 3, 7, 9}. Произведение любых двух классов вычетов, представленных этими числами, снова является один из этих четырёх классов. Из этого следует, что эти четыре класса вычетов образуют группу, в этом случае циклическую группу порядка 4, имеющую в качестве генератора 3 или 7. Представленные классы вычетов образуют группу обратимых элементов кольца ${displaystyle mathbb {Z} /10mathbb {Z} }$ . Эти классы вычетов в точности те, что имеют обратные по модулю.

Вычисление[править | править код]

Расширенный алгоритм Евклида[править | править код]

Модульное обратное для числа a по модулю m можно найти с помощью расширенного алгоритма Евклида.

Алгоритм Евклида определяет наибольший общий делитель (НОД) двух целых чисел, скажем a и m. Если a имеет обратное по модулю m число, этот НОД должен быть равен 1. Несколько последних равенств, получаемых в процессе работы алгоритма, могут быть решены для нахождения НОД. Затем, используя метод «обратной подстановки», может быть получено выражение, связывающее исходные параметры и НОД. Другими словами, могут быть найдены целые x и y, удовлетворяющие равенство Безу,

${displaystyle ax+my={text{НОД }}(a,m)=1.}$

Перепишем это следующим образом

${displaystyle ax-1=(-y)m,}$

то есть,

${displaystyle axequiv 1{pmod {m}},}$

и модульное обратное числа a вычислено. Более эффективной версией является расширенный алгоритм Евклида, который с помощью дополнительных равенств сокращает два прохода алгоритма (обратную подстановку можно понимать как прохождение алгоритма в обратном порядке) до одного.

В нотации O большое этот алгоритм работает за время ${displaystyle O(log(m)^{2})}$ в предположении, что ${displaystyle |a|<m}$ , и считается очень быстрым. Он обычно более эффективен чем альтернативный экспоненциальный алгоритм.

Использование теоремы Эйлера[править | править код]

В качестве альтернативы расширенному алгоритму Евклида для вычисления модульного обратного элемента можно рассматривать использование теоремы Эйлера^[11].

Согласно теореме Эйлера, если a взаимно просто с m, то есть НОД(a, m) = 1, то

${displaystyle a^{phi (m)}equiv 1{pmod {m}},}$

где $phi$ — функция Эйлера. Это следует из факта, что a принадлежит мультипликативной группе ${displaystyle (mathbb {Z} /mmathbb {Z} )^{times }}$ тогда и только тогда, когда a взаимно просто с m. Таким образом, модульное обратное можно найти напрямую:

${displaystyle a^{phi (m)-1}equiv a^{-1}{pmod {m}}.}$

В специальном случае, когда m простое, ${displaystyle phi (m)=m-1}$ и модульное обратное задаётся равенством

${displaystyle a^{-1}equiv a^{m-2}{pmod {m}}.}$

Этот метод, как правило, медленнее расширенного алгоритма Евклида, но иногда используется, если реализация для модульного возведения в степень уже доступна. Недостатки этого метода:

Замечательное преимущество этой техники в том, что нет условных ветвлений, которые зависят от значения a, а потому значение a, которое может быть важным секретом в криптосистемах с открытым ключом, может быть защищено от атак по сторонним каналам. По этой причине стандартная реализация Curve25519 использует технику вычисления обратного элемента.

Вычисление нескольких обратных[править | править код]

Можно вычислить обратные для нескольких чисел $a_{i}$ по общему модулю m используя один проход алгоритма Евклида и три умножения на каждое дополнительное входное число^[12]. Основной идеей является образование всех $a_{i}$ , обращение его, а затем умножение на $a_{j}$ для всех ${displaystyle jneq i}$ , чтобы остался только ${displaystyle a_{i}^{-1}}$ .

Алгоритм (вся арифметика осуществляется по модулю m):

Вычисляем префиксные произведения ${textstyle b_{i}=prod _{j=1}^{i}a_{j}=a_{i}b_{i-1}}$ для всех ${displaystyle ileqslant n}$ .
Вычисляем ${displaystyle b_{n}^{-1}}$ с помощью любого доступного алгоритма.
Для i от n до 2 вычисляем
- ${displaystyle a_{i}^{-1}=b_{i}^{-1}b_{i-1}}$ и
- ${displaystyle b_{i-1}^{-1}=b_{i}^{-1}a_{i}}$ .
Наконец, ${displaystyle a_{1}^{-1}=b_{1}^{-1}}$ .

Можно осуществить умножение в виде древесной структуры, а не линейной, чтобы обеспечить параллельность вычислений.

Приложения[править | править код]

Поиск модульного обратного имеет много приложений в алгоритмах, опирающихся на теорию модульной арифметики. Например, в криптографии использование модульной арифметики позволяет осуществлять некоторые операции быстрее и с меньшими требованиями к памяти, в то время как другие операции становится выполнить труднее^[13]. Оба этих свойства могут использоваться во благо. В частности, в алгоритме RSA шифрование и обратный этому процесс сообщения делается с помощью пары чисел, обратных друг другу по некоторому тщательно выбранному модулю. Один из этих чисел делается открытым, и он может быть использован в быстрой процедуре шифрования, в то время как другое число используется в процедуре расшифровки и не разглашается. Определение скрытого ключа по открытому считается невыполнимой задачей, так как вычислительной мощности на её решение требуется больше, чем есть на Земле, что и защищает от несанкционированного доступа^[14].

В качестве другого использования в другом контексте рассмотрим задачу точного деления в компьютерах, когда дан список нечётных чисел размером в компьютерное слово, каждое из которых делится на k, и нужно разделить их на k. Одно из решений следующее:

Используем расширенный алгоритм Евклида для вычисления $k^{{-1}}$ , модульного обратного ${displaystyle k{pmod {2^{w}}}}$ , где w равно числу бит в слове. Это обратное существует, поскольку все числа нечётные, а рассматриваются вычеты по модулю, не имеющему нечётных делителей.
Каждое число в списке умножаем на $k^{{-1}}$ и выбираем наименее значащие биты результата (то есть отбрасываем все биты за пределами компьютерного слова).

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

Модульные обратные числа используются для получения решения системы линейных сравнений, что гарантируется китайской теоремой об остатках.

Например, система

${displaystyle {begin{cases}Xequiv 4{pmod {5}}\Xequiv 4{pmod {7}}\Xequiv 6{pmod {11}}\end{cases}}}$

имеет общее решение, поскольку 5, 7 и 11 попарно взаимно просты. Решение даётся формулой

${displaystyle X=t_{1}(7times 11)times 4+t_{2}(5times 11)times 4+t_{3}(5times 7)times 6}$

где

${displaystyle t_{1}=3}$ модульное обратное ${displaystyle 7times 11{pmod {5}}}$ ,

${displaystyle t_{2}=6}$ модульное обратное ${displaystyle 5times 11{pmod {7}}}$ ,

${displaystyle t_{3}=6}$ модульное обратное ${displaystyle 5times 7{pmod {11}}}$ .

Тогда,

${displaystyle X=3times (7times 11)times 4+6times (5times 11)times 4+6times (5times 7)times 6=3504}$

и в приведённом виде

${displaystyle Xequiv 3504equiv 39{pmod {385}}}$

поскольку 385 является наименьшим общим кратным чисел 5, 7 и 11.

Модульное обратное фигурирует на видном месте в определении сумм Клоостермана.

См. также[править | править код]

Инверсный конгруэнтный метод — алгоритм генерации псевдослучайных чисел, использующий обратные по модулю числа.
Восстановление рационального числа по его модулю^[en]

Примечания[править | править код]

↑ Rosen, 1993, с. 132.
↑ Schumacher, 1996, с. 88.
↑ Stinson, 1995, с. 124–128.
↑ Trappe, Washington, 2006, с. 164−169.
↑ Moriarty, K.; Kaliski, B.; Jonsson, J.; Rusch, A. PKCS #1: RSA Cryptography Specifications Version 2.2. Internet Engineering Task Force RFC 8017. Internet Engineering Task Force (2016). Дата обращения: 21 января 2017. Архивировано 12 декабря 2018 года.
↑ Other notations are often used, including [a] and [a]_m.
↑ Ireland, Rosen, 1990, с. 32.
↑ Shoup, 2005, с. 15 Theorem 2.4.
↑ Rosen, 1993, с. 121.
↑ Ireland, Rosen, 1990, с. 31.
↑ Koshy, 2007, с. 346.
↑ Brent, Zimmermann, 2010, с. 67–68.
↑ Trappe, Washington, 2006, с. 167.
↑ Trappe, Washington, 2006, с. 165.

Литература[править | править код]

Douglas R. Stinson. Cryptography / Theory and Practice. — CRC Press, 1995. — ISBN 0-8493-8521-0.
Victor Shoup. A Computational Introduction to Number Theory and Algebra. — Cambridge University Press, 2005. — ISBN 9780521851541.
Thomas Koshy. Elementary number theory with applications. — 2nd edition. — Academic Press, 2007. — ISBN 978-0-12-372487-8.
Richard P. Brent, Paul Zimmermann. §2.5.1 Several inversions at once // Elementary number theory with applications. Modern Computer Arithmetic. — Cambridge University Press, 2010. — Т. 18. — (Cambridge Monographs on Computational and Applied Mathematics). — ISBN 978-0-521-19469-3.

Kenneth Ireland, Michael Rosen. A Classical Introduction to Modern Number Theory. — 2nd. — Springer-Verlag, 1990. — ISBN 0-387-97329-X.
- К. Айерлэнд, М. Роузен. Классическое введение в современную теорию чисел / Перевод с английского С. П. Демушкина. — Москва: «Мир», 1987.

Kenneth H. Rosen. Elementary Number Theory and its Applications. — 3rd. — Addison-Wesley, 1993. — ISBN 978-0-201-57889-8.
Carol Schumacher. Chapter Zero: Fundamental Notions of Abstract Mathematics. — Addison-Wesley, 1996. — ISBN 0-201-82653-4.
Wade Trappe, Lawrence C. Washington. Introduction to Cryptography with Coding Theory. — 2nd. — Prentice-Hall, 2006. — ISBN 978-0-13-186239-5.

Ссылки[править | править код]

Weisstein, Eric W. Modular Inverse (англ.) на сайте Wolfram MathWorld.
Геварра Васкез, Фернандо предлагает пример решения обратного по модулю с помощью Евклидова Алгоритма.

Источник

Макеты страниц

Вычисление мультипликативных обратных.

Мультипликативные обратные элементы по модулю играют важную роль в этой книге. Рассмотрим два способа их вычисления.

Как уже отмечалось в доказательстве теоремы 2.3.10, для вычисления мультипликативного обратного по модулю к элементу а, который обозначается через или просто можно

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

или, перенеся ту в правую часть,

откуда вытекает, что

и, следовательно, — мультипликативный обратный к а по модулю [Отметим, что в нашем случае мы имеем дело с короткими целыми числами; поэтому, полагая в выражении для времени работы алгоритма Евклида, получаем, что мультипликативный обратный вычисляется за время ]

Пример. В поле вычислим — мультипликативный обратный элемент к 4 по модулю 11. Применяя расширенный алгоритм Евклида к 11 и 4, получим следующую таблицу:

Итерация

Из последней строки вытекает, что , где числа —1 и 3 расположены в столбцах соответственно; следовательно, . Можно ускорить вычисление мультипликативных обратных, заметив, что в нашем случае не обязательно вычислять последовательность элементов (Обратный элемент появляется в столбце который содержит множители при 4; он мог бы появиться в столбце если бы мы поменяли местами числа 4 и 11.)

Другой способ вычисления мультипликативного обратного по модулю простого числа состоит в применении следующей замечательной теоремы (см. историческое замечание 4).

Источник

The number system includes different types of numbers for example prime numbers, odd numbers, even numbers, rational numbers, whole numbers, etc. These numbers can be expressed in the form of figures as well as words accordingly. For example, the numbers like 40 and 65 expressed in the form of figures can also be written as forty and sixty-five.

A Number system or numeral system is defined as elementary system to express numbers and figures. It is the unique way of representation of numbers in arithmetic and algebraic structure.

Numbers are used in various arithmetic values applicable to carry out various arithmetic operations like addition, subtraction, multiplication, etc which are applicable in daily lives for the purpose of calculation. The value of a number is determined by the digit, its place value in the number, and the base of the number system.

Numbers generally are also known as numerals are the mathematical values used for counting, measurements, labeling, and measuring fundamental quantities.

Numbers are the mathematical values or figures used for the purpose of measuring or calculating quantities. It is represented by numerals as 2,4,7, etc. Some examples of numbers are integers, whole numbers, natural numbers, rational and irrational numbers, etc.

Types Of Numbers

There are different types of numbers categorized into sets by the real number system. The types are described below:

Natural numbers: Natural numbers are the positive numbers that count from 1 to infinity. The set of natural numbers is represented by ‘N’. It is the numbers we generally use for counting. The set of natural numbers can be represented as N = 1, 2, 3, 4, 5, 6, 7,…
Whole numbers: Whole numbers are positive numbers including zero, which counts from 0 to infinity. Whole numbers do not include fractions or decimals. The set of whole numbers is represented by ‘W’. The set can be represented as W = 0, 1, 2, 3, 4, 5,…
Integers: Integers are the set of numbers including all the positive counting numbers, zero as well as all negative counting numbers which count from negative infinity to positive infinity. The set doesn’t include fractions and decimals. The set of integers is denoted by ‘Z’. The set of integers can be represented as Z = …..,-5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5,…
Decimal numbers: Any numeral value that consists of a decimal point is a decimal number. It can be expressed as 2.5, 0.567, etc.
Real number: Real numbers are the set numbers that do not include any imaginary value. It includes all the positive integers, negative integers, fractions, and decimal values. It is generally denoted by ‘R’.
Complex number: Complex numbers are a set of numbers that include imaginary numbers. It can be expressed as a+bi where “a” and “b” are real numbers. It is denoted by ‘C’.
Rational numbers: Rational numbers are the numbers that can be expressed as the ratio of two integers. It includes all the integers and can be expressed in terms of fractions or decimals. It is denoted by ‘Q’.
Irrational numbers: Irrational numbers are numbers that cannot be expressed in fractions or ratios of integers. It can be written in decimals and have endless non-repeating digits after the decimal point. It is denoted by ‘P’.

How to find the additive and multiplicative inverse of numbers?

To understand the additive and multiplicative inverse of a number, let’s have a brief description of the properties of the number because additive and the multiplicative inverse is one of the properties of number.

Properties of Numbers

The main properties of numbers are:

Closure property
Commutative property
Associative property
Distributive property
Identity element property
Inverse element property

Closure Property

In this property of real numbers, we can add or multiply any two real numbers that will also result in a real number.

Example:

2 + 5 = 7 and 80 + 40 = 120 for addition

6 × 5 = 30 for multiplication

Commutative Property

It states that the operation of addition or multiplication on the number does not matter what is the order, it will give us the same result even after swapping or reversing their position.

Or we can say that the placement of adding or multiplying numbers can be changed but it will give the same results.

This property is valid for addition and multiplication not for subtraction and division.

x + y = y + x or x.y = y.x

Example:

If we add 6 in 2 or add 2 in 6 results will be same If we multiply both the real number

7 + 2 = 9 = 2 + 7 7 × 5 = 35 = 5 × 7

Associative Property

This property states that when three or more numbers are added (or multiplied) or the sum(or product) is the same regardless of the grouping of the addends (or multiplicands).

The addition or multiplication in which order the operations are performed does not matter as long as the sequence of the numbers is not changed. This is defined as the associative property.

That is, rearranging the numbers in such a manner that will not change their value.

(x + y) + z = x + (y + z) and (x.y).z = x.(y.z)

Example: (8 + 5) + 6 = 8 + (5 + 6) (8 × 5) × 6 = 8 × (5 × 6)

19 = 19 240 = 240

As you can see even after changing their order, it gives the same result in both the operations adding as well as multiplication.

Distributive Property

This property helps us to simplify the multiplication of a number by a sum or difference. It distributes the expression as it simplifies the calculation.

x × (y + z) = x × y + x × z and x × (y – z) = x × y – x × z

Example:

Simplify 10 × (5 + 6)

= 10 × 5 + 10 × 6

= 50 + 60

= 110

It applies same for the subtraction also.

Identity Element Property

This is an element that leaves other elements unchanged when combined with them. The identity element for the addition operation is 0 and for multiplication is 1.

For addition, a + 0 = a and for multiplication a.0 = 0

Example:

For addition, if a = 6

a + 0 = 6 + 0 = 6

and for multiplication if a = 6

a.0 = 6.0 = 0

Inverse Element

The reciprocal for a number “a”, denoted by 1/a, is a number which when multiplied by “a” yields the multiplicative identity 1.

The multiplicative inverse of a fraction: a/b is b/a

The additive inverse of a number “a” is the number that when added to “a”, gives result zero. This number is also known as the additive inverse or opposite (number), sign change, and negation.

Or we can say for a real number, it reverses its sign from positive number to negative and negative number to positive. Zero is itself additive inverse.

Example: Reciprocal of 9 is 1/9 and the additive inverse of 9 is -9

So according to the question additive and multiplicative inverse comes in inverse element of property as explained above.

Sample Questions

Question 1: what are the additive and multiplicative inverse of the following numbers?

5, 25, 4, 4/5, -12

Solution:

First additive inverse, The additive inverse of a number “a” is the number that when added to “a”, gives result zero. This number is also known as the additive inverse or opposite (number), sign change, and negation.

Additive inverse of

5 is -5,

25 is -25,

4 is -4,

4/5 is – 4/5,

-12 is 12

Now the multiplicative inverse of

5 is 1/5,

25 is 1/25,

4/5 is 5/4,

4 is 1/4,

-12 is -1/12

Question 2: Give some examples for Commutative properties?

Answer:

For addition For multiplication

8 + 3 = 3 + 8 = 11 12 × 5 = 5 × 12 = 60

26 + 11 = 11 + 26 = 37 2 × 5 = 5 × 2 = 10

Question 3: Simplify 25 with its additive inverse property and prove?

Answer:

As per the inverse property

The additive inverse of a number “a” is the number that when added to “a”, gives result zero. This number is also known as the additive inverse or opposite (number), sign change, and negation.

Or we can say for a real number, it reverses its sign from positive number to negative and negative number to positive. Zero is itself additive inverse

So here additive inverse of 25 is -25

Now add 25 + (-25)

= 25 – 25 = 0

Hence proved

Question 4: Find the multiplicative inverse of 5 and verify the property?

Answer:

As per the inverse property

The reciprocal for a number “a”, denoted by 1/a, is a number which when multiplied by “a” yields the multiplicative identity 1.

The multiplicative inverse of a fraction: a/b is b/a

so here multiplicative inverse of 5 is 1/5

and as per the property

5 × 1/5

= 1

hence proved

Источник

Поиск мультипликативно обратного элемента по модулю

Видео: Поиск мультипликативно обратного элемента по модулю

Содержание

Примеры мультипликативного обратного
Пример 1
Пример 2
Пример 3
Пример 4
Обучение
Упражнение 1
Упражнение 2.
Упражнение 3.
использованная литература

Это понимается Обратный мультипликативный числа, другое число, умноженное на первое, дает в результате нейтральный элемент произведения, то есть единицу. Если у вас есть реальный номер к то его мультипликативный обратный обозначается через к^-1, и это правда, что:

а а^-1 = а^-1 а = 1

Обычно число к принадлежит набору действительных чисел.

Рис. 1. Y – мультипликативная инверсия X, а X – мультипликативная инверсия Y.

Если, например, взять а = 2, то его мультипликативный обратный равен 2^-1 = ½ поскольку подтверждается следующее:

2 ⋅ 2^-1 = 2^-1⋅ 2 = 1

2⋅ ½ = ½ ⋅ 2 = 1

К Обратный мультипликативный числа также называют взаимный, поскольку мультипликативная обратная величина получается заменой числителя и знаменателя, например, мультипликативная обратная величина 3/4 равна 4/3.

Как правило, можно сказать, что для рационального числа (п / д) его мультипликативная обратная (p / q)^-1 Это взаимно (q / p) как можно проверить ниже:

(p / q) ⋅ (p / q)^-1 = (p / q) ⋅ (q / p) = (p⋅ q) / (q⋅ p) = (p⋅ q) / (p⋅ q) = 1

Мультипликативное обратное не существует в числовом наборе целых чиселНапример, если взять целое число 2, его мультипликативная обратная величина в соответствии с тем, что было показано выше, будет ½, но ½ не является целым числом.

Также не существует мультипликативного обратного нулевого элемента умножения. Другими словами, число ноль (0), являющееся нулевым элементом операции умножения, не имеет обратного мультипликативного числа, поскольку нет числа, умноженного на единицу нуля.

Мультипликативный обратный существует в рациональных числах, в действительных числах и в комплексных числах.

Примеры мультипликативного обратного

Пример 1

Найдите мультипликативное значение, обратное 3/2, и убедитесь, что оно удовлетворяет свойству мультипликативных целых чисел.

Согласно приведенному выше правилу числитель и знаменатель меняются местами, так что мультипликативная обратная величина (3/2) равна (2/3). Для проверки умножение двух чисел проводится:

(3/2) ⋅ (2/3) = (3 ⋅ 2) / (2 ⋅ 3) = 6/6 = 1.

Чтобы умножить два дробных числа, просто умножьте числитель первого числа на числитель второго, чтобы получить числитель результата.

Чтобы получить знаменатель произведения дробных чисел, действуйте аналогичным образом, то есть знаменатели перемножаются, и результат является знаменателем произведения. В нашем примере проверено, что числитель произведения числа и его обратной величины равен 6, а знаменатель равен 6, а дробь 6/6 равна 1.

Пример 2

Мультипликативное обратное значение -5 не следует путать с его симметричным (+5), которое иногда называют арифметическим обратным. Мультипликативный обратный будет получен следующим образом:

(-5) ⋅ X = 1

Где X – мультипликативная обратная величина, которую нужно получить. Одна из возможных процедур – найти неизвестное X. Поскольку (-5) умножает неизвестное X в левом члене, тогда происходит деление правого члена:

Х = 1 / (-5)

Поскольку известно, что + между – это -, то, наконец, получается X:

X = – ⅕.

В заключение – ⅕ – мультипликативная величина, обратная -5.

Пример 3

Получите мультипликативное значение, обратное -√2. Предположим, что мультипликативная обратная величина – это X, тогда -√2, умноженное на X, должно быть единицей, условие, которое мы налагаем ниже:

-√2 ⋅ X = 1

Затем оба члена делятся на -√2, чтобы получить:

(-√2 ⋅ X) / (-√2) = 1 / (-√2)

В первом члене -√2 упрощается, оставляя:

Х = 1 / (-√2)

Это выражение можно рационализировать, то есть исключить корень знаменателя, умножив в числителе на (-√2) и в знаменателе на ту же величину, чтобы результат не изменился:

X = (-√2) / [(-√2) (- √2)] = – (√2 / 2)

В заключение – (√2 / 2) является мультипликативным обратным (-√2).

Пример 4

Предположим любое число x, получите его обратное мультипликативное число и изобразите его графически.

В данном случае это функция f (x) = x, получение мультипликативного обратного преобразования означает нахождение такой функции g (x), которая умножается на первое число единицы. Функция g является обратной функцией f, и ее ни в коем случае не следует путать с ее обратной функцией.

Другими словами, мультипликативный обратный x – это y такой, что верно следующее:

х ⋅ у = 1

откуда расчистка и у вас есть:

у = 1 / х.

Вышеупомянутое интерпретируется таким образом, что при заданном значении x предыдущая формула дает нам его мультипликативную обратную величину.

Его можно представить в графическом виде, как показано на следующем рисунке:

Рис. 2. Мультипликативная величина, обратная x, равна y = 1 / x.

Обучение

Упражнение 1

Дано x = 2 – √2, получим его мультипликативную обратную y.

Решение:

Чтобы y был мультипликативным обратным x, должно выполняться следующее равенство:

х ⋅ у = 1

Замените x его значением:

(2 – √2) ⋅ y = 1

Затем он очищается и:

у = 1 / (2 – √2)

Чтобы рационализировать результат, умножьте числитель и знаменатель на их сопряженный бином:

у = (2 + √2) / ((2 + √2) (2 – √2))

В знаменателе определяется замечательное произведение, называемое произведением суммы и разницы, то есть разностью квадратов. Таким образом исчезает корень в знаменателе.

у = (2 + √2) / (2 ^ 2 – (√2) ^ 2)

Решение полномочий:

у = (2 + √2) / (4-2)

Упрощение:

у = (2 + √2) / 2

Упражнение 2.

Получите мультипликативную обратную величину (1 / a + 1 / b), где a и b – ненулевые действительные числа.

Решение:

Мы называем Y мультипликативной обратной величиной (1 / a + 1 / b), поэтому должно выполняться следующее уравнение:

И ⋅ (1 / a + 1 / b) = 1

Переменная Y очищается:

Y = 1 / (1 / a + 1 / b)

Знаменатель решается:

Y = 1 / ((b + a) / a b)

Как известно из правил алгебры, знаменатель знаменателя переходит в числитель:

Y = (а б) / (б + а)

Приказано окончательно получить:

(a b) / (a + b), который является мультипликативным обратным к (1 / a + 1 / b).

Упражнение 3.

Получите мультипликативную обратную величину (a – b) / (a ^ 2 – b ^ 2).

Решение:

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

Тогда мультипликативная величина, обратная (a – b) / (a ^ 2 – b ^ 2), будет:

(а ^ 2 – Ь ^ 2) / (а – Ь)

Но это выражение можно упростить, если мы признаем, согласно правилам алгебры, что числитель – это разность квадратов, которую можно разложить на множители как произведение суммы на разность:

((a + b) (a – b)) / (a - b)

Поскольку в числителе и знаменателе есть общий множитель (a – b), мы переходим к упрощению и в итоге получаем:

(a + b), который является мультипликативным обратным к (a – b) / (a ^ 2 – b ^ 2).

использованная литература

Фуэнтес, А. (2016). ОСНОВНАЯ МАТЕМАТИКА. Введение в исчисление. Lulu.com.
Гаро, М. (2014). Математика: квадратные уравнения: как решить квадратное уравнение. Марилу Гаро.
Хаусслер, Э. Ф., и Пол, Р. С. (2003). Математика для управления и экономики. Pearson Education.
Хименес, Дж., Рофригес, М., и Эстрада, Р. (2005). Математика 1 сен. Порог.
Прециадо, К. Т. (2005). Курс математики 3-й. Редакция Progreso.
Рок, Н. М. (2006). Алгебра I – это просто! Так просто. Team Rock Press.
Салливан, Дж. (2006). Алгебра и тригонометрия. Pearson Education.

Источник

Вычисление мультипликативного обратного

Решая уравнение
вида а·х
=1(mod
M)
может
возникнуть вопрос о существовании числа
х
мультипликативного
обратного числу
а
по модулю N.

Такое число х
должно
удовлетворять сравнению a
· x≡x
·a≡1(mod
M)
и обозначается как a^-1.

Если
M
положительное
простое
число, то для любого простого
числа a≥0
существует мультипликативное обратное
число a^-1
. Т. е. число a^-1
мультипликативного обратного к числу
а существует
только тогда, когда числа а
и M
взаимно
просты, а значит
НОД(а, М) = 1.

Нахождение
мультипликативного обратного числа
может проводиться по расширенному
алгоритму Евклида, реализованного в
виде следующей функции:

Вычисление
мультипликативного обратного

Синтаксис: void
inv_l
(CLINT
a,
CLINT
M,
CLINT
g
,CLINT
a_1);

Вход: a,
M
(операнды)

Выход: g
(наибольший общий делитель чисел а и M)

a_1
(обратный элемент к a
mod
M,
если он существует)

Листинг программы,
реализующей вычисление мультипликативного
обратного

#include <FLINT.h>

#include <stdio.h>

#include <conio.h>

#include <math.h>

#define ClintToStr
xclint2str_l // Переопределение функции
xclint2str_l

int main(int argc, char*
argv[])

{

CLINT a,b,c,ed;

CLINT g , a_1 ;

char *s1 =new char;s1=”7″;
// Строка 10-х цифр

str2clint_l
(a,s1,10);//Инициализация
строкой

char *s2
=new char;s2=”13″; // Строка 10-х цифр

str2clint_l
(b,s2,10);//Инициализация
строкой

char *s3
=new char;s3=”1″; // Строка 10-х цифр

str2clint_l
(ed,s3,10);//Инициализация 1

printf(“a=%sn”,ClintToStr(a,10,1));

printf(“b=%sn”,ClintToStr(b,10,1));

// Наибольший общий
делитель (НОД)

gcd_l ( a,
b, c);

printf(“HOD(a,b)=%sn”,ClintToStr(c,10,1));

// Вычисление
мультипликативного обратного

inv_l
(a,
b,
g
, a_1);

if( cmp_l( g, ed)==0)
printf(“x_1= %sn”,ClintToStr(a_1,10,1));

getch();
return
0;

}

Извлечение квадратного корня из а по модулю m

Извлечением
квадратного корня из числа а
по модулю M
является
процедура нахождения такого x,
для которого справедливо сравнение

x
²
≡ a
(mod
M)

Квадратный корень,
в общем, определен неоднозначно, то есть
может существовать несколько квадратных
корней из одного элемента, а может не
существовать ни одного решения.

Если НОД(а,M)
=1 и существует
одно решение b
такое, что b
≡
a
mod
M,
то число
а
называется
квадратичным
вычетом по модулю M.

Если сравнение
неразрешимо, то число а
называется
квадратичным
невычетом по модулю M.

Если число M
простое, то
найти квадратные корни по модулю M
довольно
просто.

Трудность вычисления
квадратных корней по модулю составного
числа M
определяется
тем, известно ли разложение числа M
на простые
множители. Если разложение неизвестно,
то вычисление квадратных корней для
большого числа M
является
математически сложной задачей,
лежащей в основе безопасности ряда
современных криптосистем.

Определение того,
является ли число квадратичным вычетом,
и вычисление квадратных корней – это
две разные задачи, для решения каждой
из которых существуют свои методы.

В FLINT/C
описана следующая функция, позволяющая
совместно с функцией проверки числа
на простоту, выполнить извлечение
квадратного корня из а
по модулю M
.

Извлечение
квадратного корня из а
по модулю
M

Синтаксис:
int proot_l (CLINT a, CLINT M, CLINT x);

Вход: a
(операнд, a
≠ M)

M
(операнд, M
> 2 – простое,
M
≠ a)

Выход: x
(квадратный корень из а по модулю р)

Возврат: 0, если
а – квадратичный вычет по модулю р,

-1 в
противном случае

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

Источник

Модульная арифметика[править | править код]

Целые по модулю m[править | править код]

Мультипликативная группа кольца вычетов[править | править код]

Пример[править | править код]

Вычисление[править | править код]

Расширенный алгоритм Евклида[править | править код]

Использование теоремы Эйлера[править | править код]

Вычисление нескольких обратных[править | править код]

Приложения[править | править код]

См. также[править | править код]

Примечания[править | править код]

Литература[править | править код]

Ссылки[править | править код]

Вычисление мультипликативных обратных.

Types Of Numbers

How to find the additive and multiplicative inverse of numbers?

Properties of Numbers

Sample Questions

Содержание

Примеры мультипликативного обратного

Пример 1

Пример 2

Пример 3

Пример 4

Обучение

Упражнение 1

Упражнение 2.

Упражнение 3.

использованная литература

Вычисление мультипликативного обратного

Извлечение квадратного корня из а по модулю m

Вам также может понравиться

Для целей учета ндс не списано в 1с как исправить

Как составить документ купли продажи квартиры

Видео про как найти золото

Добавить комментарий Отменить ответ