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.


1 Answer 1


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.

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.