3
$\begingroup$

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?

$\endgroup$
6
  • $\begingroup$ This is hard to read. $\endgroup$
    – saulspatz
    Jan 22, 2021 at 17:07
  • 1
    $\begingroup$ 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. $\endgroup$
    – lulu
    Jan 22, 2021 at 17:11
  • 1
    $\begingroup$ $Z/35Z$ is not a field and can have divisors of 0. $\endgroup$
    – Damien
    Jan 22, 2021 at 17:11
  • $\begingroup$ You missed a couple of solutions. If you follow @lulu's suggestion, you'll find them. $\endgroup$
    – saulspatz
    Jan 22, 2021 at 17:16
  • 1
    $\begingroup$ 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. $\endgroup$
    – peter a g
    Jan 22, 2021 at 18:26

3 Answers 3

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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\}$

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .