I am trying to prove that if $g.c.d.(a, m) = 1$ then $a^{\phi(m)} \equiv 1 (\textbf{mod }m). $

I have defined the following sets:

Let set $\textbf{A}$ be the set of prime integers $<$ m

Let set $\textbf{B}$ be the set of prime integers $<$ m multiplied by a

I am having trouble proving that set B is a permutation of set A. I have proven that every element in set B is going to be unique (mod m). But how do I guarantee that these integers are going to be equivalent to a number in set A?

My understanding is that if you were proving Fermat's theorem, you have m-1 unique numbers (mod m) and therefore, they have to be congruent to each other. But I do not understand how to prove it when there are only $\phi(m)$ numbers.


Hint: Instead of representing the map solely by its image, consider the function


in $\mathbb{Z}_m$, where $a\in A$, and $A$ is (as you defined it) the set of primitive residues $\bmod m$.

You want to show that $f$ is a bijection from $A$ to $A$. To do this, first show the following:

If $x\in A$, then $f(x)\in A$ (so $f$ is well-defined).

Now, show that it is injective, i.e.that

$f(x)=f(y) \implies x=y$ for $x,y\in A$.

Any injective (you might have heard this called "one-to-one") function from a finite set to itself is a bijection, so from there you will be done.


Say $$S=\{a_1, a_2,\cdots,a_n\}$$ are all the elements in the set $\Bbb{Z}/m\Bbb{Z}$ which are coprime to $m$ (so $n=\phi(m)$). For some specific $x$ coprime to $m$ we consider the set of residues $$\tag{1}a_1x,a_2x,\cdots, a_nx\pmod{m}.$$

By definition, no prime factor of any element $a_i\in S$ occurs in the prime factorisation of $m$, so a simple application of the Fundamental Theorem of Arithmetic shows $$hcf(a_ix,m)=1,$$ which is to say all the numbers in $(1)$ are elements of $S$.

Next, assume for integers $a_i, a_j\in S$ that $$\tag{2} a_ix\equiv a_jx\pmod{m}.$$

Since we assume $gcd(x,m)=1$ we can cancel it from the congruence $(2)$ to get $$\tag{3} a_i\equiv a_j\pmod{m}$$ and as both $a_i$ and $a_j$ are elements of $\Bbb{Z}/m\Bbb{Z}$ they can only be congruent to one another if $i=j$, which proves that the list $(1)$ is exactly the set $S$ in some order.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.