2
$\begingroup$

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
    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}$?2012-09-23

3 Answers 3

1

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

  • 0
    @CodeKingPlusPlus First solve $ay \equiv 1$ (mod $n$) by Euclid's algorithm. Then $x = by$ (mod $n$\) is the solution of $ax \equiv b$ (mod $n$).2012-09-23
1

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$

  • 0
    @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.$2012-09-23
0

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)