[Search for users] [Overall Top Noters] [List of all Conferences] [Download this site]

Conference rusure::math

Title:Mathematics at DEC
Moderator:RUSURE::EDP
Created:Mon Feb 03 1986
Last Modified:Fri Jun 06 1997
Last Successful Update:Fri Jun 06 1997
Number of topics:2083
Total number of notes:14613

1938.0. "Modulus of congruence" by NETCAD::PICKETT (David - This all seems oddly familiar...) Thu Feb 23 1995 12:14

    Wisdon begins with the words "I do not know".
    
    I'm studying number theory, and am stuck on the following.
    
    a is congruent to b mod m if a-b is divisible by m.
    
    No problem here.
    
    1 is congruent to 7 mod 3, for example.
    
    My text suggests that three properties of modular congruence follow:
    
    i) a is congruent to a mod m
    
       1 is congruent to 1 mod 3,  looks good to me.
    
    ii) a is congruent to b mod m  iff  b is congruent to a mod m
    
       Now I have a problem. Clearly my understanding of 'congruency' is
    messed up here. I am tempted to replace the congruency symbol with a
    simple = symbol, and clearly 7 = 1 mod 3 does not hold. 
    
       Would someone be so kind as to clear this up for me? 
    
       Thanks,
       dp
    
    
T.RTitleUserPersonal
Name
DateLines
1938.1RUSURE::EDPAlways mount a scratch monkey.Thu Feb 23 1995 14:4417
    Re .0:
    
    You are thinking of "mod" as an operator.  It is not, despite its abuse
    in Pascal and other computer languages.  The construction of the
    statement "a is congruent to b mod m" is that "a is congruent to b". 
    The "mod m" tells you what type of congruence.  You don't look at "b
    mod m" and compute the remainder; that's not what the statement means.
    
    To tell if a is congruent to b when the congruence is modulo m, you
    check to see whether a and b have the same remainder when divided by m.
    
    
    				-- edp
    
    
Public key fingerprint:  8e ad 63 61 ba 0c 26 86  32 0a 7d 28 db e7 6f 75
To find PGP, read note 2688.4 in Humane::IBMPC_Shareware.
1938.2CSC32::D_DERAMODan D'Eramo, Customer Support CenterThu Feb 23 1995 14:4416
        "x is congruent to y mod z" is a three-place predicate which
        could be written as "x = y mod z".   In notes or email
        sometimes I write it that way and sometimes I use the notation
        "x == y mod z" instead.  No matter how you write it,
        
        	  i) a == a mod m
        	 ii) a == b mod m  implies  b == a mod m
        	iii) (a == b mod m  and  b == c mod m)  implies  a == c mod m
        
>and clearly 7 = 1 mod 3 does not hold. 
        
        But it does hold.  7 is just as congruent to 1 modulo 3 as
        1 is congruent to 7 modulo 3.  In both cases, 3 divides the
        difference (either 6 or -6).
        
        Dan
1938.3CSC32::D_DERAMODan D'Eramo, Customer Support CenterThu Feb 23 1995 14:451
        notes collision :-)
1938.4FLOYD::YODERMFYThu Feb 23 1995 14:5019
I think I get it... are you perhaps treating "mod" as if it were a binary
operator (such as it is in Pascal and Ada, for example)?  It isn't usually used
that way in mathematics.  The equation

    a == b mod m

is commonly written this way:

    a == b (mod m)

in order, I assume, to avoid precisely this confusion.  (Pretend that the == is
three horizontal lines rather than 2, I don't know the method for producing
special characters on X readers.)

It's better thought of as a 3-way relation between a, b, and m.  It is often
convenient, of course, to fix m and concentrate on the binary relation between a
and b which is thereby determined.

So 7 is congruent to 1 (mod 3) because 1-7 = -6 is divisible by 3.
1938.5Congruence is an equivalence relationEVTSG8::ESANUAu temps pour moiThu Feb 23 1995 15:3441
Quoting .2:

>        "x is congruent to y mod z" is a three-place predicate which
>        could be written as "x = y mod z".

For a given z, "x is congruent to y mod z" is an equivalence relation. So
are called binary relations (between pairs of elements) which have the 3
properties (let's call R the relation):

  i) Reflexivity:  a R a
 ii) Symmetry:  a R b  implies  b r a
iii) Transitivity: ( a R b  and  b R C )  implies  a R c

Quoting .2 again:
>        	  i) a == a mod m
>        	 ii) a == b mod m  implies  b == a mod m
>        	iii) (a == b mod m  and  b == c mod m)  implies  a == c mod m
        
So congruence mod m is an equivalence relation.

For the equivalence relation R, for each element a, the set of the elements
which are in relation with a (i.e. the b's which satisfy to a R b  - or
b R a ) is called the equivalence class of a.

The equality is a binary relation, and an equivalence relation, moreover it
is a particular case of an equivalence relation, one for which each
equivalence class is a singleton. i.e. a set with a single element.

Because of the 3 properties of the equivalence relations, one is tempted to
think of an equivalence relation as about the equality. This is not so
wrong, as if one considers the set of the equivalence classes, say C(a) is
the equivalence class of element a, then

	a R b  if and only if  C(a) = C(b)

(RHS equality is the set equality).

So 1 is really equal to 7 mod 3, in the sense that they have the same
equivalence classes.

Mihai.
1938.6congruence is a congruence relationCSC32::D_DERAMODan D'Eramo, Customer Support CenterThu Feb 23 1995 19:0321
        And furthermore...sometimes an equivalence relation on a set
        is a congruence relation with respect to some operation(s) on
        that set.  If R is an equivalence relation on a set X, and if
        f is an n-ary function from X^n into X, then R is a congruence
        relation relative to f if
        
        	a1 R b1, a2 R b2, ..., an R bn
        		implies
        	f(a1,a2,...,an) R f(b1,b2,...,bn)
        
        i.e., "f takes equivalence classes into equivalence classes"
        or "f is well-defined on X/R". :-)
        
        Congruence modulo m is just that with respect to, for example,
        addition and multiplication:
        
        	a1 == b1 (mod m)     and     a2 == b2 (mod m)
        			   implies
        	a1+a2 == b1+b2 (mod m)     and     a1*a2 == b1*b2 (mod m)
        
        Dan
1938.7Light dawnsNETCAD::PICKETTDavid - This all seems oddly familiar...Thu Feb 23 1995 19:338
    Eric put his finger on the crux of my problem, 'mod' is not an operator
    in this instance, its a qualifier, of sorts. My software engineering 
    bias is showing. 
    
    Thanks for the explanations folks.
    
    dp
    
1938.8abstraction, notationMOVIES::HANCOCKFri Feb 24 1995 11:1820
Taking a quotient of a set with respect to an equivalence relation is
the mathematical counterpart of abstraction: seeing the wood for the
trees.

Consider finite sequences of numbers s = <s[1],..,s[n]>. Define s and
t to be equivalent if 
  for some i : 1 <= i <= n, s = <t[i],..,t[n],t[0],..,t[i-1]>.  
The equivalence classes are the cycles "abstracted" from the
"concrete" sequences. (Which have irrelevant "implementation detail",
namely where a gap falls in the cycle.)

Some sort of discussion somewhere of the mod notation (that it is
distfix ... = ... (mod ...), and a different piece of syntax from
(...mod...) for a remainder operator) arises about every 6 months. 
Mathematics is full of crazy pieces of notation, like 
\integral ...x...x... . dx where confusion about what is a separable
part of the notation is positively invited.  There seems be a great
art in choosing notation that works well in the back of the brain
as well in the front.