Editing RSA cryptosystem (section)

===Proof using Fermat's little theorem===
The proof of the correctness of RSA is based on [[Fermat's little theorem]], stating that {{math| ''a''<sup>''p'' − 1</sup> ≡ 1 (mod ''p'')}} for any integer {{mvar|a}} and prime {{mvar|p}}, not dividing {{mvar|a}}.{{refn|group=note|We cannot trivially break RSA by applying the theorem (mod ''pq'') because {{math|''pq''}} is not prime.}}

We want to show that
<math display="block">(m^e)^d \equiv m \pmod{pq}</math>
for every integer {{mvar|m}} when {{mvar|p}} and {{mvar|q}} are distinct prime numbers and {{mvar|e}} and {{mvar|d}} are positive integers satisfying {{math|1=''ed'' ≡ 1 (mod ''&lambda;''(''pq''))}}.

Since {{math|1=''&lambda;''(''pq'') = [[least common multiple|lcm]](''p'' − 1, ''q'' − 1)}} is, by construction, divisible by both {{math|''p'' − 1}} and {{math|''q'' − 1}}, we can write
<math display="block">ed - 1 = h(p - 1) = k(q - 1)</math>
for some nonnegative integers {{mvar|h}} and {{mvar|k}}.{{refn|group=note|In particular, the statement above holds for any {{mvar|e}} and {{mvar|d}} that satisfy {{math|1=''ed'' ≡ 1 (mod (''p'' − 1)(''q'' − 1))}}, since {{math|1=(''p'' − 1)(''q'' − 1)}} is divisible by {{math|1=''&lambda;''(''pq'')}}, and thus trivially also by {{math|''p'' − 1}} and {{math|''q'' − 1}}. However, in modern implementations of RSA, it is common to use a reduced private exponent {{mvar|d}} that only satisfies the weaker, but sufficient condition {{math|1=''ed'' ≡ 1 (mod ''&lambda;''(''pq''))}}.}}

To check whether two numbers, such as {{mvar|m''<sup>ed</sup>''}} and {{mvar|m}}, are congruent {{math|mod&nbsp;''pq''}}, it suffices (and in fact is equivalent) to check that they are congruent {{math|mod&nbsp;''p''}} and {{math|mod&nbsp;''q''}} separately.{{refn|group=note|This is part of the [[Chinese remainder theorem]], although it is not the significant part of that theorem.}}

To show {{math|''m<sup>ed</sup>'' ≡ ''m'' (mod ''p'')}}, we consider two cases:
# If {{math|''m'' ≡ 0 (mod ''p'')}}, {{mvar|m}} is a multiple of {{mvar|p}}. Thus ''m<sup>ed</sup>'' is a multiple of {{mvar|p}}. So {{math|''m<sup>ed</sup>'' ≡ 0 ≡ ''m'' (mod ''p'')}}. 
# If {{math|''m'' <math>\not\equiv</math> 0 (mod ''p'')}}, 
#: <math>m^{ed} = m^{ed - 1} m = m^{h(p - 1)} m = (m^{p - 1})^h m \equiv 1^h m \equiv m \pmod{p},</math>
#: where we used [[Fermat's little theorem]] to replace {{math|''m''<sup>''p''−1</sup> mod ''p''}} with 1.

The verification that {{math|''m<sup>ed</sup>'' ≡ ''m'' (mod ''q'')}} proceeds in a completely analogous way:
# If {{math|''m'' ≡ 0 (mod ''q'')}}, ''m<sup>ed</sup>'' is a multiple of {{mvar|q}}. So {{math|''m<sup>ed</sup>'' ≡ 0 ≡ ''m'' (mod ''q'')}}. 
# If {{math|''m'' <math>\not\equiv</math> 0 (mod ''q'')}},
#: <math>m^{ed} = m^{ed - 1} m = m^{k(q - 1)} m = (m^{q - 1})^k m \equiv 1^k m \equiv m \pmod{q}.</math>

This completes the proof that, for any integer {{mvar|m}}, and integers {{mvar|e}}, {{mvar|d}} such that {{math|1=''ed'' ≡ 1 (mod ''&lambda;''(''pq''))}},
<math display="block">(m^e)^d \equiv m \pmod{pq}.</math>

====Notes====
{{reflist|group=note}}