Proving that RSA encryption function with non-square free modulus is not a permutation Here is a backgroung for the question on hand. While studying RSA I came up to the question about what happens if $p$ and $q$ involved in modulus computation are not actually primes? There is already a related topic on this (Why does RSA need p and q to be prime numbers?). While most of the answers boil down to efficency and security considerations, there is a single answer which states that RSA encryption function with modulus consisting of prime powers loses it's bijection properties, i.e, it is not a permutation any more. However this behaviour is shown only on example with no proof.
Given that, I've started to search a proof of RSA permutation property, and I found such a proof here. But again, it states that the proof works only if $p \ne q$, while it is not actually clear why it is not for $p = q$.
Then I have started to digging it up by myself. Actually, it seems pretty clear for $p = q$ case if $p$ is prime. Then for $N = p^2$, we got a set of plaintexts $\{m_i\}$ such that $0 \leq m_i &lt; N$ and $m_i \equiv 0\pmod{p}$, and having the exponent $e &gt; 2$ we also got $m_i^e \equiv 0\pmod{p^2}$.
But I'm not sure how to generalize cases for $N = p^s, s &gt; 2$; $N=p^sq, s &gt; 1$; $N=p^sq^r, s &gt; 2, r &gt; 2$. Let's take a second case for example. Let $N=5^23= 75$, then $\phi(N) = (5^2 - 5)(3 - 1) = 40$, and $e=3$ is acceptable exponent. Next if I compute all $c_i=m_i^3\pmod{75}$ for all $0 &lt; m_i &lt; 75$, I see that there are 3 sets of discinct $m_i$ values that give the same $c_i$ after encryption:

$c_i = 0, m_i=\{0, 15, 30, 45, 60\}$
$c_i = 50, m_i=\{5, 20, 35, 50, 65\}$
$c_i = 25, m_i=\{10, 25, 40, 55, 70\}$

Thinking of this $c_i$ values I found the following pattern $5^3 \equiv 50\pmod{75}$, $5^32\equiv 25\pmod{75}$, $5^33 \equiv 0\pmod{75}$, $5^34 \equiv 50\pmod{75}$ and so on. Given that it's clear that:

for $m_i = 5(3k_j + 0)\pmod{75}, k_j \geq 0$ we got $c_i = 0$
for $m_i = 5(3k_j + 1)\pmod{75}, k_j \geq 0$ we got $c_i = 50$
for $m_i = 5(3k_j + 2)\pmod{75}, k_j \geq 0$ we got $c_i = 25$

And that's where I stuck. I have tried to explore the examples for $N = p^s$ and $N=p^sq^r$ and have found similar patterns like shown above. But I still need some clues in order to generalize this behaviour and prove that RSA encryption with non-square free modulus is not a permutation. I believe that there should be some simple concept I missing, but since I'm not much into Number Theory, I need community help.
Just for clarification. I'm completely OK with efficency and security considerations of $p$ and $q$ being two discinct prime. The only thing I'm worrying about is RSA encryption function bijection property (or it's absense, which is the case).
Thanks in advance.
UPD
@poncho gave a clear explanation on existence of multiple preimages for $c = 0$. But it also be great to generalize existence of other ciphertexts that can have multiple preimages.
While most of the answers boil down to efficency and security considerations, there is a single answer which states that RSA encryption function with modulus consisting of prime powers loses it's bijection properties, i.e, it is not a permutation any more. However this behaviour is shown only on example with no proof.

It's rather straightforward to demonstrate (assuming $e&gt;1$; with $e=1$, it is a permutation, but not a very interesting one).
A value $N$ is nonsquarefree if there is a value $p&gt;1, q$ such that $N = p^2q$ (note that $q$ may have $p$ as a factor).  If so, then consider the encryption of the two values $0$ and $pq$.  In the two cases, we have:
$$0^e \equiv 0 \pmod N$$
$$(pq)^e \equiv p^eq^e \equiv p^{2+x}q^{1+y} \pmod N$$
for $x = e-2$ and $y = e-1$.  Now, both $x, y \ge 0$, and so $p^{2+x}q^{1+y}$ is a multiple of $p^2q$, and so this latter is equivalent to $0 \bmod N$
Since these two distinct plaintexts map to the same ciphertext 0, the mapping cannot be bijective.