Find all solutions of congruence $3x^2−2x+9≡0\pmod {35}$ [duplicate]

Find all solutions of congruence $$3x^2 - 2x + 9 ≡ 0 \bmod 35$$:

Attempt: \begin{align} 3x^2 - 2x + 9 &\equiv 0 \bmod 35\tag{* 3} \\ 9x^2-6x+27 &\equiv 0 \bmod 35 \tag{- 26} \\ (3x-1)^2 &\equiv -26 \bmod 35 \\ \\ -26 + 35 &= 9 = 3^2 \\ \\ \iff (3x-1)^2 &\equiv 3^2 \bmod 35 \\ \iff (3x-1-3)*(3x-1+3) &\equiv 0 \bmod 35 \\ \\ \implies \underbrace{3x - 4 \equiv 0 \bmod 35}_{(a)} &\lor \underbrace{3x + 2 \equiv 0 \bmod 35}_{(b)}\\ \end{align}

Case $$(a){:}\; 3x - 4 \equiv 0 \bmod 35$$ $$\Rightarrow 3x \equiv 4 \bmod 35$$ $$\Rightarrow 3x \equiv 39 \bmod 35$$
$$\quad\underset{ ( gcd(3,35) = 1)}{\implies} x \equiv 13 \bmod 35$$

Case $$(b){:}\; 3x +2 \equiv 0 \bmod 35$$ $$\Rightarrow 3x \equiv -2 \bmod 35$$ $$\Rightarrow 3x \equiv 33 \bmod 35$$
$$\quad\underset{ ( gcd(3,35) = 1)}{\implies} x \equiv 11 \bmod 35$$

So $$x = 13$$ or $$x = 11$$.

Is it correct that way?

• This is hard to read. Jan 22, 2021 at 17:07
• Usually, the way one approaches these things is to factor the modulus. Thus, solve the problem $\pmod 5$ and $\pmod 7$ separately. Of course, $35$ is so small that even a brute search is easy.
– lulu
Jan 22, 2021 at 17:11
• $Z/35Z$ is not a field and can have divisors of 0. Jan 22, 2021 at 17:11
• You missed a couple of solutions. If you follow @lulu's suggestion, you'll find them. Jan 22, 2021 at 17:16
• To make sure you understand @Damien's comment, using a popular, 'smaller' example: $x^3-x\equiv 0\pmod 6$ holds for every integer - so there are six solutions $\pmod 6$ (check this!). On the other hand the factorization $x^3-x= x (x-1)(x+1)$ only exhibits three solutions $\pmod 6$. This isn't a contradicton For instance, setting $x=2$ in the factorization, $2\cdot 1 \cdot 3 \equiv 0 \pmod 6.$ The numbers $2$ and $3$ in the factorization are 'zero divisors' $\pmod 6$; so ${\mathbb Z}/6{\mathbb Z}$ is not a field. Similar considerations hold in your question. Jan 22, 2021 at 18:26

As other comments and solutions have noted, you need to consider that 35 is composite. But nearly all of your work is correct and completing the square is a great strategy for arbitrary quadratic congruences.

$$(3x-4)(3x+2)\equiv0\pmod{35}$$ This is correct. But then you need to go from there to $$(3x-4)(3x+2)\equiv0\pmod 5 \qquad\text{ and }\qquad (3x-4)(3x+2)\equiv0\pmod 7$$

we'll tackle those one at a time.

$$3x-4\equiv0\pmod 5\qquad\text{ or }\qquad 3x+2\equiv0\pmod 5\\ 3x\equiv4\pmod 5\qquad\text{ or }\qquad 3x\equiv3\pmod 5\\ x\equiv3\pmod 5\qquad\text{ or }\qquad x\equiv1\pmod 5\\$$

$$3x-4\equiv0\pmod 7\qquad\text{ or }\qquad 3x+2\equiv0\pmod 7\\ 3x\equiv4\pmod 7\qquad\text{ or }\qquad 3x\equiv5\pmod 7\\ x\equiv6\pmod 7\qquad\text{ or }\qquad x\equiv4\pmod 7\\$$

Pairing those solutions together with the CRT (Chinese Remainder Theorem) gives you the four solutions others have mentioned.

There is a direct way to solve modulo $$35$$ with the traditional quadratics method.

$$\Delta^2=b^2-4ac=2^2-4\times3\times 9=-104\equiv 1\pmod {35}$$

However as you can see it requires you to know how to solve $$\Delta^2\equiv 1\pmod{35}$$, but let assume you have a precomputed table of the squares then:

$$\Delta\in\{1,6,29,34\}=\{-1,1,-6,6\}$$

Then use $$x=(-b\pm\Delta)\times (2a)^{-1}\pmod {35}$$

$$(2a)^{-1}\equiv 6^{-1}\equiv 6\pmod{35}$$ and we do not have to worry about the $$\pm$$ in the formula since $$\Delta$$ already covers additive inverses.

Therefore for each $$4$$ values of $$\Delta$$ we get same number values of $$x\in\{6,11,13,18\}$$

At no point in your proof did you split the congruence into $$\bmod5$$ and $$\bmod7$$, so you missed two solutions as I will show below: $$3x^2-2x+4=0\bmod5\implies x^2+x+3\equiv0\bmod5\implies x\equiv\{1,3\}\bmod5$$ $$3x^2-2x+2\equiv0\bmod7\implies x^2+4x+3\equiv0\bmod7\implies x\equiv\{-1,-3\}\bmod7$$ Combining with the Chinese remainder theorem this gives $$x\equiv\{6,11,13,18\}\bmod35$$.