Решение линейного сравнения .Метод вычисления обратного элемента можно использовать для решения сравнения
a ⋅ x ≡ b ( mod n ) . {\displaystyle a\cdot x\equiv b{\pmod {n}}.} a \cdot x \equiv b \pmod n.
Решение задаётся формулой[35]:
x ≡ b ⋅ a φ ( n ) − 1 ( mod n ) , {\displaystyle x\equiv b\cdot a^{\varphi (n)-1}{\pmod {n}},} x \equiv b \cdot a^{\varphi(n)-1} \pmod n, если ( a , n ) = 1. {\displaystyle (a,\,n)=1.} {\displaystyle (a,\,n)=1.} рассмотрим сравнение--
Рассмотрим сравнение
7 ⋅ x ≡ 3 ( mod 9 ) . {\displaystyle 7\cdot x\equiv 3{\pmod {9}}.} 7 \cdot x \equiv 3 \pmod 9.
Так как ( 7 , 9 ) = 1 , {\displaystyle (7,9)=1,} (7,9)=1, можно воспользоваться указанной формулой:
x = 3 ⋅ 7 φ ( 3 2 ) − 1 mod 9 = 3 ⋅ 7 3 ⋅ ( 3 − 1 ) − 1 mod 9 = 3 ⋅ 7 5 mod 9 = 3 ⋅ 49 ⋅ 49 ⋅ 7 mod 9 = 3 ⋅ 4 ⋅ 4 ⋅ 7 mod 9 = 3. {\displaystyle 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.} 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.
Подстановкой убеждаемся, что
7 ⋅ 3 ≡ 3 ( mod 9 ) . {\displaystyle 7\cdot 3\equiv 3{\pmod {9}}.} 7 \cdot 3 \equiv 3 \pmod 9. ----- все это в википедии не совсем точно или слишком грубо чтоб понят истинную картину этих сравнении --то что 7x=3 mod 9 х =3 -- сумма своих чисел 7 чтоб попасть умножением на 3 мод 9 которая содержит прогрессию всех чисел с суммой своих.цифр 3 то конечно только 7*3 =21=3 16*12=192=3мод9 например 7x=1mod9 х=4 7*4=28=1 но опять это только прелюдия не больше к главным процессам число образования
Редактировалось 1 раз(а). Последний 06.01.2019 22:37.
