# What is the smallest prime so that an instance of the discrete log problem has a solution?

The decision version of the discrete log problem in $\mathbb{Z} /q \mathbb{Z}$ is to determine whether there exists a k so that $x^k$=y mod q.

Let gcd(x,y)=1. I am interested in an upper bound for the smallest odd prime q not dividing x or y so that $x^k=y$ mod q has a solution for some k.

Let w=max(x,y). Based on calculations I would guess the bound to be O$(log^i w)$ for some i>1.

i=1 is too small: x or y can be a product of consecutive primes starting from 2 and it is known that the product over the primes < ln(w) is O(w) so q must be larger than O(ln(w)).

Note that if q|y-1 then a solution is guaranteed, so a trivial bound is for q to be the smallest odd factor of y-1.

-

I wonder if there exist $x$ and $y$ such that $x-y,x^2-y,x^3-y,\dots$ are all prime. It seems unlikely, but I don't see how to prove it can't happen. If there are infinitely many such $x$ and $y$, then the kind of bound you want won't exist.
EDIT: If $\gcd(x,y)=1$, $|x|\ge2$, and $x-y=p$ is prime, then $x^p-y$ is a multiple of $p$, so not a prime. But that doesn't give the kind of bound you're after.
I guess you're not interested in cases where $x=0$, $1$ or $-1$... – Robert Israel Jun 1 '11 at 1:45