I have seen that there is a similar question here but none that really answers the question. I understand that if I choose the encryption exponent $e$ not coprime with $\varphi(n)$ then there is not a unique way to decrypt a message.
What I am wondering is what is the mathematical reason behind this? It seems to me that since $m^{(k \varphi(n)+1)} = m \bmod N$ and $d$ is defined as $(k\varphi(n)+1)/e$ then $d\cdot e$ is always going to be $k\varphi(n) +1$. What am I missing?
Textbook RSA encryption goes $c\gets m^e\bmod n$ with $n=p\,q$, and $p$ and $q$ primes (all quantities non-negative integers throughout). The question states
$d$ is defined as $(k\,\varphi(n)+1)/e$
Yes¹, for some integer $k$ such that this division yields an integer. And that can only be the case if $\gcd(e,\varphi(n))=1$. Proof: Let $r=\gcd(e,\varphi(n))$. This $r$ divides $e$ and $\varphi(n)$. Let $f=e/r$, and $z=\varphi(n)/e$, both integers. We have $d=(k\,\varphi(n)+1)/e$, thus $e\,d=k\,\varphi(n)+1$, thus $r\,f\,d-k\,r\,z=1$, thus $r\,(f\,d-r\,z)=1$. When the product of two integers is $1$, both are $\pm1$; thus $r=1$. Thus by construction of $r$, we must have $\gcd(e,\varphi(n))=1$.
The definition of $d$ in the question implies $\gcd(e,\varphi(n))=1$. But the question also asks:
If I choose the encryption exponent $e$ not coprime with $\varphi(n)$ then there is not a unique way to decrypt a message. What (..) is the mathematical reason behind this?
That's asking for a seldom given proof of: if a decryption of textbook RSA encryption can be consistently made, then $\gcd(e,\varphi(n))=1$ must hold. Here we go.
We want RSA decryption to be uniquely possible, the encryption transformation $m\mapsto m^e\bmod n$ must thus be injective over $[0,n)$, which we assume in the following. This implies three facts:
If $e=1$, then $\gcd(e,\varphi(n))=1$ holds. Given fact (1.), we can restrict the proof of (3.) to $e\ge2$, and we do so in the following.
Given fact (2.), $\varphi(n)=(p-1)(q-1)$. Thus $$\begin{align} \gcd(e,\varphi(n))=1&\iff\gcd(e,(p-1)(q-1))=1\\ &\iff\gcd(e,p-1)=1\text{ and }\gcd(e,q-1)=1 \end{align}$$ Thus for the proof of (3.) it is enough that we prove $\gcd(e,p-1)=1$ (the same proof applies for $q$, giving the desired result). We do so in the following.
Given that $p$ is prime, the multiplicative group $\Bbb Z_p^*$ (that is the integers $[1,p)$ under multiplication modulo $p$) has $p-1$ elements. It is known to be a cyclic group, thus there exists a generator $g$ with $x\mapsto g^x\bmod p$ a bijection on $[1,p)$, with $p-1\mapsto 1$.
Let $r=\gcd(e,p-1)$. This $r$ divides $e$ and $p-1$. Let $f=e/r$, $s=(p-1)/r$, and $h=g^s\bmod n$. It holds $h^e={(g^s)}^e=g^{s\,e}=g^{f\,r\,s}=g^{(p-1)\,f}={(g^{p-1})}^f$. Hence $h^e\bmod p=1$.
Given fact (2.) and $p$ and $q$ prime, $p$ and $q$ are coprime. Thus by the Chineese Remainder Theorem there exists² $t\in[0,p\,q)$ with $t\bmod p=h$ and $t\bmod q=1$.
It follows that $t^e\bmod p=h^e\bmod p=1$, and $t^e\bmod q=1^e\bmod q=1$. Again by the CRT, it follows that $t^e\bmod n=1$.
It also holds $1^e\bmod n=1$. For RSA encryption $m\mapsto m^e\bmod n$ to be injective, we must thus have $t=1$, therefore $h=1$. Since $x\mapsto g^x\bmod p$ is a bijection on $[1,p)$, and transforms $x=p-1$ into $1$, and $s$ into $h=1$, it must hold $s=p-1$.
By construction $s=(p-1)/r$ and $r=\gcd(e,p-1)$, thus $\gcd(e,p-1)=1$, Q.E.D.
Note: for proper generation of $N$ the condition $p=q$ is extremely improbable, and even if it occurs it leads to vanishingly few $m$ which encryption could not be uniquely deciphered, which is why $p\ne q$ is sometime omitted in the definition of textbook RSA. However when $\gcd(e,\varphi(n))\ne1$, the proportion of $m$ which encryption could not be uniquely deciphered becomes sizable, which is why condition (3.) on $e$ or an equivalent is always required. An argument for this sizable proportion is that there are many generators $g$ leading to distinct $h$, and for each $h$ that we exhibited there are $q$ messages $t$ encrypting to the same $c$.
¹ A standard proof is that if $e\,d\equiv 1\pmod{\varphi(n)}$, then decryption per $m\gets c^d\bmod n$ works for most messages in $[0,m)$, and for all such messages when $n$ is squarefree. The converse does not hold.
² That $t$ is unique and could be computed as $\left((p^{-1}\bmod q)(h-1)\bmod q\right)\,p+1$.
