Sunday, November 27, 2016

elementary number theory - Solving simultaneous linear congruences




(a) $x≡5\pmod 7\;\;,\; x≡7\pmod{11}\;\;,\;\;x≡3\pmod{13}$



(b) $x≡3\pmod{10}\;\;,\;\; x≡8\pmod{15}\;\;,\;\;x≡5\pmod{84}$






for (a) I have a rough idea how to do it, its like:



$n_1=7,n_2=11,n_3=13$ then $n=7·11·13=1001$




${1001\over7}·k_1≡1mod(7)$



${1001\over11}·k_2≡1mod(11)$



${1001\over13}·k_3≡1mod(13)$



Hence, $k_1=[5], k_2=[4], k_3=[12]$



$x_0=(11·13)·5·5+(7·13)·4·7+(7·11)·(-1)·3=287$




the solution set is $x=x_0+k_n, k\leftarrow\mathbb{Z}, x=887+k(1001)$



Im not sure if im correct, but i just follow the standard procedure



(b) for this one, what should I do the the $n$'s are not coprime, or prime???



Thank you!!


Answer



You've got the idea...




Apply prime factorization to each of the moduli $n$, omit common factors, proceed in much the way you did for (a), and transform each statement in the system into equivalent congruences for the prime powers: (i.e. to a prime residue system). E.g. $$x \equiv 3 \pmod{10} \iff x \equiv 3 \pmod 2 \;\text{and}\; x \equiv 3 \pmod 5\,.$$



And of course, you'll then want to use the Chinese Remainder Theorem and/or the extended CRT.


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...