Theorems

$⟨$ Theorem A-4.2.1 $⟩$ Order Property (I)

For $a \in 𝔽^{\times}$ , and $n \geq 1$ , $a^{n} = 1$ if and only if ord $_{𝔽} (a) ∣ n$

(i.e., ${𝗈𝗋𝖽}_{𝔽} (a)$ divides $n$ ).

Proof.

1.: Forward Proof: If ${𝗈𝗋𝖽}_{𝔽} (a) | n$ , then for ${𝗈𝗋𝖽}_{𝔽} (a) = k$ where $k$ is $a$ ’s order, and $n = 𝑙𝑘$ for some integer $l$ .
Then, $a^{n} = a^{𝑙𝑘} = {(a^{k})}^{l} = 1^{l} = 1$ .
2.: Backward Proof: If $a^{n} = 1$ and ${𝗈𝗋𝖽}_{𝔽} (a) = k$ , write $n = 𝑞𝑘 + r$ with $0 \leq r < k$ . Then $1 = a^{n} = a^{𝑞𝑘 + r} = {(a^{k})}^{q} a^{r} = a^{r}$ . By minimality of $k$ , we must have $r = 0$ , hence $k ∣ n$ .

□

$⟨$ Theorem A-4.2.2 $⟩$ Order Property (II)

If ${𝗈𝗋𝖽}_{𝔽} (a) = k$ , then for any $n \geq 1$ , ${𝗈𝗋𝖽}_{𝔽} (a^{n}) = \frac{k}{\gcd (k, n)}$ .

Proof.

1.: $a^{k}, a^{2 k}, a^{3 k}, \dots = 1$ .
2.: Given ${𝗈𝗋𝖽}_{𝔽} (a^{n}) = m$ , ${(a^{n})}^{m}, {(a^{n})}^{2 m}, {(a^{n})}^{3 m}, \dots = 1$
3.: Note that by definition of order, $x = k$ is the smallest value that satisfies $a^{x}$ = 1. Thus, given ${𝗈𝗋𝖽}_{𝔽} (a^{n}) = m$ , then $m$ is the smallest integer that makes ${(a^{n})}^{m} = 1$ . Note that ${(a^{n})}^{m}$ should be a multiple of $a^{k}$ , which means $𝑚𝑛$ should be a multiple of $k$ . The smallest possible integer $m$ that makes $𝑚𝑛$ a multiple of $k$ is $m = \frac{k}{\gcd (k, n)}$ .

□

$⟨$ Theorem A-4.2.3 $⟩$ Order Property (III)

${𝗈𝗋𝖽}_{𝔽} (a) = 𝑘𝑛$ if and only if ${𝗈𝗋𝖽}_{𝔽} (a^{k}) = n$ .

Proof.

1.: Forward Proof: Given ${𝗈𝗋𝖽}_{𝔽} (a) = 𝑘𝑛$ , and given Theorem A-4.2.2, ${𝗈𝗋𝖽}_{𝔽} (a^{k}) = \frac{𝑛𝑘}{\gcd (k, 𝑛𝑘)} = \frac{𝑛𝑘}{k} = n$ .
2.: Backward Proof: Given ${𝗈𝗋𝖽}_{𝔽} (a^{k}) = n$ and letting ${𝗈𝗋𝖽}_{𝔽} (a) = m$ , Theorem A-4.2.2 gives $m ∕ \gcd (m, k) = n$ , so $m = n \gcd (m, k)$ . In particular $k ∣ m$ , hence $m = 𝑛𝑘$ .

□

$⟨$ Theorem A-4.2.4 $⟩$ Fermat’s Little Theorem

Given $| 𝔽 | = p$ (a prime) and $a \in 𝔽$ , $a^{p} = a$ .

Proof.

1.: If $a = 0$ , then $a^{p} = a = 0$ .
2.: If $a \neq 0$ , then $a \in 𝔽^{\times}$ , the multiplicative group of the field, which has size $| 𝔽^{\times} | = p - 1$ . By Lagrange’s theorem (in a finite group $G$ , the order of any element divides $| G |$ ), the order of $a$ divides $p - 1$ , hence $a^{p - 1} = 1$ . Therefore $a^{p} = a$ .

□