mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2010-12-08, 01:16   #12
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

Quote:
Originally Posted by 3.14159 View Post
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
CRGreathouse is offline   Reply With Quote
Old 2010-12-08, 01:20   #13
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

Quote:
Originally Posted by 3.14159 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2010-12-08, 01:48   #14
3.14159
 
3.14159's Avatar
 
May 2010
Prime hunting commission.

110100100002 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
3.14159 is offline   Reply With Quote
Old 2011-03-28, 00:24   #15
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-03-31, 13:42   #16
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

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<z so it will also turn out that x is x mod z.

Last fiddled with by science_man_88 on 2011-03-31 at 13:47
science_man_88 is offline   Reply With Quote
Old 2011-03-31, 15:02   #17
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

26·131 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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<z so it will also turn out that x is x mod z.
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
science_man_88 is offline   Reply With Quote
Old 2011-03-31, 15:07   #18
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×52×79 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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<z so it will also turn out that x is x mod z.
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.
CRGreathouse is offline   Reply With Quote
Old 2011-03-31, 15:10   #19
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

Quote:
Originally Posted by science_man_88 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2011-03-31, 15:14   #20
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

838410 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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.
science_man_88 is offline   Reply With Quote
Old 2011-03-31, 15:16   #21
Mr. P-1
 
Mr. P-1's Avatar
 
Jun 2003

7×167 Posts
Default

Quote:
Originally Posted by 3.14159 View Post
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.
Mr. P-1 is offline   Reply With Quote
Old 2011-03-31, 15:20   #22
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·52·79 Posts
Default

For division you need to separate components that are relatively prime to the modulus from those that are not.
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Basic Number Theory 5: rationals & intro to modular arithmetic Nick Number Theory Discussion Group 1 2016-10-21 22:21
modular arithmetic problem JuanTutors Math 4 2009-03-11 16:06
need C/C++ modular arithmetic code for Windows ixfd64 Programming 15 2008-07-30 03:52
Modular Arithmetic Numbers Math 27 2005-11-30 15:41
Jim Howell's modular arithmetic program? 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.