Encontrar todos los primos $p$ tal que $\text{ord}_p(2)=100$

Question

Pregunta sobre el libro de texto :

Exactamente tres primos p con $ord_p (2) = 100$ . Encuéntralos y demuestra que tu lista está completa.

Mi enfoque :

• factorizar $2^{100} - 1$ $2^{100} - 1 = 3^1*5^3*11^1*31^1*41^1*101^1*251^1*601^1*1801^1*4051^1*8101^1*268501^1$

• para cada uno de los primos de arriba he probado si: $2^{100} \ (\bmod prime) =^{?}= 1$ y el resultado es:

$3, 5, 11, 31, 41, 101, 251, 601, 1801, 4051, 8101, 268501$

Por lo tanto, tengo $12$ primos pero la pregunta dice que debería ser $3$ primos. Estoy confundido.

Código Sage :

number = 2^100 - 1
arr = list(factor(number))

for (prime, exponent) in arr:
    if 2^100 % prime == 1:
        print prime

Answer 1

Una pista: $ord_3(2)=2 \ne 100$ .

No sólo es necesario $2^{100}\equiv 1$ pero $2^k \not \equiv 1$ si $k <100$ .

Como $2^k \equiv 1 \implies k|ord_p (2)$ sólo tenemos que probar $k=2,4,5,10,20,25,50$

también si $2^{50} = -1$ eres bueno. Si $2^k =-1 $ y $k <50$ no eres tan $2^{2k}=1$ .

Ex $2^2\equiv -1 \mod 5$ así que $5$ está fuera.

$2^4 = 5\mod 11$ así que $2^5=10=-1\mod11$ . Así que el 11 está fuera. Y así sucesivamente.

Otra pista:

Si $ord_p (2) = 100$ entonces $2^{50}=-1$ y $2^{25} \ne 1;-1$ . Pero si $ord_p (2) <100$ entonces $2^{50}=1$ y $2^{25}=1;-1$ .

Así que sólo tienes que comprobar $2^{25} $ .

Answer 2

Desde $2^{p-1}=1$ (mod $p$ ), $p-1$ debe ser divisible por $100$ así que $p$ es de la forma $100k+1$ . Por otro lado $2^{50}=-1$ (mod $p$ ) por lo que $p$ divide $2^{50}+1$ .

Los factores primos de $2^{50}+1$ son {5,41,101,8101,268501}.

Sólo tres de ellos son de la forma $100k+1$ .

Answer 3

Código Arce

S:=[3, 5, 11, 31, 41, 101, 251, 601, 1801, 4051, 8101, 268501];
ord2:=proc(n) local k: for k from 1 while (2^k-1) mod n <>0  do  end do: k end proc;
map(ord2,S);
[2, 4, 10, 5, 20, 100, 50, 25, 25, 50, 100, 100]

Ahora puede encontrar el $3$ primos.

Answer 4

Consideremos el grupo abeliano (multiplicativo) $\mathbf{F}_p^*$ , un grupo de orden $p-1$ . Ahora $\mathrm{ord}_p(2)$ significa orden de $2$ en este grupo $\mathbf{F}_p^*$ . Si queremos que el orden sea 100 entonces una condición necesaria es que 100 debe dividir $p-1$ .

Así que de su lista de divisores primos de $2^{100}-1$ Sólo los de 101 en adelante lo cumplen. Para asegurar la minimidad de cada uno de esos primos, comprueba $ 2^{50}\not\equiv1\pmod p,\&\ 2^{20}\not\equiv1\pmod p $ . (Los números 50 y 20 se obtienen dividiendo 100 entre sus divisores primos. Para que 100 sea el menor $k$ para satisfacer $2^k\equiv1\pmod p$ Esto es necesario. )

Answer 5

He arreglado el código. Gracias a todos por las respuestas/consejos. Este es el código de SageMath por si acaso:

number = 2^100 - 1
result = []

for (prime, exponent) in factor(number):
    flag = True

    for i in range(1, 100): # can be 25 instead of 100
        if (2^i % prime) == 1:
            flag = False

    if flag:
        result.append(prime)

print list(set(result))

La salida:

[268501, 101, 8101]