Beweise: Die Kongruenz modulo ´m´ ist eine Äquivalenzrelation.

Beweise außerdem: Es gilt genau dann ´a -= b \ ("mod m")´, wenn ´a´ und ´b´ bei der Division durch ´m´ denselben Rest lassen.

Solution
  • Nach der Definition der Kongruenz zweier Zahlen modulo ´m´ gilt:

    ´a -= b \ ("mod m") <=>´ ´m | (a-b) <=>´ ´(a-b) in mZZ´

    Nun soll gezeigt werden: ´r_1 = r_2 => m | (a - b) => a -= b \ ("mod m")´

    <mark>Es fehlt: ´a -= b \ ("mod m") => m | (a - b)´</mark>

    Es sei ´a = q_1m + r_1´ und ´b = q_2m + r_2´ mit ´0 <= r_1, r_2 <= m´.

    ´a - b = q_1m + r_1 - q_2m + r_2´ ´= m(q_1 - q_2) + r_1 - r_2´

    Für ´r_1 = r_2´: ´a - b = m(q_1 - q_2)´

    ´=> m | (a - b)´ ´=> a -= b \ ("mod m")´

    Durch die Umkehrbarkeit der Operationen gilt auch: ´a -= b \ ("mod m") => m | (a - b) => r_1 = r_2´

    Somit ist ´a -= b \ ("mod m")´ gleichbedeutend mit "´a´ und ´b´ lassen bei der Division durch ´m´ denselben Rest".

    Damit modulo ´m´ eine Äquivalenzrelation ist müssen nun folgende Eigenschaften gelten:

    • reflexiv: ´a -= a \ ("mod m")´
    • transitiv: ´a -= b \ ("mod m") ^^ b -= c \ ("mod m") => a -= c \ ("mod m")´
    • symmetrisch: ´a -= b \ ("mod m") => b -= a \ ("mod m")´

    Dies lässt sich nun mit den vorhergegangenen Umformungen leicht zeigen:

    • reflexiv: Es gilt ´m | (a - a)´, da jede Zahl die Null teilt
    • transitiv: Aus ´m | (a − b)´ folgt ´m | −(a − b)´ bzw. ´m | (b − a)´
    • symmetrisch: Aus ´m | (a − b)´ und ´m | (b − c)´ folgt ´m | (a − b) + (b − c)´ bzw. ´m | (a − c)´
  • URL:
  • Language:
  • Subjects: math
  • Type: Proof
  • Duration: 30min
  • Credits: 4
  • Difficulty: 0.6
  • Tags: hpi congruence modulo
  • Note:
    HPI, 2014-06-02, Mathe 2, Aufgabe 34
  • Created By: adius
  • Created At:
    2014-07-26 16:10:18 UTC
  • Last Modified:
    2014-07-26 16:11:02 UTC