1

For example $x^2 \equiv 13 \bmod 29$. The only solution that comes to mind is to just calculate the squares of all of the numbers from 0 to 28, but that's tedious. Is there a better method?

EDIT: the question that this is marked as a duplicate to doesn't contain an answer as to how to solve such congruences, only for determining whether there exists a solution. So while a similar question has been asked, it hasn't been properly answered and IMO it's not duplicate then.

Joald
  • 625
  • 3
    There's the Tonelli-Shanks algorithm: https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm – Angina Seng Aug 20 '17 at 18:44
  • A slightly better method: calculate the squares of the numbers from $0$ to $14$ only, because $15 = -14$, etc. :P – Cauchy Aug 20 '17 at 18:46
  • I found $x \equiv 10 \mod{29}$ by computing the square roots of $13 + 29 k$, where $k=0,1,2, \cdots$. – Math Lover Aug 20 '17 at 18:47
  • @Ravi $x \equiv 10 \mod{29}$ satisfies $x^2 \equiv 13 \mod{29}$. – Math Lover Aug 20 '17 at 18:50
  • @MathLover Thank you! I forgot for a moment that $13$ is $1$ modulo 4. – Arkady Aug 20 '17 at 18:56
  • 1
    Quadratic reciprocity often is useful to show existence: Your question is equivalent to whether 29 is a square modulo 13 but this is the same as 3 mod 13 being a square. This is further equivalent to 13 mod 3 being a square and that's true because 13 =1 mod 3. So your equation has a solution.

    https://en.wikipedia.org/wiki/Quadratic_reciprocity

     – Arkady Aug 20 '17 at 18:56

1 Answers1

2

One technique I've found for this is to try to complete the difference of squares. For example, consider $x^2\equiv24\bmod{125}$. We can notice that $24\equiv1024 \bmod 125$, so we have $x^2-1024\equiv(x-32)(x+32)\equiv0\bmod125$ and from that it easily follows that $x\equiv32\bmod 125$ or $x\equiv-32\equiv93\bmod 125$. We can eliminate the possibility of $(x-32)(x+32)$ being a number that is divisible by 125 because the two numbers differ by 64, and they would both have to be divisible by 5 for their product to be divisible by 125.

Joald
  • 625