# solving and manipulating linear congruences

I need to find a multiple of $5$ call it $5k$ with the following properties:

1. $5k \equiv 3$ mod $6$
2. $5k \equiv 2$ mod $7$

My first instinct is to start with the Chinese Remainder Theorem, but I do not know how to start. Could I get a few hints? Please explain the modular arithmetic manipulations needed to solve this problem.

-
The inverse of $5$ mod $6$ is $5$, so want $k\equiv 15\pmod{6}$. So want $k\equiv 3\pmod{6}$. The inverse of $5$ mod $7$ is $3$, so want $k\equiv 6\pmod{7}$. Now it is a standard CRT problem. But the numbers are so small that applying CRT machinery is overkill. From $k\equiv 6\pmod{7}$, the candidates are $k=6,13,20,27, 34$. Which one of these satisifies $k\equiv 3\pmod{6}$? –  André Nicolas Sep 23 '12 at 4:55

To make the computations easy to understand, we first consider general equations.

Let $a,b,n$ be integers. Suppose gcd$(a, n) = 1$. Consider the following equation.

$ax \equiv b$ (mod $n$)

Since gcd$(a, n) = 1$, we can solve $ay \equiv 1$ (mod $n$) by Euclid's algorithm. Then $x = by$ (mod $n$) is the solution.

Let $a,b,n,m$ be integers. Suppose gcd$(n, m) = 1$. Consider the following equatiuons.

$x \equiv a$ (mod $n$)

$x \equiv b$ (mod $m$)

Since gcd$(n, m) = 1$, we can find, by Euclid's algorithm, integers $k, l$ such that

$mk \equiv 1$ (mod $n$)

$nl \equiv 1$ (mod $m$)

Then $x = amk + bnl$ (mod $nm$) is the solution.

Now let's solve the given equations

$5k \equiv 3$ (mod $6$)

$5k \equiv 2$ (mod $7$)

We get(by Euclid's algorithm or just by testing)

$k \equiv 3$ (mod $6$)

$k \equiv 6$ (mod $7$)

Then we can apply the above method to find $k$. Since

$7 \equiv 1$ (mod $6$)

$-6 \equiv 1$ (mod $7$)

$k = 3\cdot7 -6\cdot6 = -15 \equiv 27$ (mod $42$)

-
Could you explain where you get $k \equiv 3\mod 6$ and $k \equiv 6\mod7$? I do not understand all the operations of congruences. Once you get those equations and the $7 \equiv 1\mod6$ and $-6 \equiv 1\mod7$ I see how you employ the Chinese remainder theorem. –  CodeKingPlusPlus Sep 23 '12 at 14:36
@CodeKingPlusPlus By Euclid's algorithm or by testing. I added some explanations in my answer. –  Makoto Kato Sep 23 '12 at 19:11
I see now how to get those congruences you found, but now I do not remember how I understood your reasoning for $k = -15$ and how $7 \equiv 1\mod6$ and $-6 \equiv 1\mod7$ justify this. –  CodeKingPlusPlus Sep 23 '12 at 20:15
@CodeKingPlusPlus Just apply the method to solve $x \equiv a$ (mod $n$), $x \equiv b$ (mod $m$). –  Makoto Kato Sep 23 '12 at 20:24
What is "the method"? –  CodeKingPlusPlus Sep 23 '12 at 20:47

Hint $\$ By Easy CRT, $\rm\:mod\ 42\!:\ 5k\, \equiv\, 2+7\,(1/7\ mod\ 6)\, \equiv\, 9\ \Rightarrow\ k \,\equiv\, 3\cdot 3/5 \,\equiv\, 3\cdot 45/5\,\equiv\, 27$

-
Is Easy CRT always a viable solution to these linear congruences? –  CodeKingPlusPlus Sep 23 '12 at 14:34
@Code Yes, Easy CRT is simply the general Chinese Remainder Theorem packaged in a form easy to apply. To apply CRT you have two choices, either first scale both equations by $1/5$ then apply CRT to solve for $\rm\,k\,$ (as in other answers); alternatively, as I did, apply CRT to solve for $\rm\,x = 5k,\:$ then, scale the solution by $1/5$ to get $\rm\,k.$ It doesn't matter what order you do the steps of CRT and scaling by $1/5$. –  Bill Dubuque Sep 23 '12 at 15:53
when you write $\frac{1}{5}$ do you mean 5 inverse?($5^{-1}$). And to calculate $5$ inverse do you perform the following: $gcd(a, b) = 1 = a\cdot r + b\cdot s$ –  CodeKingPlusPlus Sep 23 '12 at 22:32
@Code $\$ If $\rm\:(a,m) = 1\:$ then $\rm\:1/ a = a^{-1}\:$ exists mod m, so $\rm\:ax \equiv b\:$ has the unique solution $\rm\: x \equiv a^{-1} b = b/a.\:$ You can compute inverses using the extended Euclidean algorithm, but for small numbers various tricks often are quicker, e.g. as above $\rm\,mod\ 42\!:\ 3\equiv 45\:\Rightarrow\:3/5\equiv 45/5 \equiv 9,\:$ hence $\rm\:k \equiv 9/5 \equiv 3\cdot 3/5\equiv 3\cdot 9 \equiv 27.$ –  Bill Dubuque Sep 23 '12 at 22:35