| So why does the RSA cryptosystem work? First, let's recall how it works. You pick two primes p and q of roughly the same size. You then let n = pq. This is the modulus you'll use. The public "exponent of encryption" e you set to a small constant (so that people who are sending you messages can do so at little computational cost). Then you find the multiplicative inverse d of e modulo phi(n) where phi(n) is the number of integers less than n to which it is relatively prime. This d is your private key (the "exponent of decryption"). So you publish the pair (n,e) and keep d secret. You can compute d because you know p and q and therefore phi(n). Other people cannot compute d because they don't know p and q and therefore don't know phi(n).
Whew. OK. Now for why it works:
Fact 1: if x = y mod phi(n)
then mx = my mod n for all m
Fact 2: ed = 1 mod phi(n)
because d is selected as e's inverse mod phi(n)
Therefore:
med= m1 mod n for all m by fact 1
So when someone encrypts m to you she computes: c = me mod n
When you decrypt you compute:
cd = (me)d mod n
= med mod n by high school math
= m1 mod n by fact 1
= m mod n
And we're done!
Note that you can prove Fact 1 above (the important part of the math, IMHO), using Fermat's Little Theorem or Euler's Theorem.
This cryptosystem is conjectured to be strong because given n and e, there is no known (efficient) algorithm that can find d. In fact, if you can find such an algorithm you will be very very very famous because then you will have found an efficient way to factor large numbers. | 
