Exercise (6.2).13

Determine the order of $32 \pmod {89}$.

The order of $32 \pmod {89}$ exists because $\gcd(89,32)=1$.

Noting that $32=2^5$, we'll first work in base 2 then use the Order Formula.

The order of 2 modulo 89 is a factor of $\phi(89)=88$. These factors are 1, 2, 4, 8, 11, 22, 44, 88 and are the only ones we need to test.

The following calculations show that the order of 2 modulo 89 is 11.

n	2^n	2^n mod 89
2	4	4
4	16	16
8	256	78
11	2048	1

The Order Formula (6.8) tells us that if $k$ is the order of $a \pmod n$, then the order of $a^s \pmod n$ is $k / \gcd(s,k)$. 

And so, the order of $32 \pmod {89}$ is $11 / \gcd(5,11) = 11 / 1 = 11$.

Exercise (6.2).12

Let $n \ge 2$ and $\gcd (a, n) = 1$. Prove the following:

If $a^k \not \equiv 1 \pmod n$ for $1 \le k \le \frac{\phi (n)}{2}$ then the order of $a \pmod n$ is $\phi (n)$.

The order $k$ exists because $\gcd(a,n)=1$, and is a factor of $\phi(n)$. That is, for some positive integer $j$, we have

$$ k = \frac{\phi(n)}{j} $$

Let's consider two cases for $j$, namely $j \ge 2$ and $j=1$.

For $j \ge 2$ we have $k \le \frac{\phi(n)}{2}$, which we're given means $a^k \not \equiv 1 \pmod n$.

For the case $j=1$ we have $k=\phi(n)$. By Euler's Theorem this means $a^k \equiv 1 \pmod n$.

Because $\phi(n)$ is the least positive $k$ such that $a^k \equiv 1 \pmod n$, we conclude the order of $a \pmod n$ is $\phi (n)$.

Exercise (6.2).11

Let $n \ge 2$ and $\gcd (a, n) = 1$. Disprove the following:

If $a^{\frac{\phi(n)}{2}} \not \equiv 1 \pmod n$ then the order of $a \pmod n$ is $\phi(n)$.

We'll disprove the statement with a counter-example.

Let's set $a=6, n=7$. We the confirm that

• $n = 7 \ge 2$
• $\gcd(a,n)=\gcd(6.7)=1$
• $a^{\frac{\phi(n)}{2}} \equiv 6^{\frac{6}{2}} \equiv 6 \not \equiv 1 \pmod n$

We note the order of $6 \pmod 7$ is 2, which is not $\phi(n)=\phi(7)=6$.

This counter-example disproves the given statement.

Exercise (6.2).10

(a) Let $p$ be prime and $\gcd (a, p) = 1$. Show that if the order of $a \pmod p$ is $k$ and $k$ is even then

$$ a^{\frac{k}{2}} \equiv (p− 1) \pmod p$$

(b) Let $n \ge 2$ and $\gcd (a, n) = 1$.

Disprove that if the order of $a \pmod n$ is $k$ and $k$ is even then

$$ a^{\frac{k}{2}} \equiv \pm 1 \pmod n $$

(a) The order of $a \pmod p$ being $k$ means

$$ a^k \equiv 1 \pmod p $$

We're told $k$ is even, so $k=2j$ for some integer $j$,

$$ (a^{j})^2 \equiv 1 \pmod p $$

By Proposition (3.14), this means $a^j \equiv 1 \pmod p$ or $a^j \equiv -1 \pmod p$.

But $a^j \equiv 1 \pmod p$ is not possible as the order is $k$, the least positive integer such that $a^k \equiv 1 \pmod p$, and $j<k$. This leaves 

$$a^j \equiv -1 \equiv ( p-1 ) \pmod p $$

That is, $a^{\frac{k}{2}} \equiv (p− 1) \pmod p$.

(b) We disprove the statement with a counter-example.

Let's set $n=8, a=3$.

We confirm that $n=8 \ge 2$, and $\gcd(a,n)=\gcd(3,8)=1$. 

Because $3^1 \equiv 3 \pmod 8$ and $3^2 \equiv 1 \pmod 8$, the order $k$ of $a \pmod n$ is 2, which is even.

And so

$$ 3^{\frac{2}{2}} \equiv 3 \not \equiv \pm 1 \pmod 8 $$

This counter-example disproves the given statement.

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). 

Exercise (6.2).8

State the number of integers which have an order modulo $n$ for

(a) $n = 20$

(b) $n = 200$

(c) $n = 2000$

(d) $n = 20 000$

The number of integers that have an order modulo $n$ is those from 1 to $n$ which are co-prime to $n$, that is $\phi(n)$.

(a) $\phi(20) = 20 \times (1-\frac{1}{2}) \times (1-\frac{1}{5}) = 8$

(b) $\phi(200) = 200 \times (1-\frac{1}{2}) \times (1-\frac{1}{5}) = 80$

(c) $\phi(2000) = 2000 \times (1-\frac{1}{2}) \times (1-\frac{1}{5}) = 800$

(d) $\phi(20000) = 20000 \times (1-\frac{1}{2}) \times (1-\frac{1}{5}) = 8000$

Exercise (6.2).7

Determine the orders of the complete residue system modulo 12.

What do you notice about your results?

We first note that 12 is not prime, and so the order only exists for those numbers coprime to 12. These are 1, 5, 7, 11. Let's consider each in turn.

$1^1 \equiv 1 \pmod {12}$, and so the order of 1 modulo 12 is 1.

$5^2 \equiv 1 \pmod {12}$, and so the order of 5 modulo 12 is 2.

$7^2 \equiv 1 \pmod {12}$, and so the order of 7 modulo 12 is 2.

$11^1 \equiv -1 \pmod {12}$, which means $11^2 \equiv 1 \pmod {12}$, and so the order of 11 modulo 12 is 2.