The title is a bit long, but i think it explains my question well.
Let's say we want to test if an integer p is prime
With Fermat's Little Theorem this is a simple check if
$a^{p-1} \equiv 1 (mod \ p)$
But using the Euler's version:
If $gcd(a,n) = 1, $ then $\ a^{\Phi(n)} \equiv 1 (mod\ n)$
Can we say with a high probability that n is a prime in this case?
Best Answer
We cannot say that $n$ is prime, given $a^{n-1}\equiv 1 \bmod n$; see Carmichael numbers:
Understanding Carmichael Number
Fermat primality test $\gcd$ condition and carmichael numbers