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

Multiplicative order

  1. Sep 9, 2007 #1
    Hey guys, I've been studying some number theory recently and have a question. We know if (a,n) = 1 then a^phi(n) is congruent to 1 (mod n)

    where phi(n) = euler's totient function

    Now my question is the totient function does not always return the smallest possible integer such that a^k is congruent to 1. So how do i find k if phi(n) does not equal k?
  2. jcsd
  3. Sep 9, 2007 #2
    k would be a divisor of phi(n) but as far as I know there is no known formula for specific n and a except for a = +/-1 mod n in which case k = 1 or 2.
  4. Sep 10, 2007 #3
    The numbers that has phi(n) as there orders are called primitive roots. It is still an unresolved problem in mathematics, i.e. how to determine the primitive roots of numbers. (However, something about special cases are known).

    Thus, brute force is the best way to go.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook