[NBLUG/talk] What is arithmetic mod n

[Andru Luvisi]

On Tue, 20 May 2003, Steve Zimmerman wrote:
> I mean besides being RTFM stuff.
>
> It doesn't mean the same as the C construct
>
> 	var = var2  %  n;
>
> does it?  I've tried to RTFM, but Knuth assumes
> you already know it, and I can't stand any more
> college.

a mod n is the remainder when you devide a by n.  10 mod 3 is 1.  20 mod 5
is 0.  30 mod 4 is 2.

We say that two numbers are congruent (typically written as an equal sign
with three dashes instead of two) modulo n if they have the same
remainders when devided by n.

Arithmetic mod n is what you get when you only work with the numbers mod
n.  For example, 5+5 is congruent to 1 mod 3.  2+2 is also congruent to 1
mod 3.  In a sense, 5+5 is the same as 2+2 because 5 is congruent to 2.

It is an interesting fact that:

(a mod n) + (b mod n) = (a + b) mod n
(a mod n) - (b mod n) = (a - b) mod n
(a mod n) * (b mod n) = (a * b) mod n

2*2 = 4 mod 7
2*4 = 1 mod 7

there are only 7 numbers mod 7.  You can think of them as being in a sort
of circle if you like.

Does that help at all?

Andru
-- 
Andru Luvisi, Programmer/Analyst

Quote Of The Moment:
  Quidquid latine dictum sit, altum viditur.
  ( Whatever is said in Latin sounds profound. )