What is the order of $\bar{2}$ in the multiplicative group $\mathbb{Z}_{221}^\times$?

Question

What is the order of $\bar{2}$ in the multiplicative group $\mathbb{Z}_{221}^\times$?

I keep computing $2^0, 2^1,...$ until we get $1\ (\operatorname{mod} 221)$, but this will take forever! Is there an easier way to do this? A hint that was given is that $221= 13 \times 17$.

Answer 1

The order of $2$ mod $13$ is $\color{blue}{12}$ because $2^{12}\equiv1\bmod13$ by Fermat's little theorem,

but $2^6=64\equiv-1\not\equiv1$ and $2^4=16\equiv3\not\equiv1\bmod13$.

The order of $2 $ mod $17$ is $\color{blue}8$ because $2^4=16\equiv-1\bmod17$, so $2^8\equiv(-1)^2\equiv1\bmod17$.

The order of $2$ mod $221$ is the least common multiple of $\color{blue}{12}$ and $\color{blue}8$.

See this Wikipedia article about the Carmichael function.

Answer 2

While the essence of the answer is the same as in that by JW Tanner, I would like to offer a solution in a more algebraic language:

By the Chinese remainder theorem, we know that $$ \mathbb{Z}_{221}\simeq \mathbb{Z}_{13}\times \mathbb{Z}_{17}$$ by the isomorphism $$ x+221\mathbb{Z}\mapsto (x+13\mathbb{Z},x+17\mathbb{Z})$$ The order of $x$ and its image have to be the same.

Both $\mathbb{Z}_{13}$ and $\mathbb{Z}_{17}$ are fields, so their multiplicative groups are of order $12=2^2\cdot 3$ and $16=2^4$ respectively. Thus the order of $2$ in $\mathbb{Z}_{13}$ has to be in $\{2,3,4,6,12\}$ (because its order must divide the order of the multiplicative group, this is Lagrange's theorem). Just trying these possibilities you see that its order is $12$. Similarly the order of $2$ in $\mathbb{Z}_{17}$ is in $\{2,4,8,16\}$. Trying the first three possibilities gives that it's $8$.

Now if we are looking for the smallest integer $n>0$ such that $$(x+13\mathbb{Z},x+17\mathbb{Z})^n=(x^n+13\mathbb{Z},x^n+17\mathbb{Z})=(1,1)$$ it becomes clear that it must be the least common multiple of $12$ and $8$, which is $24$.