# Solving the congruence $39x+14y \equiv 3\pmod{18}$

Solve the congruence $39x+14y \equiv 3\pmod{18}$

I have a question regarding the proof of this exercise.

We first note that the congruence is equivalent to

$$3x - 4y \equiv 3\pmod{ 18}$$

We also note that $3\mid y$ so $y=3v$ or $y\equiv 3v \pmod{18}$ for $v \in \{0,\ldots, 5\}$. Let's put it back in the congruence. We get:

$$3x - 12v \equiv 3 \pmod{ 18}$$

Is the same as solving

$$x - 4v \equiv 1 \pmod {6}\tag{*}$$

So far so good - And now for the interesting part:

The author claims that it is as solving

$$\color{red}{x \equiv 1 + 4v + 6u \pmod {18}}$$

Where $\color{red}{u \in \{0,1,2\}}$

It is unclear to me:

1. Why $u \in \{0,1,2\}$
2. How to get back from $(*)$, which is $\pmod{6}$ to the red equation which is $\pmod{18}$.

## 1 Answer

Your two questions are the same. From the starred equation, you have

$$x\equiv 1+4v \pmod{6},$$

so $x = 1+4v+6u$ for some integer $u$. But mod $18$ the multiples of $6$ are $0, 6$ and $12$, or $6\cdot 0$, $6\cdot 1$, and $6\cdot 2$, so the possibilites for $u$ mod $18$ are $0, 1$, and $2$.