Zeigen Sie die Äquivalenz → a ≡ b mod m ⇔ r1 = r2 .

Question

Es sei \( m \in \mathbb{N}, m>0 \). Wir erinnern an Definition 22 aus den Vorlesungsnotizen: Für \( a, b \in \mathbb{Z} \) gilt \( a \equiv b \bmod m \), genau dann, wenn \( m \mid(a-b) \) gilt. Es sei nun \( a=q_{1} \cdot m+r_{1} \) mit \( 0 \leq r_{1}<m \) und \( b=q_{2} \cdot m+r_{2} \) mit \( 0 \leq r_{2}<m \). Zeigen Sie die Äquivalenz

a ≡ b mod m ⇔ r₁ = r₂ .

Comments

Hey

Liebe Grüße aus Ffm bin eine Kommilitonin. Könnte ich dich auf Discord kontaktieren. Dann würdest du mir echt weiterhelfen. Da ich jetzt Aufgaben mache die du bereits gemacht hast.

Lg

---

hey, ich habe erst jetzt deine nachicht gelesen. gerne können wir uns kontaktieren.

Answer 1

Subtraktion der beiden Kongruenzen ergibt

a -b≡(q₁-q₂)·m+r₁-r₂ mod m.

dann gilt a -b≡r₁-r ₂ mod m.

D.h. für r₁=r₂ gilt a ≡ b mod.

Answer 2

Hallo,

Definition 22 kann ja einfach geschrieben werden, als:

$$a\equiv b\bmod m\Leftrightarrow m\mid (a-b)$$

Setzt man in den rechten Term \(a=q_1\cdot m+r_1\) und \(b=q_2\cdot m+r_2\) ein, erhält man:

$$m\mid (a-b)\Leftrightarrow m\mid (q_1\cdot m+r_1-(q_2\cdot m+r_2)\Leftrightarrow m\mid (m\cdot(q_1-q_2)+(r_1-r_2))$$

Wendet man nun die Summenregel an, erhält man:

$$m\mid (m\cdot(q_1-q_2)+(r_1-r_2))\Leftrightarrow m\mid (m\cdot(q_1-q_2))\land m\mid (r_1-r_2)$$

Ersteres ist letztlich trivial, es steht ja eigentlich bereits da.

Es gilt aber \(\vert r_1-r_2\vert<m\), sodass \(m\mid (r_1-r_2)\) nur dann gelten kann, wenn \(r_1-r_2=0\) und somit \(r_1=r_2\) gilt.

Damit erhält man die zu beweisende Äquivalenz.

Beste Grüße,

FDF