2
$\begingroup$

$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!

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – André Nicolas Sep 17 '14 at 18:12
  • $\begingroup$ As was pointed out by a comment now gone, I missed $n=4$. $\endgroup$ – André Nicolas Sep 17 '14 at 18:38
  • $\begingroup$ @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$. $\endgroup$ – Dietrich Burde Sep 17 '14 at 19:10
5
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ I see that this problem is equivalent to pseudoprimes. I'll search further. Thank you so much :) $\endgroup$ – rsadhvika Sep 17 '14 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.