(a) Write where .
Since a divides both k and , a divides r. Similarly b divides r because it divides both k and .
So and . As is the least positive integer divisible by both a and b and , r cannot be positive. , i.e. .
(b) First show that if , then . Then note that for any positive integer k, and .
2(a) If , then . Hence since is divisible by 3 for all non-negative integers r.