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



Given an odd integer N find the smalletst prime p > N such that (p-1,N)=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)$.


