description/proof of that for 2 natural numbers whose greatest common divisor is 1, there are some 2 integers s.t. linear combination of natural numbers with integers coefficients is 1
Topics
About: set
The table of contents of this article
Starting Context
- The reader knows a definition of natural numbers set.
- The reader knows a definition of greatest common divisor of subset of natural numbers set.
- The reader admits 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.
Target Context
- The reader will have a description and a proof of the proposition that for any 2 natural numbers whose greatest common divisor is 1, there are some 2 integers such that the linear combination of the natural numbers with the integers coefficients is 1.
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:
\(gcd (\{n, n'\}) = 1\), where \(gcd (\bullet)\) denotes the greatest common divisor of the argument
\(\implies\)
\(\exists z, z' \in \mathbb{Z} (z n + z' n' = 1)\)
//
2: Proof
Whole Strategy: Step 1: deal with the case that \(n = 0\); Step 2: deal with the case that \(n = 1\); Step 3: deal with the case that \(1 \lt n\).
Step 1:
Let us suppose that \(n = 0\).
\(gcd (\{n, n'\}) = 1\) means that \(n' = 1\).
So, there are \(z = 0, z' = 1\) such that \(z n + z' n' = 1\).
Step 2:
Let us suppose that \(n = 1\).
\(n'\) can be any.
But anyway, there are \(z = 1, z' = 0\) such that \(z n + z' n' = 1\) (also \(z = - (n' - 1), z' = 1\) is possible).
Step 3:
Let us suppose that \(1 \lt n\).
\(gcd (\{n, n'\}) = 1\) means that \(n \lt n'\), because if \(n = n'\), \(gcd (\{n, n'\}) = n \neq 1\).
So, \(1 \lt n \lt n'\).
We think iteratively, so, let \(n_0 := n, n'_0 := n'\).
Let us take \(n'_0 - n_0 \in \mathbb{N} \setminus \{0\}\).
If \(n'_0 - n_0 = 1\), we are done, because \(-1 n_0 + 1 n'_0 = -1 n + 1 n' = 1\).
Let us suppose otherwise, which means that \(1 \lt n_0, n'_0 - n_0 \lt n'_0\).
\(n_0 \neq n'_0 - n_0\), because if \(n_0 = n'_0 - n_0\), \(n'_0 = 2 n_0\), which would mean that \(n_0\) was a common divisor where \(1 \lt n_0\), a contradiction.
So, \(n_0 \lt n'_0 - n_0\) or \(n'_0 - n_0 \lt n_0\).
\(gcd (\{n_0, n'_0 - n_0\}) = 1\), by 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.
When \(n_0 \lt n'_0 - n_0\), let \(n_1 := n_0, n'_1 := n'_0 - n_0\); when \(n'_0 - n_0 \lt n_0\), let \(n_1 := n'_0 - n_0, n'_1 := n_0\).
Then, \(1 \lt n_1 \lt n'_1\) with \(gcd (\{n_1, n'_1\}) = 1\), which means that the \(n_1, n'_1\) pair satisfies all the requirements for the \(n_0, n'_0\) pair, with the condition, \(n'_1 \lt n'_0\).
So, we do the same operation to the \(n_1, n'_1\) pair as has been done to the \(n_0, n'_0\) pair, to reach \(n'_1 - n_1 = 1\) or get the \(n_2, n'_2\) pair, with the condition, \(n'_2 \lt n'_1\), and so on.
The point is that as \(1 \lt n'_k \lt n'_{k - 1} \lt ... \lt n'_2 \lt n'_1 \lt n'_0\), the iteration cannot go on forever, which means that \(n'_l - n_l = 1\) happens for an \(l \in \mathbb{N}\).
But, \(n'_l - n_l = 1\) means that \(z n + z' n' = 1\) for some \(z, z' \in \mathbb{Z}\): \(n'_l - n_l\) is an integers coefficients linear combination of \(n_{l - 1}, n'_{l - 1}\), while \(n_{l - 1}, n'_{l - 1}\) are some integers coefficients linear combinations of \(n_{l - 2}, n'_{l - 2}\), which means that \(n'_l - n_l\) is an integers coefficients linear combination of \(n_{l - 2}, n'_{l - 2}\), ..., and so on, and \(n'_l - n_l\) is an integers coefficients linear combination of \(n_0 = n, n'_0 = n'\).
