modular arithmetic

[science_man_88]

I was wondering how much I knew about modular arithmetic and if anyone else could add more it would be appreciated. I know (a*b) mod x = (a mod x * b mod x)mod x, I've thought about addition and a few others as well looks like it holds for other operations. I know there's more than this to modular arithmetic anyone care to expand my knowledge or give me a link because they don't care lol I can look up more I guess I will have to.

[davieddy]

Your post count is approaching that of the legendary Mally, sm.

[science_man_88]

Originally Posted by davieddy

Your post count is approaching that of the legendary Mally, sm.

so in other words I should stop ?

[CRGreathouse]

For basic introductions, see
http://www.cut-the-knot.org/blue/Modulo.shtml
http://www.math.rutgers.edu/~erowlan...rithmetic.html

For more depth, I suggest finding a basic number theory textbook, maybe at a local library. Alternately, here are some online texts:
http://www.math.usf.edu/~eclark/elem_num_th_book.pdf
http://shoup.net/ntb/
http://modular.math.washington.edu/ent/

[davieddy]

Originally Posted by science_man_88

so in other words I should stop ?

Nah.
Hasn't done me any harm.
Yet.
Touch wood.

David

[science_man_88]

Originally Posted by CRGreathouse

For basic introductions, see
http://www.cut-the-knot.org/blue/Modulo.shtml
http://www.math.rutgers.edu/~erowlan...rithmetic.html

For more depth, I suggest finding a basic number theory textbook, maybe at a local library. Alternately, here are some online texts:
http://www.math.usf.edu/~eclark/elem_num_th_book.pdf
http://shoup.net/ntb/
http://modular.math.washington.edu/ent/

I see uses I never thought of as modular arithmetic lol.

[3.14159]

Operations using modular arithmetic;

(a mod x + b mod x) mod x = (a + b) mod x.

(a mod x * b mod x) mod x = (a * b) mod x.

The above does not hold for exponentiation;

((261 mod 19)↑(771 mod 19)) mod 19 != (261↑771) mod 19.

[CRGreathouse]

Originally Posted by science_man_88

I know (a*b) mod x = (a mod x * b mod x)mod x, I've thought about addition and a few others as well looks like it holds for other operations.

Originally Posted by 3.14159

Operations using modular arithmetic;

(a mod x + b mod x) mod x = (a + b) mod x.

(a mod x * b mod x) mod x = (a * b) mod x.

Yes. But it's sometimes useful to reduce only partially: (a - Ax)(b - Bx) mod x = a * b mod x. This is used in some efficient algorithms where fully reducing at each step would be more costly.

[CRGreathouse]

Originally Posted by 3.14159

The above does not hold for exponentiation;

((261 mod 19)↑(771 mod 19)) mod 19 != (261↑771) mod 19.

Right. The base can be reduced mod the exponent, and the exponent can... usually... be reduced mod phi(the modulus).

[3.14159]

Originally Posted by CRGreathouse

Yes. But it's sometimes useful to reduce only partially: (a - Ax)(b - Bx) mod x = a * b mod x. This is used in some efficient algorithms where fully reducing at each step would be more costly.

List a few examples.

[3.14159]

Originally Posted by CRGreathouse

Right. The base can be reduced mod the exponent, and the exponent can... usually... be reduced mod phi(the modulus).

Going back to my example: By phi, do you mean, phi(19, (exponent))? Or do you mean, 19?