Find the order of the following:
(a) $1 \pmod 5$
(b) $2 \pmod 5$
(c) $3 \pmod 5$
(d) $4 \pmod 5$
(a) $\gcd(5,1)=1$ and so the order exists.
Clearly $1^1 \equiv 1 \pmod 5$ and so the order of 1 modulo 5 is 1.
(b) $\gcd(5,2)=1$ and so the order exists.
We note that $2^2 \equiv -1 \pmod 5$, and so $2^4 \equiv 1 \pmod 5$.
Is this the smallest index? We can check:
- $2^1 \equiv 2 \not \equiv 1 \pmod 5$
- $2^2 \equiv 4 \not \equiv 1 \pmod 5$
- $2^3 \equiv 3 \not \equiv 1 \pmod 5$
And so the order of 2 modulo 5 is 4.
(c) $\gcd(3,5)=1$ and so the order exists.
The order is a factor of $\phi(5)=4$. These factors are 1, 2, 4.
- $3^1 \equiv 3 \not \equiv 1 \pmod 5$
- $3^2 \equiv 4 \not \equiv 1 \pmod 5$
- $3^4 \equiv 1 \pmod 5$
And so the order of 3 modulo 5 is 4.
(d) $\gcd(4,5)=1$ and so the order exists.
We note that $4 \equiv -1 \pmod 4$, and so $4^2 \equiv 1 \pmod 5$.
There is no smaller candidate than the index 2, and so the order of 4 modulo 5 is 2.