1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – fleablood Aug 3 '16 at 6:17
  • $\begingroup$ 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.) $\endgroup$ – fleablood Aug 3 '16 at 6:23
  • $\begingroup$ Are you comfortable with proofs by induction? $\endgroup$ – fleablood Aug 3 '16 at 6:25
1
$\begingroup$

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$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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$

$\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.