Sei a ∈ Z. Bestimmen Sie die Lösungen der Gleichung
ax ≡ 0 (mod m) in Zm
heisst in Zm, dass die Restklassen [ax] und [0] gleich sind.
[0] = {…-2m, -m, 0, m, 2m,…} = {z| z= km, k ∈ Z}.
Allgemein gilt: Sobald Restklassen modulo m ein gemeinsames Element haben, sind sie gleich.
und sobald eine Restklasse ein Element enthält, das in der andern nicht vorkommt, haben sie gar kein gemeinsames Element. Somit muss man nur schauen, ob ax in [0] enthalten ist.
Somit ist
ax = km zu lösen.
wenn
(a) m eine Primzahl ist ;
ax = km ist zu lösen.
Falls a=0 gilt 0x = 0m =0 für alle x ∈ Z. L = {[0],[1],[2],[3],[4],…[m-1]}
Falls a≠0 gilt ax= km
kann gelöst werden mit x=0 und k=0. Also L={[0],…?}
wenn auch x≠0, müsste x oder a durch m teilbar sein. alle durch m teilbaren x sind in [0] schon enthalten.
man kommt nur zu weiteren Lösungen, wenn a durch m teilbar ist. in diesem Fall ist aber [a]=0.
Fazit:
Für a ein Vielfaches von m oder 0, also [a] = [0] folgt L = {[0],[1],[2],[3],[4],…[m-1]}
Für a kein Vielfaches von m und nicht 0, also [a] ≠ [0] folgt L = {[0]}
(b) m ∈ N>0 beliebig
Es ist ax = km zu lösen.
Für a ein Vielfaches von m oder 0, also [a] = [0] folgt auch hier L = {[0],[1],[2],[3],[4],…[m-1]}
Sonst: ax = km, geht sicher, wenn x=0. L={[0],…}
Weitere Lösungen findet man mit der Primfaktorzerlegung aller Faktoren, von denen keiner mehr 0 sein kann.
ax = km habe die Primfaktorzerlegung
a1*a2*…x = k1*k2…m1*m2…
Die Primfaktoren ai können entweder mit den mi weggekürzt werden, oder sie treten auch bei den ki auf.
Es bleibt nach geeigneter neuer Nummerierung:
x =km/a = a1*a2*…k1*…m1*m2… Die gemeinsamen Teiler von a und m sind also hier weg.
In ax = km kann x also auch ein Vielfaches eines Teilers von m sein, wenn die anderen Teiler von m in a enthalten sind.
Wenn zB a1=m1, löst x=m/a1 die Gleichung ax = km.
Also L = {[0], [m/a1] ,… [m/weitere Teiler von a, die auch Teiler von m sind; nicht nur Primteiler]}
