Vlasenko D

Приєднався 11 травня 2013
 
5</math>. Виконаємо перевірку: <math>13*45=13*(-8)=-80-24=</math>.
 
=== Решение линейного сравнения ===
Метод вычисления обратного элемента можно использовать для решения сравнения
: <math>a \cdot x \equiv b \pmod n.</math>
Решение задается формулой
: <math>x \equiv b \cdot a^{\varphi(n)-1} \pmod n,</math>   если <math>(a,n) = 1.</math>
 
{{Hider| title = Пример (Решение линейного сравнения)| content =
<!------------------------------------------------------------------------------------->
Рассмотрим сравнение
:<math>7 \cdot x \equiv 3 \pmod 9.</math>
Так как <math>(7,9)=1,</math> можно воспользоваться указанной формулой:
:<math>x = 3 \cdot 7^{\varphi(3^{2})-1} \;\bmod \;9 = 3 \cdot 7^{3 \cdot (3-1) - 1} \;\bmod \;9 = 3 \cdot 7^{5} \;\bmod \;9 = 3 \cdot 49 \cdot 49 \cdot 7 \;\bmod \;9 = 3 \cdot 4 \cdot 4 \cdot 7 \;\bmod \;9 = 3.</math>
Подстановкой убеждаемся, что
:<math>7 \cdot 3 \equiv 3 \pmod 9.</math>
<!------------------------------------------------------------------------------------->
|frame-style = border: 1px solid rgb(200,200,200); |
title-style = color: black; background-color: rgb(255,221,255); font-weight: bold; text-align: left;|
content-style = color: black; background-color: white; text-align: left; |
hidden=1
}}
 
{{Hider| title = Замечание (Неединственность решения или отсутствие решения в случае (a, n) ≠ 1)| content =
<!------------------------------------------------------------------------------------->
Если <math>(a,n) \not = 1</math>, сравнение либо имеет не единственное решение, либо не имеет решения. Как легко убедиться, сравнение
:<math>2 \cdot x \equiv 3 \pmod 4</math>
не имеет решения на множестве натуральных чисел. В то же время сравнение
:<math>4 \cdot x \equiv 6 \pmod {22}</math>
имеет два решения
:<math>x = 7, \; x = 18.</math>
<!------------------------------------------------------------------------------------->
|frame-style = border: 1px solid rgb(200,200,200); |
title-style = color: black; background-color: rgb(255,255,221); font-weight: bold; text-align: left;|
content-style = color: black; background-color: white; text-align: left; |
hidden=1
}}