# In RSA, what happens if the plaintext $m$ is not coprime to $n$? [duplicate]

Coming from the Wikipedia page on RSA, I think I understand the following:

RSA is based on generating an integer $$n$$ as the product of two large primes, $$p$$ and $$q$$, and encryption/decryption exponents $$e$$ and $$d$$ such that for any given plaintext $$m$$, $$(m^e)^d \equiv (m^d)^e \equiv m^{ed} \equiv m \mod n\,,$$ i.e. such that modular exponentiation with $$e$$ (encryption) composed in any order with exponentiation with $$d$$ (decryption) is the identity mapping on the plaintext.

This works because $$e$$ and $$d$$ are chosen such that $$ed \equiv 1 \mod{|m|}$$ for any plaintext $$m$$, where $$|m|$$ denotes the order of $$m$$ in $$\mathbb{Z}/n\mathbb{Z}$$. This is done by selecting a multiplicative inverse pair $$e$$, $$d$$ in the ring of integers mod $$\lambda(n)$$, where $$\lambda$$ is Carmichael's totient function; and if I understand correctly the latter is essentially the least common multiple of the orders of all positive integers less than $$n$$ that are coprime to $$n$$, so that if $$ed \equiv 1 \mod \lambda(n)$$ is true then $$ed \equiv 1 \mod |m|$$ is too for all $$m$$ coprime to $$n$$, since $$|m| \mid \lambda(n)$$.

But what happens if $$m$$ happens not to be coprime to $$n$$, i.e. if $$m$$ is either a multiple of $$p$$ or of $$q$$? What guarantees that in this case too the first identity shown above (the encryption-decryption identity) still holds?

I thought along the lines of using Fermat's Little Theorem, i.e. if I could prove that $$ed$$ was congruent to $$p$$ mod $$\lambda(n)$$, then $$m^{ed} \equiv m \mod p$$. But after some thought, this doesn't seem to lead anywhere.

• Two dupliactes: 1. Can RSA be used to encrypt p? 2. Does RSA work for any message M? Jan 23 '21 at 18:38
• Does something remain unclear after reading this, including the second note?
– fgrieu
Jan 23 '21 at 18:38
• Ah, thanks @fgrieu, I just found that one myself too. This can be closed as duplicate of that. There's just one thing, I don't yet understand how they conclude that. Jan 23 '21 at 18:44
• Leave a note (e.g. here or in the other answer) if you don't understand something. Basically, as long as $p\ne q$, nothing special happens from the standpoint of encryption or decryption yielding consistent results if the plaintext $m$ is not coprime to $n$. The proof just needs to consider this special case. Also, it becomes trivial to factor $n$ and decipher for one who realize the plaintext or ciphertext is not coprime to $n$, except if that plaintext or ciphertext is $0$,$1$ or $n-1$.
– fgrieu
Jan 23 '21 at 19:00