
Text erkannt:
3.1.12 Satz (Lemma von Euklid). Seien a,b∈Z und n∈N+ gegeben mit ggT(a,n)=1. Dann gilt
n∣ab⟹n∣b
Insbesondere gilt für p∈P, dass
p∣ab⟹(p∣a)∨(p∣b)
3 Ganzzahlige Arithmetik
30
Beweis. Wegen n∣ab existiert ein k∈Z mit kn=ab. Mit Satz 3.1.11 existieren x,y∈Z mit 1=xa+yn. Multiplizieren wir diese Gleichung mit b, so erhalten wir
b=b(xa)+b(yn)=(ab)x+nby=(kn)x+nby=n(kx+by)
Dies bedeutet n∣b. Sei nun p∈P eine Primzahl mit p∣ab. Für ggT(a,p) gibt es nur zwei Fälle. Falls ggT(a,p)=p, so gilt p∣a. Falls ggT (a,p)=1, so folgt aus dem ersten Teil p∣b. Insgesamt folgt also (p∣a)∨(p∣b).