I am trying to prove that RSA is a permutation. All I can find is places where it is stated that it is a permutation because the function is bijective. I know that it is, but would like to see a detailed proof.
For clarity, we have $N = p \cdot q$, where $p$ and $q$ are prime and $e$ such that $1 = \gcd(e, (p-1)\cdot(q-1))$. We want to show that $f(x) = x^e \pmod N$ is a permutation. I am thinking we must use Fermat's little theorem somewhere but I cannot complete a detailed proof myself.
First let's clarify notations. $f(x)=x^e \pmod N$ is non-standard, hesitating between
What's meant in RSA encryption is the later.
A permutation of a set is a bijection from that set to that same set. Any injective function from a finite set to a set with the same cardinality (number of elements) is a bijection. Thus we only need to prove that for any integers $x$ and $y$ in $[0,N)$ , if $f(x)=f(y)$ , then $x=y$. We do that in the following.
We assume $f(x)=f(y)$. By definition of $f$ that means $(x^e\bmod N)=(y^e\bmod N)$. That implies $N$ divides $x^e-y^e$. That implies any prime factor $p$ of $N$ divides $x^e-y^e$, that is $x^e\equiv y^e\pmod p$.
It is hypothesized $1=\gcd(e,(p-1)\cdot(q-1))$. Therefore $e$ and $p-1$ are coprime, the multiplicative inverse of $e$ in $\mathbb Z_{p-1}$ is well defined, and there exists a positive integer $d_p$ and a non-negative integer $k$ such that $e\cdot d_p=1+k\cdot(p-1)$.
Raising $x^e\equiv y^e\pmod p$ to that power $d_p$, we get that $(x^e)^{d_p}\equiv (y^e)^{d_p}\pmod p$; thus $x^{e\cdot d_p}\equiv y^{e\cdot d_p}\pmod p$; thus $x^{1+k\cdot(p-1)}\equiv y^{1+k\cdot(p-1)}\pmod p$.
For any prime $p$ and any integer $x$, Fermat's little theorem states that $x^p\equiv x\pmod p$. That allows to prove by induction on $k$ that for any non-negative integer $k$, $x^{1+k\cdot(p-1)}\equiv x\pmod p$.
Thus $x^{1+k\cdot(p-1)}\equiv y^{1+k\cdot(p-1)}\pmod p$ becomes $x\equiv y\pmod p$, that is $p$ divides $x-y$. Similarly, $q$ divides $x-y$.
Here we hypothesize that $p\ne q$ (which is unstated in the question). If distinct primes divide an integer, their product does. It follows that $p\cdot q$ divides $x-y$, that is $x\equiv y\pmod N$, that is $x=y$ given that both belong to the set $[0,N)$; that completes our proof.
Note: the hypothesis $p\ne q$ is necessary. Illustration: $p=q=e=3$, $f(3)=f(6)$.
