Smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$

Question

Can anybody give me a hint about how to find smallest such $n \in \mathbb{N}$ that $2^{n} \equiv 1 \pmod{5\cdot 7\cdot 9\cdot 11\cdot 13}$?

I thought that I will find it piece by piece with help from my friend Fermat's Little Theorem, so :

1. $2^{n_{1}} \equiv 1 \mod 5$, so $n_{1}=4$.

2. $2^{n_{2}} \equiv 1 \mod 7$, so $n_{2}=6$.

3. $2^{n_{3}} \equiv 1 \mod 3$, so $n_{3}=2$.

4. $2^{n_{4}} \equiv 1 \mod 11$, so $n_{4}=10$.

5. $2^{n_{5}} \equiv 1 \mod 13$, so $n_{5}=12$.

So, since I know that $x \equiv y \mod mz \Leftrightarrow x \equiv y \mod m$ when $z \neq 0$, so my lucky was to take the lowest common multiple of $4,6,2,10,12$, which is $60$ and lo and behold it fits the bill. But is it the smallest such $n$? If so, how to explain it?

Answer 1

You are looking for the smallest $n_1,..,n_5$, FLT only gives you some $n$. But you should know that the order (the smallest such $n_i$) divides any other $n$.

So in each line, the smallest one must be a divisor of the one given by FLT.

1. You know $2^{n_{1}} \equiv 1 \mod 5$ and $n_1$ is a divisor of $4$. Since $1,2$ don't work $n_1=4$.

2. You know $2^{n_{2}} \equiv 1 \mod 7$ and $n_1$ is a divisor of $6$. We test $1,2,3,6$ and the smallest one which works is....

Continue.

At the end, the smallest number which works must be divisible by all of them, thus the lcm is the right choice.

Answer 2

First of all, $p-1$ is not necessarily the Multiplicative Order ord$_pa$ for prime $p$ and $(a,p)=1$

For example, ord$_72=3\ne 7-1$

Again, $9=3^2$ is not prime, we need Euler's Totient Theorem here

Now as ord$_{11}2=10$ and ord$_{13}2=12,$ there can be no number $<$lcm $(10,12)=60$ to satisfy $2^n\equiv1\pmod {5\cdot7\cdot9\cdot11\cdot13}$