wu :: forums « wu :: forums - PRIME GCD » Welcome, Guest. Please Login or Register. Aug 8th, 2022, 2:48pm RIDDLES SITE WRITE MATH! Home Help Search Members Login 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 Notify of replies Send Topic Print
 Author Topic: PRIME GCD  (Read 858 times)
Pietro K.C.
Full Member

Gender:
Posts: 213
 PRIME GCD   « on: Nov 4th, 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 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)
 Pages: 1 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium   - hard   - what am i   - what happened   - microsoft   - cs => putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »