wu :: forums
wu :: forums - PRIME GCD

Welcome, Guest. Please Login or Register.
Aug 8th, 2022, 2:48pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   putnam exam (pure math)
(Moderators: Icarus, william wu, Eigenray, SMQ, Grimbal, towr)
   PRIME GCD
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: PRIME GCD  (Read 858 times)
Pietro K.C.
Full Member
***





115936899 115936899    
WWW

Gender: male
Posts: 213
PRIME GCD  
« on: Nov 4th, 2002, 2:40pm »
Quote Quote Modify 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 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 Quote Modify 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: male
Posts: 37
Re: NEW PROBLEM: PRIME GCD  
« Reply #2 on: Nov 5th, 2002, 7:09am »
Quote Quote Modify 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
***





115936899 115936899    
WWW

Gender: male
Posts: 213
Re: NEW PROBLEM: PRIME GCD  
« Reply #3 on: Nov 5th, 2002, 8:56am »
Quote Quote Modify 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. Smiley 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. Shocked
 
   Good luck! Smiley
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)
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright 2000-2004 Yet another Bulletin Board