verify if $8x^2 - 2x - 3 \equiv 0 \pmod{75}$ has solutions or not.

Question

verify if $8x^2 - 2x - 3 \equiv 0 \pmod{75}$ has solutions or not.

I tried to write the left term in a form $y^2 \equiv a \pmod{75}$, where $a \in \mathbb{Z}$ so then I can use quadratic repriocity laws to solve this problem. But i get a fraction:

$8x^2 - 2x = 2((2x - \frac{1}{2})^{2} - \frac{1}{4}) $. So the previous statement is equivalent to proving:

$(2x - \frac{1}{2})^2 \equiv 3\frac{1}{2} \cdot \frac{1}{2} \mod 75$. which obviously does not help me further.

Any tips hints on this problem?

Answer 1

Multiply both sides by $8$:

$$(8x-1)^2\equiv 25\pmod{75}$$

So $5\mid 8x-1$. I.e. $3x\equiv 1\equiv 6\pmod{5}\stackrel{:3}\iff x\equiv 2\pmod{5}$. Assuming this,

$$\iff \left(\frac{8x-1}{5}\right)^2\equiv 1\pmod{3}$$

$$\iff \frac{8x-1}{5}\equiv \pm 1\pmod{3}$$

$$\iff 8x-1\equiv \pm 5\equiv \pm 2\pmod{3}$$

$$\iff \left(2x\equiv 0\pmod{3}\, \text{ or }\, 2x\equiv 2\pmod{3}\right)$$

$$\iff \left(x\equiv 0\pmod{3}\, \text{ or }\, x\equiv 1\pmod{3}\right)$$

By Chinese Remainder Theorem we'll surely have a solution. In this case, $x\equiv 12\pmod{15},\, x\equiv 7\pmod{15}$ are all the solutions.

Answer 2

Hint: $$ 8x^2-2x-3=(4x-3)(2x+1) $$ Is $2$ invertible mod $75$?

---

Since a full answer has been given in another post, I will add the following.

Indeed $2\cdot38\equiv1\pmod{75}$, so there are solutions.

---

Although not required by the question, we can find all the solutions as follows. $$ \begin{align} 8x^2-2x-3 &=(4x-3)(2x+1)\\ &\equiv8(x-57)(x-37)\pmod{75} \end{align} $$ Besides the obvious $$ x\equiv57\pmod{75}\\ x\equiv37\pmod{75} $$ we also have $$ \left.\begin{align} x&\equiv57\pmod{3}\\ x&\equiv37\pmod{25} \end{align}\right\}x\equiv12\pmod{75} $$ $$ \left.\begin{align} x&\equiv57\pmod{25}\\ x&\equiv37\pmod{3} \end{align}\right\}x\equiv7\pmod{75} $$ However, all of the preceding are contained in $$ \left.\begin{align} x&\equiv57\pmod{15}\\ x&\equiv37\pmod{5} \end{align}\right\}x\equiv12\pmod{15} $$ $$ \left.\begin{align} x&\equiv57\pmod{5}\\ x&\equiv37\pmod{15} \end{align}\right\}x\equiv7\pmod{15} $$

Therefore, all solutions are either $x\equiv7\pmod{15}$ or $x\equiv12\pmod{15}$.