# Probability of Fermat test going wrong

How can I proof that in Fermat's primality test the probability of going wrong after k iterations is $\big(\frac{\phi(n)}{n-1}\big)^{k}$?

• $\left({\phi(n)\over n-1}\right)^k$ is an upper bound of the probability, which is typically much lower, except for Charmichael numbers 561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, ... $\;$ Hint: what happens if you make a Fermat test of a composite $n$ using a witness $x$ with $\gcd(x,n)\ne 1$?
– fgrieu
Oct 26 '16 at 10:32
• Hint: $\phi(n)$ is the number of invertible elements modulo $n$ and $n-1$ is the number of non-zero elements modulo $n$. Being invertible is equivalent to having some power that is $1$ modulo $n$. (Combine this with fgrieu's hint). Oct 26 '16 at 12:00

Being invertible in $\mathbb{Z}_{n }$ is equivalent to having some power equal to 1.
If $b$ is invertible there exist $b^{-1}$ and as we are working in finite groups in the sequence $1,b,b^2,...,b^n$ there must be repetitions, let's say $b^i = b^j$. Then using the existence of $b^{-1}$ we have that (assume $i > j$) $b^{i-j} = 1$ so for power $i-j$ we have 1 modulo n.
If we have some power that is equal to one, say $b^x$ then we can take $b^{-1} = b^{x-1}$
Now, in Fermat's test we pick $b$ in $\{1,\cdots,n-1\}$ and going wrong means that in fact $b^{n-1} = 1$ so that $b$ must be invertible. Therefore, the total number or wrongs $W$ must be bounded by $\phi(n)$. The probability of going wrong in k attempts is therefore $\big(\frac{W}{n-1}\big)^k \le \big(\frac{\phi(n)}{n-1} \big)^k$ assuming independence.
As fgrieu pointed out this is only an upper bound which is an equality if number $n$ has the particularity that every invertible $b$ verifies $b^{n-1} = 1$ so that $W = \phi(n)$. These funny numbers are Carmichael numbers.