Es handelt sich hierbei um sogenannte lineare diophantische Gleichungen. Eine Gleichung der Form \(ax+by= m \) ist genau dann lösbar, wenn der \(ggT(a,b)\) das \(m\) teilt. Mit dem erweiterten euklidischen Algorithmus berechnet man zunächst eine Lösung der Gleichung \(ax+by=ggT(a,b) \) und multipliziert diese dann mit \( \frac{m}{ggT(a,b)} \), um eine Lösung \((x_0,y_0)\) der Gleichung \(ax+by=m\) zu erhalten. Alle weiteren Lösungen ergeben sich dann als \((x_0 + \frac{z \cdot b}{ggT(a,b)},y_0 - \frac{z \cdot a}{ggT(a,b)}) \) für \(z \in \mathbb{Z} \).