## Math 310: Problem set 6

Instructions: This problem set is due Thursday, October 5, 2006. Your goal is not only to give correct answers but to communicate your ideas well. Make sure you use good English.
1. Read 5ABC.
2. Optional: Read the New Yorker article on events concerning Perelman's sketched solution of the Poincare Conjecture. One of the authors is Sylvia Nasar who wrote the book about John Nash that the movie of the same name, "A Beautiful Mind", is based on. (Also of interest is the reply of Yau's lawyer.)
3. Let b and c be positive integers. If gcd(b,c)=8, what are the possible values of gcd(b3,c4)? Give examples of specific values of b and c that show each value of gcd(b3,c4) that you claim is possible really is possible, and justify why those are the only possible values of gcd(b3,c4).
• Write b = 8x and c = 8y. Thus b3 = 83x3 and c4 = 84y4, We know gcd(b3,c4) = 83gcd(x3,8y4), by Problem 6 on Homework 4 (and by the solution to that problem). We also know gcd(x,y) = 1 (by Problem 4 on Homework 4), so x and y have no common prime factor. Thus the only possible common prime factor for x3 and 8y4 is 2. Thus gcd(x3,8y4) = 1 if x is odd and gcd(x3,8y4) = 8 if x is even. Thus the only possible values for gcd(b3,c4) are 83 and 84. If we take b=8 and c=8, then gcd(b3,c4) = 83, while if we take b=16 and c=8, then gcd(b3,c4) = 84, so both possibilities really do occur.
4. Let m, b and c be positive integers. Prove that [mb,mc] = m[b,c].
• We know that [b,c] = bc/gcd(b,c) and [mb,mc] = mbmc/gcd(mb,mc). But gcd(mb,mc) = m(gcd(b,c)) by Problem 6 of Homework 4 (and its solution), so [mb,mc] = mbmc/gcd(mb,mc) = mbmc/(m(gcd(b,c)) = mbc/gcd(b,c) = m[b,c].
5. Let b and c be positive integers. Show that the smallest positive integer k such that b divides kc is k = b/gcd(b,c).
• Note that kc is the least multiple of c which is also a multiple of b; i.e., kc = lcm(b,c) = bc/gcd(b,c), hence k = b/gcd(b,c).
6. Suppose b and c are positive integers such that gcd(b,c)=12 and [b,c]=120 with b <= c (where I use "<=" to mean "less than or equal to", since it's not easy to use the standard symbol in a way that any web browser will display correctly). Find all possible values of b and c. Justify your answer.
• We know that [b,c] = bc/gcd(b,c) so 120*12 = [b,c]gcd(b,c) = bc = 12*12xy, where b=12x and c=12y for some x and y which are relatively prime with x <= y. Thus xy = 10, so either x=1 and y=10 or x=2 and y=5. Thus either b=12 and c=120, or b=24 and c=60.
7. Suppose m, x and y are positive integers. If x == y (mod m), prove that gcd(m,x) = gcd(m,y).
• Since x == y (mod m), we can write y = x + km for some k. Thus any common divisor of x and m also divides y, and vice versa. Thus gcd(m,x) is a common divisor of m and y, hence gcd(m,x) <= gcd(m,y), and gcd(m,y) is a common divisor of m and x, hence gcd(m,y) <= gcd(m,x). I.e., gcd(m,x) = gcd(m,y).