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.

  • 1
    $\begingroup$ 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}$? $\endgroup$ – 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$)

  • $\begingroup$ 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. $\endgroup$ – CodeKingPlusPlus Sep 23 '12 at 14:36
  • $\begingroup$ @CodeKingPlusPlus By Euclid's algorithm or by testing. I added some explanations in my answer. $\endgroup$ – Makoto Kato Sep 23 '12 at 19:11
  • $\begingroup$ 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. $\endgroup$ – CodeKingPlusPlus Sep 23 '12 at 20:15
  • $\begingroup$ @CodeKingPlusPlus Just apply the method to solve $x \equiv a$ (mod $n$), $x \equiv b$ (mod $m$). $\endgroup$ – Makoto Kato Sep 23 '12 at 20:24
  • $\begingroup$ What is "the method"? $\endgroup$ – 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$

  • $\begingroup$ Is Easy CRT always a viable solution to these linear congruences? $\endgroup$ – CodeKingPlusPlus Sep 23 '12 at 14:34
  • $\begingroup$ @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$. $\endgroup$ – Bill Dubuque Sep 23 '12 at 15:53
  • $\begingroup$ 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$ $\endgroup$ – CodeKingPlusPlus Sep 23 '12 at 22:32
  • $\begingroup$ @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.$ $\endgroup$ – Bill Dubuque Sep 23 '12 at 22:35

Let x = 5k. Solve x = 3(mod 6) and x = 2(mod 7) simultaneously. You get x = 9(mod 42). Therefore

5k = 9(mod 42)

5k = 135(mod 42)

k = 27(mod 42)


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.