Let say if Alice would like to send a secret message to Bob, she may want to first encrypt the message before sending it. Modern cryptographic techniques all use some secret keys to encrypt and decrypt a message. For example, we may generate a random sequence with a predefined seed (the key) and take the bitwise sum of the random sequence and the message as the encrypted message (also known as ciphertext). At the other end of communication, as long as Bob also has the key (the original seed), he can regenerate the random sequence and decipher the message as the bitwise sum of the random sequence and the ciphertext.
The above scenario is an example of symmetric cryptography. The problem is that Alice has to share with Bob the secret key somehow. And if some malicious Eve manages to get the secret key, she can eavesdrop the message without being caught.
Public key cryptography
To avoid the above problem, it is much better if we have an `”asymmetric” system, where the encryption and decryption keys are different. Alice will then encrypt her message with the encryption key (the public key) and Bob will decipher the ciphertext with the decryption key (the secret key). Basically, when Alice needs to send a secret message to Bob, she will first ask Bob to send her his public key. After receiving Bob’s public key, Alice will encrypt the message with his key. And only Bob can decipher the message with his secret key. Therefore, this is also called public key cryptography.
For the above to work, we need to make sure that while it is easy to compute the original message from the ciphertext with the decryption key, it is computationally infeasible (extremely expensive) to decipher the message without the key. Moreover, we need to make sure that we cannot derive the secret key from the public key, the ciphertext, or the combined information.
RSA encryption algorithm
RSA encryption algorithm considers the following math problem
$latex m^e \equiv c \mod N$,
where $latex m$, $latex e$, $latex c$ are the original message, encryption key, and ciphertext, respectively, and $latex N$ is some very large integer. In plain English, the ciphertext $latex c$ is the remainder of $latex m^e$ divided by $latex N$.
Note that while it is easy to compute the $latex c$ from $latex m$ given $latex e$ and $latex N$. It is very difficulty to compute the inverse for large $latex N$ and $latex e$. Now, the question is what should the secret key $latex d$ be and what should we do with $latex d$ so that we can solve $latex m$ given $latex c$. Actually it is not even clear from the equation alone that the inverse exists or is unique.
Euler’s theorem
Euler’s theorem luckily comes to the rescue. It states that
for any integer 
From Euler’s theorem, for any arbitrary positive integer $latex k$, we immediately have
$latex a^{k \phi_n + 1} \equiv a \mod n$.
So if we pick $latex e d = k \phi_n + 1$, we have
$latex c^d = (a^e)^d \equiv a \mod n$. In plain English, we can decipher the message as the remainder of $latex c^d$ divided by $latex n$.
Numerical example
Let’s borrow an numerical example from this very nice video. In particular, we will construct $latex n$ as the product two prime numbers $latex p$ and $latex q$. Let’s choose $latex p=53$ and $latex q=59$, then $latex n=53 \times 59 = 3127$ and $latex \phi_n = (p-1)(q-1) = 3016$. Pick $latex e=3$ and $latex k=2$. Note that $latex d=\frac{k \phi_n +1}{e}=\frac{2 \cdot 3016 +1}{3}=2011$, which is an integer as desired.
So to transmit a secret message, Bob should first send the public key $latex e$ and $latex n$ to Alice. For example, Alice would like to send the message $latex m = 89$ to Bob. The ciphertext should then be computed as the remainder of $latex 89^e=89^3$ divided by $latex n=3127$, which gives us $latex c = 1394$. And when Bob received $latex c = 1394$, he should decipher the message as the remainder of $latex 1394^d=1394^{2011}$ divided by $latex n=3127$. This gives us back the original message of $latex 89$.
Final words
A really careful reader here may catch a “bug” of our argument above. Note that Euler’s theorem only hold for message which is coprime with $latex n$. Since $latex n=p q$, not every integer smaller than $latex n$ is coprime with it. This suggests that we should limit our message only to a subset of positive integers smaller than $latex n$. However, it turns out that this is not necessary. A complete proof for RSA can be shown using a combination of Chinese remainder theorem and Fermat’s little theorem (a special case of Euler’s theorem). But that would be another story.