Submit solutions to the following problems. Write in complete sentences, with full explana- tions. You will be graded on both content and form; clear communication is important! 1. Let a,b,c,d Z. Prove that if a | b and | d then ac | bd. 2. (a) Prove that for any positive integers a and b, if a | b then a 0 and write b = ag + r as in the division algorithm. Prove that a|bif and only if r = 0. 4. Apply the extended Euclidean algorithm to compute the greatest common divisor of 270 and 312, and find integers = and y such that 270z + 312y = (270, 312). 5. For each of n = 1,2, 3,4, find the GCD (6n + 8,4n +5). (Just give the answers; you don't need to show any work.) Then, make a conjecture of the form \"for all positive integers n, (6n + 8,4n + 5) is equal to [blank],\" and then apply a theorem from class to prove your conjecture. 6. Let @ and b be arbitrary integers. Recall that in class we proved that if there exists z,y Z with ax + by = 1, then (a,b) = 1. (a) Show that the statement \"if there exists x, y Z with ax+by = 2, then (a,b) = 2" is false by giving an example of integers a, b, z, and y with az + by = 2, but where (a, b) # 2. (b) If there exists integers z and y with az + by = 2, what are the possibilities for what (a,b) could be? That is, formulate a statement of the form \"if there exists z,y Z with az + by = 2, then (a,b) must be equal to one of the following numbers: [blank]\" and prove it. () Prove that it is not possible to find two integers a and b with a + b = 100 and (a,b) = 3. 7. Let a,b,c Z, all of which are nonzero. (a) Assume that a and b are relatively prime (that is, {a,b) = 1) and that a | and (b ) b|c. Prove that ab | c. Conversely, assume that a and b are not relatively prime. Show that the conclusion to the statement in the previous part is false by finding an integer such that a|cand b| e but abte. (I am not just looking for a single counterexample here! You need to prove the universally quantified statement: For all a,b Z, if (a,b) > 1, then there exists a c Z with a | c and b | but ab{ c. That said, a useful way to get started might be to write down some examples, and then try to build a general proof from those examples.) Homework 5 Math 310 8. Let a, b, and be integers, not all gero. The greatest common divisor of a, b, and is defined to be the largest element of D(a) N D(b) M D(c) and is denoted by (a, b, c). (Recall that for an integer n, D(n) = {k Z | k|n} is the set of divisors of n.) (a) Let a,b,c Z, not all zero. Prove that (a,b, c) = ((a,b),c). (For clarity: ((a,b), ) is the GCD of the two integers (g, b) and . This means that we don't really need a special definition for the GCD of three integers because it can be calculated only using the standard GCD function! Hint: First show that D(a) N D(b) = D((a,b)).) (b) Prove or disprove: If (a,b) > 1, (a,) > 1, and (b,c) > 1, then (a,b,c) > 1