Trying to find a modulo for $2^{24}$

Question

I was trying to figure out which modulo $n$ would make $2^{24}$ congruent to $1 \bmod n$. One answer is $241$, and I wonder if there is a good way to find it.

I tried to use Fermat's little theorem or Chinese Remainder theorem, but $24$ is not a prime and $241$ is not composite.

Answer 1

Direct factoring gives:

$$2^{24}-1=(2^{12}-1)(2^{12}+1)=(2^6-1)(2^6+1)(2^{12}+1)=(2^3-1)(2^3+1)(2^6+1)(2^{12}+1)$$

So: $2^3-1=7$ will work (as will $3$ or any of the factors of $2^6+1$ or $2^{12}+1$).

Indeed, a little effort shows that the full list of primes that work here is $\{3,5,7, 13,17, 241\}$

Answer 2

We want to find factors of

\begin{align}(2^{24}-1)&=(2^{12}-1)(2^{12}+1)\\ &= (2^6-1)(2^6+1)(2^{12}+1) \end{align}

Hence we can for example, pick our $n$ to be $2^6-1, 2^6+1$ or $2^{12}+1$. Notice that $241$ is a factor of $2^{12}+1$.

Also note that $$2^{24}=(2^3)^8=(7+1)^8$$

Hence we can pick $n=7$.

Also $$2^{24}=(2^8)^3=((2^8-1)+1)^3$$

Hence, we can pick $n=2^8-1$ or its factors and so on.

Answer 3

the simplest is to find an odd prime $p$ such that $p-1$ is a divisor of $24$. You have at once: $$p= 3, 5, 7,13.$$ You also have chances it works with a prime $p$ such that a divisor of $24$ ($>1$) is also a divisor of $p-1$. For instance $17$ works ($2$ has order $8$ modulo $17$).

Answer 4

Factor the Mersenne number:

$$ 2^{24} - 1 = 2 \cdot 3 \cdot 5 \cdot 7 \cdot 13 \cdot 17 \cdot 241 $$