Zeigen Sie, dass folgendes gilt:

Question

Aufgabe:

Seien \( a, x, y, q \) ganze Zahlen, und es gelte \( a x \equiv a y(\bmod q) \). Sei \( d=(a, q) \). Zeigen Sie, dass \( x \equiv y(\bmod q / d) \) gilt.

Problem/Ansatz:

Moin, ich benötige Hilfe für diese Aufgabe. Wie sieht der Beweis hierfür aus?

Answer 1

es gelte \( a x \equiv a y(\bmod q) \)

Also gibt es ein k∈ℤ mit ax - ay = kq bzw.  a(x-y)=kq

Wegen  d=ggT(a,q) sind die Brüche a/d und q/d wieder ganze Zahlen.

Dann gilt \( \frac{a}{d} \)(x-y)=k\( \frac{q}{d} \). Kommst du damit weiter?

Comments

ja klar, das hilft mir weiter^^
Vielen Dank!