RSA: Fermat-Euler Theorem - coprimality of message and modulus
It's a consequence of the Chinese Remainder Theorem (look it up, if you don't know it) if you want to be more precise and understand it algebraically. If $n=pq$ and $de \equiv 1\;(\textrm{mod }\phi(n))$, then we also have that

$$de \equiv 1\;(\textrm{mod }p-1),\;\;de \equiv 1\;(\textrm{mod }q-1),$$

since $\phi(n)=(p-1)(q-1)$. It follows that for any integer $a$,

$$a^{ed} \equiv a\;(\textrm{mod }p),\;\;a^{ed} \equiv a\;(\textrm{mod }q),$$

which follows from Fermat's Little Theorem. Note that this also holds if $a\equiv 0$ modulo $p$ or $q$, since both sides of the equation becomes zero. Now the Chinese Remainder Theorem in the case when $p\mid a$, will translate the equation

$$a^{ed} \equiv a\;(\textrm{mod }n)$$

into the two equations

$$0^{ed} \equiv 0\;(\textrm{mod }p),\;\;\; a^{ed} \equiv a\;(\textrm{mod }q)$$

Since we know that these equations are true by Fermat's Little Theorem as well as the trivial case when the element is zero, the Chinese Remainder Theorem will say that since the equation holds in these two cases, it also holds in the original (since more technically it's an isomorphism between the original ring and the product ring). Therefore, RSA's encryption/decryption algorithm also works in these degenerate cases.

In other words, it's not purely a consequence of Fermat's Little Theorem, but you can use it in the subcases that the CRT translation will give you.