# Can't understand the magic of relationship between private an public key functions

To encrypt a message

$$P = 53, Q=59, n=PQ=3127, e =3$$

let message M, for example, \$ 89

$$cipher = 89^{e}mod\quad n.$$ cipher = 1394 this is the encrypted message

$$\phi=(P-1)(Q-1)=3016$$

$$d=\frac{2(\phi(n))+1}{e} = 2011$$

decrypt $$89 = 1394^{2011}mod\quad 3127.$$

This is the original message

But I don't understand the mathematical logic behind this.

1. I can't understand what logic behind the generation of those successive equations that magically generate the original message

2. why P Q should be prime number?

When you exponentiate a number $$x$$ modulo $$n$$ to the $$i$$-th power, as you increase $$i$$, you will eventually reach $$x$$ again. In your example, $$89^{3017} \pmod{3127} = 89$$. This "magic exponent" is computed as $$\phi(n) + 1 = (p-1)(q-1) + 1$$.
In RSA, we choose the numbers $$e$$ and $$d$$ such that, when multiplied, they are equal to $$\phi(n) + 1$$, i.e. the "magic exponent" that gets you back to the original number.
Now, you encrypt with $$c = m^e \pmod{n}$$. This will get you "half way" into the exponentiation, into a seemingly "random" number that has nothing to do with $$m$$. Then, in order to decrypt, you compute $$c^d \pmod{n}$$ which will finish the exponentiation and get the result back to $$m$$. This is because $$c^d = (m^e)^d = m^{ed} \pmod{n}$$, and $$e$$ and $$d$$ were chosen precisely to be equal to $$\phi(n)+1$$, a.k.a. the "magic exponent".
If $$p$$ and $$q$$ weren't prime numbers, then your adversary can compute $$p$$ and $$q$$ from $$n$$ (which is part of public key together with $$e$$, and as the name says, is public). This is because factoring a number is easier the larger the number of factors it has, and if $$p$$ and $$q$$ aren't prime, then they are multiple of two or more prime factors, making $$n$$ have 4 or more prime factors, instead of just two as intended. If the adversary computes $$p$$ and $$q$$, they can compute $$d$$, which allows they to decrypt any message that was encrypted to you.