20101208, 01:16  #12 
Aug 2006
3·5^{2}·79 Posts 
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 20101208 at 01:21 
20101208, 01:20  #13 
Aug 2006
3·5^{2}·79 Posts 
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.

20101208, 01:48  #14 
May 2010
Prime hunting commission.
11010010000_{2} Posts 

20110328, 00:24  #15  
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} Posts 
Quote:


20110331, 13:42  #16 
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} 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^2x =< 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 20110331 at 13:47 
20110331, 15:02  #17  
"Forget I exist"
Jul 2009
Dumbassville
2^{6}·131 Posts 
Quote:
if((x^a)%z==x,x^y%z=x for all y>=a. Last fiddled with by science_man_88 on 20110331 at 15:03 

20110331, 15:07  #18  
Aug 2006
3×5^{2}×79 Posts 
Quote:
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. 

20110331, 15:10  #19 
Aug 2006
3·5^{2}·79 Posts 

20110331, 15:14  #20  
"Forget I exist"
Jul 2009
Dumbassville
8384_{10} Posts 
Quote:


20110331, 15:16  #21  
Jun 2003
7×167 Posts 
Quote:
But this doesn't work for division: (20 mod 4) / (10 mod 4) = 0/2 = 0 but (20/10) mod 4 = 2. 

20110331, 15:20  #22 
Aug 2006
3·5^{2}·79 Posts 
For division you need to separate components that are relatively prime to the modulus from those that are not.

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  20161021 22:21 
modular arithmetic problem  JuanTutors  Math  4  20090311 16:06 
need C/C++ modular arithmetic code for Windows  ixfd64  Programming  15  20080730 03:52 
Modular Arithmetic  Numbers  Math  27  20051130 15:41 
Jim Howell's modular arithmetic program?  ixfd64  Software  0  20040527 05:42 