Understanding an excerpt of notes on RSA using the Chinese Remainder theorem

Question

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$

1. Compute $d_p \equiv d \mod (p-1)$, $d_q \equiv d \mod (q-1)$
2. Compute $C_p \equiv C (\mod p)$, $C_q \equiv C (\mod q)$,
3. Compute $M_p \equiv C_p^{d_p} (\mod p)$, $M_q \equiv C_q^{d_q} (\mod q)$
4. 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?

Answer 1

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)$