CTK Exchange
Front Page
Movie shortcuts
Personal info
Awards
Reciprocal links
Privacy Policy

Interactive Activities

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

Manifesto: what CTK is about |Store| Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot

CTK Exchange

Subject: "Chinese Remainder Theorem"     Previous Topic | Next Topic
Printer-friendly copy     Email this topic to a friend    
Conferences The CTK Exchange College math Topic #74
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 <https://www.cut-the-knot.com/blue/chinese.shtml>

--
Solve

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 ?


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


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top
alexb
Charter Member
672 posts
Mar-13-01, 00:12 AM (EST)
Click to EMail alexb Click to send private message to alexb Click to view user profileClick to add this user to your buddy list  
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) then
3t + 2 = 3 (mod 5), or
3t = 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 get

3t = 1 (mod 5)

since obviously 5s = 0 (mod 5).


  Alert | IP Printer-friendly page | Edit | Reply | Reply With Quote | Top

Conferences | Forums | Topics | Previous Topic | Next Topic

You may be curious to visit the old CTK Exchange archive.

|Front page| |Contents|

Copyright © 1996-2018 Alexander Bogomolny

[an error occurred while processing this directive]
 Advertise

New Books
Second editions of J. Conway's classic On Numbers And Games and the inimitable Winning Ways for Your Mathematical Plays