Taking an example of RSA with numbers small enough to reason with:
Is that right so far? As it happens, for any i from zero to 142, taking i to the power of 721 mod 143 gives you i back. That's a good thing, because decryption wouldn't work otherwise. For a number that's relatively prime to the modulus, that's explainable by Euler's theorem  x to the power of phi is 1, and taking those powers out of the equation leaves you with x by itself. For a number like 26 that has a common factor with the modulus, the encryption/decryption happens to work in this example  26 to the power of 721 is 26 mod 143. But it's not explainable by the Euler technique, since 26 to the power of phi isn't 1, it's 78. So why does this work? Should it work? Does RSA require it to work? EDIT: To summarize the proof cited in Job's answer:
Back to the example: $$ m^{ed} = m.m^{ed1} = m.m^{720} = m.m^{6.10.12} = m.(m^{10})^{72} = m.(m^{12})^{60} $$ So if m is relatively prime to 11, then Fermat shows that taking m to the power of ed mod 11 is like multiplying by 1. If m isn't relatively prime to 11, then you're multiplying zeros mod 11 and end up with zero. Similarly for mod 13. And then FACT X combines the two and shows that taking m to the power of ed leaves the message unchanged mod 11 x 13. ddd 
It still works even if the message is not relatively prime to the modulus. Wikipedia offers two proofs  http://en.wikipedia.org/wiki/RSA_(algorithm)#Proofs_of_correctness Job Evers ♦♦ 
A followup question for anyone who's been patient enough to read my wall of text above... If I'm understanding this correctly:
e x d doesn't need to be == 1 mod phi. It suffices that it be == 1 mod (p11) and mod (p21). In the example above, I can take encryption exponent 7 and decryption exponent 43. 7 x 43 = 301. 301 == 1 mod 10 and mod 12, but it's not == 1 mod phi. For all i from 0 to 142, you can encrypt by taking the 7th power and decrypt by taking the 43rd power. That seems to me to be a correct cipher. So the question is:
ddd @D__ Ask yourself the following question from grouptheory: Given a finite abelian group $%G$%. For each element $%g\in G$%, the equation $g^r=e$ holds ($%e:=$% neutral element in $%G$%). What properties must $%r$% have ? EXAMPLE: [1] $%G:=(Z/2Z \times Z/2Z \times Z/2Z,\ +) $% has 8 elemens. For each $%x\in G$% it holds $%x^2=e$%, hence here is $%r=2$%. [2] $%G:=(Z/aZ \times Z/bZ,\ +) $% has $%a\cdot b$% elemens. For each $%x\in G$% it holds $%x^{a\cdot b}=e$%, hence $%r\leq ab$% (more precisely $%k\cdot r=a\cdot b$%). BUT if $%a=b$% then $%r=a$% and IF $%a,b\ both\ prime,\ different$% then $%r=a\cdot b$%. As you can see, the answer depends on the structure of $%G$%. I assume $%r=lcm(a,b)$% in general. If you REALLY want to know, you have to study group theory. In our RSAsituation: Only a person who knows $%p,q$% and hence knows $%\varphi(pq)$% can tell you what $%r$%value is enough. The answer depends on the structure of the multiplicative group $%((Z/\varphi(n))^{\times},\ast)$% . If you know $%r$%, you are able to answer the question for $%e,\ d$%. This sounds all a bit complex, but it is not since all possible structures of $%((Z/\varphi(n))^{\times},\ast)$% are well known. Each structure defines an $%r$%. Finally you only have to test these finitely many scenarios, hence possibilities for $%r$%. After you know $%r$%, you have to find $%\ e,\ d\ $% with $%\quad ed1\equiv 1\ mod\ r$%.
(10 May '12, 08:24)
1
I think you can figure out the answer to your question by looking here: http://en.wikipedia.org/wiki/Carmichael_function
(10 May '12, 09:30)
I think you are right. Thanks for the hint. I didn't know about its definition. As a consequence, we also could solve $%\quad e\cdot d\equiv 1\ (mod\ \lambda(n))$%. And now I see that $%\lambda(n)=\varphi(n)$% if $%n\neq Power\ of\ 2$%, so no big progress.
(10 May '12, 09:35)
@Wolfgang : the "power of 2" part is not correct. For instance, let p=11 and q=13. n=pq=143 is not a power of 2, but the totient (120) is not equal to the reduced totient (60).
(10 May '12, 10:31)
i refer to your website, not to $%n=pq$%. But you are even right in this case. Thanks for clarification. The website lists all cases where both values are the same. It seems that the difference of their values is not "too big".
(10 May '12, 11:58)
From an implementation point of view, calculating the reduced totient/Carmichael function requires finding the least common multiple of p and q, which I assume involves factoring p1 and q1. So that's probably why it's not done in practice. But from a point of view of proving the correctness of the cipher, it seems to me (correct me if I'm wrong) that the Carmichael function is a more precise definition of what's required of e and d. Or maybe it's just a matter of least common multiples. For example, take primes 11 and 13 again, so modulus = 143... Taking powers of numbers mod 143 gives you subgroups of certain sizes. For example, the powers of 42 are a subgroup of size 15: {42, 48, 14, 16, 100, 53,..., 126, 1}. Not all of the subgroups include 1, for example the powers of 26 are {26, 104, 130, 91, 78}. The biggest subgroups of this kind have size 60, as predicted by the Carmichael function, and all of the subgroup sizes are divisible by 60. If you look at those sequences mod 11 and mod 13, more structure can be seen. The powers of 42 mod 11 run through the cycle {9,4,3,5,1}, and mod 13, they run through the cycle {3,9,1}, so the period of 15 is the combination of periods of 5 and 3. So for encryption/decryption to work for 42 (for example) mod_pow(42, ed, 143) needs to be equal to 42. This would work if ed was 16, 31, or in general ed = 15x + 1. For 26, ed needs to be 5y + 1. Applying this to all numbers, ed  1 needs to be a multiple of all of the subgroup sizes. The least common multiple of the subgroup sizes, which happens to be the Carmichael function, is the smallest possible ed  1.
(10 May '12, 16:17)
@D__ [Literature] $%\quad$% Each $%(e,d)$% with $%\quad e\cdot d\equiv 1\ (mod\ Lcm(p1,\ q1))\quad$% would be fine to be used in RSA. (1) Charmichael function = more precise definition ? > If you want to use the smallest possible modulus, then Charmichael Numbers are the choice (2) Since the value of $%\ \lambda(n)\varphi(n)=$%small $%\ $% I think it's not really worth to evaluate $%\lambda(n)$%
(11 May '12, 00:08)
@D__ Could you post your followup question to the thread Unit 4 Questions that will be used for office hours? I think Prof. Evans should enlighten all of us on this point.
(13 May '12, 08:33)

Job targets the keypoint. It's surprising that $%\quad m^{e\cdot d}\equiv m\ (mod\ n)\quad $% with $%\ n\neq prime\ $% holds for ALL $%m\in Z$%. You can use the following ($%p$% and $%q$% connecting) ''theorem'' to remove your problem and to verify Job's statement: $%\bullet$% Let $%p,q$% be prime and $%p\neq q$%. Then it holds: $%x\equiv a\ (mod\ p)\quad AND\quad x\equiv a\ (mod\ q)\ \Longleftrightarrow\ x\equiv a\ (mod\ pq)$% You may also check the (very short) RSAproof in ''Inroduction to Algorithms'' (Cormen, Lesierson, Rivest). They address exactly your point and they solve the issue nicely. Wolfgang 
Great , Anything you wrote is correct, inclusive the order of steps. You proved the extended Fermat Theorem $% m^{ed}=m\ (mod\ \varphi(pq))$% for all $%m\in Z$%. Very nice and short too.
Wolfgang