The question asks how to systematically pick the public exponent $e$ in RSA. I'll stick to public modulus $N$ that is the product of exactly two distinct odd primes $p$ and $q$, but the choice of $e$ is not fundamentally different in multiprime RSA.
What's an acceptable public exponent $e$?
The public exponent in RSA should be an integer $e>1$ with $\gcd(e,p-1)=\gcd(e,q-1)=1$, so that $e$ will have an inverse both $\pmod{p-1}$ and $\pmod{q-1}$; or, equivalently, such that $e$ will have an inverse $\pmod{\phi(p\cdot q)}$. This insures that $e$ is odd, for we have assumed that $p$ and $q$ are.
Also, $e$ must not reveal so much information (about $p$ or $q$, or $\phi(p\cdot q)$) that it significantly simplifies factorization of $N$. This rules out some non-iterative constructive methods like $e=\max(p,q)$, or $e=(p-1)(q-1)+1$, or $e=(p-1)(q-1)-1$ (which do insure that $\gcd(e,p-1)=\gcd(e,q-1)=1$, assuming $\min(p,q)>3$ for the last formula).
Some RSA definitions, most notably PKCS#1, require $e<N$. There is no stated rationale for that requirement.
An old, straightforward (but non standard) method to chose $e$
If we ignore the requirement that $e<N$, one straightforward method is to set $e=N$, which satisfies all other requirements provided that $\min(p,q)$ does not divide $\max(p,q)-1$ (which does not hold in the example in the question, but is extremely likely for large random primes $p$ and $q$; and is certain if $2\min(p,q)>\max(p,q)$, or if $p$ and $q$ have exactly the same bit size, or if $2^{k-1/2}<p<2^k$ and $2^{k-1/2}<q<2^k$ for some integer $k$; all of which are common requirements for $p$ and $q$, listed by increasing selectivity).
This choice of $N$ as the public exponent historically is the first method that was considered, before RSA got named (C. Cocks, A Note on "non-secret encryption", classified GCHQ note dated 20 November 1973, re-typeset here). It is demonstrably as safe as can be with respect to attacks factoring $N$ (or equivalent to that), since we do not reveal anything beyond $N$, which we make public anyway; however, as noted by Chris Peikert, the RSA problem (of finding $x$ knowing $x^e\bmod N$) might be easier for this choice of $e$ (we have no indication of that).
A PKCS#1-conformant (if not standard) method to chose $e$ from $N$
An idea is to select $e$ as a prime with $N/3\le e<N$; such $e$ is acceptable, since it is a prime at least $\max(p,q)$, thus co-prime to $p-1$ and $q-1$. We can pick the smallest prime at least $N/3$, or the highest prime less than $N$. For small $N$ we can restrict to $e$ in a table of pre-computed primes: $7$, $17$, $41$, $97$, $257$, $769$, $1153$, $2113$, $4129$, $12289$, $18433$, $40961$, $65537$, $163841$, $270337$, $786433$.. (I have picked values with at most 3 bits set in their binary representation, which slightly simplifies raising to the $e$th power). Since these choices of $e$ do not depend on the factorization of $N$, they can't help factorize $N$ (but we have no idea if that's a bad or good choice w.r.t. the RSA problem).
The above methods are uncommon, for reasons explained below. To my knowledge, standard and safe methods to chose $e$ somewhat use trial an error in the choice of $e$ from $p$ and $q$, or the choice of $p$ and $q$ from $e$; and most such methods have additional objectives.
Should $e$ have other characteristics?
There is incentive not to chose $e$ too large, for a large $e$ slows down the public-key operation (about proportionally to the bit size of $e$) with no tangible benefit provided proper padding is used. That's one good reason not to use any of the above methods. FIPS 186-4, appendix B.3.1 puts the limit at $e<2^{256}$. In fact, $e\ge2^{32}$ has become uncommon, for it has caused interoperability hurdles with some RSA implementations (formerly including that bundled in Windows); and unduly long waits for users of Smart Cards.
Some standards/security authorities set a lower bound on $e$, typically $e>2^{16}$. That's of debated rationality when using a proper padding scheme.
It is common to choose $e$ prime, because this decreases the amount of trial and error, for odds that a prime $e$ and much larger prime $p$ meet $\gcd(e,p-1)=1$ are $(e-2)/(e-1)$ (thus quickly converging to $1$ when $e$ grows) if either $e$ or $p$ is random; while odds are lower if we remove the condition that $e$ is prime (the odds become mostly independent of the magnitude of $e$; as a hint to that, odds that two large integers each uniformly chosen below some limit $m$ are coprime converges to $6/\pi^2\approx60.8\%$ when $m$ grows). As an aside, if $e$ is composite, revealing it as part of the public key arguably reveals even so slightly more information about $p$ and $q$ (or about $\phi(N)$ or $\lambda(N)$) than if $e$ was a large prime, for there are less possible $p$ and $q$ knowing $e$.
There is also incentive to choose $e$ of the form $2^i+1$, because that's allowing the fastest computation of $x^e\bmod N$ for a given size of $e$ (only $i$ modular squaring and one modular multiplication are required). If we combine with $e$ prime, that leaves the Fermat primes $F_j=2^{(2^j)}+1$ with $0\le j\le4$ as the only candidates (it is conjectured that there exists no other Fermat prime, and known that there are none of manipulable size).
Choice of $p$ and $q$ before search of $e$ by trial and error
RSA key generation as in a textbook typically choose $p$ and $q$ first. An unobjectionable method to then chose $e$ is to try values of $e$ that are moderate random primes in some suitably large interval, until one $e$ is found such that $e$ does not divide $p-1$ or $q-1$. Such $e$ is acceptable w.r.t. both $p$ and $q$ (assumed much larger, random and independent primes) with odds $(e-2)^2/(e-1)^2$, thus high for all but very small $e$. If we specify a large enough interval for $e$ (e.g. $2^{16}<e<2^{17}$) and the choice of $p$ and $q$ is without relations to the primes in that interval, it is not even necessary to insure that the $e$ tested are distinct to find a suitable $e$ quickly, with overwhelming odds.
Some (including the teacher in the question) select $e$ as the lowest prime at least some fixed minimum (chosen no less than $3$) dividing neither $p-1$ nor $q-1$ (or not dividing $\phi(N)$). Notice that doing so often reveals some information about $\phi(N)$: if in a large collection of public keys known to have been generated by the same device we see keys where $1/4$ of the $e$ are $3$ (thus $25\%$ of $e$), $9/16$ of the other $e$ are $5$ (thus about $42.2\%$ of $e$), $25/36$ of the other $e$ are $7$ (thus about $22.8\%$ of $e$), and generally $(r-2)^2/(r-1)^2$ of the other $e$ are $r$ for $r$ the successive primes starting from $11$, we have reverse-engineered the choice of $e$, and know that for the few public keys of the form $(N,23)$, $\phi(N)$ and $\lambda(N)$ are a multiple of $3\cdot5\cdot7\cdot11\cdot13\cdot17\cdot19$, which can be used to speed-up a straight brute-force search of these quantities (it is likely that there is at least one such public key if we gathered $27600$ of these). It might give a feeling of discomfort, although we do not know that such knowledge can significantly improve one's ability to find $\phi(N)$ or $\lambda(N)$ knowing the public key, or otherwise derive a working private key, or factor $N$ (rationale: these goals are equivalent, factorization of $N$ is by far the most efficient avenue known to reach any of these goals, and we do not know how to use a known moderate divisor of $\phi(N)$ or $\lambda(N)$ to speed up that factorization).
We can also choose $e$ as an (odd) random integer (not necessarily prime) in some similar interval until $\gcd(e,p-1)=\gcd(e,q-1)=1$. It will require significantly more trials, but success is also virtually insured; and by the same reasoning as above, whatever little extra information we leak is not a worrying security issue.
Hand computation of small $e$ for moderate $p$ and $q$ expressed in decimal
We can easily test divisibility by the primes $5$, $3$, $11$, $37$, $101$. We'll pick the first $e$ in this list that is suitable. Odds that none is suitable are only $0.0068\%$.
If neither of $p$ and $q$ has a $1$ or $6$ as its rightmost decimal digit, then neither $p-1$ nor $q-1$ is divisible by $5$, and we select $e=5$. That won't do for the example in the question (because $q=11$ ends in $1$), but is enough for $p=14627$, $q=15959$ (because neither $7$ nor $9$ are $1$ or $6$).
Otherwise, we sum the digits in $p$; subtract $1$; recursively sum the digits in the result, until the result is single-digit; if that digit is not divisible by $3$, $p-1$ is not, and we do the same test for $q$; if we find that $q-1$ is not divisible by $3$, we select $e=3$. That's the case for $p=5$, $q=11$ in the question (because neither $4$, nor $1$, are divisible by $3$).
Otherwise, we use similar techniques for $e=11$, $37$, and $101$; the divisibility rules are explained here.
Choice of $e$ before search for $p$ and $q$ by trial and error
Real-world RSA implementations tend to choose $e$ first, typically because
- very commonly, $e=2^{16}+1=65537$ is required, because that's the minimum value recognized as acceptable by all security authorities, thus unobjectionable and well-supported;
- sometime $e=3$ is required, because that gives the best speed of the public-key RSA operation, with no known drawback if proper padding methods are used;
- having a fixed $e$ simplifies the transmission of the public key; in that case, one of the Fermat primes $F_j=2^{(2^j)}+1$ is typical.
With $e$ prime, we can pick a prime $p$ such that $p-1$ is not a multiple of $e$, and it insures $\gcd(e,p-1)=1$. The contrary has odds only $1/(e-1)$ for random prime $p$, and that's rare enough to be mildly hard to test for the very popular $e=2^{16}+1$.
An unobjectionable method reducing guesswork (especially for the smaller $e$ like $3$) is to chose $e$ prime, then when it comes to the choice of $p$ chose a secret $f$ uniformly random with $0<f<e-1$, then only explore candidate primes of the form $p=(2k+(f\bmod 2))\cdot e+f+1$, which insure $p$ is odd and $\gcd(e,p-1)=1$. $f$ should be randomly drawn again when it comes to the choice of $q$.
ewill certainly take longer than findinge. $\endgroup$evia trival division in less than a minute, it's so big that you won't be able to do the rest of RSA. For example no four-digit number is co-prime to 3, 5, 7, 11 and 13. $\endgroup$