Proving Euler-Fermat's Theorem

Question

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.

Answer 1

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.

Answer 2

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.