So the title says it all,

> Q: Given a large odd integer $N>>0$, what can we prove about the smallest prime $p>N$ such that $gcd(p-1,N)=1$?

Note that such a prime exists: Given an integer $a$ coprime to $N$ we know that there are infinitely many primes $p$ with $p\equiv a\pmod{N}$. In particular, since $N$ is odd we may take $a=2$ and thus we know that there are infinitely many primes $p\equiv 2\pmod{N}$ and thus infinitely many primes $p$ such that $gcd(p-1,N)=1$ so the question makes sense.

I would be extremely happy if we could always prove the existence of a prime $N < p < \frac{3N}{2}$ (for $N$ a large odd integer) such that $(p-1,N)=1$.

The first question seems to be difficult so here is a more tracktable question:

Q: So let $N$ be a large odd integer. Is it always possible to find two prime numbers $p,q$ in the interval $(N,\frac{3N}{2})$ such that $(p-1,q-1,N)=1$?