# Linear Congruences

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?

-
I don't really understand the question. Isolate $\sqrt{x}$, then square. – Qiaochu Yuan May 31 '12 at 4:49

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}$.
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$. – Arturo Magidin May 31 '12 at 5:18
Right. $-2$... thanks. – Char May 31 '12 at 5:20