Rabin encryption when M is not Disjoint to n I need help with proving that the encryption going well when the message $M$ is not Disjoint to $n$ (public key).

Encryption message $\ C= M^2 \bmod n$

Decryption message $\ C^{(p+1)/4} \equiv ±M \bmod p$ and $\ C^{(q+1)/4} \equiv ±M \bmod q$.

Now, we can't use Fermat's little theorem.
Suppose that $M \neq 0 \pmod p$ and $M \equiv 0 \bmod q$ 

(because $n = pq$ and $p,q$ are primes)
The definition of the Rabin cryptosystem in the question likely is similar to:


Setup:


choose $p$ and $q$ large distinct primes with $p\equiv q\equiv 3\pmod 4$ ;
compute and publish public modulus $n=p\;q$, and publish it as the public key;
the private key is $p,q$ .

Encryption of message (representative) $M$ with $0\le M&lt;n$ :


compute ciphertext $C=M^2\bmod n$ [implying by definition $0\le C&lt;n$ ]

Decryption of ciphertext $C$ :


compute $M_p=C^{(p+1)/4}\bmod p$ and $M_q=C^{(q+1)/4}\bmod q$ ;
deduce that $M\equiv\pm M_p\pmod p$ and $M\equiv\pm M_q\pmod q$ [see proof at end];
noticing that $\gcd(p,q)=1$ by construction, use the Chinese Remainder Theorem to find the set $\mathcal M$ of possible $M$ as follows:


compute $q_\text{inv}=q^{-1}\bmod p$ [this value can be reused for multiple $C$ ];
compute these 4 values:
$$\begin{align}
M_0&amp;=(q((q_\text{inv}(M_p-M_q))\bmod p)+M_q)\bmod n\\
M_1&amp;=-M_0\bmod n\\
M_2&amp;=(q((q_\text{inv}(M_p+M_q))\bmod p)-M_q)\bmod n\\
M_3&amp;=-M_2\bmod n
\end{align}$$
the set $\mathcal M$ is $\{M_0,M_1,M_2,M_3\}$ ;

select $M$ as the message in $\mathcal M$ that pass some consistency check.



Further, it is commonly restricted to $p\ne q\pmod8$ at setup, yielding $n\equiv5\pmod8$; and $M\equiv4\pmod8$ [or some other value $\pmod8$ ], which then is enough to always allow recognition of which element of the set $\mathcal M$ is $M$.

Depending on $M$ or $C$, the set $\mathcal M$ will have one, two or four distinct elements. One element only occurs for $M=0$ ($M_p=M_q=0$); two elements occur when otherwise $\gcd(M,n)\ne1$ [equivalently, when a single of  $M_p=0$ (x)or $M_q=0$ holds; or in other words, when $M\ne0$ is not disjoint to $n$ ; ]; four elements occurs otherwise, that is for overwhelmingly most $M$.

The original reference on the Rabin encryption scheme is: Michael O. Rabin; Digitized Signatures and Public Key Functions as Intractable a Factorization, MIT-LCS-TR-212 (1979). It defines $C=M(M+b)\bmod n$ for some public $b$ with $0\le b&lt;n$, which makes the cryptosystem somewhat less malleable; also, it is not restricted to $p\equiv q\equiv 3\pmod 4$.



Proof that for all $M$, it holds $C^{(p+1)/4}\equiv\pm M\pmod p$ [same for $q$ rather than $p$ ]


By construction, $C=M^2\bmod n$, and $p$ divides $n$; therefore $C\equiv M^2\pmod p$
$p\equiv3\pmod4$ therefore $(p+1)/4$ is an integer, and we can raise the above to that power, giving
$$\begin{align}
C^{(p+1)/4}&amp;\equiv(M^2)^{(p+1)/4}&amp;&amp;\pmod p\\
C^{(p+1)/4}&amp;\equiv M^{(p+1)/2}&amp;&amp;\pmod p\\
C^{(p+1)/4}&amp;\equiv M\cdot M^{(p-1)/2}&amp;&amp;\pmod p&amp;&amp;(1)
\end{align}$$
If $M\equiv0\pmod p$ :


by Fermat's little theorem, and since $p$ is prime, $M^{p-1}\equiv1\pmod p$ holds;
define $X=M^{(p-1)/2}\bmod p$ [implying by definition $0\le X&lt;p$ ]; the above becomes $X^2\equiv1\pmod p$, that is $(X+1)(X-1)\equiv0\pmod p$, which  has exactly two solutions $X=1$ and $X=p-1$ ;
therefore $M\cdot M^{(p-1)/2}\equiv\pm M\pmod p$ ;

Otherwise [ that is, when $M\equiv0\pmod p$ ]


$M\cdot M^{(p-1)/2}\equiv\pm M\pmod p$ holds [both sides are $0\pmod p$ ];

Replacing in $(1)$, it comes $C^{(p+1)/4}\equiv\pm M\pmod p$ for both cases.