What is the proof that the RSA is collision-free?

The part of the reasoning that goes from the correct $a\equiv b\pmod n\implies a^k\equiv b^k\pmod n$ to the conclusion $m_1\not\equiv m_2\pmod n\implies{m_1}^e\not\equiv {m_2}^e\pmod n$ is of the form: $P\implies Q$ therefore $\bar P\implies\bar Q$. That line of reasoning is wrong. Counterexample to the conclusion thus obtained: $n=25$, $k=e=3$, $a=m_1=10$, $b=m_2=20$. Slightly different one: $n=35$, $k=e=3$, $a=m_1=2$, $b=m_2=22$. Yet with proper hypothesis, textbook RSA is collision-free. We have a [closely related question](https://crypto.stackexchange.com/q/1004/555).

In that kind of proof about RSA, notation is important. In cryptography, we tend to write $c\equiv m^e\pmod n$ (`$c\equiv m^e\pmod n$`) when we mean that $m^e-c$ is a multiple of $n$. The opening parenthesis right before$\bmod$denotes that$\bmod$is _not_ an operator. We tend to write $c=m^e\bmod n$ (`$c=m^e\bmod n$`) when we mean that $c\in[0,n)$ and $c\equiv m^e\pmod n$. In this$\bmod$is an operator, similar to `%` in C except for precedence and what happens for negative arguments. Anything in-between, like $c=m^e\pmod n$, is ambiguous. Avoid $mod n$ at all cost.

Sorry, i'm not that familiar with Latex, and thank you for pointing me to the right direction.

Hints: you'll need a definition of RSA such that $n$ is the product of _distinct_ primes, and such that if prime $p$ divides $n$ then $\gcd(e,p-1)=1$. My counterexamples can be because they violate these rules.

So if we prove the correctness of RSA (All encrypted M can be decrypted to M), then we prove the collision-freeness as well, because two encrypted message can not yield the same decrypted message, am I right?

Yes, that argument is correct. It's not the only possible line of proof. Another, more direct, shows that with proper hypothess on $n$ and $e$, it holds ${m_1}^e\equiv {m_2}^e\pmod n\implies m_1\equiv m_2\pmod n$, using the Chinese Remainder Theorem, Fermat's little theorem, and that $\gcd(e,p-1)=1$ imples $e$ has an inverse modulo $p-1$.

I sit in a Tesla and translated this thread with Ai: