Skip to main content
1 of 4
Hugo Chapdelaine
  • 7.6k
  • 2
  • 28
  • 70

Given an odd integer N find the smalletst prime p 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$.

Hugo Chapdelaine
  • 7.6k
  • 2
  • 28
  • 70