I have been given this as an assignment question but I'm not sure approach it.
EDIT: Sorry I should have added more details. It is a cryptosystem using the RSA scheme. p and q are both old prime numbers and the encryption exponent must be greater than 1000.
Taking up @ccorn's suggestion, here is my slighty expanded comment as an answer:
With $p,q$ odd primes and $p\ne q$ the restrictions for the public RSA exponent $e$ is $1 < e < \varphi(pq)$ and $\gcd(e, \varphi(pq))=1.$ Because you have a more restrictive lower bound, your smallest exponent $e$ can be found as the smallest odd $e > 1000$ with $\gcd(e, p-1)=1$ and $\gcd(e, q-1)=1$ or using one gcd and larger numbers $\gcd(e, (p-1)(q-1))=1$.
You do not have to check even $e$ because $\varphi(pq)$ is even and therefor the gcd would be at least 2.
Edit: In most case you get $e$ simply by computing the gcd, computing gcds is fast. If it is not 1, go to the next possible value $e+2$. There $\varphi(\varphi(pq))$ legitimate values (if you include the $e<1000$). In many of your practical cases $e=1001$ will work.
An example for the small values $p=97, q=101.$ You have $\varphi(pq)=9600$ and $\varphi(\varphi(pq))=2560$, i.e. here roughly $52\%\,$ of all odd values are legitimate and $\gcd(1001,9600)=1$. If you would start at $e=3$ you get $$\gcd(3,9600)=3,\quad\gcd(5,9600)=5,\quad\gcd(7,9600)=1$$
An example where $e=1001$ is not legitimate is $p=97,\, q=113.$ Here you have $\varphi(pq)=10752\,$ and $\gcd(1001, 10752)=7,\,$ but the next value works $\gcd(1003, 10752)=1.$