1085: For 2 Natural Numbers, Set of Common Divisors of Numbers Is Set of Common Divisors of Non-Larger Number and Non-Negative Difference of Numbers

<The previous article in this series | The table of contents of this series | The next article in this series>

description/proof of that for 2 natural numbers, set of common divisors of numbers is set of common divisors of non-larger number and non-negative difference of numbers

---

Topics

About: set

---

The table of contents of this article

• Starting Context
• Target Context
• Orientation
• Main Body
• 1: Structured Description
• 2: Note 1
• 3: Proof
• 4: Note 2

---

Starting Context

• The reader knows a definition of natural numbers set.
• The reader knows a definition of common divisors of subset of natural numbers set.

---

Target Context

• The reader will have a description and a proof of the proposition that for any 2 natural numbers, the set of the common divisors of the numbers is the set of the common divisors of the non-larger number and the non-negative difference of the numbers.

---

Orientation

There is a list of definitions discussed so far in this site.

There is a list of propositions discussed so far in this site.

---

Main Body

---

1: Structured Description

Here is the rules of Structured Description.

Entities:
$\mathbb{N}$:
$n$: $\in \mathbb{N}$
$n^{\prime }$: $\in \mathbb{N}$ such that $n\le n^{\prime }$
//

Statements:
$cd(\{n,n^{\prime }\})=cd(\{n,n^{\prime }-n\})$, where $cd(\bullet )$ denotes the set of the common divisors of the argument
//

---

2: Note 1

As an immediate corollary, $gcd(\{n,n^{\prime }\})=gcd(\{n,n^{\prime }-n\})$, because the greatest common divisor is determined by the set of the common divisors.

---

3: Proof

Whole Strategy: Step 1: for each $d\in cd(\{n,n^{\prime }\})$, see that $d\in cd(\{n,n^{\prime }-n\})$; Step 2: for each $d\in cd(\{n,n^{\prime }-n\})$, see that $d\in cd(\{n,n^{\prime }\})$.

Step 1:

Let $d\in cd(\{n,n^{\prime }\})$ be any.

There are some $m,m^{\prime }\in \mathbb{N}$ such that $n=dm$ and $n^{\prime }=d{m}^{\prime }$ where $m\le m^{\prime }$.

$n^{\prime }-n=d{m}^{\prime }-dm=d(m^{\prime }-m)$ where $m^{\prime }-m\in \mathbb{N}$.

So, $d\in cd(\{n,n^{\prime }-n\})$.

Step 2:

Let $d\in cd(\{n,n^{\prime }-n\})$ be any.

There are some $m,m^{\prime }\in \mathbb{N}$ such that $n=dm$ and $n^{\prime }-n=d{m}^{\prime }$.

$n^{\prime }=n+d{m}^{\prime }=dm+d{m}^{\prime }=d(m+m^{\prime })$, where $m+m^{\prime }\in \mathbb{N}$.

So, $d\in cd(\{n,n^{\prime }\})$.

---

4: Note 2

It holds when $n=0$: $cd(\{n,n^{\prime }\})=cd(\{0,n^{\prime }\})=cd(\{n,n^{\prime }-n\})$: $cd(\{0,n^{\prime }\})$ are the factors of $n^{\prime }$: $0$ does not inflict any restriction, because $0=d0$ for any $d\in \mathbb{N}$.

For example, $cd(\{0,6\})=\{1,2,3,6\}$.

It holds when $n=n^{\prime }$: $cd(\{n,n^{\prime }\})=cd(\{n,n\})=cd(\{n,0\})=cd(\{n,n^{\prime }-n\})$: $cd(\{n,n\})$ are the factors of $n$ and $cd(\{n,0\})$ are the factors of $n$.

---

References

<The previous article in this series | The table of contents of this series | The next article in this series>