Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Modular arithmetic

  1. Sep 3, 2011 #1
    If [itex]p[/itex] is a prime and [itex]a[/itex] an integer coprime with [itex]p[/itex], why is

    [itex]a^{\frac{p-1}{2}}\equiv -1 mod p[/itex] ?
     
  2. jcsd
  3. Sep 3, 2011 #2

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    It's not true. Consider p=5 and a=4.
     
  4. Sep 3, 2011 #3
    Yes, i was trying some examples and I think it only works with primitive roots... But why?
     
  5. Sep 3, 2011 #4

    micromass

    User Avatar
    Staff Emeritus
    Science Advisor
    Education Advisor
    2016 Award

    Are you aware of Fermat's little theorem?? Try to use that...
     
  6. Sep 3, 2011 #5

    I like Serena

    User Avatar
    Homework Helper

    Hah, that's basically the definition of a primitive root. :smile:

    Any co-prime "a" has a "period" indicating how soon it gets to "1".
    Fermat's little theorem guarantees that (p-1) will bring it back to "1".
    The actual period will be a divider of (p-1).
    Only for primitive roots, the period is exactly (p-1).
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Modular arithmetic
  1. Modular arithmetic (Replies: 11)

  2. N^2 Modular Arithmetic (Replies: 3)

  3. Modular arithmetic (Replies: 1)

Loading...