Author |
Topic: PRIME GCD (Read 865 times) |
|
Pietro K.C.
Full Member
 
Gender: 
Posts: 213
|
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 10th, 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 5th, 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 5th, 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 5th, 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 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. 
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)
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print