Why do we use Φ while calculating the encryption key in RSA method?

As you know, in RSA encryption, we calculate an n value by multiplying two long primes. Then we calculate Φ(n), which is equal to (p-1)(q-1). After that, we choose an encryption key which satisfies gcd(e,Φ(n))=1. I know that it is necessary to calculate decryption key, which is the modular inverse of e. My question is: Why do we use Φ(n) in determination of encryption and decryption key processes? How can one prove it is working for RSA encryption?

Short answer. We use $\Phi(n)$ because that is the order of the multiplicative group of units modulo $n=pq$.

Long answer. RSA works via modular exponentiation modulo $n$. The idea is to take a message that corresponds to a number $M$, "encrypt" it by raising it some power $e$ to obtain an encyphered text $M^e$; and then "decrypt" by raising it to an appropriate power $d$ to recover $M$. The reason this works is that the multiplicative group of units modulo $n$ is a finite group, and by Euler's Theorem we know that $M^{\Phi(n)} \equiv 1 \pmod{n}$ for all $M$ that is relatively prime to $n$.

That means that for every integer $k$ we have $$M^{\Phi(n)+k} = M^{\Phi(n)}M^k \equiv 1\cdot M^k =M^k\pmod{n}.$$

That is, raising a number that is realtively prime to $n$ to the $\Phi(n)$-th power will "kill it": make it congruent to $1$.

In order to be able to recover $M$ from $M^e$ by exponentiation, we need there to exist a $d$ such that $M\equiv (M^e)^d = M^{ed}\pmod{n}$. But for this to be possible, we want $ed \equiv 1 \pmod{\Phi(n)}$; because if $ed\equiv 1 \pmod{\Phi(n)}$, then we can write $ed = r\Phi(n) + 1$ for some $r$, and then $$M^{ed} = M^{r\Phi(n)+1} = (M^{\Phi(n)})^rM \equiv 1^r\cdot M = M \pmod{n},$$ and we have recovered $M$.

The reason why you pick $e$ relative prime to $(p-1)(q-1)$ is because we know that all relative primes to $(p-1)(q-1)$ form a group with respect to multiplication, thus $e$ has a multiplicative inverse mod $(p-1)(q-1)$ (see group axioms). Let's call this number d.

Now to proof that the encryption/ decryption works, we have to show that $x^{ed} \equiv x \pmod{pq}$.

We do so as follows: remember that $ed \equiv 1 \pmod{(p-1)(q-1)}$. thus $ed = 1 + t(p-1)(q-1)$. for some $t \in \mathbb{Z}$.

Plugging this into $x^{ed}$ we get $x^{ed} \equiv x^{1+t \,(p-1)(q-1)} \equiv xx^{t\,(p-1)(q-1)}$

Now here you can apply Fermats little theorem when x is relative prime to p.

Thus we get $xx^{t(p-1)(q-1)} \equiv x(x^{(p-1)})^{t \,(q-1)} \equiv x1^{t \,(q-1)} \equiv x \pmod{p}$

and $xx^{t(p-1)(q-1)} \equiv x(x^{(q-1)})^{t \,(p-1)} \equiv x1^{t \,(p-1)} \equiv x \pmod{q}$.

Now because of the above and because $p$ and $q$ are relative prime, we know that $x^{ed} = x \pmod{pq}$.

When x and p or x and q are not relative prime, we cannot use Fermats little theorem. However, you should try deriving the correctness here yourself. If you can't work it out, give me a tell.

In RSA, $\rm\,\phi = \phi(pq)\,$ arises because it is the order of the group of the invertible integers $\!\!\rm\pmod{\!pq}$ The exponent $\rm\:e\:$ in the encryption map $\rm\:x\to x^e\:$ is chosen coprime to $\:\phi,\,$ i.e. $\rm\:(e,\:\phi) = 1,\:$ to ensure that the map $\rm\:x\to x^e\:$ is $1$ to $1$ so invertible, a necessary requirement for decryption to be unique. The proof is easy. If $\rm\:x^e \equiv y^e\:$ then $\rm\:z^e\equiv 1\:$ for $\rm\:z = x/y\:.\:$ By Euler $\rm\:z^\phi\equiv 1\:$ so by the Lemma below $\rm\:z^{(e,\:\phi)} \equiv 1\:.\:$ Thus if $\rm\:(e,\phi) = 1$ then $\rm\: z\equiv 1\:$ $\Rightarrow$ $\rm\ x\equiv y\ $ hence $\rm\:x\to x^e\:$ is $1$ to $1.$

Lemma $\rm\ (e,\phi) = \color{#c00}de+k\phi = 1, \ z^{e}\equiv z^{\phi}\equiv 1 \ \Rightarrow \ z^{(e,\,\phi)} =\ z^{\:d\,e+k\,\phi} = (z^e)^d (z^\phi)^k \equiv 1\cdot 1$

Remark $ $ More generally, this answer explains at length how we can take $\rm\,e\:\!$'th roots when $\,\rm e\,$ is coprime to the period (here $\phi)$ by simply raising to the power $\rm \,\frac{1}e\bmod \phi \ (\equiv\rm \color{#c00}d\,$ above).