All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Just Math
Up to 35 (Posted on 2004-11-14) Difficulty: 3 of 5
S is a set of N distinct positive integers such that no member of S has a prime factor greater than 35. Let P be the set of products of members of S taken 2 at a time. (For example, if x, y and z are members of S, then xy, xz and yz will be members of P.)

What is the smallest value of N for which it is certain that P contains a perfect square?

See The Solution Submitted by Brian Smith    
Rating: 3.5000 (4 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Scaled Down Version | Comment 3 of 5 |
By considering a scaled-down version of the problem, the crux of the matter becomes quite apparent.
Let us consider the case of just 2 different prime divisors p and q (which can be 2 and 3, if you like). We need to show that there is an N such that all sets of N or more numbers of the form (p^x)*(q^y) contain a pair whose product is a square. The product (p^u)*(q^v) of two of the numbers of the set is a square exactly when u and v are both even numbers. Consider now the exponent pairs (x,y). Mod 2, (x,y) is congruent to (0,0), (0,1), (1,0), or (1,1) and, (u,v) is congruent to the component-wise mod 2 sum of two of these, possibly the same one taken twice. It is precisely when the same one is taken twice that u and v both turn out to be even. Hence any set of 5 numbers of the form (p^x)*(q^y) will always contain a pair whose product is a square, but a smaller set need not.

Edited on November 15, 2004, 12:38 am
  Posted by Richard on 2004-11-15 00:35:56

Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (11)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information