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