1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Playing around with the modulo operation

  1. Jun 18, 2010 #1
    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. jcsd
  3. Jun 18, 2010 #2

    Mark44

    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.
     
  4. Jun 19, 2010 #3

    uart

    User Avatar
    Science Advisor

    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 [itex] a^p = b^q = x [/itex] 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 [itex]ab = 1[/itex] then [itex]abx = x[/itex],

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

    Perhaps someone else will be able to provide a more complete proof.
     
  5. Jun 23, 2010 #4
    Wow, thank you very much, uart! That was just the kick-start I needed to think about this more.
     
  6. Jun 25, 2010 #5

    disregardthat

    User Avatar
    Science Advisor

    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.
     
  7. Jun 25, 2010 #6
    Awesome, yes, this is what I ended up with. Thanks for your help, everyone!
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook