Proving Euler-Fermat's Theorem

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

$$f(x)=ax$$

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.