CTK Exchange Front Page Movie shortcuts Personal info Awards Reciprocal links Privacy Policy Cut The Knot! MSET99 Talk Games & Puzzles Arithmetic/Algebra Geometry Probability Eye Opener Analog Gadgets Inventor's Paradox Did you know?... Proofs Math as Language Things Impossible My Logo Math Poll Other Math sit's Guest book News sit's
|Store|

CTK Exchange

 Subject: "Chinese Remainder Theorem" Previous Topic | Next Topic
 Conferences The CTK Exchange College math Topic #74 Printer-friendly copy     Email this topic to a friend Reading Topic #74
gh@over-yonder.net (Guest)
guest
Mar-12-01, 01:42 PM (EST)

"Chinese Remainder Theorem"

 I read the proof, but I am lost in the solution to problem one.Problem 1, on --Solvep1: x = 2 (mod 3)p2: x = 3 (mod 5)p3: x = 2 (mod 7)From p1, x = 3t 2, for some integer t. Substituting this into p2 gives 3t = 1. --I see thatx = 3t 2 = 5s 3, which gives,3t - 5s = 1, but how does that yield 3t = 1 ?Thank you for helping me to understand this.(Note that I am only in high school, which may contribute to the lack of knowledge which has prevented me from understanding this; and for that I apologize.)dan

alexb
Charter Member
672 posts
Mar-13-01, 00:12 AM (EST)

1. "RE: Chinese Remainder Theorem"
In response to message #0

 >>p1: x = 2 (mod 3) >p2: x = 3 (mod 5) >p3: x = 2 (mod 7) >>>From p1, x = 3t > 2, for some integer >t. Substituting this into p2 >gives 3t = 1. >-- >>I see that >x = 3t + 2 = >5s + 3, which >gives, >3t - 5s = 1, but >how does that yield >3t = 1 ? >If x = 3t + 2 and x = 3 (mod 5) then3t + 2 = 3 (mod 5), or3t = 1 (mod 5).This is what substitution is about. Or you can refer to the transitive law: if A = B and B = C, then A = C.It matters not whether the equality here is the "real" equality or equality modulo some number.You may also continue in your way. Except that you should note that what is asserted is that 3t = 1 (mod 5)(Now that I had a look at the page, it really says "3t = 1", which is of course not true. I am going to fix this. You have my appreciation for detecting the mistype.)3t - 5s = 1 is true in general, but modulo 5 we get3t = 1 (mod 5)since obviously 5s = 0 (mod 5).