13
$\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$
7
  • $\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, 2019 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, 2019 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, 2019 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$ Apr 13, 2019 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, 2019 at 6:09

1 Answer 1

3
$\begingroup$

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

$\endgroup$
5
  • 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$ Apr 13, 2019 at 23:04
  • 1
    $\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 Tey
    Apr 13, 2019 at 23:22
  • $\begingroup$ Because it's just a number without any justification. Anyway, I'll retract the comment. $\endgroup$
    – egreg
    Apr 13, 2019 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, 2019 at 5:49
  • $\begingroup$ @Peter: Yes, there are some tricks -- see my updated answer at math.stackexchange.com/q/3186676 $\endgroup$ Apr 14, 2019 at 18:40

You must log in to answer this question.

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