Métodos para encontrar un número entero relativamente primo

Question

Este es el problema:

Dado un primo $p$ y un número entero $x$ , encuentre un número entero $c$ tal que $gcd(x+c,p\#)=1$ donde $p\#$ es el primitivo para $p$ .

Es sencillo resolver este problema utilizando la fuerza bruta o el Teorema Chino del Resto.

¿Hay algún otro método que se pueda utilizar para encontrar $c$ ? Idealmente, sería interesante encontrar el mínimo $c$ donde $gcd(x+c,p\#)=1$ .

Gracias,

-Larry

Answer 1

$c=p\#-x+1$ claramente es una solución.
Barato, pero una solución.
El mínimo $c$ si no me equivoco se conjetura que en el peor de los casos $O(p^2)$ pero creo que esto sigue abierto.
EDITAR :
Se sabe por el teorema de los números primos que $ln(p\#)\sim p$
Así que si miras http://oeis.org/wiki/Jacobsthal_function se puede ver que efectivamente $c\sim O(p^2)$ es válido si consideramos el peor caso para el número $x$ .
Sin embargo, por supuesto, $x$ podría ser un número apropiado (por ejemplo $x=p\#-1$ ) que nos permite considerar incluso el caso $c=0$