Number Theory: Find Multiplicative Order for (a,n) = 1

[SeReNiTy]

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?

 

[ramsey2879]

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?

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.

 

[Kummer]

So how do i find k if phi(n) does not equal k?

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.