1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

I Congruence vs equality in mod arithmetic

  1. Aug 1, 2016 #1
    I've encountered what seems to be two different notations for modular arithmetic and I'm confused as to whether they mean the same thing.

    My abstract algebra textbook (Pinter) and professor would write, for example, 5 = 15mod(10), as though mod(10) is an operation that returns the amount by which 15 differs from a multiple of 10.

    But the other notation that I've run into, and the one that seems to be more common, is to write 15 ≡ 5mod(10), identifying 15 as an element of the set of integers that are 5 more than a multiple of 10.

    Which notation is generally preferred? Are there cases where it is more appropriate to use one notation instead of the other?
     
  2. jcsd
  3. Aug 1, 2016 #2

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    I have never seen the first version used in mathematics, and I have never seen the second version used in computer science or anything related to programming.
     
  4. Aug 1, 2016 #3

    fresh_42

    Staff: Mentor

    It is by far more important that you know what is meant.
    ##\mod 10## is simply the image under the natural projection ##\pi : \mathbb{Z} \twoheadrightarrow \mathbb{Z}_{10}##, that is the remainder of division by ##10##. So

    ##5 = 15 \mod 10##
    ##⇔ 15 = 5 \mod 10##
    ##⇔ \pi(5) = \pi(15) ##
    ##⇔ \pi(15-5) = 0##
    ##⇔ 15 - 5 \in \ker \pi = 10\mathbb{Z}##
    ##⇔ 15 \equiv 5 \mod 10##
    ##⇔ 5 \equiv 15 \mod 10##
    ##⇔ 15 \equiv 5 \; (10)##
    ##⇔ 5 \equiv 15 \; (10)##
    ##⇔ 10 \; | \; (15-5) ##
    ##⇔ 10 \; | \; (5-15) ##
    ##⇔ (5 = z_1 \cdot 10 + r_1 ∧ 15 = z_2 \cdot 10 + r_2 ⇒ r_1 = r_2)##

    Make your choice. Probably many here would object one or another notation. Don't bother. Everybody has likely his own preferences. I prefer ##15 \equiv 5 \mod 10## or ##15 \equiv 5 \; (10)## if lazy. The ##\equiv## sign only indicates, that the equality isn't the one in ##\mathbb{Z}## but the one in ##\mathbb{Z}_{10}##. However, if people deal with abstract rings instead, say ##\pi : R \twoheadrightarrow S##, nobody (or at least almost nobody) will write ##r_1 \equiv r_2 \mod \ker \pi## but probably ##\pi(r_1) = \pi(r_2)## without using ##\equiv##. However, most people (I guess) will write ##15 \equiv 5 \mod 10## when they deal with integers and want to emphasize whether they are in ##\mathbb{Z}## or ##\mathbb{Z}_{10}## and with the true (smallest positive) remainder on the right hand side as it is the standard representation of ##\mathbb{Z}_{10}##
     
  5. Aug 1, 2016 #4

    Stephen Tashi

    User Avatar
    Science Advisor

    Doesn't Pinter's define the notation A = B (mod C) to indicate a relation between A and B rather than an operation on B ?

    I think Pinter would also write 15 = 5 (mod 10).


    Some authors prefer "=" and other's prefer "≡".

    Ambiguity in both the notion of "congruence" and its notation is usually glossed over because calculations look the same with different interpretations. In many texts, it is ambiguous is whether A = B mod (C) indicates a relation between integers A and B or whether A = B mod(C) indicates an equality of sets. One can regard "5" as the integer 5 or abuse notation by regarding "5" as denoting the set of all integers that satisfy the relation of being congruent to 5 mod C.

    A equivalence relation has associated "equivalence classes". It's often convenient to denote a set that is an equivalence class by labelling it with one of the elements in the set. If you wanted to do things in a refined way, you could write "A ≡B (mod C)" to denote a relation between integers A and B and write "[A] = [ B ] (mod C)" to indicate the equality of the sets "[A]" and "[ B ]", where the brackets are used to emphasize that "[A]" is the set of all integers that are equivalent to A under the relation "≡... mod(C)".

    (Amusing - the message window has decided to use bold text, presumably because I wrote a "[ B ] ".)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Congruence vs equality in mod arithmetic
  1. Triangle congruence (Replies: 1)

  2. Are these equal? (Replies: 2)

Loading...