1086: 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

<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 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
• Target Context
• Orientation
• Main Body
• 1: Structured Description
• 2: Proof

---

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^{\prime }$: $\in \mathbb{N}$ such that $n\le n^{\prime }$
//

Statements:
$gcd(\{n,n^{\prime }\})=1$, where $gcd(\bullet )$ denotes the greatest common divisor of the argument
$⟹$
$\mathrm{\exists }z,z^{\prime }\in \mathbb{Z}(zn+z^{\prime }{n}^{\prime }=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<n$.

Step 1:

Let us suppose that $n=0$.

$gcd(\{n,n^{\prime }\})=1$ means that $n^{\prime }=1$.

So, there are $z=0,z^{\prime }=1$ such that $zn+z^{\prime }{n}^{\prime }=1$.

Step 2:

Let us suppose that $n=1$.

$n^{\prime }$ can be any.

But anyway, there are $z=1,z^{\prime }=0$ such that $zn+z^{\prime }{n}^{\prime }=1$ (also $z=-(n^{\prime }-1),z^{\prime }=1$ is possible).

Step 3:

Let us suppose that $1<n$.

$gcd(\{n,n^{\prime }\})=1$ means that $n<n^{\prime }$, because if $n=n^{\prime }$, $gcd(\{n,n^{\prime }\})=n\ne 1$.

So, $1<n<n^{\prime }$.

We think iteratively, so, let $n_0:=n,n_0^{\prime }:=n^{\prime }$.

Let us take $n_0^{\prime }-n_0\in \mathbb{N}\setminus \{0\}$.

If $n_0^{\prime }-n_0=1$, we are done, because $-1n_0+1n_0^{\prime }=-1n+1n^{\prime }=1$.

Let us suppose otherwise, which means that $1<n_0,n_0^{\prime }-n_0<n_0^{\prime }$.

$n_0\ne n_0^{\prime }-n_0$, because if $n_0=n_0^{\prime }-n_0$, $n_0^{\prime }=2n_0$, which would mean that $n_0$ was a common divisor where $1<n_0$, a contradiction.

So, $n_0<n_0^{\prime }-n_0$ or $n_0^{\prime }-n_0<n_0$.

$gcd(\{n_0,n_0^{\prime }-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<n_0^{\prime }-n_0$, let $n_1:=n_0,n_1^{\prime }:=n_0^{\prime }-n_0$; when $n_0^{\prime }-n_0<n_0$, let $n_1:=n_0^{\prime }-n_0,n_1^{\prime }:=n_0$.

Then, $1<n_1<n_1^{\prime }$ with $gcd(\{n_1,n_1^{\prime }\})=1$, which means that the $n_1,n_1^{\prime }$ pair satisfies all the requirements for the $n_0,n_0^{\prime }$ pair, with the condition, $n_1^{\prime }<n_0^{\prime }$.

So, we do the same operation to the $n_1,n_1^{\prime }$ pair as has been done to the $n_0,n_0^{\prime }$ pair, to reach $n_1^{\prime }-n_1=1$ or get the $n_2,n_2^{\prime }$ pair, with the condition, $n_2^{\prime }<n_1^{\prime }$, and so on.

The point is that as $1<n_k^{\prime }<n_{k-1}^{\prime }<...<n_2^{\prime }<n_1^{\prime }<n_0^{\prime }$, the iteration cannot go on forever, which means that $n_l^{\prime }-n_l=1$ happens for an $l\in \mathbb{N}$.

But, $n_l^{\prime }-n_l=1$ means that $zn+z^{\prime }{n}^{\prime }=1$ for some $z,z^{\prime }\in \mathbb{Z}$: $n_l^{\prime }-n_l$ is an integers coefficients linear combination of $n_{l-1},n_{l-1}^{\prime }$, while $n_{l-1},n_{l-1}^{\prime }$ are some integers coefficients linear combinations of $n_{l-2},n_{l-2}^{\prime }$, which means that $n_l^{\prime }-n_l$ is an integers coefficients linear combination of $n_{l-2},n_{l-2}^{\prime }$, ..., and so on, and $n_l^{\prime }-n_l$ is an integers coefficients linear combination of $n_0=n,n_0^{\prime }=n^{\prime }$.

---

References

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