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:
- Why $u \in \{0,1,2\}$
- How to get back from $(*)$, which is $\pmod{6}$ to the red equation which is $\pmod{18}$.
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$.