elementary number theory - Solve the Linear Congruence Equations.

I get so frustrated with modular arithmetic. It seems like every example I look at leaves steps out. I am trying to solve this problem:

Solve the linear congruence equations for x:

$x \equiv 2 \mod 7$

$x \equiv 1 \mod 3$

Ok, so I start

We know that 1st equation has a solution when $7 \mid (x-2)$. So there exists an integer k where $x = 2 + 7k$.

Ok, great. So I substitute into the 2nd equation:

$
2+7k \equiv 1 \mod 3 \implies \\
7k \equiv -1 \mod 3 \implies \\
7k \equiv 2 \mod 3
$

Now I need to find an inverse of this last congruence. How do I do that? I know there is one solution because gcd(7,3) = 1. This is the step I'm having problems on. If I can get the solution to $7k \equiv 2 \mod 3$ into the form $k = a + bj$ where $a,b \in \mathbb{N}$ then I know how to solve it.

Thank you.

Answer

Firstly note that by CRT we know that a solution exists $\pmod{3\cdot 7}$

To find the solution, you was right we have $x = 2 + 7k$ and then we find $7k \equiv 2 \mod 3$ that is

$$7k \equiv 2 \mod 3 \iff k \equiv 2 \mod 3 \implies k=2+3h$$

and therefore

$$x=2+7(2+3h)=16+21h \iff x\equiv16 \pmod{3\cdot 7}$$