# How to solve $n$ in $5^{n-1}\equiv 1 \pmod{n}$

$5^{n-1}\equiv 1 \pmod{n}$

I see that this holds true when $n$ is prime by Fermat's little theorem. However there could be few composite numbers, $n$ for which the congruence might hold true ? How to find them ?

I know how to handle problems involving the variable outside the mod, like, $2^{500}\equiv x \pmod{5}$ etc... but never dealt with the problems when the unknown is inside the mod itself. Any help is highly appreciated!

We have just started congruences chapter and I know basic congruence properties and Fermat little theorem. If possible, kindly avoid carmichael numbers/group theory/euler theorems as they are not covered yet. Thank you!

• You are asking for a "nice" characterization of the Fermat pseudoprimes to the base $5$. That may be difficult. The smallest one I can think of is $n=124$. – André Nicolas Sep 17 '14 at 18:12
• As was pointed out by a comment now gone, I missed $n=4$. – André Nicolas Sep 17 '14 at 18:38
• @AndréNicolas Oh, sorry, I have moved this comment with $n=4$ to the "answer" (although your comment is already an answer). Actually, Crandall and Pomerance also exclude $n=4$. – Dietrich Burde Sep 17 '14 at 19:10

There is help in terms of the integer sequences project. There Fermat pseudoprimes to the base $5$ have been found; see here. The page gives some helpful references too, but a "nice" characterisation seems not to be available. The sequences starts with $4, 124, 217, 561, 781, 1541,\ldots$, so the smallest $n$ is equal to $4$.