Find all primes $p$ such that $\text{ord}_p(2)=100$

Question

Textbook question:

Exactly three primes p with $ord_p (2) = 100$. Find them and show your list is complete.

My approach:

• factorize $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$

• for each of primes in above I tested if: $2^{100} \ (\bmod prime) =^{?}= 1$ and result is:

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

So, I get $12$ primes but question says it should be $3$ primes. I am confused.

Sage code:

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

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

Answer 1

Hint: $ord_3(2)=2 \ne 100$.

You need not just $2^{100}\equiv 1$ but $2^k \not \equiv 1$ if $k <100$.

As $2^k \equiv 1 \implies k|ord_p (2)$ we just need to test $k=2,4,5,10,20,25,50$

also if $2^{50} = -1$ you are good. If $2^k =-1 $ and $k <50$ you aren't as $2^{2k}=1$.

Ex $2^2\equiv -1 \mod 5$ so $5$ is out.

$2^4 = 5\mod 11$ so $2^5=10=-1\mod11$. So 11 is out. And so on.

Nother hint:

If $ord_p (2) = 100$ then $2^{50}=-1$ and $2^{25} \ne 1;-1$. But if $ord_p (2) <100$ then $2^{50}=1$ and $2^{25}=1;-1$.

So you just need to check $2^{25} $.

Answer 2

Since $2^{p-1}=1$ (mod $p$), $p-1$ must be divisible by $100$ so $p$ is of the form $100k+1$. On the other hand $2^{50}=-1$ (mod $p$) so $p$ divides $2^{50}+1$.

The prime factors of $2^{50}+1$ are {5,41,101,8101,268501}.

Only three of these are of the form $100k+1$.

Answer 3

Maple code

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]

Now you can find the $3$ primes.

Answer 4

Consider the (multiplicative) abelian group $\mathbf{F}_p^*$, a group of order $p-1$. Now $\mathrm{ord}_p(2)$ means order of $2$ in this group $\mathbf{F}_p^*$. If we want the order to be 100 then a necessary conditions is that 100 should divide $p-1$.

So from your list of prime divisors of $2^{100}-1$, only those from 101 onwards satisfy this. To ensure minimality for each of those primes, check $ 2^{50}\not\equiv1\pmod p,\&\ 2^{20}\not\equiv1\pmod p $. (The numbers 50 and 20 come by dividing 100 by its prime divisors. For 100 to be least $k$ to satisfy $2^k\equiv1\pmod p$, this is needed. )

Answer 5

I fixed the code. Thanks everyone for the all answers/hints. This is the SageMath code just in case:

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))

Output:

[268501, 101, 8101]