Welcome guest
You're not logged in.
491 users online, thereof 1 logged in

Proof: (related to "Congruence Classes")

  • Let $m > 0$ be a positive integer and let $a\equiv b(m)$ (two integers $a,b$ being congruent modulo $m$).
  • We show three properties, applying the definitions of congruence and divisors:
    • Reflexivity: $m\mid (a-a)=0$, therefore $a\equiv a(m).$
    • Symmetry: $m\mid (a-b)\Leftrightarrow m\mid (b-a),$ therefore $a\equiv b(m)\Leftrightarrow b\equiv a(m).$
    • Transitivity:
      • If $a\equiv b(m)$ and $b\equiv c(m)$, then $m\mid(a-b)$ and $m\mid(b-c).$
      • But then $m\mid (a-b)+(b-c)=(a-c)$
      • It follows $a\equiv c(m).$
  • Altogether, it follows that that the relation $”\equiv”\subset \mathbb Z\times\mathbb Z$ is an equivalence relation.
q.e.d

| | | | created: 2016-08-23 21:05:28 | modified: 2019-04-10 22:02:02 | by: bookofproofs | references: [1272], [8152]


This work was contributed under CC BY-SA 3.0 by:

This work is a derivative of:

(none)

Bibliography (further reading)

[8152] Jones G., Jones M.: “Elementary Number Theory (Undergraduate Series)”, Springer, 1998

[1272] Landau, Edmund: “Vorlesungen ├╝ber Zahlentheorie, Aus der Elementaren Zahlentheorie”, S. Hirzel, Leipzig, 1927

FeedsAcknowledgmentsTerms of UsePrivacy PolicyImprint
© 2018 Powered by BooOfProofs, All rights reserved.