|
||
|
Title: PRIME GCD Post by Pietro K.C. on Nov 4th, 2002, 2:40pm In spite of the small number of responses to previous problems I posted, here's another, also taken from a random Putnam. Suppose S is a finite set of integers greater than 1 with the property that, for every natural number n, there exists an s in S such that gcd(n,s) = 1 or gcd(n,s) = s. Prove that there exist s,t in S such that gcd(s,t) is prime. |
||
|
Title: Re: NEW PROBLEM: PRIME GCD Post by oliver on Nov 5th, 2002, 5:59am Hmm, bummer, methinks the proposition to be proved is wrong. S = {2,3,5} or any finite set of primes would be a counterexample, wouldn't it (IOW, is 1 to be considered a prime?). Furthermore, I think it should be forbidden to allow s=t when testing gcd(s,t) = prime, otherwise the proof would be trivial (and my above counterexample wouldn't be one) Maybe I'm just confused. |
||
|
Title: Re: NEW PROBLEM: PRIME GCD Post by Jamie on Nov 5th, 2002, 7:09am Well, it doesn't say that s and t have to be distinct, so if S contains any prime, p, then just let s=t=p. |
||
|
Title: Re: NEW PROBLEM: PRIME GCD Post by Pietro K.C. on Nov 5th, 2002, 8:56am Jamie is indeed correct, and 1 is NOT a prime. Otherwise the proof would REALLY be trivial. However, the possibility s = t does not render the proof "trivial", unless you're a seasoned number theorist, I guess. This WAS in one of the Putnams, after all, and it was question B-6 (usually only questions A-1 and B-1 are easier). Took me about 5 minutes to come up with the general idea, and another 15 to work out the full details. So your counterexample is not one, in fact. :) Notice that the problem statement does not imply that there are any primes in set S. If you succeed in proving that, then you've solved it. I doubt you'll succeed, though, since S = {4, 6, 9} satisfies the requirements and contains no primes. :o Good luck! :) |
||
|
Powered by YaBB 1 Gold - SP 1.4! Forum software copyright © 2000-2004 Yet another Bulletin Board |