363X is congruent to 345(mod624) solve for X

C

corbell777

New member
Joined
Feb 21, 2012
Messages
9
I have been stuck on this one problem for like two weeks! I would truly like some help! 363 is congruent to 345(mod624) becomes 121x is congruent to 115(mod208) 208=121+87 121=87+34 87=2(34)+19 34=19+15 19=15+4 15=4(4)-1 1=4(4)-15 1=4(19)-5(15) 1=9(19)-5(34) 1=9(87)-23(34) 1=32(87)-23(121) 1=32(208)-55(121) 115=3680(208)-6325(121) So x=6325. But the answer in the book is x=123. So how do I get from 6325 to 123? I thought about taking out the multiples of 208 from 6325. But that gives an answer of 85. Where did I go wrong?
 
corbell777 said:
I have been stuck on this one problem for like two weeks! I would truly like some help! 363 is congruent to 345(mod624) becomes 121x is congruent to 115(mod208) 208=121+87 121=87+34 87=2(34)+19 34=19+15 19=15+4 15=4(4)-1 1=4(4)-15 1=4(19)-5(15) 1=9(19)-5(34) 1=9(87)-23(34) 1=32(87)-23(121) 1=32(208)-55(121) 115=3680(208)-6325(121) So x=6325. But the answer in the book is x=123. So how do I get from 6325 to 123? I thought about taking out the multiples of 208 from 6325. But that gives an answer of 85. Where did I go wrong?
Click to expand...

363 is congruent to 345(mod624)???????????????

If a>1 and b<c\(\displaystyle \le\)a, then it is never the case that
b is congruent to c (mod a)
As a correlory, it is also true, under the same circumstances, that it is never the case that
c is congruent to d (mod a)

Please post the complete problem.
 
Best Ellen, please explain in more detail how you arrived at the equation x=208t+123. That's the part I'm having trouble getting to. Thanks! Ishuda, I apologize I typed the problem correctly in the heading but incorrectly in the body. The correct equation is 363x is congruent to 345(mod624), solve for x.
 
corbell777 said:
Best Ellen, please explain in more detail how you arrived at the equation x=208t+123. That's the part I'm having trouble getting to. Thanks! Ishuda, I apologize I typed the problem correctly in the heading but incorrectly in the body. The correct equation is 363x is congruent to 345(mod624), solve for x.
Click to expand...
I can't seem to post the answer I have so I'll shorten it. Basically find the greatest common divisor of 121 and 208. Almost by inspection it is one. Use the extended Euclid algorithm
http://en.wikipedia.org/wiki/Extended_Euclidean_algorithm
to get a and b so that
208 a + 121 b = 1
Multiple by 115
115 * b = 123 mod(208)
so
x = 123 mod(208)
 
You must log in or register to reply here.
Top