14,443
edits
(→Proof using Fermat's little theorem: add note about modern RSA implementations often not requiring ed ≡ 1 (mod (p − 1)(q − 1)) but only ed ≡ 1 (mod λ(pq))) 
m (→Proof using Fermat's little theorem: tweak phrasing, since the last equation above is not actually a congruence) 

for some nonnegative integers ''h'' and ''k''.
(Note: In particular, the statement above holds for any ''e'' and ''d'' that satisfy {{nowrap1=''ed'' ≡ 1 (mod (''p'' − 1)(''q'' − 1))}}
To check whether two numbers, like ''m<sup>ed</sup>'' and ''m'', are congruent mod ''pq'' it suffices (and in fact is equivalent) to check they are congruent mod ''p'' and mod ''q'' separately. (This is part of the [[Chinese remainder theorem]], although it is not the significant part of that theorem.) To show {{nowrap''m<sup>ed</sup>'' ≡ ''m'' (mod ''p'')}}, we consider two cases: {{nowrap''m'' ≡ 0 (mod ''p'')}} and {{nowrap''m'' <math>\not\equiv</math> 0 (mod ''p'')}}.
