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

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

• Some of them have order less than 100. Example $2^2 = 1\mod 3$ so it isn't three. You need to show $2^{50} \not \mod p$. Nov 5, 2016 at 6:35
• @fleablood can you please clarify more. I attached my code. Thank you. Nov 5, 2016 at 6:42
• Wait, this is programming? Not math? Add another if clause. If 2^100 % prime 1 then check that 2^k does not % 1 for $k=1....99$. Nov 5, 2016 at 6:51
• 2^2=3+1, so 3 is out. 2^2=5-1 so 5 is out. 2^5=33-1so 11 is out, 2^5=31+1 so 31 is out. Nov 5, 2016 at 6:55

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}$.

• Sorry for my poor math knowledge, So for each $k$ less than 100, I need to test if $2^{k} \bmod prime \neq 1$ Nov 5, 2016 at 7:06
• You don't have to test all. Just k=2,4,5,10,20,25,and 50. In fact, you just have to test k=25. If 2^25 ne 1 or -1 then ord of 2 is the full 100. Nov 5, 2016 at 7:13

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$.

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.

• Why you have only two primes? i.e. 2 and 5 instead of 3 primes Nov 5, 2016 at 7:38
• No. From the list you may see that the primes are $101, 8101, 268501$
– Leox
Nov 5, 2016 at 7:46

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

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]