Problem Set 3 are opposite each other. Let P(n)be the proposition that opposite cards are the same color Base case. In the initial configuration, hearts are opposite diamonds and clubs are opposite spades. Therefore, all opposite cards are the same color Inductive step. Suppose that all opposite cards are the same color. Consider an arbitrary configuration of the deck C1C2C3. C52 A perfect shuffle leaves the deck in one of the following orders C1C27C2C28C3C29··C25C51C26C52 C27C1C28C2C29C3 51C25C52C26 In both cases, exactly the same cards remain opposites: Ci and Cs2, C2 and csl, etc. So, in particular, opposite cards are still the same color By induction, opposite cards are always the same color. Therefore, the hearts, clubs diamonds, spades configuration is unreachable since there all opposite cards are different colors Problem 4. Prove the following basic facts about greatest common divisors (a)gcd(ka, kb)=k ged(a, b) Solution. The smallest positive value of s·(ka)+t·(kb)=k·(s·a+t·b) over alls, t e Z is k times the smallest positive value of +t·b over all s, t E Z. The first quantity is gcd(ka, kb) and the second is gcd(a, b). There- fore, gcd(ka, kb)= k gcd(a, b) (b) gcd(a, b)=gcd(a+kb, b)for allkE Z Solution. We show that every linear combination of a and b is a linear combination of a+ kb and b and vice-versa ·Ifx=s·a+t· b then a=8·(a+kb)+t"· b where s'= s and t=t-sk ·Ifx=s(a+kb)+t.b, then x=s·a+t· b where s=s'andt=t'+sk hus, in particular, the smallest positive linear combinations are equal, so gcd(a, b) cd(a+ kb, b)4 Problem Set 3 are opposite each other. Let P(n) be the proposition that opposite cards are the same color. Base case. In the initial configuration, hearts are opposite diamonds and clubs are opposite spades. Therefore, all opposite cards are the same color. Inductive step. Suppose that all opposite cards are the same color. Consider an arbitrary configuration of the deck: c1c2c3 . . . c52 A perfect shuffle leaves the deck in one of the following orders: c1c27c2c28c3c29 . . . c25c51c26c52 c27c1c28c2c29c3 . . . c51c25c52c26 In both cases, exactly the same cards remain opposites: c1 and c52, c2 and c51, etc. So, in particular, opposite cards are still the same color. By induction, opposite cards are always the same color. Therefore, the hearts, clubs, diamonds, spades configuration is unreachable since there all opposite cards are different colors. Problem 4. Prove the following basic facts about greatest common divisors: (a) gcd(ka, kb) = k · gcd(a, b) for all k > 0. Solution. The smallest positive value of s · (ka) + t · (kb) = k a · (s · · + t b) over all s, t ∈ Z is k times the smallest positive value of s a · · + t b over all s, t ∈ Z. The first quantity is gcd(ka, kb) and the second is gcd(a, b). There￾fore, gcd(ka, kb) = k gcd(a, b). (b) gcd(a, b) = gcd(a + kb, b) for all k ∈ Z. Solution. We show that every linear combination of a and b is a linear combination of a + kb and b and vice­versa. • If x = s a + t b, then x = s� · (a + kb) + t � b where s� = s and t � = t − s� · · · k. • If x = s� · (a + kb) + t � b, then x = s a + t b where s = s� and t = t � + s� · · · k. Thus, in particular, the smallest positive linear combinations are equal, so gcd(a, b) = gcd(a + kb, b)