Loading [MathJax]/extensions/TeX/mathchoice.js

1 votos

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

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 1ϕ(n)p|n,p primegcd(p1,n1) donde ϕ 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  p1|n1

La probabilidad de que d|n es 11n1ϕ(n1) Pero, aparte de esto, no estoy seguro de cómo probarlo. Gracias.

1voto

Will Seath Puntos 1

Dejamos que n tienen factorización n=pi|npαii 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)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X