Решение сравнения - не могу понять шаг в решении [дубликат]
Новое в сравнениях и теории чисел
Ниже приводится текст из книги Джозеф Х. Сильверман: дружеское введение в теорию чисел , 4-е издание, глава 8, стр. 56.
Решать
$4x\equiv 3 \pmod{19}$
мы умножим обе стороны на $5$. Это дает
$20x\equiv 15 \pmod{19}$ - Шаг 1
Но $20\equiv 1\pmod{19}$, так $20x\equiv x\pmod{19}$ - Шаг 2
Таким образом, решение
$x\equiv 15\pmod{19}$
Я понимаю, что до шага 2 я не могу понять, как прийти к решению из шага 2.
Как
$20x\equiv x \pmod{19}$
привести к
$x\equiv 15 \pmod{19}$
Откуда взялся $20$на LHS идти? Как$x$ на RHS заменить на $15$?
Ответы
Я думаю, что здесь речь идет об основных свойствах конгруэнтности.
Во многих важных отношениях конгруэнтность ведет себя точно так же, как равенство. То есть он удовлетворяет трем критическим свойствам:
$1)$ Рефлексивный: $a\equiv a \pmod n$.
$2)$ Симметричный: $a\equiv b \pmod n\iff b\equiv a \pmod n$
$3)$ Переходный: $a\equiv b\pmod n$ а также $b\equiv c\pmod n$ подразумевать $a\equiv c \pmod n$.
Каждый из них легко следует из основного определения конгруэнтности.
Эти три свойства вместе делают конгруэнтность https://en.wikipedia.org/wiki/Equivalence_relation. Это важное понятие само по себе ... во многих отношениях вы можете работать с отношениями эквивалентности так же, как вы работаете с Equality. Вот что происходит в данном расчете.
В этом случае у вас есть $$20x\equiv x\pmod {19}\quad \&\quad 20x\equiv 15\pmod {19}$$ так что объединение симметричного свойства и транзитивного свойства дает нам $x\equiv {15}\pmod {19}$.
Но, как всегда, важен общий принцип. Эти три свойства являются причиной того, почему сравнения так важны и полезны ... убедитесь, что вы понимаете, почему они верны.
Подчеркну, что $\gcd(5,19)=1$. поскольку$5$ взаимно прост с модулем, умножаясь на $5$не меняет решений, поэтому эти две сравнения эквивалентны 1
$$4x\equiv3\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$$
Теперь, когда $x\equiv20x\pmod{19}$, последнее эквивалентно $x\equiv15\pmod{19}$.
Поскольку комментарии здесь (и другие ответы) поясняют, что это основная проблема, позвольте мне подробно описать последнюю эквивалентность. (Я буду свободно использовать как симметрию, так и транзитивность.)
- $x\equiv20x\pmod{19}$ а также $20x\equiv15\pmod{19}$ подразумевает $x\equiv15\pmod{19}$
- $20x\equiv x\pmod{19}$ $x\equiv15\pmod{19}$ подразумевает $20x\equiv15\pmod{19}$
- Итак, у нас есть оба $$20x\equiv15\pmod{19} \Longrightarrow x\equiv15\pmod{19}$$ а также $$x\equiv15\pmod{19} \Longrightarrow 20x\equiv15\pmod{19}$$ что дает нам эквивалентность $x\equiv15\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$.
1 См., Например:
В качестве примечания я упомяну, что существуют чаты, такие как https://chat.stackexchange.com/transcript/12070 а также https://chat.stackexchange.com/transcript/77161. А еще естьhttps://chat.stackexchange.com/transcript/36. Смотрите также:https://math.meta.stackexchange.com/q/26814#26817. (Я говорю об этом в основном потому, что видел, что вы несколько раз обменивались комментариями. Если комментариев слишком много, это может быть признаком того, что обсуждение в чате может быть более подходящим.)
Что ж, $20\equiv 1 \mod 19$ так что $20\cdot x\equiv 1\cdot x\mod 19$.
Остальное, как вы объяснили: умножение $4x\equiv 3\mod 19$ от $5$ с обеих сторон дает $20x\equiv 15\mod 19$, т.е. $x\equiv 15\mod 19$.
Отсюда
$$20x\equiv 15 \mod19$$
у нас есть это
$$20x=19x+x \implies 20x\equiv x \mod19$$
следовательно
$$20x\equiv x\equiv 15 \mod19$$
Действительно по определению
$$a\equiv b \mod n \iff a-b=kn$$
следовательно $20x\equiv x \mod 19 $ поскольку $20x-x=19x$.
Вы можете разделить стороны отношения, полученного на шаге 1, на стороны отношения, полученного на шаге 2:
$\frac{20x}{20x} ≡ \frac {15} x \mod (19)$
⇒ $1 ≡ \frac {15} x \mod (19)$
⇒ $x ≡ 15 \mod (19)$