Probabilidad de que la prueba de Fermat devuelva "probablemente primo"

Question

Nuestro objetivo es demostrar que la probabilidad de impar $n>1$ pasar la prueba de Fermat para todas las bases a coprima a n es $$\frac{1}{\phi(n)}\prod_{p|n, p \ prime}gcd(p-1,n-1) $$ donde $\phi$ es la función totiente de Euler. Ya sabemos que los únicos números que pasan son los primos y los números de Carmichael, así que satisface

(i) $ \ n$ es libre de cuadrados

(ii)Para todos los $p|n$ tenemos $\ p-1|n-1$

La probabilidad de que $d|n$ es $1-\frac{1}{n-1}\phi(n-1)$ Pero, aparte de esto, no estoy seguro de cómo probarlo. Gracias.

Answer 1

Dejamos que $n$ tienen factorización $$n=\prod_{p_i|n} p_i^{\alpha_i}$$ Por el Teorema Chino del Resto, el número de soluciones de la congruencia $b^{n-1}=n\mod{n}$ es el producto del número de soluciones de las congruencias $b^{n-1}=1\mod{p_i^{\alpha_i}}$ . Para cada uno de estos $p_i$ el grupo multiplicativo módulo $p_i^{\alpha_i}$ es de orden cíclico $\phi(p_i^{\alpha_i})=p_i^{\alpha_i-1}(p_i-1)$ .

Desde $p_i|n, n-1$ es primordial para $p_i^{\alpha_i-1}$ por lo que el número de soluciones en el grupo multiplicativo módulo $p_i^{\alpha_i}$ es $gcd(p_i-1,n-1)$ . Dividiendo por cada $\phi(p_i^{\alpha_i})$ y llevar el producto a través de todos los $i$ obtenemos nuestro resultado $$\frac{1}{\phi(n)}\prod_{p_i|n}gcd(p_i-1,n-1)$$