Author 
Topic: PRIME GCD (Read 858 times) 

Pietro K.C.
Full Member
Gender:
Posts: 213


PRIME GCD
« on: Nov 4^{th}, 2002, 2:40pm » 
Quote Modify

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.

« Last Edit: Dec 10^{th}, 2002, 8:36am by Pietro K.C. » 
IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



oliver
Newbie
Posts: 25


Re: NEW PROBLEM: PRIME GCD
« Reply #1 on: Nov 5^{th}, 2002, 5:59am » 
Quote Modify

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.


IP Logged 



Jamie
Newbie
Gender:
Posts: 37


Re: NEW PROBLEM: PRIME GCD
« Reply #2 on: Nov 5^{th}, 2002, 7:09am » 
Quote Modify

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.


IP Logged 



Pietro K.C.
Full Member
Gender:
Posts: 213


Re: NEW PROBLEM: PRIME GCD
« Reply #3 on: Nov 5^{th}, 2002, 8:56am » 
Quote Modify

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 B6 (usually only questions A1 and B1 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. Good luck!


IP Logged 
"I always wondered about the meaning of life. So I looked it up in the dictionary under 'L' and there it was  the meaning of life. It was not what I expected." (Dogbert)



