Saturday, August 4, 2018

elementary number theory - Chinese Remainder Theorem/Simultaneous congruences



Find an integer N , 0 ≤ N < 105 such that




N ≡ 2 mod 3,



N ≡ 1 mod 5, and



N ≡ 4 mod 7.



What I have done:



So I have been able to start by splitting up the summation of $x$ into 3 sections:




$ x = 5*7 + 3*7 + 3*5 $



with the first multiplication corresponding with the mod 3 equation, the second multiplication corresponding with the mod 5 equation and the third multiplication corresponding with the mod 7 equation.



Therefore:



$x = 35 + 21 +15$



However, I know that this isn't complete. But I am not exactly sure on how to proceed.




Any help?


Answer



$N \equiv 2 \mod 3$ so $N = 2 + 3a$.



$N \equiv 1 \mod 5$ so $N =1 + 5b$



So $2+3a = 1 + 5b$ so $5b - 3a = 1$. One solution is $b = 2$ and $a = 3$



So $N \equiv 2 + 3*3 = 1 + 2*5 = 11 \mod 3*5$.




So $N = 11 + 15c$.



$N \equiv 4 \mod 7$ so $N = 4 + 7d$.



So $11 + 15c = 4 + 7d$ so $15c - 7d = -7$. $c =0$ and $d = 1$ is a solution.



So $N \equiv 11 = 4+7 \equiv 11 \mod 3*5*7 = 105$.



And, indeed, $11 \equiv 2 \mod 3$ and $11 \equiv 1 \mod 5$ and $11\equiv 4 \mod 7$.







Trying to follow your partition reasoning.



$5*7 = 35 \equiv 2 \mod 3$ so that satisfies.



$3*7 = 21 \equiv 1 \mod 5$ so that satisifies.



$3*5 = 15 \equiv 1 \not \equiv 4 \mod 7$ so that does not satisfy.




But $4*3*5 \equiv 4 \mod 7$ so that does.



So $5*7 + 3*7 + 60 = 116$ solves all three. But $116 > 105$. But any $k \equiv 116 \mod 105$ so do so $116 - 105 = 11$ will do.



.... or ... when we hae $3*5 \equiv 1 \mod 7$ and we could have figured $4 \equiv -3 \mod 7$ so $-3*3*5 \equiv 4 \mod 7$.



So $N = 5*7 + 3*7 - 3*3*5 = 11$. (by taking a negative we know we won't get a number too large).



Actually, I had never done the "partitioning" before.




It works well. I like it.


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