Homework6 Math8 Yuyue Chen MW 6pm 1 a we assume d hcf 345 598 step1 598 1 345 253 so d 253 step2 345 1 253 92 so d 92 step3 253 2 92 69 so d 69 step4 92 69 23 so d 23 step5 69 3 23 0 so d 23 CLAIM hcf 345 598 23 Proof step 5 shows that 23 69 hence step4 shows that 23 92 hence step3 shoes that 23 253 hence step2 shows that 23 345 hence step1 shows that 23 598 Therefore 23 divides both 345 and 598 so d 23 As d 23 so d 23 So d 23 2 A train leaves Moscow for ST every 7 hours on the hour Show that on some days it is possible to catch this train at 9am Whenever there is a 9am train Ivan takes it to visit his aunt Olga How often does Olga see her nephew Discuss the corresponding problem involving the train to Vladivostock which leaves Moscow every 14 hours 3 a hcf 6n 8 4n 5 1 Prove let d hcf 6n 8 4n 5 since d is the highest common factor of 6n 8 and 4n 5 so d 6n 8 and d 4n 5 since there is a proposition suppose d a and d b for a b are positive integers then d ma nb for any m n Z so d 2 6n 8 3 4n 5 therefore d 1 so d 1 since 1 6n 8 and 1 4n 5 so d 1 So d 1 b prove Since a b so b na n Z Since b a so a mb m Z so b nmb So 1 nm Since n m Z so n m 1 when n m 1 a b When n m 1 a b so a b c prove we assume d hcf a b so d a and d b so we suppose a nd and b md n m Z so sa snd and tb tmd so snd tmd 1 so d sn tm 1 so d 1 therefore d 1 Since 1 can divide all integers so 1 d so 1 d so d 1 so hcf a b 1