Solve the Linear Congruence Equations.

Question

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 1

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}$$

Answer 2

Hint:

You have to find the inverse of $7$ mod. $3$. In theory, this will be deduced from a Bézout's relation between $7$ and $3$. However, here, $7\equiv 1\mod 3$, so the modular equation is, really, $$1\cdot k=k\equiv 2\mod 3.$$

Answer 3

$\!\bmod 3\!:\ \color{#0a0}7\equiv\color{#c00}1\ $ so $\ 2\equiv \color{#0a0}7k\equiv \color{#c00}1k\equiv k.\ $ Generally mod arithmetic is simplest if you reduce all arguments of sums and products $\bmod 3\,$ (valid by the Congruence Sum & Product Rules)

Remark $\ $ Below is an alternative method using the mod Distributive Law

\begin{align} ab\,\bmod\, ac\, &=\, a\,[\,b\bmod c\,]\\[.5em] \Rightarrow\ \ x\!-\!2\,\bmod\, 21\, &=\, \underbrace{7\left[\dfrac{\color{#0a0}{x\!-\!2}}{\color{#0a0}7}\bmod 3\right] = 7\left[\dfrac{\color{#c00}1\!+\!\color{#c00}1}{\color{#c00}1}\bmod 3\right]}_{\ \ \Large \color{#0a0}{x,\,\ 7,\ {-}2}\ \ \equiv\ \ \color{#c00}1\ \pmod{3}\!\!\!\!\!\!\!}\! = 7[2]\,\Rightarrow\ x\equiv 16\!\!\!\pmod{\!21}\end{align}