A plaintext message T is then encrypted as a ciphertext C, where C = Te mod φ(n); a ciphertext message C is then decrypted by taking Cd mod φ(n). The reason that decryption is the inverse of encryption -- which is of course what one wants -- is Euler's theorem, which states that aφ(n) mod n = 1 whenever n and a are relatively prime positive integers. Assuming T and φ(n) are relatively prime, then, applying the encryption map and then the decryption map to some plaintext message T gives Tde mod n; but de is one more than some multiple of φ(n), so that's just T. (This is only true when T and φ(n) are relatively prime.)
Anyway, the point of this post really wasn't to talk about RSA cryptography, but to point to a letter written from Fermat to Frenicle in 1640. One often hears that Fermat very rarely proved things but just made motions saying "I have a proof", but the only such remark one actually hears repeated is the famous statement of Fermat's Last Theorem:
Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et generaliter nullam in infinitum ultra quadratum potestatem in duos ejusdem nominis fas est dividere: cujus rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.
which translates as something like:
It is impossible for a cube to be the sum of two cubes, a fourth power to be the sum of two fourth powers, or in general for any number that is a power greater than the second to be the sum of two like powers. I have discovered a truly marvelous demonstration of this proposition that this margin is too narrow to contain.
(I don't know Latin, so I take no responsibility for the correctness of this translation.) It turns out that there's a less famous remark regarding the Little Theorem:
Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.
This proposition [Fermat's Little Theorem] is generally true for all progressions and for all prime numbers; I would send you the demonstration if I did not fear that it were too long.
(The "progressions" refer to Fermat's phrasing of the theorem, in which he refers to the p-1 term of a geometric progression a, a2, a3, ... and claims that it is one more than a multiple of p.) The rest of the letter includes other such statements without proofs, but illustrated with copious examples. (The link I provided is to the version of David Zhao and Amanda Bergeron, which includes both the French text of the letter and their English translation; the English translation of Fermat's French I gave above is my own.)