Theorems

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

For $a \in 𝔽$ , 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$ , then for ${𝗈𝗋𝖽}_{𝔽} (a) = k$ , $n \geq k$ , because by definition of order, $k$ is the smallest value that satisfies $a^{k} = 1$ . For any $n > k$ , $n$ has to be a multiple of $k$ , because in order to satisfy $a^{n} = a^{k} \cdot a^{n - k} = 1 \cdot a^{n - k} = 1$ , the next smallest possible value for $n$ is $2 k$ (as $a^{k}$ is the smallest value that is equal to 1). By induction, the possible values of $n$ are $n = k, 2 k, 3 k, \dots$ .

□

$⟨$ 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}, . . . = 1$ .
2.: Given ${𝗈𝗋𝖽}_{𝔽} (a^{n}) = m$ , ${(a^{n})}^{m}, {(a^{n})}^{2 m}, {(a^{n})}^{3 m}, . . . = 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 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)

Given $k | n$ , ${𝗈𝗋𝖽}_{𝔽} (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$ , we should prove that ${𝗈𝗋𝖽}_{𝔽} (a) = 𝑛𝑘$ . Let ${𝗈𝗋𝖽}_{𝔽} (a) = m$ . Then, by TheoremA-4.2.2, ${𝗈𝗋𝖽}_{𝔽} (a^{k}) = \frac{m}{gcd (m, k)}$ , which is $n$ . In other words, $m = n \cdot gcd (m, k)$ . But as $k | n$ , it is also true that $k | m$ . Then, $gcd (m, k) = k$ . Therefore, $m = n \cdot gcd (m, k) = 𝑛𝑘$ .

□

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

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

Proof.

1.: ${a^{1}, a^{2}, . . . a^{p}}$ forms a multiplicative subgroup $H$ of the group $G = 𝔽^{\times}$ (i.e., $𝔽$ without ${0}$ ).
2.: Lagrange’s Group Theory states that for any subgroup $H$ in a group $G$ , $| H |$ divides $| G |$ . This means that given ${𝗈𝗋𝖽}_{G} (a) = k$ (where $a^{k} = 1$ ), $k$ divides $| G |$ (where $| G | = p - 1$ ).
3.: Therefore, given $𝑘𝑙 = p - 1$ for some integer $l$ , $a^{p - 1} = {(a^{k})}^{l} = 1^{l} = 1$ . Thus, $a^{p} = a$ .

□