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.

• Right here you could just use the defintion of the congrunce. Obviously $3$ divides $6k$, so the rest must be just $k$. In general, finding the inverse of $a$ modulo $n$, is equivalent with solving the linear congruence $ax\equiv 1 \pmod{n}$, which results in the linear Diophantine equation $ax-ny=1$. In this case, the inverse of $7$ modulo $3$ is $1$ because $7 \cdot 1 \equiv 1 \pmod{n}$ – Markus Oct 21 '18 at 0:12

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

• Why does $7k \equiv 2 \mod 3$ imply $k \equiv 2 \mod 3$? I think if I understand that piece then I may understand the problem. – Idle Math Guy Oct 20 '18 at 23:50
• @IdleMathGuy Because $7\cdot k \equiv 1\cdot k \pmod 3$. – gimusi Oct 20 '18 at 23:55
• any chance you could give a rough idea of how to calculate an inverse to a congruence in the form $ak \equiv b$? I believe it would help others out as well as myself. If it is too much trouble, I understand. Thanks for your help so far. – Idle Math Guy Oct 21 '18 at 16:30
• When we are dealing with $ax\equiv b \pmod m$ and $(a,m)=1$, that is $a$ and $m$ are relatively primes, by Bezout’s theorem we know that $r,s$ exist such that $$r\cdot a+ s\cdot m=1 \implies r\cdot a=1- s\cdot m$$ and therefore we define $r$ the inverse of $a \pmod m$ indeed $$r\cdot a\equiv 1 \pmod m$$ Then we can solve the original equation multiplying by $r$ that is $$ax\equiv b \pmod m \iff rax\equiv rb \pmod m \iff x\equiv rb \pmod m$$. The calculation can be carried out by Euclidean algorithm. – gimusi Oct 21 '18 at 17:19
• @IdleMathGuy Refer also to the related OP – gimusi Oct 21 '18 at 17:47

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

• So, I'm not finding the inverse of $7k \equiv 2 \mod 3$ what I'm really finding is the inverse of $7 \mod 3$? It is this step that I'm getting hung up on and I can't seem to find a book / example that explains it really well. :( – Idle Math Guy Oct 20 '18 at 23:47
• Think in terms of congruence classes: the set of classes mod. $3$ is the firld with $3$ elements, and you solve linear equation exactly as in any field: the solution of $7k=2$ is $k=7^{-1} 2=2$ since $7\equiv1$. – Bernard Oct 20 '18 at 23:56

$$\!\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\,\Rightarrow\ x\equiv 16\!\!\!\pmod{\!21}\end{align}

• Excellent Page - Congruence Sum and Product Rules! – Idle Math Guy Oct 21 '18 at 1:14