System of linear and quadratic congruences

245 Views Asked by At

Solve the system:

$x^2+x+1\equiv 0\pmod {7}$

$2x-4\equiv 0\pmod {6}$

Completing the square for first equation gives:

$$(2x+1)^2\equiv 4\pmod {7}$$ $$y^2\equiv 4\pmod{7}\Rightarrow y_1=2,y_2=5$$ $$2x+1\equiv 2\pmod{7}\Rightarrow (2,7)=1|7\Rightarrow x=4$$ $$2x+1\equiv 5\pmod{7}\Rightarrow (2,7)=1|4\Rightarrow x=2$$

Second equation:

$$2x-4\equiv 0\pmod{6}\Rightarrow (2,6)=2|4\Rightarrow x=2,x=1$$

One particular solution of the system is $x=2$.

How to find general solution?

1

There are 1 best solutions below

4
On BEST ANSWER

You solved the quadratic congruence correctly, but the solutions of $2x-4\equiv 0\pmod{6}$ are $x\equiv \{2,5\}\pmod{6}$.

Divide everything by $\gcd(2,4,6)=2$: $$\iff x-2\equiv 0\pmod{3}\iff x\equiv 2\pmod{3}$$

$$\iff x\equiv \{2,5\}\pmod{6}$$

The solutions of $x^2+x+1\equiv 0\pmod{7}$ are $x\equiv \{2,4\}\pmod{7}$ (as you've found).

There are $4$ solutions of the whole system: $\begin{cases}x\equiv 2\pmod{7}\\x\equiv 2\pmod{6}\end{cases}$, $\begin{cases}x\equiv 4\pmod{7}\\x\equiv 2\pmod{6}\end{cases}$, $\begin{cases}x\equiv 2\pmod{7}\\x\equiv 5\pmod{6}\end{cases}$, $\begin{cases}x\equiv 4\pmod{7}\\x\equiv 5\pmod{6}\end{cases}$. Use Chinese Remainder Theorem to find the $4$ solutions of your system.