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.
- Read 5ABC.
- 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.)
- 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).
Let m, b and c be positive integers. Prove that [mb,mc] = m[b,c].
- 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.
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).
- 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].
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.
- 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).
Suppose m, x and y are positive integers. If x == y (mod m),
prove that gcd(m,x) = gcd(m,y).
- 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.
- 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).