Given an odd integer N find the smalletst prime p > N such that (p-1,N)=1

Question

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$?

Answer 1

Your first question seems to follow fairly easily from the Bombieri-Vinogradov theorem; actually it seems only to need Renyi's original result.

By Moebius inversion, it should suffice to find an asymptotic formula of the form $\sum_{d|N} \mu(d) \psi(x;d,1) = cx + O(x/\log{x})$ for some $c > 0$ and $N < x \leq 3N/2$.
If $d>z$ with $z$ some fixed small power of $x$ (say $z=x^{1/100}$) then the trivial bound $\psi(x;d,1) \ll x/d$ gives a satisfactory error term. Otherwise, by Bombieri-Vinogadov we have $$\sum_{d|N, d < z} |\psi(x;d,1) - x/\phi(d)| = O(x (\log{x})^{-100}).$$ Finally, compute $\sum_{d | N , d < z} \mu(d)/\phi(d)$.