Monday, 20 January 2014

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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...