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
    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.2012-09-23
  • 0
    @CodeKingPlusPlus By Euclid's algorithm or by testing. I added some explanations in my answer.2012-09-23
  • 0
    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.2012-09-23
  • 0
    @CodeKingPlusPlus Just apply the method to solve $x \equiv a$ (mod $n$), $x \equiv b$ (mod $m$).2012-09-23
  • 0
    What is "the method"?2012-09-23
  • 0
    @CodeKingPlusPlus I wrote the method in my answer from the line 5 to the line 11.2012-09-23
  • 0
    I am trying to really understand this. I see in the first part that $ax \equiv b\mod n$ then if we can write $ay \equiv 1\mod n$ then our solution is $x = by$. However, I do not see how this fact plays a role in solving our problem. It appears to me that our coefficient $a$ is $5$ and we never set up an equation of the form $5y \equiv 1\mod n$.2012-09-23
  • 0
    @CodeKingPlusPlus Do you understand how to solve $ax \equiv b$ (mod $n$)?2012-09-23
  • 0
    I think I see it now. If you plugin $amk$ for $x$ into $x \equiv a\mod n$ then you satisfy the congruence. Where $mk \equiv 1\mod n$2012-09-23
  • 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
    Is Easy CRT always a viable solution to these linear congruences?2012-09-23
  • 0
    @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$.2012-09-23
  • 0
    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$2012-09-23
  • 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)