# RSA: Fermat-Euler Theorem - coprimality of message and modulus [duplicate]

This question already has an answer here:

I understand the implication of the Fermat-Euler theorem and how it applies to RSA and the detailed explanation by user Ninefingers at What is the relation between RSA & Fermat's little theorem? is very useful.

However, the Fermat-Euler Theorem states that $a$ and $n$ should be relatively prime to satisfy the following equation. $$a^{\phi\left(n\right)}\equiv1\mod n$$ But I do not recall RSA stating any exceptions of $a$ which cannot be properly encrypted

Edit: Note that I have seen Does RSA work for any message M? which is very similar BUT the question is different and thus the given answer satisfies it however the answer does not show or prove why the fermat's theorem could still be used.

Edit 2: The reason it is a different question is because I am looking for the number theory function which enables the cryptographic system to work the way it does.

## marked as duplicate by Gilles, poncho, otus, DrLecter, e-sushiNov 10 '14 at 18:59

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

## 1 Answer

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.

• Thank you for your quick solution, but it took me quite sometime and help to kick the idea into my head. Thank you :) – Lordbalmon Nov 16 '14 at 20:27