# Fermat's little theorem in RSA with CRT [duplicate]

I have a question about the calculation of RSA decryption with the help of the CRT (Chinese Remainder Theorem).

If $$c$$ is the crytogram, $$m$$ the message, $$d$$ the private key and $$p, q$$ the primes. Then in RSA with CRT they use:

$$m_1 = c^d \bmod p = c^{(d \bmod (p-1))} \bmod p$$ with the help of Fermat's little theorem (FLT).

But for FLT you need that $$\text{gcd}(c,p)=1$$ That is given if $$c$$ is less than $$p$$ because $$p$$ is a prime. But what is, if $$c$$ is bigger (because $$c = m^e \bmod p*q$$)? Then we can have $$\text{gcd}(c,p)=p$$

Does FLT also apply in this case? Or did I do something wrong?

• Welcome to Cryptography. Check the answer by Thomas. Jul 9 '19 at 11:12