Friday, 17 April 2026

Exercise (6.2).9

(a) Show that the order of $1 \pmod n$ is 1.

(b) Show that the order of $(n− 1) \pmod n$ where $n > 2$ is 2.


(a) The order of $1 \pmod n$ is the smallest positive $j$ such that $1^j \equiv 1 \pmod n$.

Here $j=1$ satisfies $1^j \equiv 1 \pmod n$. 

Furthermore, $j$ is the smallest positive integer, and so it satisfies the requirements to be an order.


(b) The order of $(n-1) \pmod n$ is the smallest positive $j$ such that $(n-1)^j \equiv 1 \pmod n$.

Since we are asked to show the order is $2$, we only need to rule out $j=1$ and show that $j=2$ satisfies $(n-1)^j \equiv 1 \pmod n$ . 

Taking $j=1$ gives us

$$ (n-1)^1 \equiv n -1 \equiv - 1\pmod n$$

This is not equivalent to 1. 

Having ruled out $j=1$, let's consider $j=2$.

$$ (n-1)^2 \equiv n^2 -2n + 1 \equiv 1 \pmod n $$

And so the order of $(n− 1) \pmod n$ where $n > 2$ is 2.


Note: The exercise assumed the existence of the orders. If the assumption wasn't made, then we would need to show $\gcd(1,n)=1$ for part (a), and $\gcd(n-1,n)=1$ for part (b).