1
$\begingroup$

I understand how to solve an equation like: $$17x \equiv 3 \pmod 5$$

But is there a known method for solving a congruence of the form:

$$17 \equiv 3\frac{\sqrt{x}}{2} \pmod 5\quad ?$$

Is it as simple as moving the $x$ through operations and applying the congruence to the new equation? $$(34/3)-\sqrt{x}\equiv 0 \pmod5$$ or $$(14)/(\sqrt{x})\equiv3\pmod5$$ Or is the position of $x$ insignificant?

  • 1
    I don't really understand the question. Isolate $\sqrt{x}$, then square.2012-05-31

1 Answers 1

5

You have to be careful with square roots in modular equations, since not every number has a square root (much like you would for integers), and when they do, there is no way to select one the way we do with real number (where we always pick the nonnegative one). That is, $\sqrt{x}$ is not well-defined modulo $5$. For example, if $x=4$, does $\sqrt{x}$ represent $2$, or does it represent $3$? Both numbers, when squared, are congruent to $4$ modulo $5$.

But you can work essentially the same way as you do with equations. From $$17\equiv \frac{3\sqrt{x}}{2}\pmod{5}$$ we note that $17\equiv 2\pmod{5}$; multiplying through by $2$ we get $$4\equiv 3\sqrt{x}\pmod{5}.$$ The multiplicative inverse of $3$ modulo $5$ is $2$, so multiplying through by $2$ and noting that $8\equiv 3\pmod{5}$ we get $$3\equiv \sqrt{x}\pmod{5}.$$ So $9\equiv x \pmod{5}$. Hence $x\equiv 4\pmod{5}$. Note that $4$ does have a square root modulo $5$; in fact, it has two square roots: $2$ and $3$. However, $\sqrt{x}=2$ does not satisfy the original equation, so you need to have $x\equiv 4\pmod{4}$ and $\sqrt{x}\equiv 3\pmod{5}$.

  • 0
    thanks for the response, but I am confused when you say "4 _does_ have a square root modulo 5". Can you explain your process showing 2 and 3 satisfy this statement? Or give a numerical explanation?2012-05-31
  • 0
    Since, in the integers, $4=2^2$, then $2$ is certainly a square root of $4$ modulo $5$ as well. The "other" square root will be $-2$, but $-2\equiv 3\pmod{5}$, so $3$ works. But the point is that whereas in the real numbers there *is* a clear way to "prefer" $2$ to $-2$ (via the general instruction "always take the positive square root when given the choice), there is no such general way to say why we would "prefer" $2$ to $3$ for "the" square root of $4$.2012-05-31
  • 0
    Right. $-2$... thanks.2012-05-31