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'\): \(\in \mathbb{N}\) such that \(n \le n'\)
//
Statements:
\(cd (\{n, n'\}) = cd (\{n, n' - n\})\), where \(cd (\bullet)\) denotes the set of the common divisors of the argument
//
2: Note 1
As an immediate corollary, \(gcd (\{n, n'\}) = gcd (\{n, n' - 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'\})\), see that \(d \in cd (\{n, n' - n\})\); Step 2: for each \(d \in cd (\{n, n' - n\})\), see that \(d \in cd (\{n, n'\})\).
Step 1:
Let \(d \in cd (\{n, n'\})\) be any.
There are some \(m, m' \in \mathbb{N}\) such that \(n = d m\) and \(n' = d m'\) where \(m \le m'\).
\(n' - n = d m' - d m = d (m' - m)\) where \(m' - m \in \mathbb{N}\).
So, \(d \in cd (\{n, n' - n\})\).
Step 2:
Let \(d \in cd (\{n, n' - n\})\) be any.
There are some \(m, m' \in \mathbb{N}\) such that \(n = d m\) and \(n' - n = d m'\).
\(n' = n + d m' = d m + d m' = d (m + m')\), where \(m + m' \in \mathbb{N}\).
So, \(d \in cd (\{n, n'\})\).
4: Note 2
It holds when \(n = 0\): \(cd (\{n, n'\}) = cd (\{0, n'\}) = cd (\{n, n' - n\})\): \(cd (\{0, n'\})\) are the factors of \(n'\): \(0\) does not inflict any restriction, because \(0 = d 0\) for any \(d \in \mathbb{N}\).
For example, \(cd (\{0, 6\}) = \{1, 2, 3, 6\}\).
It holds when \(n = n'\): \(cd (\{n, n'\}) = cd (\{n, n\}) = cd (\{n, 0\}) = cd (\{n, n' - n\})\): \(cd (\{n, n\})\) are the factors of \(n\) and \(cd (\{n, 0\})\) are the factors of \(n\).
