Here I wrote about
why one of the integer solutions (paticular solution) of a linear Diophantine equation can be obtained by Euclidean algorithm.
I hope this will help those high school students who have learned the procedure of Euclidean algorithm and can use it for the time being, but are still puzzled as to why it can be used.
I hope it will be of help for such high school students.
If you understand the "why," you will not forget the procedure. And if you don't remember the procedure in the first place, this article will help you remember it and not forget it.
The main question.,,..,,,
Contents
Steps to find a particular solution to a linear Diophantine equation by Euclidean algorithm
As an example of a liner Diophanine equation, let's think about the following equation:
\( 23x + 16y = 1 \).
To find a particular solution of this, you would do the operation (Euclidean algorithm) in the following figure, right?
To put the procedure in words properly,
- Divide by the coefficients of \(x, y\) (here, \(23 and 16\)),
the larger one by the smaller one - Change the divisor and the obtained remainder to the dividend and divisor.
Then divide again - Repeat the step 2
Here, the divisions are expressed with this form:
\( (\text{dividend}) - (\text{divisor}) \times (\text{quotient}) = (\text{remainder}) \)
（from the beginning, instead of later）. In the class in your school or your textbook, the teacher or author may express the divisions, in the beginning, with this form
\( (\text{dividend}) = (\text{divisor}) \times (\text{quotient}) + (\text{remainder}), \)
and then, transform this from into the former form. But this is a mere extra work.
Actually, by repeating these tasks of divisions,
It's guaranteed that you will reach the remainder 1
without any division exactly divisible on the way,
which is what matters!
I shall explain later why this is guaranteed (shall make it be the title of the topic below), and let's go to the next flow for the time being.
The last expression（\(7 - 2 \times 3 = 1 \)）will become the equation（\(23x + 16y = 1 \)）as it is.
In other words,
the 1 of the last remainder = the 1 of the equation's right hand side,
and it's guaranteed that you can transform the LHS of the last expression like
\( 7 ~- ~2~ \times~ 3 = 23 ~×~ ? ~+~ 16 ~×~ ? \),
and furthermore, you can find (if hanging there) that the procedure of the expression transformation is given in the Eucliden algorithm.
In the end, this means that the pair of two "?" is one of the solutions（a particular solution).
That's the route until you reach a particular solution by Euclidean algorithm.
All that's left for you to understand "Why the particular solution obtained by Euclidean algorithm" should be only the two things below:
- Why you can reach the remainder 1 without any divisoin exactly divisible on the way
- Why the last expression with the remainder 1 can be definitely transformed into 23 × ? + 16 × ? = 1 .
The procedure of transformation.
I shall explain about these two belowwww.
Why can you reach the remainder 1
without any division exactly divisible?
Why by repeating those tasks of dividion, without exact divisibility, can you reach the remainder 1 evenyually, definitely?
There, what's important is that \(23\) and \(16\) are relatively prime (whose common divisor is only 1).
Besides, you need to be conscious of the following proposition.
Theorem
To put it in words, especially regarding the expression above as a division,
In a division by relatively prime numbers,
the remainder and divisor are also relatively prime definitely.
（By the way this is an interpretation of
"the greatest common divisor of \(a, b\) is that of \(b, r\)."
Well, you don't have to think about this now.）
The proof for this preposition can be written shortly. I shall write it below.
Let's assume that one of the common divisors of \(b, r\) is \(d\) and that \(b= b' d, r=r'd \). Then, (moving \(-bq\) to the RHS,) you can find
\(a= bq + r = (b'q + r') d \).
Therefore, since \(a= ( \text{integer}) \times d \), \(d\) is a dividor (aliquot part) of \(a\) as well.
Then, since \(d\) is a divisor of relatively prime \(a, b\) (←"relatively prime" is supposition, precondition), definitely \(d=1\).
therefore, \(b, r\) are relatively prime（ \(d=1\) is only one divisor of \(b, r\)).
QED.....,,,...
To put it in words words specifically about the above Euclidean algorithm,
\(23, 16\) are relatively prime. ⇒ So are \(16, 7\). ⇒ So are \(7, 2\).
Like that, "relatively prime" is chained to the following division.
Also, considering the remainder is definitely smaller than the divisor,
Every time you proceed to the next dividion, the divosor and diviend get smaller, which, furthermore, are always relatively prime, and the divisions are never exactly divisible. Therefor, you definitely reach the remainder 1 eventually.
Dat's it~~~
Why can the last expression
with the remeinder 1 be transformed into the problem's equation form?
For explanation, one technical term,,,,
23 × ? + 16 × ?（a sum of 23 and 16 multiplied by constants）is called
linear combination of 23 and 16.
This term may be used frequently not at high school but at college,
but it's a convenient expression.
For other examples, \(3\vec{a}+2\vec{b}\) and \(6f(x)-5g(x)\) are linear combinations of \(\vec{a}\), \(\vec{b}\) and \(f(x)\), \(g(x)\) respectively.
As you can find from the divisions in the above figure,
the remainder in a division is (can be expressed as) a linear combination of the divisor and diviend.
Also, a linear combination of linear combinations of \(23\) and \(16\) can be expressed as a linear combination of \(23\) and \(16\).
This is because, for example, as a linear combination of "\(\vec{a}\) & \(\vec{b}\) linear combinations" \(3\vec{a}+2\vec{b}\) and \(\vec{a}-\vec{b}\),
\( 2\times (3\vec{a}+2\vec{b}) + 3\times (\vec{a}-\vec{b}) = 9\vec{a}+\vec{b} \)
is a linear combination of \( \vec{a}, \vec{b}\) as well.
From those two things with red characters, in the above figure, you can find
\(7\) can be expressed as a linear combination of \(23, 16\),
and next, since \(2\) is expressed as a linear combination of \(16, 7\),
therefor \(2\) can be expressed as a linear combination of \(23, 16\),
and in the end, \(1\) is expressed as a linear combination of \(7, 2\),
therefore can be expressed as a linear combination of \(23, 16\).
These mean
"can be expressed as a linaer combination of \(23\) and \(16\)" is chained to the following divisions.
Dat's it..!.~~~
And the specific procedure of expression transformation is like the following...
Please substitute the expressions of the remainders except the last 1 (here 2and 7） as linaer combinations of the divisors and diviends (RHS) in the expression of the last remainder 1. Speciffically,
\( 7-2 \times 3 = 1 \)
is, by substituting \( 16 -7 \times 2 = 2 \) in it, transformed to
\( 7- (16 - 7 \times 2) \times 3 = 1 \) ⇔ \( 7 \times 7 - 16 \times 3 = 1 \)
is, by substituting \( 23 -16 \times 1 =7 \) in it, transformed to
\( (23 - 16 \times 1 ) \times 7 -16 \times 3 = 1 \) ⇔ \( 23 \times 7 - 16 \times 10 = 1 \).
In this way, as a particular solution of \(23x + 16y = 1 \),
\( (x,y) = (7, 10) \) has been gotten.
（Perhaps, u ain't familiar with the symbol "⇔". This means equivalence or having same meaning.）
Summay
From the above, What matter about "why is the particular solution can be obtained by Euclidean algorithm?" are
- In the Eucliden algorithm beginning from the two relatively-prime numbers,
It's guaranteed that you reach the remainder 1 eventually, - A linear combination of linear combinatoins of \(m\) and \(n\) (a sum of the two with constant factors) can be expressed as a linear combination of \(m\) and \(n\) as well.
Here, "\(m\) and \(n\)" are, for example, "\(23\) and \(16\)", "\(\vec{a}\) and \(\vec{b}\)" or "\(f(x)\) and \(g(x)\)", which are arbitary addible two. - In the divisions, pay attention to the chain of "relatively prime" and "can be expressed as a linear combination".
Do you think this theory is too well-made? Even though I can understand why the algorithm can be used, I wonder how such a well-made method can be come up with.
Strongest-ish Mr. Euclid.
Thank you for having read until here,,,appreciate you..
Aside
If you understand the above, you can also find
all integers can be expressed as linear combinations of two relatively prime integers.
(Dat may be obvious, or not really)
If possible, please try thinking why this is true