# Understanding the proof of unique natural divisor

Let $m,n \in \mathbb{Z}$. There exists a unique natural number $d \in \mathbb{N}$ such that $\text{div} (m) \cap \text{div} (n)= \text{div} (d)$.

Now I know this is just saying that between any two numbers, there is a natural number that divides both. It is a fact learned in primary school and is obvious. Apologies in advance if this proof is super easy and I am just a slow learner.

I will put asterisks ** before any line of the proof I am struggling with.

Proof:
The uniqueness follows from the fact that $$\text{div}(d_1)=\text{div}(d_2)\;\text{if and only if}\; d_1=d_2$$ assuming that $d_1,d_2 \in \mathbb{N}$. When proving the existence of $d$ we may assume $m,n \in \mathbb{N}$, since $\text{div}(x)=\text{div}(-x)$ for $x \in \mathbb{Z}$. We proceed using induction on $\min(m,n)$, where $\min(m,n)=m$ if $m \le n$ and $\min(m,n)=n$ if $m \gt n$. If $\min(m,n)=0$ we may assume $n=0$.

1. ** Therefore $$\text{div}(m) \cap \text{div}(n)=\text{div}(m)$$ This is where I got confused, if $m \gt n$ how can this be true?

2. ** This settles the intial step $$\min(m,n)=0$$ of the induction. So how does this line tie into what we were trying to prove?

3. ** Now assume that we have proved $$\text{div}(m) \cap \text{div}(n)=\text{div}(d)$$ for every $m,n \in \mathbb{N}$ with $\min(m,n) \lt N$, where $N \gt 0$.

How can we assume the very thing we are trying to prove? Suppose for the induction step that we are given $m,n \in \mathbb{N}$ with $\min(m,n)=N$. Then we may write $m=qn+r$, where $0 \le r \lt n$.

4. ** But $$\text{div}(m) \cap \text{div}(n)= \text{div}(m-qn) \cap \text{div}(n)= \text{div}(r) \cap \text{div}(n)$$ Since a number divides $m$ and $n$ if and only if it divides $m-qn$ and $n$ (this line I understand).

5. ** By induction we know that $$\text{div}(r) \cap \text{div}(n)=\text{div}(d)$$ for some $d \in \mathbb{N}$, since $\min(r,n)= r \lt n=N$. And this completes the proof.

Where I have put an asterisk is either I don't understand how they came to that conclusion, or I don't understand how it ties into what we are trying to prove. Sorry, sometimes it is hard for me to explain exactly what I don't understand.

• Question 1. n = 0 so div(n) = $\mathbb Z$. Everything divides 0. This is a special case of m > n = 0. so div(m) $\cap$ div(0) = div(m) $\cap \mathbb Z$ = div(m). – fleablood Aug 3 '16 at 6:17
• Question 3: We have proven it of $N = 1$. Then min(n,m) < 1 means min(n,m) = 0. We've done that. THis is how iduction works. We show it is true for $N=1$. We show that if it is true for some $N$ which mayb be equal to 1 or maybe equal to something else then True for N => True for N + 1. If we can show this we are done. (Because since it is true for N=1 it must be true for N = 2. And therefore it is true for N=3. And N=4 ... etc.) – fleablood Aug 3 '16 at 6:23
• Are you comfortable with proofs by induction? – fleablood Aug 3 '16 at 6:25

I don't like that proof at all. It's too hard to read. So I wrote a new proof.

A nonempty subset $I$ of $\mathbb{Z}$ is called an ideal if:

(i) If $x,y \in I$, so is $x+y$.

(ii) If $x \in I$, and $y$ is any integer, then $xy \in \mathbb{Z}$.

Here are some examples:

(I): $\mathbb{Z}$ is an ideal.

(II): If $n$ is any integer, then $n\mathbb{Z}$, by definition the set of all integers which are divisible by $n$, is an ideal (check that this satisfies the definition).

Actually, these are all the ideals of $\mathbb{Z}$.

Lemma: If $I$ is an ideal, then there exists a positive integer $n$ such that $I = n\mathbb{Z}$. If $m$ is another integer, and $n\mathbb{Z} = m\mathbb{Z}$, then $n = \pm m$.

Proof: If $I$ just consists of the number $0$, then we are done, because then $I = 0\mathbb{Z}$, which is an ideal. So assume $I$ has a nonzero element $x$.

Then $I$ has a positive element. If $x$ is positive, great. If $x$ is negative, then $(-1) \cdot x = -x$ is a positive member of $I$, by property (ii) of the definition of an ideal.

So $I$ has positive elements. Let $n$ be the smallest positive member of $I$ (remember that every nonempty subset of $\mathbb{N}$ has a smallest element). I claim that $$I = n\mathbb{Z}$$ If $a \in n\mathbb{Z}$, then $a = nk$ for some integer $k$. But since $n \in I$, so is $nk$ by property (ii). This shows that $n\mathbb{Z} \subseteq I$.

Now let $x \in I$. Then there exist integers $q, r$ such that $$x = qn + r$$ with $0\leq r \leq n-1$. Now $x$ and $qn$ are elements of $I$. Hence $(-1)qn = -qn$ is an element of $I$. Hence $x + (-1)qn = r$ is an element of $I$ by property (i). But by the way we defined $n$, the set $I$ does not contain any positive elements which are smaller than $n$. So we must have $r = 0$. This shows that $x = qn$ lies in $n\mathbb{Z}$. Thus $I = n\mathbb{Z}$.

If $m\mathbb{Z} = n\mathbb{Z}$, then since $m \in m\mathbb{Z}$, it is also an element of $n\mathbb{Z}$, hence $m = kn$ for some integer $k$. Therefore, $|m| = |kn| \geq |n|$. By the same reasoning, $|n| \geq |m|$. Therefore, $|n| = |m|$, which means that $n = \pm m$. $\blacksquare$

Proposition: Let $n,m$ be integers. There exists a unique natural number $d$ whose divisors are exactly those numbers which are divisors of both $m$ and $n$.

Proof: Let $n\mathbb{Z} + m\mathbb{Z}$ denote the set of integers which can be written in the form $x+y$, where $x \in n\mathbb{Z}$ and $y \in m\mathbb{Z}$. You can check that $n\mathbb{Z} + m\mathbb{Z}$ is an ideal. So by the lemma, we know that there exists a positive integer $d$ such that $$n\mathbb{Z} + m\mathbb{Z} = d \mathbb{Z}$$

We claim that $d$ does what you want. First, note that $n\mathbb{Z} + m\mathbb{Z}$ contains $n\mathbb{Z}$ as a subset. Since $n \in n\mathbb{Z}$, we then see that $n$ is divisible by $d$. Similarly, $m$ is divisible by $d$. So any divisor of $d$ must also divide both $n$ and $m$.

We now just have to show that if $x$ divides both $n$ and $m$, then $x$ divides $d$. Since $d$ is an element of $n\mathbb{Z} + m\mathbb{Z}$, there exist integers $a, b$ such that $$d = an + bm$$ Since $x$ divides $n$ and $m$, we can write $n = kx$ and $m = lx$ for some integers $k, l$. But then $$d = akx + blx = (ak + bl)x$$ so $x$ divides $d$.

The last thing to establish is the uniqueness of $d$. If $d'$ is any other number with the same properties, then, since $d'$ is a divisor of itself, it must be a divisor of both $m$ and $n$. But $d$ divides all numbers with those properties. So $d$ divides $d'$. But reversing the roles of $d$ and $d'$, we see that $d'$ divides $d$. The only way two integers $d$ and $d'$ can divide each other is if $d = \pm d'$. $\blacksquare$

The language and choice of variables is confusing.

Let me rewrite it.

Prove that for $m, n \in \mathbb N+\{0\}$ $m \ne n$, there exist a $d$ such that $div(m) \cap div(n) = div(d)$.

Since either $m > n$ or $n > m$ we might as well assume $m > n$ (otherwise we'd just relabel and get the same result.

Initial step:

$n = 0$

Then every number divides $0$ so $div(0) = \mathbb Z$.

So $div(m) \cap div(0) = div(m) \cap \mathbb Z = div(m)$.

Induction step:

Assume we have shown it is true for all $n \le k-1$. (We have proven it is true for $k = 1$ as we have proven it is true for $n = 0$). We want to prove it must be true for $n = k$.

Let $m = q*k + r$ with $0 \le r < 0$.

Then

$div(m) \cap div(k) = div(m - kq) \cap div(k) = div(r) \cap div(k)$

Since $r < k$ and we have assumed $div(m) \cap div(n)= div(d)$ for some $d$ if $m>n$ and $n \le k-1$, we can conclude $div(r) \cap div(k) = div(d)$ for some $d$.

Thus we have shown this is not only true for $n \le k-1$ it is true for $n = k$ too.

So by induction we know it is true for $n = 0$ (because $div(m) \cap div(0) = div(m)$).

Therefore it must be true for $n = 0+ 1= 1$ (because $m = q*1 + 0$ and $div(m) \cap div(1) = div(m - q*1) \cap div(1) = div(0) \cap div(1) = div(1)$)

Therefore it must be true for $n = 1+ 1 = 2$ (because $m = q*2 + r$ $r < 2$ and $div(m) \cap div(2) = div(m - 2q) \cap div(2) = div(r) \cap div(2)$. div(r) = either $div(1)= \{1\}$ or $div(0)$ so the intersection equals either $div(2)$ or $div(1)$.)

Therefore it must be true fore $n = 2+1 = 3$ (because $m = 3q + r$ and $div(m) \cup div(3) = div(m - 3q) \cup div(3) = div(r) \cup div(3)$ and we've proven that for $r < 3$ that $div(r) \cup div(m) = div(d)$ for some $d$.)

Etc. repeat forever.

I am short of time, but I try to explain the first two questions. An example for $\text{div}()$: $$\text{div}(6)=\{-6,-3,-2,-1,1,2,3,6\}$$ and $$\text{div}(-6)=\{-6,-3,-2,-1,1,2,3,6\}$$

So $\text{div}$ is a subset of $\mathbb {Z}$ that contains negative and poisitive numbers. it does not contain $0$ except for $$\text{div}(0)=\mathbb{Z}$$ because $$\forall n \in \mathbb{Z}: \, n\cdot 0=0$$ and so $$\forall n \in \mathbb{Z}: \, n \mid 0$$

1. we assume $n=0$. Therefore $\text{div}(n)=\mathbb{Z}$ and so $$\text{div}(m) \cap \text{div}(n) = \text{div}(m) \cap \mathbb{Z} =\text{div}(m)$$
2. We have $$\mathbb{N}=\{0,1,2,3,\cdots\}$$ We want to proof $$\forall m \in \mathbb{N}, \forall n \in \mathbb{N}:\,\exists d \in \mathbb{N}: \; \text{div} (m) \cap \text{div} (n)= \text{div} (d) \tag{1}$$ by induction on $\min(m,n)$ so we formulate $(1)$ as $$\forall N \in \mathbb{N}: \, \left(m \in \mathbb{N} \land n \in \mathbb{N}\land \min(m,n)\le N \implies \; \exists d \in \mathbb{N}: \; \text{div} (m) \cap \text{div} (n)= \text{div} (d) \right) \tag{2}$$ If $m,n \in \mathbb{N}$ then $$\min_{m,n \in \mathbb{N}}(m,n)= \min(\min_{m \in \mathbb{N}}(m),\min_{n \in \mathbb{N}}(n)) = \min(0,0) = 0$$ So the smallest $\min(m,n)$ we encounter is $0$. Therefore we have to check $(2)$ for $N=0$, which is done in paragraph 1.

The remaining part of the proof is to show that

If $(2)$ is valid for an arbitrary $N=k \in \mathbb{N}$ then $(2)$ is valid for $N=k+1$