Modular Arithmetic

[Peter_APIIT]

Hello to all, i try to implement modular arithmetic in C++ but finding it quite difficult to understand what is modular arithmetic.

I reading a book title: Algorithms by S. Dagupta, C H Papadimitriu, and U. V. Vaziran in chapter 1.

Substitution rule If x  x0 (mod N) and y  y0 (mod N), then:
x + y  x0 + y0 (mod N) and xy  x0y0 (mod N):

x + (y + z)  (x + y) + z (mod N) Associativity
xy  yx (mod N) Commutativity
x(y + z)  xy + yz (mod N) Distributivity

This content is taken from http://www.cs.berkeley.edu/~vazirani...thms/chap1.pdf


I hope someone can explain this to us.

Thanks for your help.

[VictorN]

Hello to all, i try to implement modular arithmetic in C++ but finding it quite difficult to understand what is modular arithmetic.

I reading a book title: Algorithms by S. Dagupta, C H Papadimitriu, and U. V. Vaziran in chapter 1.

Did you read this book or you only copied/pasted this "Substitution rule"?

[AmadeusAD]

What exactly do you implement? Modular arithmetic covers a lot... Anything, somehow related to remainders and integer division...
The signature (x op y) (mod N) means, in terms of C++, that ((x % N) op (y % N)), where x, y - integers, op - some operator.
Anything more could be provided until you make yourself ask more specific question...

[Peter_APIIT]

I just need the explanation of associative, commutative and distributive law of modular arithmetic.

Thanks.

[Peter_APIIT]

Anyone.

[VictorN]

What *explanations* do you need?
Well, try http://www.google.com/search?source=...metic&aq=f&oq=

[Peter_APIIT]

What is this ?

xy mod n = [(x mod n)×(y mod n)] mod n

Can you list all associative, commutative and distributive law for modular arithmetic ?

Thanks.

[VictorN]

Mathematical Background

[jefranki]

If you need to get your head around this stuff, just make up some simple problems and work them by hand in -fraction- form.

i.e. 7 divided by 2 == 7/2 (improper fraction) == 3 1/2 (mixed number) == 3 + 1/2 (additive form) == 3 rem. 1 (remainder form)

Play with the math in these different forms and you'll be able to work through the distributive property, etc. from basic algebra.