I have a description in my cryptography notes of a way to make RSA more efficient using the Chinese Remainder Theorem. Let $p,q$ be large primes, $N=pq$ , $e$ be the public encryption exponent, $d$ the private encryption exponent. I will only ask about the excerpt I don't understand for brevity. Let $C$ be the ciphertext and $M \equiv C^d \mod N$
- Compute $d_p \equiv d \mod (p-1)$, $d_q \equiv d \mod (q-1)$
- Compute $C_p \equiv C (\mod p)$, $C_q \equiv C (\mod q)$,
- Compute $M_p \equiv C_p^{d_p} (\mod p)$, $M_q \equiv C_q^{d_q} (\mod q)$
- Compute the unique $M_1$ such that $M \equiv M_p (\mod p)$ and $M \equiv M_q (\mod q)$ using the Chinese remainder theorem
Then the author states without proof that:
** $M \equiv C^d \equiv C_p^{d_p} \equiv M_1 (\mod p)$
referring to "an earlier result about groups" as the reason for this claim and that $p-1$ divides $d-d_p$.
Why is (**) this true?
Here is what I have deduced (I admit this could be wrong). Since $p-1$ divides $d-d_p$, then for some $k$ we have $k(p-1)=d-d_p$, so that $d_p=d-k(p-1)$ but then by Fermat's little theorem:
$C^{d_p}\equiv C^{d-k(p-1)}\equiv C^dC^{-k(p-1)} \equiv C^d(1)^{-k} = C^d (\mod p)$