In $\mathbb{Z}_q$ where $q$ is prime, show that $[a^q]=[a]$ for all $[a]\in \mathbb{Z}_q$

Question

Question: In $\mathbb{Z}_q$ where $q$ is prime, show that $a^q=a$ for all $a\in \mathbb{Z}_q$.

My attempt: To show $[a^q]=[a]$ for all $[a]\in \mathbb{Z}_q$, it suffices to show that for any $a\in\mathbb{Z}_q$, $a^q \equiv a(\mod q)$. In other words, we want to show that $q$ divides $a^q-a$. Then I just got stuck.

$a^q-a$=$a(a^{q-1}-1)$. Since $q$ does not divide $a$, it has to divide $a^{q-1}-1$. But then I don't know how to proceed. How should I translate the condition that "$q$ is prime"? I only know that $\gcd(q,a^q)=$ has to be either $1$ or $q$. I did some experiments with examples and seems like it has to be $1$ (although I cannot think of a proof ).

Even then, all I can conclude is that $\exists u,v\in\mathbb{Z}$ such that $1=qu+a^q v$, and I don't see how that could help me. Or maybe I should use the fact that $\mathbb{Z}_q$ is a field?

Answer 1

We can show that this is true for any integer $a \in \mathbb{N}$, that is $a^q - a$ is divisible by $q$ for any $a \in \mathbb{N}$.

First of all, for $a=1$ this is simply $1-1 = 0$ and $q$ divides $0$.

Now assume this is true for some $a \ge 1$. We will show that the statement holds for $a+1$.

Now $(a+1)^q = a^q + 1 + \sum_{n=1}^{q-1} {q \choose n} a^{n}$. This means that $$(a+1)^q - (a+1) = a^q - a + \sum_{n=1}^{q-1} {q \choose n} a^{n}.$$ By induction, the first term is divisible by $q$. For the sum, it is enough to recognize that $${q \choose n} = \frac{q \cdot (q-1) \cdot (q-2) \cdots (q-n-1)}{(q-n)!}$$ is divisible by $q$ for each $n$.

This theorem you are asking about is known as Fermat's Little Theorem. This is the standard proof that can be found in many textbooks, as @MarcvanLeeuwen points out.

---

My favorite proof of Fermat's little theorem is through a coloring method, and can be found in George Andrew's text on Number Theory as well as on the first page of "A Coloring Proof of a Generalisation of Fermat's Little Theorem" C. J. Smyth.

Essentially you have $p$ boxes arranged in a circle, and you have $a$ number of colors available to paint them with. There are a total of $a^p$ ways to paint these boxes, and $a$ ways to paint them all the same color. The number of colorings where the boxes are not all colored the same is $a^p - a$. This must be a multiple of $p$ since for each such coloring, the boxes can be rotated $p$ times to obtain different colorings.

That's a quick and sketchy proof, but I thought it was pretty nifty.

Answer 2

If you want to use group theory, use that the multiplicative group $\def\Z{\Bbb Z}(\Z/q\Z)^\times$ has order $q-1$, and the fact that the order of every element divides the order of the group. If you want to use ring theory, use that $(a+b)^q=a^q+b^q$ in characteristic $q$ (proved using the binomial formula and an arithmetic property of binomial coefficients), which implies that from $x^q=x$ it follows that $(x+1)^q=x+1$. Also $0^q=0$.

If these arguments do not work for you, you can take a look at the proofs of Fermat's little theorem to see if any one suits your taste. Here is a fairly basic argument I found there (essentially the same as the first one above, but without using the language of group theory). Consider $a\neq0$; since $\Z/q\Z$ is an integral domain, multiplication by $a$ is injective, and since $\Z/q\Z$ is finite, it is in fact a permutation of its elements. Then since the permutation fixes$~0$, one has $\prod_{b=1}^{q-1}b=\prod_{b=1}^{q-1}ab=a^{q-1}\prod_{b=1}^{q-1}b$ in $\Z/q\Z$. Now simplify by $\prod_{b=1}^{q-1}b$, which is nonzero (use the integral domain property both for "nonzero" and to allow simplification).

Answer 3

If $q$ is a prime number, then $(\mathbb{Z}_q,+,\cdot )$ is a field. The multiplicative (Abelian) group is $(\mathbb{Z}_q \setminus \{0\}, \cdot)$, so its order is $q-1$. By a corollary of Lagrange's Theorem in Group Theory, we have $$ a^{q-1} = 1 $$ for all $a \in \mathbb{Z}_q$. Multiplying with $a$ finishes the proof.