- #1

Math100

- 768

- 212

- Homework Statement
- Find the solutions of the following system of congruences:

## 5x+3y\equiv 1\pmod {7} ##

## 3x+2y\equiv 4\pmod {7} ##.

- Relevant Equations
- None.

Consider the following system of congruences:

## 5x+3y\equiv 1\pmod {7} ##

## 3x+2y\equiv 4\pmod {7} ##.

Then

\begin{align*}

&5x+3y\equiv 1\pmod {7}\implies 15x+9y\equiv 3\pmod {7}\\

&3x+2y\equiv 4\pmod {7}\implies 15x+10y\equiv 20\pmod {7}.\\

\end{align*}

Observe that ## [15x+10y\equiv 20\pmod {7}]-[15x+9y\equiv 3\pmod {7}] ## produces ## y\equiv 17\pmod {7} ##.

This means ## y\equiv 17\pmod {7}\implies y\equiv 3\pmod {7} ##.

Since ## 3y\equiv 9\pmod {7}\implies 3y\equiv 1-5x\pmod {7} ##,

it follows that ## 1-5x\equiv 9\equiv 2\pmod {7}\implies -5x\equiv 1\pmod {7} ##.

Thus

\begin{align*}

&-5x\equiv 1\pmod {7}\implies -15x\equiv 3\pmod {7}\implies -x\equiv 3\pmod {7}\\

&\implies x\equiv -3\pmod {7}\implies x\equiv 4\pmod {7}.\\

\end{align*}

Therefore, the solutions are ## x\equiv 4\pmod {7}; y\equiv 3\pmod {7} ##.

## 5x+3y\equiv 1\pmod {7} ##

## 3x+2y\equiv 4\pmod {7} ##.

Then

\begin{align*}

&5x+3y\equiv 1\pmod {7}\implies 15x+9y\equiv 3\pmod {7}\\

&3x+2y\equiv 4\pmod {7}\implies 15x+10y\equiv 20\pmod {7}.\\

\end{align*}

Observe that ## [15x+10y\equiv 20\pmod {7}]-[15x+9y\equiv 3\pmod {7}] ## produces ## y\equiv 17\pmod {7} ##.

This means ## y\equiv 17\pmod {7}\implies y\equiv 3\pmod {7} ##.

Since ## 3y\equiv 9\pmod {7}\implies 3y\equiv 1-5x\pmod {7} ##,

it follows that ## 1-5x\equiv 9\equiv 2\pmod {7}\implies -5x\equiv 1\pmod {7} ##.

Thus

\begin{align*}

&-5x\equiv 1\pmod {7}\implies -15x\equiv 3\pmod {7}\implies -x\equiv 3\pmod {7}\\

&\implies x\equiv -3\pmod {7}\implies x\equiv 4\pmod {7}.\\

\end{align*}

Therefore, the solutions are ## x\equiv 4\pmod {7}; y\equiv 3\pmod {7} ##.