Wie löst man solche Modulo-Gleichungen?

Question

Aufgabe:

$$\text{Finde die kleinsten natürlichen Zahlen s,t} \in \mathbb{N} \text{ sodass gilt:}\\ 11*s \mod\ 29=1\\ 12*t \mod\ 43=1$$

Answer 1

Benutze den erweiterten euklidischen Algorithmus.

Ich erhalte

8 * 11 - 3 * 29 = 1
18 * 12 - 5 * 43 = 1

Comments

Funktioniert das auch wenn das Mod auf der rechten Seite steht? Als Beispiel

55*x=1 mod 89

---

Ja, das funktioniert auch.

34 * 55 - 21 * 89 = 1