Conference rusure::math

    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.

        "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

        notes collision :-)

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.

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.

        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

    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
    

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.