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

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

-
 Hugo, please see my last comment (after your comment) below. – GH Mar 30 2011 at 15:33

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)$.

-
Thanks a lot Matt, Bombieri-Vinogradov is really cool! – Hugo Chapdelaine Mar 28 2011 at 17:03
Perhaps it is worth noting that $c\gg\frac{1}{\log\log x}$ which is sufficient. – GH Mar 28 2011 at 19:02
Very good point GH, this is the worst case namely when $N\sim\prod\limits_{p\leq\log(N)}p$. Then one uses the fact that $\prod_{p\leq x}(1-1/p)\sim\frac{1}{\log(x)}$. So we don't quite get a constant but $c>>\frac{1}{\log\log(x)}$ is good enough! – Hugo Chapdelaine Mar 29 2011 at 19:48
I admit I was pretty lazy about the constant! – Matt Young Mar 29 2011 at 20:16
@Hugo: Actually I have not verified my claim. I am sure the product of first primes is the worst case, but this requires a rigorous proof! – GH Mar 30 2011 at 15:32