Editing RSA cryptosystem (section)

===Proof using Euler's theorem===
Although the original paper of Rivest, Shamir, and Adleman used Fermat's little theorem to explain why RSA works, it is common to find proofs that rely instead on [[Euler's theorem]].

We want to show that {{math|''m<sup>ed</sup>'' ≡ ''m'' (mod ''n'')}}, where {{math|1=''n'' = ''pq''}} is a product of two different prime numbers, and {{mvar|e}} and {{mvar|d}} are positive integers satisfying {{math|''ed'' ≡ 1 (mod ''&phi;''(''n''))}}. Since {{mvar|e}} and {{mvar|d}} are positive, we can write {{math|1=''ed'' = 1 + ''h&phi;''(''n'')}} for some non-negative integer {{mvar|h}}. ''Assuming'' that {{mvar|m}} is relatively prime to {{mvar|n}}, we have
<math display="block">m^{ed} = m^{1 + h\varphi(n)} = m (m^{\varphi(n)})^h \equiv m (1)^h \equiv m \pmod{n},</math>

where the second-last congruence follows from [[Euler's theorem]].

More generally, for any {{mvar|e}} and {{mvar|d}} satisfying {{math|''ed'' ≡ 1 (mod ''&lambda;''(''n''))}}, the same conclusion follows from [[Carmichael function#Carmichael's theorem|Carmichael's generalization of Euler's theorem]], which states that {{math|''m''<sup>''&lambda;''(n)</sup> ≡ 1 (mod ''n'')}} for all {{mvar|m}} relatively prime to {{mvar|n}}.

When {{mvar|m}} is not relatively prime to {{mvar|n}}, the argument just given is invalid. This is highly improbable (only a proportion of {{math|1/''p'' + 1/''q'' − 1/(''pq'')}} numbers have this property), but even in this case, the desired congruence is still true. Either {{math|''m'' ≡ 0 (mod ''p'')}} or {{math|''m'' ≡ 0 (mod ''q'')}}, and these cases can be treated using the previous proof.