# Playing around with the modulo operation

1. Jun 18, 2010

### Archosaur

Hey guys,
I am by no means a mathematician, but I do have a decent eye for patterns, and I found a pretty cool one today. I was hoping one of you guys could tell me more about it.

As a general rule, I've found that if (a*b) mod c = 1, then the sequence a^n mod c is the reverse of the sequence b^n mod c.

For example, (7*8) mod 11 = 1
and 7^n mod 11= 7,5,2,3,10,4,6,9,8...
while 8^n mod 11= 8,9,6,4,10,3,2,5,7...

As another example, (56*24) mod 17 =1
and 56^n mod 17 = 5,8,6,13,14,2,10,16,12,9,11...
while 24^n mod 17= 11,9,12,16,10,2,14,13,6,8,5...

What do you all think about this? I'm willing to bet that all I've done is show a simple concept in a convoluted way, but I'm to fried to think critically about this any more.

2. Jun 18, 2010

### Staff: Mentor

This is very interesting. For your first example, it is significant that 7 and 11 are relatively prime (no factors in common other than 1), and the same is true for 8 and 11.

3. Jun 19, 2010

### uart

Hi Archosaur. Here's a partial proof that's very straight forward. (BTW, to save typing please take all equalities as " = modulo c" and all variables as positive integer in what follows).

1. Assume that we have some power of "a" that is equal to some power of "b", that is $a^p = b^q = x$ for some p,q. (I haven't shown under what conditions this is guaranteed to occur, so this is definitely only a partial proof).

2. Since $ab = 1$ then $abx = x$,

so $ab b^p = a^p$ and hence $b^{p+1} = a^{q-1}$, which proves the reversed nature of the two series.

Perhaps someone else will be able to provide a more complete proof.

4. Jun 23, 2010

### Archosaur

Wow, thank you very much, uart! That was just the kick-start I needed to think about this more.

5. Jun 25, 2010

### disregardthat

All modulo c: If ab = 1, then a= b^-1. So a^n=b^-n. The periodicity of the sequences assures that they are opposite. a^n = b^-n is going in the "opposite direction" to b^n.

6. Jun 25, 2010

### Archosaur

Awesome, yes, this is what I ended up with. Thanks for your help, everyone!