How to solve the below system of congruence?

Question

I have tried to solve the below congruence system but i don't succeed , such that i have wrote $3x+5y=6$ as $5y =-3x²\mod (6)$ then i can't write this equation as : $y= z \bmod 6$ in order to solve this system , Then my question here is

Question How to solve this system : $$ \begin{cases} 3x+5y=6 \\ y \equiv x² \pmod{5} \end{cases} $$

Answer 1

We have that

• $3x+5y=6 \implies 3x\equiv 1 \mod 5\implies x\equiv 2 \mod 5$
• $y \equiv x² \pmod{5}\implies y \equiv 4 \pmod{5}$

then one solution is given by

• $3(2+5k)+5(4+5j)=6\implies 15k+25 j=-20\implies3k+5j=-4\\\implies k=2\quad j=-2$

and therefore

• $x=12$
• $y=-6$

Note that since $gdc(3,5)=1$, by Bezout's identity, the equation $3k+5j=-4$ has infinitely many solutions, notably $\forall m\in \mathbb{Z}$

$$3(2)+5(-2)=-4\implies 3(2+5m)+5(-2-3m)=-4 $$

thus all the pairs

• $k=2+5m$
• $j=-2-3m$

leads to different solutions

• $x=12+25m$
• $y=-6-15m$

Answer 2

I would solve first the linear diophantine equation $\;3x+5y=6$. The method is standard:

• First step: solve $\;3x+5y=1$.

Start from a Bézout's relation between $3$ and $5$: $$ 2\times 3-1\cdot 5=1. $$ All other solutions have the form $$x=2+5k,\quad y=-1-3k\qquad(k\in\mathbf Z).$$

• Second step: deduce the solutions of $\;3x+5y=6$.

A basic solution is obtained multiplying the basic solution of the previous equation by $6$: $\; x_0=12,\;y_0=-6$, and the general solution, as in the previous case, is $$x=12+5k,\quad y=-6-3k\qquad(k\in\mathbf Z).$$

• Quadratic congruence: as $x \equiv 2\mod 5$, $\;y\equiv x^2\equiv -1\mod 5$. In terms of $k$, this means $$y=-6-3k\equiv-1-3k\equiv -1\mod 5 \iff 3k\equiv 0\iff k\equiv 0\mod 5,$$ since $3$ is a unit mod. $5$. Thus $k=5\ell\enspace (\ell\in\mathbf Z)$, and finally $$x=12+25\ell,\quad y=-6-15\ell\qquad(\ell\in\mathbf Z). $$

Answer 3

$3x + 5y = 6$. As $\gcd(3,5) = 1$, by Bezouts Theorem there are an infinite number of solutions.

$3x = 6 - 5y$

$x = 2 - \frac {5y}3$. So $3|y$. Let $y = 3k$ then

$x = 2 - 5k$. So all solutions are $\{(2 - 5k, 3k)\}$

$y \equiv x^2 \mod 5$

$3k \equiv (2-5k)^2 \mod 5$

$3k \equiv 4 \mod 5$

$2*3k \equiv 2*4 \mod 5$

$k \equiv 3 \mod 5$.

So $k = 2 + 5m$ for some $m$ and $x = 2- 5(2-5m) = -8 + 25m$ and $y = 3(2+5m) = 6 + 15m$.

So all possible solutions are $\{(-8 + 25m, 6+15m)\}$.