1
$\begingroup$

I am interested in the solutions of the equation $2^{q-1} \equiv q \pmod {p} $ where $p=4q^2+1$ for an odd prime $q$.

So far the only solution I found by trial and error is $q=193$ but I don't know how to realize it as a solution. I'd like to know if there are other solutions.

By relaxing the condition on $q$ one gets two more solutions: $q=1,2$. It would also be interesting to see if there are other positive integer solutions.

$\endgroup$
4
$\begingroup$

Of the $148932$ odd primes $q<2000000$, the only solution to your equation is $q=193$. If you drop the primality restriction on $q$, then as well as $q=1$ and $2$, $q=29570$ is also a solution (with, as it happens, $p$ prime).

$\endgroup$
  • $\begingroup$ Thank you very much for your quick response. It was very helpful. $\endgroup$ – Yusuf Gurtas Jun 2 '15 at 15:37
3
$\begingroup$

I've checked all primes $q$ below $10^{11}$ with no new solutions found (even if the primality of $p=4q^2+1$ is relaxed).

Notice that $2^{q-1}\equiv q\pmod{4q^2+1}$ implies $2^{2q}\equiv 4q^2\equiv -1\pmod{4q^2+1}$, further implying that the multiplicative order of $2$ is $4q$ (also, 2 is a $q$-th power residue) modulo $4q^2+1$. Heuristically, this has probability $\frac{1}{q}$ and since primes $4q^2+1$ with prime $q$ are rather sparse (cf. A052292 in the OEIS), this likely means that there are only a finite number of suitable $q$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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