I need to find a multiple of $5$ call it $5k$ with the following properties:
- $5k \equiv 3 $ mod $6$
- $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.
Answer
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$)
No comments:
Post a Comment