mersenneforum.org modular arithmetic
 Register FAQ Search Today's Posts Mark Forums Read

 2010-12-07, 14:47 #1 science_man_88     "Forget I exist" Jul 2009 Dumbassville 26·131 Posts modular arithmetic 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.
 2010-12-07, 15:34 #2 davieddy     "Lucan" Dec 2006 England 194A16 Posts Your post count is approaching that of the legendary Mally, sm.
2010-12-07, 15:46   #3
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

20C016 Posts

Quote:
 Originally Posted by davieddy Your post count is approaching that of the legendary Mally, sm.
so in other words I should stop ?

 2010-12-07, 18:49 #4 CRGreathouse     Aug 2006 592510 Posts 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/
2010-12-07, 19:06   #5
davieddy

"Lucan"
Dec 2006
England

2×3×13×83 Posts

Quote:
 Originally Posted by science_man_88 so in other words I should stop ?
Nah.
Hasn't done me any harm.
Yet.
Touch wood.

David

2010-12-07, 22:29   #6
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

100000110000002 Posts

Quote:
 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.

 2010-12-07, 22:30 #7 3.14159     May 2010 Prime hunting commission. 24×3×5×7 Posts 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. Last fiddled with by 3.14159 on 2010-12-07 at 22:34
2010-12-07, 22:42   #8
CRGreathouse

Aug 2006

172516 Posts

Quote:
 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.
Quote:
 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.

2010-12-07, 22:46   #9
CRGreathouse

Aug 2006

3×52×79 Posts

Quote:
 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).

2010-12-08, 00:20   #10
3.14159

May 2010
Prime hunting commission.

24·3·5·7 Posts

Quote:
 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.

2010-12-08, 00:25   #11
3.14159

May 2010
Prime hunting commission.

69016 Posts

Quote:
 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?

Last fiddled with by 3.14159 on 2010-12-08 at 00:26

 Similar Threads Thread Thread Starter Forum Replies Last Post Nick Number Theory Discussion Group 1 2016-10-21 22:21 JuanTutors Math 4 2009-03-11 16:06 ixfd64 Programming 15 2008-07-30 03:52 Numbers Math 27 2005-11-30 15:41 ixfd64 Software 0 2004-05-27 05:42

All times are UTC. The time now is 10:01.

Wed Sep 30 10:01:32 UTC 2020 up 20 days, 7:12, 0 users, load averages: 1.93, 1.49, 1.38