0
$\begingroup$

I have been facing some problems recently, when I need to prove that there are infinitely many natural numbers with some conditions. It is very hard, because usually we can prove that of one or more conditions meet this criteria, however it will not neccesarily mean that the statement is true for all criteria at the same time. To compare different infinities is not easy. I thought I would ask your help on a simple problem and learn how you would approach a problem like this. I am interested in as many approaches as possible, be open minded, because I would like to use these methods for more end more complicated problems and you never know what the best approach will be for those. My example is simple: prove that there are infinitely many natural numbers that can not be written as either 2x, or 5x, where x is a natural number. Here we do have infinitely many natural numbers that are not 2x, and we do have infinitely many natural numbers that are not 5x. How would you prove the example?

$\endgroup$
  • 1
    $\begingroup$ for the sake of proving your simple statement, consider prime numbers. $\endgroup$ – Maged Saeed Oct 22 '18 at 13:39
  • $\begingroup$ ... but then you have to assume or prove that there are an infinite number of primes. $\endgroup$ – gandalf61 Oct 22 '18 at 13:56
  • $\begingroup$ I am aware of a proof. Please read my question, I am interested in learning methods how the community would approach problems like this. I gave a simple example just to keep it relatively simple. Thanks. $\endgroup$ – Tilsight Oct 22 '18 at 14:06
  • $\begingroup$ @gandalf that's rather simple. Assume there is a maximum prime $P$, then $$Q=1+\prod_{p\text{ prime}}^P{p}$$ has no prime divisor $\le P$. So it is either prime or has a prime divisor $> P$, a contradiction that $P$ is the maximum prime. $\endgroup$ – Rhys Hughes Oct 22 '18 at 14:18
  • $\begingroup$ @RhysHughes - yes, but my point was that using prime numbers replaces one "prove this set is infinite" proof with an other more complex "prove this set is infinite" proof. IMO a direct proof of the example problem is simpler than a proof that depends on the infinitude of primes. $\endgroup$ – gandalf61 Oct 22 '18 at 14:25
3
$\begingroup$

There is no general answer for problems of the form "are there infinitely many natural numbers with these properties" -- a large part of the entire field of number theory could be rewritten in this form. The only way to learn how to do this is to get used to specific examples.

For your specific example, the way to approach it is probably to just look at what numbers satisfy the two conditions.

What numbers cannot be written as $2x$? Clearly $2, 4, 6, 8, 10, \ldots$ can, so the numbers you are looking for are the odd numbers $1, 3, 5, 7, \ldots$. Similarly, for 5: what numbers can be written as $5x$? Clearly $5, 10, 15, 20, 25, 30, \ldots.$. So the numbers you are looking for are the ones that do not end in a 0 or a 5.

Can you name infinitely many odd numbers that do not end in a 0 or a 5?

$\endgroup$
0
$\begingroup$

Take a natural number $a$ that is not a multiple of $2$ and is not a multiple of $5$. Then its square $a^2$ is also not a multiple of $2$ and is not a multiple of $5$ ($2$ and $5$ share a property that makes this true - think about what that property is).

Let $S$ be the set of natural numbers that are not a multiple of $2$ and not a multiple of $5$. If $S$ were finite than it would have a largest member $s_{max}$. But we have just shown above that $s_{max}^2$ would also be a member of $S$ and $s_{max}^2 > s_{max}$ (well, as long as $s_{max} >1$, but this is trivial). So this contradicts the assertion that $s_{max}$ is the largest member of $S$. Hence $S$ cannot be finite.

The general strategy here for proving a set $S$ of natural numbers with property $P$ is infinite is to assume $S$ is finite, and then find or construct a number that has property $P$ but is not in $S$, typically because it is greater than the largest member of $S$. This proves that $S$ cannot be finite.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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