Distinct cleartexts that are invariant under encryption I'm really new in this whole cryptography thing. And while I was going through some articles about RSA I stumble upon a really weird thing and it goes like this:  


  If $n = pq$ is a RSA modulus, and d is the encryption exponent. There are at least 9 distinct cleartexts m that are invariant under encryption, i.e. $m^d\ ≡\ m\ (mod\ n)$ ?   


Why is it at least 9, can it be more ? And is there any proof for this ?      

I seem really interesting and I would like to know the answer on this. If anyone can answer it would be so helpful.
Why is it at least 9?


Actually, we have to assume that $p$ and $q$ are distinct odd primes, and that $d$ is odd; this is presumably covered by the assertion that $n = pq$ is an RSA modulus.

With that assumption, we can proceed as follows: we have $m^d \equiv m \pmod n$ iff both these hold:

$$m^d \equiv m \pmod p$$

$$m^d \equiv m \pmod q$$

This is a consequence of the Chinese Remainder Theorem, which we'll be using a lot.

For the relation $m^d \equiv m \pmod p$, for odd prime $p$, we have at least 3 values of $m \bmod p$ that satistify it, namely $m \equiv 0, 1, p-1 \bmod p$ (and the later is often written as $-1$, as $p-1 \equiv -1 \pmod p$).

Similarly, we have at least 3 values of $m \bmod q$ that satify $m^d \equiv m \pmod q$, $0, 1, -1 \pmod q$.

Now, by the Chinese Remainder Theorem, and because $p, q$ are relatively prime, then for any pair of integers $a, b$, there exists an $m$ with $m \equiv a \pmod p$ and $m \equiv b \pmod q$.

As a consequence, for any one if the values $a \in \{0, 1, -1\}$, and any one of the values $b \in \{0, 1, -1\}$, there exists an $m$ with $m \equiv a \pmod p$ and $m \equiv b \pmod q$.  Such an $m$ satisfies both of our original relations modulo $p, q$, and hence satisifies $m^d \equiv m \pmod n$.

There are a total of 9 such sets of $a, b$ values, and hence 9 such values of $m$.


  can it be more ?


Actually, if we have $d = 3$ (or if $d$ is the decryption exponent corresponding to $e = 3$), then no, we can't; for the relation $m^3 = m \pmod p$, there can only be at most 3 solutions (as $p$ is prime); as we have listed 3 such solutions, that must be all of them (and similarly for $q$).

However, if we consider larger values of $d$, then yes, there can certainly be more.  As an example, if we have $pq = 65$ and $d = 5$, there happens to be 25 such 'value preserving cleartexts' (and it should be easy to reconstruct why this is).


  And is there any proof for this ?


The above explination can be expanded to a formal proof; if you want, you can find explicit representations of all 9.