Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
I guess you're not interested in cases where $x=0$, $1$ or $-1$... – Robert Israel Jun 1 '11 at 1:45
@Robert, not really, but of course I should have dotted those "i"s and crossed those "t"s. – Gerry Myerson Jun 1 '11 at 1:48

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.