Einsatz des Euklidischen Algorithmus

 Eine alternative und rechnerisch sehr effiziente Methode, eine Kongruenz ax ≡  b (m) ersten Grades zu lösen, besteht erneut darin, den größten gemeinsamen Teiler (a, m) mit Hilfe des Euklidischen Algorithmus als Linearkombination von a und m darzustellen. Wir nehmen zunächst wieder an, dass a und m teilerfremd sind. Sind nun ganze Zahlen c, d gefunden mit

c a  +  d m  =  1,

so gilt wegen m|(dm), dass a c ≡  1 (m). Folglich ist

a c b ≡  b (m).

Damit ist x = cb die modulo m eindeutige Lösung der Kongruenz. Die φ-Funktion muss nicht verwendet werden (was ihre Bedeutung für die Zahlentheorie nicht schmälert).

 Ist g = (a, m) > 1 und g ein Teiler von b (sonst gibt es keine Lösung), so verfahren wir analog: Der Euklidische Algorithmus liefert c, d mit

ca  +  dm  =  g,

sodass a c ≡  g (m). Mit b* = b/g gilt

acb*  ≡   gb*  ≡   b  (m),

sodass x = c b* eine Lösung der Kongruenz ist. Die anderen Lösungen ergeben sich wie durch den obigen Satz beschrieben durch Addition von Vielfachen von m* = m/d.

Beispiel

Wir lösen noch einmal die Kongruenz 3x ≡  5 (11) mit Hilfe des Euklidischen Algorithmus. Mit a0 = 11 und a1 = 3 gilt:

11 =  3 · 3  +  2q0  =  3a2  =  2
3 =  1 · 2  +  1q1  =  1a3  =  1
2 =  2 · 1q2  =  2 

Damit können wir die 1 als Linearkombination von 3 und 11 darstellen:

1  =  (11, 3) =  3  −  1 · 2
=  3  −  1 · (11  −  3 · 3)  =  4 · 3  −  1 · 11.

Damit ist c = 4 und

x  =  4b  =  4 · 5  =  20  ≡   9  (11)

eine Lösung der Kongruenz, in Übereinstimmung mit der mit Hilfe der φ-Funktion berechneten Lösung.