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.

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
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).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you very much for your quick response. It was very helpful. $\endgroup$
    – Yusuf Gurtas
    Commented Jun 2, 2015 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$.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .