3

The proof that i came up is as follows.

Assume any non prime positive integer${}> 1$ will have factors of either $2,3,5$ or a combination of them. Let $S$ be a set of sets where each set conatians a combination of $2,3,5$ $S = \{\{\}, \{2\}, \{3\}, \{5\}, \{2,3\}, \{2,5\}, \{3,5\}, \{2,3,5\}\}$ Since $|S|$ is $8$ and there are $9$ positive integers, by pigeonhole-principle, some two of them should share all of their prime factors that are less than or equal to $5$.

Is my reasoning correct? I am specially concered about whether my assumption of "any non prime positive integer $> 1$ will have factors of either $2,3,5$ or a combination of them" is correct

Michael Hardy
  • 1
user119020
  • 283
  • It's not properly stated, since it doesn't include the empty set (no factors from 2,3,5) but since S is correctly put you just need to reword the statement. – Paul Dec 04 '21 at 01:21
  • Your construction gives an ordered triple for each number, each number either 0 or 1 in each $(n_2, ; n_3, ; n_5)$ There are 8 triples, 8 pigeonholes. – Will Jagy Dec 04 '21 at 01:23
  • The expression $S = {{}, {2}, {3}, {5}, {2,3}, {2,5}, {3,5}, {2,3,5}}$ is now entirely in MathJax. Alternating in and out of MathJax results in font mismatches and spacing errors (as, in this case, to the right of the "equals" sign). – Michael Hardy Dec 04 '21 at 02:39

1 Answers1

2

I'm now working on this problem. I've come to the conclusion that it is a false statement. The question says "Any set of positive integers", so what happens if the set consists of only prime numbers? In that case, no number shares any prime factor (as 1 itself is not prime). Unless I am missing something, I would think that this is at least one counterexample which proves the statement false.

John
  • 167
  • No number shares any prime factor is actually fine (apparently), although according to the wording it may appear excluded. It says "share all their prime factors", so if there's nothing to share, by default "all" is shared, I would think. – Sarvesh Ravichandran Iyer May 19 '22 at 16:07
  • 1
    Thanks for pointing that out, I was puzzling over the wording also. So it's like "they all share nothing" which means zero. And since zero is less than 5 then I suppose this reasoning is valid. Thanks! – John May 19 '22 at 16:28
  • Exactly, you understood what I meant – Sarvesh Ravichandran Iyer May 19 '22 at 17:29