# How do I prove this using Fermat's little theorem?

Let $p$ be a prime $>2$ and

let set $S=\{1,...,p-1\}$ modulo $p$

define $S^n=\{1^n,...,(p-1)^n \}$ modulo $p$

Prove that $S=S^n$ if $gcd(p-1,n)=1$.

EDIT: Fermat's little theorem says that if p is a prime number, then for any integer a, the number $a^p − a$ is an integer multiple of $p$. In the notation of modular arithmetic, this is expressed as

${\ a^{p}\equiv a{\pmod {p}}.}$

• Do you know about isomorphism and bijections? A little group theory might be of use here, although I don't know much so I can't say for sure... – Airdish Apr 5 '17 at 16:25
• An obvious observation is that $n$ must be odd, so $(p - 1)^n \equiv (-1)^n \equiv p - 1 \pmod p$. And if $n = p$, then it is obvious, but your question implies that $n$ can be any integer coprime to $p - 1$. – Airdish Apr 5 '17 at 16:27
• Hi @Airdish I do know what a bijection is but I can't seem to understand how could I use them to solve this problem. Though I understand that we need to prove that above operation is bijection from $S$ to $S^n$ . – aroma Apr 5 '17 at 16:31
• Do you know that every prime modulus has a primative root (also known as a generator)? I see this as following from that more than from Fermat's Theorem – Stella Biderman Apr 5 '17 at 16:36
• @StellaBiderman How would we prove this using primitive roots? – aroma Apr 5 '17 at 16:42

We have to show that for $i\ne j$ , $i,j=1,2,\cdots ,p-1$ we have $$i^n\ne j^n\mod p$$

So, suppose $i^n\equiv j^n\mod p$ implying $(ij^{-1})^n\equiv 1\mod p$. The order of $ij^{-1}$ modulo $p$ must be a divisor of $p-1$ and of $n$. But $p-1$ and $n$ are coprime,so the order must be $1$, implying $ij^{-1}=1$ and therefore $i=j$.

Since it is clear that $i^n\ne 0\mod p$ for $i=1,2,\cdots ,p-1$ and the powers are distinct modulo $p$, the set of the powers must coincide with $S$.

• @Peter did you assume that $i|j$ or $j|i$ , otherwise how else could you say a fraction raised to $n$ is congruent to $1$ $mod$ $p$. – aroma Apr 6 '17 at 7:26
• @ash In a field $\mathbb Z_p$, every element $j\ne 0$ has a multiplicative inverse $j^{-1}$ with the property $j\cdot j^{-1}=1$. Multiplying $i^n\equiv j^n$ with $(j^{-1})^n$ gives $(ij^{-1})^n=i^n\cdot (j^{-1})^n\equiv j^n(j^{-1})^n=(jj^{-1})^n=1$ – Peter Apr 6 '17 at 13:02

Here's a way to do it using primative roots, but not Fermat's Theorem.

In the comments you note that you recognize that the problem is solved if we know how to prove that the map $x\to x^n$ is a bijection. Suppose it's not. Since this is a finite set, a function is a surjection iff it's an injection iff its a bijection, so let's suppose the map isn't injective. That would mean that for some $n$ relatively prime to $p-1$, there would exist two numbers $a,b$ such that $a^n\cong b^n\pmod{p}$ and $a\not\cong b\pmod{p}$.

Let $g$ be a generator of $\mathbb{Z}/p\mathbb{Z}$. Then there exists $x,y$ such that $g^x=a,g^y=b, 0< x,y \leq p-1$ and by assumption $x\neq y$. Then $g^{xn}=a^n=b^n=g^{yn}\Rightarrow (g^n)^x=(g^n)^y$. However, since $n$ is relatively prime to $\varphi(p)=p-1$, $g^n$ is also a generator of $\mathbb{Z}/p\mathbb{Z}$ which is a contradiction. Thus the function is surjective, and so it is bijective, and so we are done.

Clearly $S^n\subseteq S$, so the only way one could have $S^n\not=S$ is if $a^n\equiv b^n$ mod $p$ but $a\not\equiv b$ mod $p$. Let's show this can't happen, using Fermat's little theorem in the form $a^{p-1}\equiv1$ mod $p$ if $p\not\mid a$.

Now $\gcd(n,p-1)=1$ implies $nx-(p-1)y=1$ for some pair of positive integers $x$ and $y$. We can write this as $1+(p-1)y=nx$. So if $a^n\equiv b^n$ mod $p$ with $p\not\mid a,b$, then, since $a^{p-1}\equiv b^{p-1}\equiv1$ mod $p$, we have

$$a\equiv a\cdot1\equiv a\cdot a^{(p-1)y}\equiv(a^n)^x\equiv(b^n)^x\equiv b\cdot b^{(p-1)y}\equiv b\cdot1\equiv b\mod p$$

Thus $S^n=S$.