# Does such a natural number exist, that it would be divisible by every other natural number

I've got to prove (or disprove) the following statement:

$\exists x \in \mathbb{N} \; \forall y \in \mathbb{N}: y \mid x$,

which translates into "It exists such $x$ from the set of natural numbers, that it is divisible by every other natural number."

What puzzles me is that (at the first sight) theoretically we can always build such $x$ by simple multiplication with $y$, but at the same time I am not really sure if we can do this in general. Let for example $y$ be bigger than $x$ (which it can be since this should work for every natural $y$); this clearly does not divide into $y$ anymore. Again by multiplication, I could find a new $x$ that would statisfy the condition... but so can I find $y$ bigger than this new $x$...

So in fact, this statement would only be true when there exists the biggest natual number that is at the same time a multiple of all the previous natural numbers. This clearly cannot be satisfied.

Could this already do as a proof that such $x$ does not exist or do I have to prove the negation of the original statement $\lnot (\exists x \in \mathbb{N} \; \forall y \in \mathbb{N}: y \mid x)$?

EDIT: Note that we distinguish between $\mathbb{N}$ and $\mathbb{N}_0$ ($0 \not\in \mathbb{N}$, but $0 \in \mathbb{N}_0$).

-

If you include $0$ in the natural numbers then note that $0$ is divided by any other number, except for itself. It is often the custom to say that $0$ does divides itself, to allow the relation to be reflexive.

In this case indeed $0$ is such number.

However if $0$ is not included in your definition of the natural numbers then the answer is no. Such number would be divisible by all the prime numbers, and therefore will be at least as large as any of them. Since the prime numbers are unbounded it means that such number will be at least as large as any other number, and therefore it would be larger than all of them. There is no number which is larger than all the natural numbers, and so the answer is negative.

-

If you consider zero as a natural number then $\,x=0\,$ solves your problem as

$$\forall\,\,y\in\Bbb N\;\;,\;\;y\,\mid 0\Longleftrightarrow\,\,\exists\,n\in\Bbb N\,\,s.t.\,\,0=ny$$

and choosing $\,n=0\,$ does the job.

If you mean non-zero $\,x\,$ then the answer is no as it wouldcontradict hte Fundamental Theorem of Arithmetic

-

In one sense, the answer is yes: $0$ is divisible by any positive integer, and depending on how you define divisibility, $0$ may be divisible by $0$ as well.

However, in another sense, the answer is no: if $n$ is a positive integer and $m$ divides $n$, then $n \ge m$, so a positive integer can never be divisible by all positive integers.

Finally, perhaps it's worth mentioning that one can construct a non-standard model of Peano arithmetic in which there exists a non-zero number divisible by every standard natural number. Indeed, you have already made the key observation needed: for any finite set $D$ of standard natural numbers, I can construct a standard natural number that is divisible by everything in $D$. Thus, by the compactness theorem, there is a non-standard model with a non-standard number that is divisible by all standard natural numbers. (Alternatively, take an ultrapower of the standard model and consider the class of $(1, 2, 3!, 4!, 5!, 6!, \ldots)$.)

-
As for the last paragraph, I think it should be mentioned that while it will be divisible by any standard number it will not be divisible by all the numbers (internally). This can be confusing to someone unfamiliar with internal and external definability issues. –  Asaf Karagila Dec 16 '12 at 12:20

In case you define $N$ such that $0\in N$:

Note that $x|y$ does not imply that $x\leq y$

In fact $\forall y\in N [y|0]$ and $0\in N$. This is because $\forall y\in N[(y)(0)=0]$

-
Does $0|0$? I thought that no number can be divided by zero. :-) –  Asaf Karagila Dec 16 '12 at 11:48
Depends on your definition. I say $x \mid y$ if and only if $\exists z . y = x z$, in which case $x \mid x$ always. –  Zhen Lin Dec 16 '12 at 11:50
So did I, yet extending (or contracting...?) the definition of "divide" from ring theory to the naturals makes the cut...I think. –  DonAntonio Dec 16 '12 at 11:50
I was going to say what Zhen lin said. $0=0$x$0$. –  Amr Dec 16 '12 at 11:51
Sorry, we distinguish between $\mathbb{N}$ and $\mathbb{N}_0$ ($0 \not\in \mathbb{N}$, but $0 \in \mathbb{N}_0$) –  smihael Dec 16 '12 at 11:51