Methods for finding a relatively prime integer

Question

Here's the problem:

Given a prime $p$ and an integer $x$, find an integer $c$ such that $gcd(x+c,p\#)=1$ where $p\#$ is the primorial for $p$.

It is straight forward to solve this problem using brute force or the Chinese Remainder Theorem.

Is there any other methods that can be used to find $c$? Ideally, it would be interesting to find the minimal $c$ where $gcd(x+c,p\#)=1$.

Thanks,

-Larry

Answer 1

$c=p\#-x+1$ clearly is a solution.
Cheap,but a solution.
The minimal $c$ if i am not mistaken is conjectured to be at the worst case $O(p^2)$ but i think this is still open.
EDIT:
It is known from the prime number theorem that $ln(p\#)\sim p$
So if you look at http://oeis.org/wiki/Jacobsthal_function you can see that indeed $c\sim O(p^2)$ is valid if we consider the worst case for the number $x$.
Of course though, $x$ could be an appropriate number (for example $x=p\#-1$) wich allows us to consider even the case $c=0$