RSA: How to compute the number of possible plaintexts if $e$ is not coprime to $\varphi(n)$? I'm studying for an exam next week, and there are two questions that me and my friend don't understand:

Question 1:
Let $p,q$ be big prime numbers and $n=pq$.
Let $e$ be a number between $1$ and $\varphi(n)$ such that $e\mid(p-1)$, $e\mid(q-1)$.
For a plaintext $M$, the ciphertext is $C=M^e \bmod n$.

How many different $M$s will be ciphered to the same $C$?
Edit: what is the maximum number of messages $M$ that will yield to the same $C$?
Why is the answer $e^2$?

Question 2:
Let $p,q$ be big prime numbers and $n=pq$.
Let $e$ be a number between $1$ and $\varphi(n)$ such that $\gcd(e,p-1)=a &gt; 1$ and $\gcd(e,q-1)=1$.
For a plaintext $M$, the ciphertext is $C=M^e \bmod n$.

How may different $M$s will be ciphered to the same $C$?
Why is the answer $a$?
Both questions can be answered using the same kind of argument.

First, observe that in both cases we are really only interested in the number of $e$th roots of unity in $\mathbb Z/n$: Any $e$th root of unity can be multiplied to some $M$ without changing the value of $M^e\bmod n$, and two different $M$ with equal $M^e\bmod n$ differ by an $e$th root of unity. Thus we restrict our attention to the case $M=1$.

For succinctness, I will sometimes write only root for "$e$th root of unity".

The Chinese remainder theorem gives an isomorphism of rings
$$
  \pi\colon\; \mathbb Z/n \cong \mathbb Z/p \times \mathbb Z/q
  \text.
$$

The image of $x^e\bmod n$ under $\varphi$ is $(x^e\bmod p,x^e\bmod q)$.
Some element $x\in\mathbb Z/n$ is a root if and only if both components of $\varphi(x)$ are roots in $\mathbb Z/p$ and $\mathbb Z/q$.
In other words: Each root in $\mathbb Z/n$ "consists" of roots in $\mathbb Z/p$ and $\mathbb Z/q$, and vice-versa.
Thus, if $\mathbb Z/p$ has $a$ roots and $\mathbb Z/q$ has $b$, the ring $\mathbb Z/n$ has $ab$ roots.

Now note that the order of the cyclic group $(\mathbb Z/p)^\ast$ is $p-1$, thus if $e$ divides $p-1$, there must be an element $r$ of multiplicative order $e$ in $\mathbb Z/p$. Its powers $r^1,r^2,\dots,r^{e-1}$ are nontrivial $e$th roots of unity in $\mathbb Z/p$, thus (including $1$) there are $e$ roots in $\mathbb Z/p$.
There cannot be more than $e$ roots since $\mathbb Z/p$ is a field.
Of course, the same holds for $q$.

Armed with that knowledge, let's tackle question 1: If $e$ divides both $p-1$ and $q-1$, there must exist $e$ different roots in both $\mathbb Z/p$ and $\mathbb Z/q$. Thus, by the above, there are $e^2$ different $e$th roots of unity in $\mathbb Z/n$.

As to question 2: Since $(\mathbb Z/q)^\ast$ has order $q-1$ and $\gcd(e,q-1)=1$, the map $x\mapsto x^e\bmod q$ is a permutation on $\mathbb Z/q$. In particular, there are no nontrivial $e$th roots of unity in $\mathbb Z/q$.
Concerning $\mathbb Z/p$, note that the map $x\mapsto x^{e/a}\bmod p$ is a permutation since $e/a$ is coprime to $p-1$. Thus, $1=x^e=(x^a)^{e/a}$ in $\mathbb Z/p$ if and only if $x^a=1$. As $a\mid p-1$, we can apply the above results (with $a$ in place of $e$) to conclude that $\mathbb Z/p$ has $a$ roots, thus $\mathbb Z/n$ has $a\cdot 1=a$.