Es gibt Lösungen, wenn \(\operatorname{ggT}(51,85) \,|\, 34\) ist.
Wegen \(\operatorname{ggT}(51,85) = 17\, |\, 34\) gibt es also eine Lösung.
Mit dem erweiterten euklidischen Algorithmus findet man
\(17 = 2\cdot51-1\cdot85\)
also
\(34 = 4\cdot 51-2\cdot85\).
Die Kongruenz
\(51x \equiv 34 \mod 85\)
kann deshalb umgeformt werden zu
\(51x \equiv 4\cdot 51-2\cdot85 \mod 85\)
also
\(51x \equiv 4\cdot 51 \mod 85\)
weil der Summand \(-2\cdot 85\) keinen Einfluss auf die Kongruenzklasse hat. Eine Lösung ist somit \(x = 4\).
Lösungsmenge ist somit
\(\{x\in \mathbb{Z} | \exists r\in \mathbb{Z}: x = 4 + r\cdot \frac{85}{17}\}\).
