12
$\begingroup$

I wonder whether the congruence $$2^{n-1}\equiv 203\mod n$$ with integer $n>1$ has only the solution $n=101$.

Up to $n=10^9$, there is no solution.

Since $n$ must be odd, every prime factor $p$ of $n$ must have $203$ as a quadratic residue modulo $p$ and $2^k\equiv 203 \mod p$ must be solvable.

Deeper analysis reveals that the smallest possible prime factors are $17$ and $53$.

  • If $17$ is a prime factor , $n$ must be of the form $136k + 85$.
  • If $53$ is a prime factor , $n$ must be of the form $2756k +477$.
$\endgroup$
  • $\begingroup$ how can you say that every prime factor must have $203$ as a quadratic residue modulo $p$? Could you elaborate? $\endgroup$ – vidyarthi Apr 5 at 7:35
  • 2
    $\begingroup$ @vidyarthi Since $n$ is odd , $n-1$ is even , hence $2^{n-1}$ a perfect square. $\endgroup$ – Peter Apr 5 at 9:02
  • $\begingroup$ Assuming $2^{n-1}\equiv 203\pmod n$, can you determine $n\mod 3$ or $n\mod 4$? $\endgroup$ – W-t-P Apr 6 at 8:56
  • $\begingroup$ Is this question about $203$ and $n=101$ in particular, or is it really asking the general question, how to determine the greatest $n$ satisfying $2^{n-1} \equiv r$ (mod $n$), and/or whether a greatest $n$ always exists? If in fact there is a greatest $n$ for every given $r$, and the law of it can be even roughly determined, it might be unnecessary in the posted case to test values of $n$ beyond a limit far less than $10^9$. $\endgroup$ – Edward Porcella Apr 13 at 22:52
  • 1
    $\begingroup$ @EdwardPorcella This question is only about $203$, the smallest case for which I could not find a solution, even with several tricks. I am actually interested in the general case, but the answer to this question is what Max answered. Since no further information was given by Max, I assume that he used more or less brute force. $\endgroup$ – Peter Apr 14 at 6:09
3
$\begingroup$

No. The next solution is $n=33191065315201$.

$\endgroup$
  • 1
    $\begingroup$ It seems to answer the question when I read it. We have another solution, which is what the OP seems to ask. $\endgroup$ – Oscar Lanzi Apr 13 at 23:04
  • $\begingroup$ @egreg while this is not as good as a complete solution (which might be impossible or extremely tough), this is an extremely valuable answer and a counterexample to the conjecture in the question. Why do you disagree? $\endgroup$ – YiFan Apr 13 at 23:22
  • $\begingroup$ Because it's just a number without any justification. Anyway, I'll retract the comment. $\endgroup$ – egreg Apr 13 at 23:24
  • $\begingroup$ This is actually what I wanted : A second solution. @MaxAlekseyev Did you find the solution by brute force or did you use some trick ? $\endgroup$ – Peter Apr 14 at 5:49
  • $\begingroup$ @Peter: Yes, there are some tricks -- see my updated answer at math.stackexchange.com/q/3186676 $\endgroup$ – Max Alekseyev Apr 14 at 18:40

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.