Intereting Posts

Is this matrix positive semi-definite?
Infinitely many simple groups with conditions on order?
Automorphisms in $Z_n$
Calculate integrals $\int_0^1 {\frac{{\arcsin x}}{x}dx} $
$z_0$ non-removable singularity of $f\Rightarrow z_0$ essential singularity of $\exp(f)$
Why is a raised to the power of Zero is 1?
How is the set of all closed intervals countable?
Hard integral that standard CAS get totally wrong
How do I prove that 15462227 and 15462229 relatively prime?
Combinatorial identity's algebraic proof without induction.
Function always continuous in a Sobolev Space?
What shape is a Calippo?
nth convolved Fibonacci numbers of order 6 modulo m
Why does the semigroup commute with integration?
Show that $R/(I \cap J) \cong (R/I) \times (R/J) $

I’ve seen it said that you can prove Bezout’s Identity using Euclid’s algorithm backwards, but I’ve searched google and cannot find such a proof anywhere. I found another proof which looks simple but which I don’t understand.

Bezout’s lemma is:

```
For every pair of integers a & b there are 2 integers s & t such that as + bt = gcd(a,b)
```

Euclid’s algorithm is:

- How to solve this quadratic congruence equation
- If $\gcd(a,b)=1$ and $\gcd(a,c)=1$, then $\gcd(a,bc)=1$
- $x^5 + y^2 = z^3$
- If $a|b$ and $c|d$, then $ac|bd$
- Is this argument valid? (Number Theory)
- Proving the equivalency of Principle of Mathematical Induction and Well Ordering Principle

```
1. Start with (a,b) such that a >= b
2. Take reminder r of a/b
3. Set a := b, b := r so that a >= b
4. Repeat until b = 0
```

So here’s the proof by induction that I found on the internet:

```
Base case:
b = 0
gcd (a,b) = a
s = 1
t = 0
Inductive Step:
Assume Bezout's Lemma is true for all pairs of b < k.
a = qb + r with 0 =< r < b = k
gcd (a,b) = gcd (b,r)
By the inductive hypothesis there are integers x and y with bx and ry = gcd(a,b)
bx + ry = bx + (a - qb)y = b(x - qy) + ay = gcd(a,b)
Set t = (x - qy) and s = y. This establishes the identity for a pair (a,b) with b = k and completes the induction.
```

I only followed the proof up to the base case. I don’t see how it proved b = k from b < k. Could you please explain this to me?

Thanks.

EDIT: After two days of trying to figure it out I still don’t understand the proof. I conclude that either I lack the requisite knowledge or the intelligence or both. Thanks for trying to help.

- Reference request: Clean proof of Fermat's last theorem for $n=3$.
- Show $\,1897\mid 2903^n - 803^n - 464^n + 261^n\,$ by induction
- Find a positive integer $n$ such that $ϕ(n) = ϕ(n + 1) = ϕ(n + 2)$
- Is knowing the Sum and Product of k different natural numbers enough to find them?
- Given $a,b$, what is the maximum number which can not be formed using $na + mb$?
- Discussion on even and odd perfect numbers.
- Show that a Sophie Germain prime $p$ is of the form $6k - 1$ for $p > 3$
- Proving $\phi(m)|\phi(n)$ whenever $m|n$
- Conditions for which $n | {n \choose k}$ for all $k$
- $a^2-b^2 = x$ where $a,b,x$ are natural numbers

Here is a simple conceptual proof of Bezout’s identity for the gcd.

The set $\rm\:S\:$ of *all* integers of the form $\rm\:a\:x + b\:y,\,\ x,y\in \mathbb Z,\:$ is closed under subtraction so, by the Lemma below, every positive $\rm\:n\in S\:$ is divisible by $\rm\:d = $ least positive $\rm\in S,\:$ so $\rm\:a,b\in S\:$ $\Rightarrow$ $\rm\:d\:|\:a,b.\:$ So $\rm\:d\:$ is a *common* divisor of $\rm\:a,b,\:$ necessarily *greatest,* $ $ by $\rm\:c\:|\:a,b\:$ $\Rightarrow$ $\rm\:c\:|\:d = a\:x\!+\! b\:y\:$ $\Rightarrow$ $\rm\:c\le d.$

**Lemma** $\ \ $ If a nonempty set of positive integers $\rm\: S\:$ satisfies both $\rm\ n > m\: \in\, S \ \Rightarrow\ n-m\, \in\, S$

then every element of $\rm\:S\:$ is a multiple of the least element $\rm\:m_{\:1} \in\, S.$

**Proof 1** $\ $ If not there is a least nonmultiple $\rm\:n\in S,\,$ contra $\rm\:n-m_{\:1} \in S\:$ is a nonmultiple of $\rm\:m_{\:1}.$

**Proof 2** $\rm\ \ S\,$ closed under subtraction $\rm\:\Rightarrow\:S\,$ closed under remainder (mod), when it is $\ne 0,$ since mod may be computed by repeated subtraction, i.e. $\rm\: a\ mod\ b\, =\, a – k b\, =\, a-b-b-\cdots -b.\:$ Hence $\rm\:n\in S\:$ $\Rightarrow$ $\rm\: n\ mod\ m_1 = 0,\:$ else it is $\rm\,\in S\,$ and smaller than $\rm\:m_1,\:$ contra mimimality of $\rm\:m_1.$

**Remark** $\ $ In a nutshell, two applications of induction yield the following inferences

$$\rm\begin{eqnarray} S\ closed\ under\ subtraction &\:\Rightarrow\:&\rm S\ closed\ under\ mod = remainder = repeated\ subtraction \\

&\:\Rightarrow\:&\rm S\ closed\ under\ gcd = repeated\ remainder\ (Euclid’s\ algorithm) \end{eqnarray}$$

Interpreted constructively, this yields the extended Euclidean algorithm for the gcd. Namely, $ $ starting from the two elements of $\rm\,S\,$ that we know: $\rm\ a \,=\, 1\cdot a + 0\cdot b,\ \ b \,=\, 0\cdot a + 1\cdot b,\ $ we search for the least element of $\rm\,S\,$ by repeatedly subtracting elements to produce smaller elements of $\rm\,S\,$ (while keeping track of every elements linear representation in terms of $\rm\,a\,$ and $\rm\,b).\:$ This is essentially the *subtractive* form of the Euclidean algorithm (vs. the mod/remainder form).

The idea you allude to is doing euclids algorithm to find the gcd, then back substituting all the way to get the values to plug into the bezout equation.

Actually this is a waste of time, you can do both simultaneously! This is called Blankenship’s algorithm

You can read about it here http://mathworld.wolfram.com/BlankinshipAlgorithm.htm

- Is $\sqrt {2 \sqrt {3 \sqrt {4 \ldots}}}$ algebraic or transcendental?
- How many numbers of 6 digits, that can be formed with digits 2,3,9. And also divided by 3?
- how to find the order of an element in a quotient group
- Continuous deformations of points in $\mathbb{R}^n$ in a monotonic fashion
- Example of non-Noetherian non-UFD Krull domain?
- Levi Cevita and Kronecker Delta identity
- Let $Y$ be an ordered set in the order topology with $f,g:X\rightarrow Y$ continuous, show that $\{x:f(x)\leq g(x)\}$ is closed in $X$
- Rank of the sum of two positive semi-definite matrices
- Microeconomics (quasi-linear utility function)
- Orders of Elements in Minimal Generating sets of Abelian p-Groups
- The last two digits of $9^{9^9}$
- First Course in Linear algebra books that start with basic algebra?
- Proof regarding Robin's inequality (RI).
- Difference between lattice and complete lattice
- Prove that $f$ is one-to-one iff $f \circ h = f \circ k$ implies $h = k$.