Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that there is a set of natural numbers $a, b, c, d...$

Is there any such set that any product of two different numbers is a multiple of $x$, but any product of two same numbers - that is a number squared - is not a multiple of $x$?

How does one determine such set?

Edit: I want to know a general method for determining for any cardinality of a set. Not just two or so.

share|improve this question
    
Are you another alias for TTTY, who has been asking variations on this question lately? –  Gerry Myerson Oct 31 '12 at 4:27
    
The first part of your question would be clearer if you wrote "Does there exist a subset $S$ of the natural numbers such that any product..." A hint - consider the prime factorizations of members of a hypothetical such set. –  Jonah Sinick Oct 31 '12 at 5:34

3 Answers 3

up vote 3 down vote accepted

To exhibit an $n$-element set with this property, choose $n$ distinct primes $p_1,p_2,\dots,p_n$; then let $x=\left(\prod_i p_i\right)$ and $$ S=\left\{\frac{x}{p_1}, \frac{x}{p_2},\dots,\frac{x}{p_n}\right\}. $$ Each entry is missing one of the prime factors of $x$, and so is any power of a single entry; but the product of any two distinct entries is divisible by $x$.

share|improve this answer

What about $\,\{2,3\}\,$? The product of any two different of these numbers is a multiple of $\,6\,$ but none of them squared is such a multiple...

share|improve this answer

And for a three element set $$\{2 \cdot 3^4 \cdot 5^7, 2^4 \cdot 3^7 \cdot 5^1, 2^7 \cdot 3^1 \cdot 5^4\}$$ $x = 2^5 3^5 5^5$.

An example in the general case if, for a $n$ element set, first choose $n$ distinct primes, say $p(0),p(1),p(2),\ldots, p(n-1)$, then the set is given by $$S = \left \{ p(\overline{k}), p(\overline{k+1})^4, p(\overline{k+2})^7, \cdots, p(\overline{k+n-1})^{3n-2} : \overline{k} = k \pmod{n}\right \}$$

and $x = (p(0) p(1) p(2) \cdots p(n-1))^5$.

Once you get this idea, you can construct infinite other counterexamples as well.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.