Résoudre une congruence - ne peut pas comprendre une étape de la solution [dupliquer]
Nouveau dans les congruences et la théorie des nombres
Vous trouverez ci-dessous le texte du livre Joseph H. Silverman: A Friendly Introduction to Number Theory , 4e édition, chapitre 8, page 56.
Résoudre
$4x\equiv 3 \pmod{19}$
nous multiplierons les deux côtés par $5$. Cela donne
$20x\equiv 15 \pmod{19}$ - Étape 1
Mais $20\equiv 1\pmod{19}$, donc $20x\equiv x\pmod{19}$ - Étape 2
Ainsi, la solution est
$x\equiv 15\pmod{19}$
Je comprends jusqu'à l'étape 2, je suis incapable de comprendre comment on arrive à la solution à partir de l'étape 2.
Comment
$20x\equiv x \pmod{19}$
mener à
$x\equiv 15 \pmod{19}$
Où est-ce que $20$sur le LHS aller? Comment$x$ sur le RHS être remplacé par $15$?
Réponses
Je pense que la question ici concerne les propriétés fondamentales de la congruence.
À bien des égards, la congruence se comporte exactement comme l'égalité. Autrement dit, il satisfait les trois propriétés critiques:
$1)$ Réfléchi: $a\equiv a \pmod n$.
$2)$ Symétrique: $a\equiv b \pmod n\iff b\equiv a \pmod n$
$3)$ Transitif: $a\equiv b\pmod n$ et $b\equiv c\pmod n$ impliquer $a\equiv c \pmod n$.
Chacun de ces éléments découle facilement de la définition fondamentale de la congruence.
Ces trois propriétés, ensemble, font de la congruence un https://en.wikipedia.org/wiki/Equivalence_relation. C'est une notion importante en soi ... à bien des égards, vous pouvez travailler avec Equivalence Relations de la même manière que vous travaillez avec Equality. C'est ce qui se passe dans le calcul donné.
Dans ce cas, vous avez $$20x\equiv x\pmod {19}\quad \&\quad 20x\equiv 15\pmod {19}$$ alors combiner la propriété symétrique et la propriété transitive nous permet $x\equiv {15}\pmod {19}$.
Comme d'habitude, cependant, l'important est le principe général. Ces trois propriétés expliquent pourquoi les congruences sont si utiles et importantes ... assurez-vous de comprendre pourquoi elles sont valables.
Je soulignerai que $\gcd(5,19)=1$. Depuis$5$ est le coprime du module, multiplié par $5$ne change pas les solutions donc ces deux congruences sont équivalentes 1
$$4x\equiv3\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$$
Maintenant depuis $x\equiv20x\pmod{19}$, ce dernier équivaut à $x\equiv15\pmod{19}$.
Étant donné que les commentaires ici (et aux autres réponses) ont clarifié que c'est le problème principal, permettez-moi d'épeler la dernière équivalence en détail. (J'utiliserai librement à la fois la symétrie et la transitivité.)
- $x\equiv20x\pmod{19}$ et $20x\equiv15\pmod{19}$ implique $x\equiv15\pmod{19}$
- $20x\equiv x\pmod{19}$ $x\equiv15\pmod{19}$ implique $20x\equiv15\pmod{19}$
- Donc nous avons les deux $$20x\equiv15\pmod{19} \Longrightarrow x\equiv15\pmod{19}$$ et $$x\equiv15\pmod{19} \Longrightarrow 20x\equiv15\pmod{19}$$ ce qui nous donne l'équivalence $x\equiv15\pmod{19} \Longleftrightarrow 20x\equiv15\pmod{19}$.
1 Voir, par exemple:
- https://math.stackexchange.com/q/1845718
- https://math.stackexchange.com/q/1752523
En passant, je mentionnerai qu'il existe des forums de discussion tels que https://chat.stackexchange.com/transcript/12070 et https://chat.stackexchange.com/transcript/77161. Et il y a aussi lehttps://chat.stackexchange.com/transcript/36. Voir également:https://math.meta.stackexchange.com/q/26814#26817. (Je mentionne cela principalement depuis que j'ai vu que vous avez eu plusieurs échanges dans les commentaires. S'il y a trop de commentaires, cela pourrait être un signe que la discussion dans le chat pourrait être plus appropriée.)
Bien, $20\equiv 1 \mod 19$ et donc $20\cdot x\equiv 1\cdot x\mod 19$.
Le reste est comme vous l'avez expliqué: multiplier $4x\equiv 3\mod 19$ par $5$ des deux côtés donne $20x\equiv 15\mod 19$, c'est à dire, $x\equiv 15\mod 19$.
D'ici
$$20x\equiv 15 \mod19$$
nous avons ça
$$20x=19x+x \implies 20x\equiv x \mod19$$
par conséquent
$$20x\equiv x\equiv 15 \mod19$$
En effet par définition
$$a\equiv b \mod n \iff a-b=kn$$
par conséquent $20x\equiv x \mod 19 $ depuis $20x-x=19x$.
Vous pouvez diviser les côtés de la relation résultant de l'étape 1, les côtés de la relation résultant de l'étape 2:
$\frac{20x}{20x} ≡ \frac {15} x \mod (19)$
⇒ $1 ≡ \frac {15} x \mod (19)$
⇒ $x ≡ 15 \mod (19)$