Question 33 Pre Write

33. Let $p$ be a prime.
a. Prove that if $[0]\neq [a]\in \mathbb{F}_p$, then $\{[a],[2a],\dots, [(p-1)a]\}=\mathbb{F}_p^\times$.
Proof: For $1 \leq b \leq p-1$ there exists some $c$ such that $[ca]=[b]$. We can use this fact to show that $\{[a],[2a],\dots, [(p-1)a]\}= \{[1], [2],\dots,[p-1]\}$.

b. Prove Fermat's little theorem: if $[0]\neq [a]\in \mathbb{F}_p$ , then $[a]^{p-1}=[1]$.
Proof: Let $S = \{1,2,3,\cdots, p-1\}$. Then, the set $a \cdot S$, is $S \equiv \{1a, 2a, \cdots, (p-1)a\} \pmod{p}$
None of the $ia$ for $1 \leq i \leq p-1$ are divisible by $p$, so we can show that all of the elements in $a \cdot S$ are distinct. Suppose that $ai \equiv aj \pmod{p}$ for $i \neq j$. Since $GCD(a,p) = 1$, by the cancellation rule, that reduces to $i \equiv j \pmod{p}$, which is a contradiction.
Thus, $\mod{p}$, we have that the product of the elements of $S$ is
$1a \cdot 2a \cdots (p-1)a \equiv 1 \cdot 2 \cdots (p-1) \pmod{p}$
Cancelling the factors $1, 2, 3, \ldots, p-1$ from both sides, we are left with $a^{p-1} \equiv 1 \pmod{p}$.

page revision: 4, last edited: 12 Apr 2018 01:54