(Twitter)
0
Moin,
die Idee sollte klar sein; man nimmt sich $x\in \mathbb{Z}$ her und sucht $y\in \mathbb{Z}$, s.d. $x*y\equiv 1 \text{ (mod n) }$. Das ist nun äquivalent dazu, dass $x*y=1+n*z$ für $z\in\mathbb{Z}$. Das kann man umformen zu $$x*y+z*n=1$$und optimaler Weise ist einem nun das Lemma von Euklid ein Begriff. Von hier aus schaffst du es sicher alleine, wenn nicht, melde dich wieder.
LG
die Idee sollte klar sein; man nimmt sich $x\in \mathbb{Z}$ her und sucht $y\in \mathbb{Z}$, s.d. $x*y\equiv 1 \text{ (mod n) }$. Das ist nun äquivalent dazu, dass $x*y=1+n*z$ für $z\in\mathbb{Z}$. Das kann man umformen zu $$x*y+z*n=1$$und optimaler Weise ist einem nun das Lemma von Euklid ein Begriff. Von hier aus schaffst du es sicher alleine, wenn nicht, melde dich wieder.
LG
Diese Antwort melden
Link
geantwortet
fix
Student, Punkte: 3.85K
Student, Punkte: 3.85K