$\begingroup$
I want to prove that in last step of Euclidean algorithm we have lcm representation
(by last step I mean the step with zero representation as $0 = x * E_0 + y * E_1$, where we apply euclidean algorithm for $E_0$ and $E_1$)
I can proof that statement $lcm(E_0, E_1) = |x * E_0| = |y * E_1| $ is equivalent to the statement that $gcd(x, y) = 1$
I can proof that we can consider only cases with $gcd(E_0, E_1) = 1$
I know that $x * y = lcm(x, y) * gcd(x, y)$
I also know that $lcm(x, y) = |x * E_0| = |y * E_1|$ (since $gcd(E_0, E_1) = 1$)
And here I stuck. I only can get some obvious relation like $E_0 = \frac{y}{gcd(x, y)}$ and $E_1 = \frac{x}{gcd(x, y)}$
Or, equivalently, $y = E_0 * gcd(x, y)$, $x = E_1 * gcd(x, y)$ (calculations up to sign, we can chose representation with $x \gt 0$ and omit all modules)
I thought we can prove more strong statement, i.e. on every step of euclidean algorithm, when we have representation $E_r = x_r * E_0 + y_r * E_1$, we always have $gcd(x_r, y_r) = 1$ and tried to prove it by induction, but there were too many variables
I suppose there should exist an easier way to prove it, but I can`t find it
$\endgroup$
1
I want to prove that in last step of Euclidean algorithm we have lcm representation
(by last step I mean the step with zero representation as $0 = x * E_0 + y * E_1$, where we apply euclidean algorithm for $E_0$ and $E_1$)
I can proof that statement $lcm(E_0, E_1) = |x * E_0| = |y * E_1| $ is equivalent to the statement that $gcd(x, y) = 1$
I can proof that we can consider only cases with $gcd(E_0, E_1) = 1$
I know that $x * y = lcm(x, y) * gcd(x, y)$
I also know that $lcm(x, y) = |x * E_0| = |y * E_1|$ (since $gcd(E_0, E_1) = 1$)
And here I stuck. I only can get some obvious relation like $E_0 = \frac{y}{gcd(x, y)}$ and $E_1 = \frac{x}{gcd(x, y)}$
Or, equivalently, $y = E_0 * gcd(x, y)$, $x = E_1 * gcd(x, y)$ (calculations up to sign, we can chose representation with $x \gt 0$ and omit all modules)
I thought we can prove more strong statement, i.e. on every step of euclidean algorithm, when we have representation $E_r = x_r * E_0 + y_r * E_1$, we always have $gcd(x_r, y_r) = 1$ and tried to prove it by induction, but there were too many variables
I suppose there should exist an easier way to prove it, but I can`t find it
-
$\begingroup$ Do you want a proof of something or simply a means of finding LCM? $\endgroup$poetasis– poetasis2020-08-14 20:37:23 +00:00Commented Aug 14, 2020 at 20:37
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
First, you find the GCD of two terms then multiply each term by the other-divided-by-GCD. For example $$x_1=10\quad\land\quad X_2=35\implies GCD(x_1,x_2)=5$$ $$LCM(x_1,x_2)=x_2\times\frac{x_1}{GCD(x_1,x_2)}=35\times\frac{10}{5}=70$$ or $$LCM(x_1,x_2)=x_1\times\frac{x_2}{GCD(x_1,x_2)}=10\times\frac{35}{5}=70$$ or $$LCM(x_1,x_2)=\frac{x_1\times x_2}{GCD(x_1,x_2)}=\frac{350}{5}=70$$
The algorithm for finding GCD is expressed in this simple [BASIC] program
100 input i1
110 input i2
120 x1 = i1
130 x2 = i2
140 r1 = x1 mod x2
150 c1 = c1+1
160 if r1 > 0
170 x1 = x2
180 x2 = r1
190 goto 140
200 endif
210 print "iterations( " c1 ")",;
220 print "GCD( " i1 ", " i2 ") = " x2
