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}$?
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 &gt; 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.