Number Theory : Solve the system of congruence $28x+17y\equiv 18 \pmod{41}$ and $31x+11y\equiv 35\pmod{41}$

Question

Number Theory : Solve the system of congruence

(1) $28x+17y\equiv 18 \pmod{41}$

(2) $31x+11y\equiv 35\pmod{41}$

Attempt :

we know that equation (1) and (2) are in the same$\pmod{41}$. so we can use Modular arithmetic

lets multiply the first equation (1) by $31$ and the second equation(2) by $28$.

(1) $31\cdot(28x+17y)\equiv 31\cdot18 \pmod{41}$

(1) $868x+527y\equiv 558\pmod{41}$

(2) $28\cdot(31x+11y)\equiv 28\cdot35\pmod{41}$

(2) $868x+308y\equiv 980\pmod{41}$

So finally we can subtract equation (1) from (2) we get:

$219y\equiv -422\pmod{41}$

lets check the $\gcd(219,41)$ by Euclidian algorithm :

$219 = 41\cdot 5 + 14$

$41= 14\cdot 2 + 13$

$14= 13\cdot 1 + 1$

$\gcd(219,41)=1$

Hence, because the $\gcd$ is equal to $1$ we can find the Inverse and multiply the equation by the Inverse to find $y$.

$219y\equiv 1\pmod{41}$

$219a = 1+41k$ , the $41k$ must end with the digit of $8$ for $1+$digit $8$ will be $9$ so $k$ must be multiply of number with end digit of $8$.

I don't know how to continue from here .

Answer 1

Starting from your result of

$$219y \equiv -422 \pmod{41} \tag{1}\label{eq1A}$$

the first thing I recommend doing is reducing the coefficients to smaller values since these are generally easier to deal with, plus sometimes you may be able to find simplifications you can use, such as common factors relatively prime to $41$ so they can be "removed" using their multiplicative inverses. Doing this, and using that $\gcd(2, 41) = \gcd(7, 41) = 1$, gives

$$\begin{equation}\begin{aligned} 14y & \equiv -12 \pmod{41} \\ 7y & \equiv -6 \pmod{41} \\ 7y & \equiv 35 \pmod{41} \\ y & \equiv 5 \pmod{41} \end{aligned}\end{equation}\tag{2}\label{eq2A}$$

Using this result in your first congruence equation, along with $\gcd(28, 41) = 1$, gives

$$\begin{equation}\begin{aligned} 28x + 85 & \equiv 18 \pmod{41} \\ 28x + 3 & \equiv 18 \pmod{41} \\ 28x & \equiv 15 \pmod{41} \\ 28x & \equiv 56 \pmod{41} \\ x & \equiv 2 \pmod{41} \end{aligned}\end{equation}\tag{3}\label{eq3A}$$

In general, though, if you can't fairly easily simplify the results as I did above, you can instead use something like either the constructive proof or direct proof methods described in Wikipedia's "Chinese remainder theorem" article.

Answer 2

Alternatively, use linear algebra. The system is $$ \begin{pmatrix} 28 & 17 \\ 31 & 11 \end{pmatrix} \begin{pmatrix} x \\ y\end{pmatrix} = \begin{pmatrix} 18 \\ 35 \end{pmatrix} $$ The inverse of the matrix is $$ -\frac{1}{219}\begin{pmatrix} \hphantom-11 & -17 \\ -31 & \hphantom-28 \end{pmatrix} $$ It remains to find the inverse of $219$ mod $41$, which is $3$ by the extended Euclidean algorithm.

Answer 3

$$-13x+17y\equiv 18 \pmod{41}\tag1$$ $$-10x+11y\equiv -6 \pmod{41}\tag2$$

$(1)\times 10-(2)\times 13$ $$ 27y\equiv 12 \pmod{41} \implies y \equiv \frac{12}{27} \equiv \frac{4}{9} \equiv \frac{20}{45} \equiv \frac{20}{4} \equiv 5 \pmod{41} $$

$$ x \equiv \frac{11y+6}{10}\equiv \frac{61}{10} \equiv \frac{20}{10} \equiv 2 \pmod{41}.\blacksquare $$

Answer 4

You used the Euclidean algorithm to find $\gcd(219,41)=1$;

you could then use the extended Euclidean algorithm to find that

$1=14\cdot3-1=14-(41-14\cdot2)=3\cdot14-41=3(219-41\cdot5)-41=3\cdot219-16\cdot41$,

from which we know that $3\cdot219\equiv1\bmod41$,

so $219y\equiv-422\equiv29$ means $y\equiv3\cdot219y\equiv3\cdot29=87\equiv5\bmod41$.

Can you take it from here?

Answer 5

Let $p \in \Bbb N$ be a prime number.

Recall the following two facts from elementary number theory:

Let $p$ be a prime integer.

For all $u,v,w \in \Bbb Z$ satisfying $u\not\equiv 0 \pmod{p}$, $v\not\equiv 0 \pmod{p}$ and $w\not\equiv 0 \pmod{p}$,

$\tag 1 u \equiv v \pmod{p} \; \text{ iff } \; uw \equiv vw \pmod{p}$

If $a \in \Bbb N$ and $a\not\equiv 0 \pmod{p}$ and $a\not\equiv 1 \pmod{p}$ then there exist $q \in \Bbb Z$ and $r \in \Bbb N$ such that

$\tag 2 aq \equiv r \pmod{p} \; \text{ and } \; 1 \le r \lt p \; \text{ and } \; r \lt a$

The above theory is the counterpart to algorithms that compute the inverse
of non-zero elements in $(\mathbb{Z}/p\mathbb{Z})^\times$.

---

We are now ready to continue where the OP left off.

Since

$\quad 219y\equiv -422\pmod{41} \; \text{ iff } \; 14y\equiv 29\pmod{41}$

we are motivated to 'divide' (with a small negative residue) $41$ by $14$ and write ,

$\quad 41 = 14 \cdot 3 - 1$

and set $q = 3$.

Next,

$\quad 14y\equiv 29\pmod{41} \; \text{ iff } \; (3 \cdot 14) y\equiv 3 \cdot 29\pmod{41} \; \text{ iff } \; 1y\equiv 5 \pmod{41}$

and the OP's problem is solved in one step.

By being flexible with the sign of the residue, this is a one step solution. If you can only perform Euclidean division, this is what happens:

Presented with

$\quad 14y\equiv 29\pmod{41}$

we divide $41$ by $14$ and write ,

$\quad 41 = 14 \cdot 2 + 13$

and set $q = -2$.

Next,

$\quad 14y\equiv 29\pmod{41} \; \text{ iff } \; (-2 \cdot 14) y\equiv (-2 \cdot 29)\pmod{41} \; \text{ iff } \; 13 y\equiv 24 \pmod{41}$

and write

$\quad 41 = 13 \cdot 3 + 2$

and set $q = -3$

Next,

$\quad 13y\equiv 24\pmod{41} \; \text{ iff } \; (-3 \cdot 13) y\equiv (-3 \cdot 24)\pmod{41} \; \text{ iff } \; 2 y\equiv 10 \pmod{41}$

and write

$\quad 41 = 2 \cdot 20 + 1$

and set $q = -20$

Next,

$\quad 2 y\equiv 10 \pmod{41} \; \text{ iff } \; (-20 \cdot 2) y\equiv (-20 \cdot 10)\pmod{41} \; \text{ iff } \; 1y\equiv 5 \pmod{41}$

and the OP's problem is solved in $3$ steps.