RSA exercises example I have doubts about this question


  Consider the following textbook RSA example. Let be p = 7, q = 11 and
  e = 3. Give a general algorithm for calculating d and run such
  algorithm with the above inputs.  What is the max integer that can be
  encrypted? Is there any changes in the answers, if we swap the values
  of p and q?


I tried to apply RSA in this way:

$p=7$ and $q = 11$ so $n=(pq)$ and $n=77$, therefore $$\phi(pq) = (p-1)(q-1) = (7-1)(11-1)= 60$$

Pick $e$ that is $&lt;60$ and isn't coprime (which means I can't use $2,3$ and $5$)

So after that, I'm blocked, and my solution is to choose another coprime, for example $e=7$ in order to have  public-key: $(n,e)= (77,7)$

But I'm wrong somewhere, because if I use $7$ (or another coprime like $11$) I can't compute $d$. 
In fact, for all numbers that I used, for example with $e=7$, if I pick $d=9$ I have $63$ that if I divided for $60$ I have $1$ with rest $3$.

So my questions are these :


Am I wronging? (where?)
As a request , can I pick 3, even if it isn't coprime? (because as I saw
on theory, I need at least a coprime). 
pick $e= p$ or $q$ seams wrong.right?
if I use $e=7$ (or another coprime like $11$) I can't compute $d$


You can use $e=7$. When $n$ is squarefree, a private exponent $d$ will work if (not: only if) $e\;d\equiv1\pmod{\phi(n)}$, that is by definition when $e\;d-1$ is divisible by $\phi(n)$. There are solutions to that if and only if $e$ is coprime with $\phi(n)$. The textbook systematic way to find such $d$ is the Extended Euclidean Algorithm. See there for a more efficient and easier to implement variant; or there for a "binary" variant.

Note: When $n$ is squarefree, the necessary and sufficient condition for $d$ to work in RSA is: $e\;d\equiv1\pmod{\lambda(n)}$ (where $\lambda$ is the Carmichael function). That simplifies computation of $d$, and typically leads to a smaller one. $d=e^{-1}\bmod\lambda(n)$ is required by some RSA standards including FIPS&nbsp;186-4. When $n$ is the product of distinct primes $p$ and $q$, $\lambda(n)$ can be computed as
$$\begin{align}\lambda(n)&amp;=\operatorname{lcm}(p-1,q-1)\\&amp;=\frac{(p-1)(q-1)}{\gcd(p-1,q-1)}\end{align}$$


  Can I pick $e=3$, even if it isn't coprime with $\phi(n)$?


No. It is required that $e$ is coprime with $\phi(n)$ [equivalently: that $\gcd(e,p-1)=1=\gcd(e,q-1)$ ] in order to insure unique decryption of ciphertexts. Otherwise, there will be multiple plaintexts $m\in[0,n)$ leading to the same ciphertext $m^e\bmod n$. In your case $(n,e)=(77,3)$, for example, $m=4$ and $m=15$ would lead to the same ciphertext $64$.


  Picking $e=p$ or $q$ seams wrong


For large $n$, it would be bad to choose $e$ equal to a factor of $n$ (or with any other approximate relation between $e$ and a factor of $n$) since that would allow factoring $n$. But when one deliberately illustrates RSA with a toy $n$ such as $n=77$ which is trivial to factor, choosing $e$ equal to one of the factors is a non-issue. Still, one could use $e=13$ to avoid that special case.


  What is the largest integer that can be encrypted?


In textbook RSA, plaintext and ciphertext space is the integer interval $[0,n)$. The largest integer that can be encrypted (and decrypts correctly) is thus $n-1$. Notice that it is always encrypted to itself, thus trivial to decipher. More generally, textbook RSA is insecure when directly used to encipher data. It is conjectured secure when $p$ and $q$ are large random secret primes, and a random $x$ in the plaintext space $[0,n)$ is enciphered.