We aim to show that probability of odd $n>1$ passing the Fermat test for all bases a coprime to n is $$\frac{1}{\phi(n)}\prod_{p|n, p \ prime}gcd(p-1,n-1) $$where $\phi$ is the Euler totient function. We already know that the only numbers that pass are primes and Carmichael numbers, so satisfy
(i)$ \ n$ is square-free
(ii)For all $p|n$, we have $\ p-1|n-1$
The probability that $d|n$ is $1-\frac{1}{n-1}\phi(n-1)$, but other than this I am unsure as to how to go about proving this. Thanks.
We let $n$ have factorisation $$n=\prod_{p_i|n} p_i^{\alpha_i}$$ By the Chinese Remainder Theorem, the number of solutions to the congruence $b^{n-1}=n\mod{n}$ is the product of the number of solutions to the congruences $b^{n-1}=1\mod{p_i^{\alpha_i}}$. For each such $p_i$, the multiplicative group modulo $p_i^{\alpha_i}$ is cyclic order $\phi(p_i^{\alpha_i})=p_i^{\alpha_i-1}(p_i-1)$.
Since $p_i|n, n-1$ is prime to $p_i^{\alpha_i-1}$, so the number of solutions in the multiplicative group modulo $p_i^{\alpha_i}$ is $gcd(p_i-1,n-1)$. Dividing by each $\phi(p_i^{\alpha_i})$ and taking the product across all $i$ we get our result $$\frac{1}{\phi(n)}\prod_{p_i|n}gcd(p_i-1,n-1)$$