I was wondering if there was a 'smart' way to solving a congruence like: . This is a sub-problem to an overall problem but I think I'm on the right track. Things to note: there are exactly 3 solutions and all integers with ordre six satisfies the congruence (as a consequence of earlier work).
I know the solutions are but I could only come up with a brute force way of finding them:
To attain integer solutions to a, we see that:
Now it's a matter of testing values of a from 1 to 31 until k is an integer. Luckily, it doesn't take long to find a = 6 works which implies that works as well.
This is a rather inelegant way of doing it so is there a better way of doing this or would this suffice?
The problem is finding the primitive root.
I find the solution by NonCommAlg to be the best approach.
But it is not so bad because once the primitive root r is found the index of -1 is then .
Thus, knowledge of the primitive root will basically solve the problem immediately.