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}$?

  • 2
    $\begingroup$ $\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$? $\endgroup$ – fgrieu Oct 26 '16 at 10:32
  • 2
    $\begingroup$ 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). $\endgroup$ – Hope that's a start Oct 26 '16 at 12:00

I give an answer summarizing and precising the comments you provided.

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.


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.