2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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}$ $\endgroup$ – Markus Oct 21 '18 at 0:12
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Idle Math Guy Oct 20 '18 at 23:50
  • 1
    $\begingroup$ @IdleMathGuy Because $7\cdot k \equiv 1\cdot k \pmod 3$. $\endgroup$ – gimusi Oct 20 '18 at 23:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Idle Math Guy Oct 21 '18 at 16:30
  • 1
    $\begingroup$ 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. $\endgroup$ – gimusi Oct 21 '18 at 17:19
  • 1
    $\begingroup$ @IdleMathGuy Refer also to the related OP $\endgroup$ – gimusi Oct 21 '18 at 17:47
3
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. :( $\endgroup$ – Idle Math Guy Oct 20 '18 at 23:47
  • $\begingroup$ 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$. $\endgroup$ – Bernard Oct 20 '18 at 23:56
3
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.