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

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?

## 2 Answers

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

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.

• @ArekKrawczyk Also, as lab pointed out, be careful with $9$ as it is not prime. I missed that. Commented Oct 26, 2013 at 17:02