3

These are the forms I'm talking about:

  1. $a^{p}\equiv a\pmod p$
  2. $a^{p-1}\equiv 1\pmod p$

I thought that the only difference was that (1) is true even when p does divide a (producing a trivial 0==0 in that case).

But then I found out that (2) seems to be a stronger one, by which I mean that if I'm trying them both for a p equal to a Carmichael number 561, then (1) holds for any a, and (2) breaks for some a's (those which are not coprime with p, I guess) thus exposing that p is not a prime (e.g. for 17 (1) holds and (2) gives 34).

(1) is also called "weaker definition" here.

But I can't find any strict definition of "stronger" for it, is there any?

PS: I know that there are better tests, I'm just trying to make sense of this one.

vorou
  • 131
  • The second definition applies , if $\ p\nmid a$ , which you mentioned as well. – Peter May 31 '20 at 06:04
  • If $\ n\ $ is squarefree , we have $a^n\equiv a\mod n$ for every $\ a\ $ as a definition equivalent to $a^{n-1}\equiv 1\mod n$ for every $\ a\ $ coprime to $\ n\ $ – Peter May 31 '20 at 06:10
  • 1
    Study the carmichael function (wikipedia), this article should completely clarify it. – Peter May 31 '20 at 06:15
  • Usually , $\ p\ $ is used , if we have a prime number and $\ n\ $ , if the number is arbitary. Fermat's little theorem only (generally) holds for primes, Euler has generalized it to $\ a^{\varphi(n)}\equiv 1\mod n\ $ whenever $\ \gcd(a,n)=1\ $ and the carmichael function improves this result. – Peter May 31 '20 at 06:19

0 Answers0