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

2010-12-08, 01:16   #12
CRGreathouse

Aug 2006

3·52·79 Posts

Quote:
 Originally Posted by 3.14159 List a few examples.
It's common in many basic applications like exponentiation and vector gcd. Often it's easier to find a partial reduction than a total reduction when doing a large series of operations mod a number.

There was a good paper on the subject; if I can find a link I'll post it. (I'm not sure if it would be appropriate for your level, though.)

Last fiddled with by CRGreathouse on 2010-12-08 at 01:21

2010-12-08, 01:20   #13
CRGreathouse

Aug 2006

3·52·79 Posts

Quote:
 Originally Posted by 3.14159 Going back to my example: By phi, do you mean, phi(19, (exponent))? Or do you mean, 19?
I mean that the exponent can be reduced mod phi(19) = 18. In all cases you should be able to reduce a + bM to a + M (a, b natural and M = phi(m)); when the base is coprime to the modulus you can reduce to a.

2010-12-08, 01:48   #14
3.14159

May 2010
Prime hunting commission.

110100100002 Posts

Quote:
 Originally Posted by CRGreathouse I mean that the exponent can be reduced mod phi(19) = 18. In all cases you should be able to reduce a + bM to a + M (a, b natural and M = phi(m)); when the base is coprime to the modulus you can reduce to a.
Ah, okay. I understand.

2011-03-28, 00:24   #15
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 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/
been looking at these and the number theory thread I started comes to mind.

 2011-03-31, 13:42 #16 science_man_88     "Forget I exist" Jul 2009 Dumbassville 838410 Posts hypothesis: if((x^2)%z==x,x^y%z=x for all y>=0. proof: 1) if ((x^y)%z==x, then (x^(y+1))%z = (x^2)%z = x) therefore if it works for y=2 it sets up for when y = 3 and so on until infinity.Also it work out that unless x^2-x =< x ( as is the case for 2 and 1) that x
2011-03-31, 15:02   #17
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts

Quote:
 Originally Posted by science_man_88 hypothesis: if((x^2)%z==x,x^y%z=x for all y>=0. proof: 1) if ((x^y)%z==x, then (x^(y+1))%z = (x^2)%z = x) therefore if it works for y=2 it sets up for when y = 3 and so on until infinity.Also it work out that unless x^2-x =< x ( as is the case for 2 and 1) that x
I can see how it can be extended to:

if((x^a)%z==x,x^y%z=x for all y>=a.

Last fiddled with by science_man_88 on 2011-03-31 at 15:03

2011-03-31, 15:07   #18
CRGreathouse

Aug 2006

3×52×79 Posts

Quote:
 Originally Posted by science_man_88 hypothesis: if((x^2)%z==x,x^y%z=x for all y>=0. proof: 1) if ((x^y)%z==x, then (x^(y+1))%z = (x^2)%z = x) therefore if it works for y=2 it sets up for when y = 3 and so on until infinity.Also it work out that unless x^2-x =< x ( as is the case for 2 and 1) that x
I assume you mean "for all y > 0".

Yes, the result is correct, though I'm not sure I like the proof. It seems to use induction without saying so, and to skip over key steps. I hope that you had it right in your head, at least.

I think you can generalize this as far as idempotent elements in any magma... there's nothing special here about working with the integers mod z. That is, if x * x = x (where * is any sort of operation you like) then x^y = x for all y > 0, where x^1 = x and x^y = x * x^(y - 1). In this case x is an element of the magma ("integers mod z" in your case) and y is an integer.

2011-03-31, 15:10   #19
CRGreathouse

Aug 2006

3·52·79 Posts

Quote:
 Originally Posted by science_man_88 I can see how it can be extended to: if((x^a)%z==x,x^y%z=x for all y>=a.
No. (3^3)%8 = 3, and 4 >= 3, but (3^4)%8 ≠ 3.

2011-03-31, 15:14   #20
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

838410 Posts

Quote:
 Originally Posted by CRGreathouse I assume you mean "for all y > 0". Yes, the result is correct, though I'm not sure I like the proof. It seems to use induction without saying so, and to skip over key steps. I hope that you had it right in your head, at least. I think you can generalize this as far as idempotent elements in any magma... there's nothing special here about working with the integers mod z. That is, if x * x = x (where * is any sort of operation you like) then x^y = x for all y > 0, where x^1 = x and x^y = x * x^(y - 1). In this case x is an element of the magma ("integers mod z" in your case) and y is an integer.
basically my proof was taken that x*x=x^2 would have to be the value to mod z next by increasing the exponent 1 we come to the fact that if x^2 mod z = x that the next one up always happens to have x^2 mod z= x mod z so no matter how many times you add 1 you never escape it.

2011-03-31, 15:16   #21
Mr. P-1

Jun 2003

7×167 Posts

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. The above does not hold for exponentiation; ((261 mod 19)↑(771 mod 19)) mod 19 != (261↑771) mod 19.
Also (a mod x - b mod x) mod x = (a - b) mod x.

But this doesn't work for division:

(20 mod 4) / (10 mod 4) = 0/2 = 0
but (20/10) mod 4 = 2.

 2011-03-31, 15:20 #22 CRGreathouse     Aug 2006 3·52·79 Posts For division you need to separate components that are relatively prime to the modulus from those that are not.

 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 21:25.

Wed Sep 30 21:25:56 UTC 2020 up 20 days, 18:36, 0 users, load averages: 1.39, 1.33, 1.52