$\begingroup$

I tried to prove it with linear combination.

Also other information,

• $h*\gcd(m, n)=h*am+h*bn$
• At each iteration $i$, $y_i=x_iq+r$
• Last iteration $t$, so $x_t=\gcd(m, n)$.

Base case: Iteration t. $x_t=h_t*\gcd(m, n)=h_t*am+h_t*bn$. Last iteration, $x_t=\gcd(m, n)$, so $h_t = 1$. Hence, $\gcd(m, n)=am+bn$

I don't know how to prove that m, n are positive integers and a, b are integer.

Assume iteration k, $x_k=h_k*\gcd(m, n)=h_k*am+h_k*bn$, for some integer h, $x_k$ is a multiple of gcd.

We need to prove $x_{k+1}=h_{k+1}*\gcd(m, n)=h_{k+1}*am+h_{k+1}*bn$.

I don't know is that correct, if it is wrong, please tell me

Also, I don't know is this prove correct.

$\endgroup$ 10

3 Answers

$\begingroup$

The simplest is to prove the basis of the extended euclidean algorithm: at each step of the euclidean algorithm, the remainder is a linear combination of $m$ and $n$.

Let's fix some notations: we have a sequence of euclidean divisions\begin{alignat}{2} m&=q_1n&&+r_1 \\ n&=q_2 r_1 &&+r_2 \\ \vdots&&&\phantom{+}\!\!\vdots \\ r_{i-1}&=q_{i+1}r_i&&+r_{i+1}\\ \vdots&&&\phantom{+}\!\!\vdots \\ \end{alignat}and we rewrite the $(i+1)$th step as$$r_{i+1}=r_{i-1}-q_{i+1}r_i,\tag{1}$$so that we can make an induction of order $2$:

• Initialisation: conventionally, $r_{-1}=m,\: r_0=n$, and we can write$$r_{-1}=1\cdot m+0\cdot n,\qquad r_0=0\cdot m+1\cdot n.$$
• Inductive step: if we suppose $r_{i-1}=a_{i-1}m+b_{i-1}n,\quad r_i=a_i m+b_in$, and using $(1)$, we deduce instantly that$$r_{i+1}=(a_{i-1}-q_{i+1}a_i)m+(b_{i-1}-q_{i+1}b_i)n.$$

$\endgroup$ $\begingroup$

So we need to prove $ h_{k+1} * $ gcd $ (m,n) = h_{k+1} * am + h_{k+1} * bn $

Actually this is Bezout's Identity. It states $ax+by=$gcd$(a,b)$. So are you in a good position to complete the proof OP?

Edit: Just as Magdiragdag wrote in comments:

"Actually a and b are just random integers. Once write down really exactly what you are trying to prove and you'll see that the base case is totally trivial"

$\endgroup$ 2 $\begingroup$

Let $k = \gcd(m,n)$. This implies that $m=kc$ and $n=kd$ for some integers $c$ and $d$, such that $\gcd(c,d)=1$. Now, it is only necessary to prove that two integers exist such that $ac+bd=1$, as one can then multiply both sides by $k$ to solve the original problem.

$$ac+bd=1 \implies \frac {ac}{d}+b=\frac {1}{d} \implies ac \equiv 1 \pmod d$$

Further equivalent to proving that some $a$ exists such that, for at least one value of $n$,

$$ac=nd+1$$

Edit: my bad, I didn't notice the request for this to be in induction.

$\endgroup$