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
    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
    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).
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook