Bézout und modulares Kürzen

Kongruenzen und Restklassen · Abschnitt 39 von 64

Satz

Bézouts Identität

Für nicht gleichzeitig verschwindende ganze Zahlen $a,b$ gibt es ganze $u,v$ mit $ua+vb=\operatorname{ggT}(a,b)$ .

Beweis

Beweis mit dem kleinsten positiven Wert

Wähle die kleinste positive Linearkombination $d=ua+vb$ . Bei Division von $a$ durch $d$ wäre ein positiver Rest kleiner als $d$ erneut eine Linearkombination – unmöglich. Also $d\mid a$ , ebenso $d\mid b$ . Jeder gemeinsame Teiler von $a,b$ teilt umgekehrt $d$ . Daher ist $d$ der ggT.

Gelöstes Beispiel

Beispiel mit 35 und 12

Aus $35=2\cdot12+11$ und $12=11+1$ folgt rückwärts $1=3\cdot12-35$ . Deshalb ist 3 die multiplikative Inverse von 12 modulo 35.

Satz

Wann Kürzen erlaubt ist

Aus $ca\equiv cb\pmod m$ und $\operatorname{ggT}(c,m)=1$ folgt $a\equiv b\pmod m$ . Denn Bézout liefert ein $u$ mit $uc\equiv1\pmod m$ ; Multiplikation mit $u$ entfernt den Faktor $c$ rechtmäßig.

Beweis

Die offene Beweisklammer schließt sich

Ist $p$ prim, $p\mid ab$ und $p\nmid a$ , so ist $\operatorname{ggT}(p,a)=1$ . Aus $ab\equiv0\pmod p$ darf daher $a$ gekürzt werden und es folgt $b\equiv0\pmod p$ . Das ist Euklids Lemma aus Kapitel 8.