Vlasenko D

Приєднався 11 травня 2013
<nowiki>{{Перекладена стаття|ru||Перекладено з російської Вікіпедії станом на 2014 року.}}</nowiki>
 
=== Решение линейного сравнения ===
Метод вычисления обратного элемента можно использовать для решения сравнения
: <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 \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
}}