Tuesday, October 4, 2016

elementary number theory - 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.


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

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...