Solve $ord_x(2) = 20$

Question

Given that the (multiplicative) order of $2$ mod $x$ is $20$, how can I work out what $x$ is?

Answer 1

We seek $x$ such that $2$ has order $20\pmod x$. To do that, we first address the congruence $$2^{20}\equiv 1\pmod x$$

As $2^{20}-1=3\times 5^2\times 11\times 31\times 41$ we see that we are looking for $x$ that can be assembled from those terms. we then have to eliminate the orders $2,4,5,10$ (aka the non-trivial divisors of $20$). Clearly we need $x>20$

The smallest candidate is $x=25$. We easily verify that $2^{10}-1=1023\equiv 23\pmod {25}$ (the smaller exponents can be ruled out by inspection). Thus the order of $2\pmod {25}$ is $20$ as desired.

If you want a prime example, then $x=41$ works (it's the only one). Brute force reveals that $2^{10}-1\equiv 39 \pmod {41}$ and again the smaller candidates can be ruled out by inspection. That suffices.

The case of general exponent can be solved similarly...as you can imagine, it becomes difficult if $a$ is large.

Answer 2

Method 1:-

From Euler Totient Function(or theorem) we know-

$$a^{\phi(n)}\equiv1\pmod n$$ for $\gcd(a,n)=1$

Here you have,$2^{20}\equiv1\pmod n$.

Comparing the two equations we have,$\phi(n)=20$.Try to find $n$ from it.

Method 2:-

We know that for all $n$,$(a-b)|(a^n-b^n)$ and $a^n-b^n$ is also divisible by $a+b$ if $n$ is odd.

So,We need to find $x$ such that $x|2^{20}-1$

Note that $2^{20}-1$ can be written as $2^{20}-1^{20}$.

This can be written in the following forms-

$(2^5)^4-(1^5)^4$ Hence,$n=2^5-1$ is a factor.

$(2^{10})^2-(1^{10})^2$ Hence,$n=2^{10}-1$ is a factor.

$(2^4)^5-(1^4)^5$ Hence,both $2^4-1$ and $2^4+1$ are factors.

Important note-Factors of the values of $n$ given are also factors of the number.

Answer 3

You need $$2^k\cdot2^{20-k}=1$$ for $k=1,2,...,20$. In other words $2^k$ has as inverse $2^{20-k}$ Since $2$ is a primitive root modulo $11$ we examine if this is verified for $x=11$. We have in the field $\mathbb F_{11}$ $$\begin{cases}2^1=2\\2^2=4\\2^3=8\\2^4=5\\2^5=10\\2^6=9\\2^7=7\\2^8=3\\2^9=6\\2^{10}=1\end{cases}$$ and we can see the condition $2^k\cdot2^{20-k}=1$ is verified. So $\color{red}{x=11}$

Is there another solution? I will come back (some trouble to write in English and I could less the first answer as many times).

NOTE.-This is an answer to the question as it was formulated before it was changed: this question was $2^{20}\equiv 1\pmod x$

Answer 4

The divisors of $2^{20}-1$, which are not also divisors of $2^{10}-1$ or $2^4-1$ do the job. You will quickly find out that the smallest number satisfying this is $25$.

You can determine them with PARI/GP :

? for(s=1,n,if((Mod(2^20-1,s)==0)*(Mod(2^10-1,s)<>0)*(Mod(2^4-1,s)<>0),print1(s,
" ")))
25 41 55 75 123 155 165 205 275 451 465 615 775 825 1025 1271 1353 1705  2255 232
5 3075 3813 5115 6355 6765 8525 11275 13981 19065 25575 31775 33825 41943 69905
95325 209715 349525 1048575

Answer 5

By Fermat's little theorem we know that, in general, $n^{\varphi (x)} \equiv 1 \pmod x$ for every $n$ coprime with $x$. We want $x$, then, such that $\gcd (2,x) = 1$ (i.e. $2 \nmid x$) and $\varphi (x) = 20$.

By Euler's product formula, $x = p_1 ^{n_1} \dots p_k ^{n_k}$, then $\varphi (x) = (p_1 - 1) p_1 ^{n_1 - 1} \dots (p_k - 1) p_k ^{n_k - 1}$. Since $\varphi (x) = 20 = (5-1) \cdot 5^1$, it follows that $k=1$ and $p_1 = 5$, so $x = 5^2 = 25$ is a solution (clearly $2 \nmid 25$).