Find the order of $2 \pmod {1001}$.
We first check $\gcd(1001, 2)=1$ which means the order exists.
The order is a factor of $\phi(1001)=720$. These factors are 1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, 16, 18, 20, 24, 30, 36, 40, 45, 48, 60, 72, 80, 90, 120, 144, 180, 240, 360, 720.
The following tables shows calculations for the first few factors, and shows the order is not one of the factors between 2 and 36.
| n | 2^n | 2^n mod 1001 |
| 2 | 4 | 4 |
| 3 | 8 | 8 |
| 4 | 16 | 16 |
| 5 | 32 | 32 |
| 6 | 64 | 64 |
| 8 | 256 | 256 |
| 9 | 512 | 512 |
| 10 | 1024 | 23 |
| 12 | 4096 | 92 |
| 15 | 32768 | 736 |
| 16 | 65536 | 471 |
| 18 | 262144 | 883 |
| 20 | 1048576 | 529 |
| 24 | 16777216 | 456 |
| 30 | 1073741824 | 155 |
| 36 | 68719476736 | 911 |
We need undertake the calculations more indirectly, as follows, making use of these previous results
$$ 2^{40} \equiv (2^{10})^4 \equiv (23)^4 \equiv 562 \pmod {1001} $$
$$ 2^{45} \equiv (2^9)^5 \equiv (512)^5 \equiv 967 \pmod {1001} $$
$$ 2^{48} \equiv (2^{12})^4 \equiv (92)^4 \equiv 729 \pmod {1001} $$
$$ 2^{60} \equiv (2^{30})^2 \equiv (155)^2 \equiv 1 \pmod {1001} $$
And so the order of 2 modulo 1001 is 60.