\documentclass[a4paper,12pt]{article}

\begin{document}

\parindent=0pt

QUESTION

Find the orders of the following elements:-

(i) 2 mod 7\hspace{1.5cm} (ii) 3 mod 14\hspace{1.5cm} (iii) 5 mod
17.



ANSWER

Note that if gcd$(a,n)=1$, then the order of $a$ mod $n$ is a
divisor of $\phi(n)$.

\begin{description}

\item[(i)]
$\phi(7)=6$, so $o(2)$ is 1,2,3 or 6. $o(2)\neq1$ as only 1 has
order 1, and $o(2)\neq2$ as only $-1$ has order 2. (This is
because 7 is prime, so th only roots of $x^2\equiv1$ mod 7 are
$\pm1$) If we calculate $2^3$ mod  7 we find $2^3\equiv8\equiv1$
mod 7, so the order of 2 mod 7 is 3.

\item[(ii)]
$\phi(14)=14\left(1-\frac{1}{2}\right)\left(1-\frac{1}{7}\right)=6$
so the order is 1,2,3 or 6. Again, only 1 has order 1, so we may
eliminate 1, but the argument we used too eliminate 2 worked for
primes only, so we must check 2 directly. $3^2\equiv9\not\equiv1$
mod 14. so the order is not 2. Also
$3^3\equiv27\equiv-1\not\equiv1$ mod 14, so the order is not 3.
Thus the order must be 6.

\item[(iii)]
$\phi(17)=16$, so the order is 1,2,4,8 or 16. As 17 is a prime, we
can eliminate 1 and 2 as in part (i). Now
$5^4\equiv25^2\equiv8^2\equiv64\equiv13$ mod 17, so the order is
not 4. Also $5^8\equiv13^2\equiv(-4)^2\equiv16$ mod 17, so the
order is not 8. Thus the order is 16.

\end{description}




\end{document}
