Intereting Posts

Integral ${\large\int}_0^{\pi/2}\frac{\sin\left(x-a\ln2\cdot\tan x\right)}{\left(e^{2\pi a\tan x}-1\right)\cdot\cos x}\,dx$
How can you prove that $1+ 5+ 9 + \cdots +(4n-3) = 2n^{2} – n$ without using induction?
Unprovable statements in ZF
What is the significance of $\sigma$-fields in probability theory?
Help find the MacLaurin series for $\frac{1}{e^x+1}$
Are $\sigma$-algebras that aren't countably generated always sub-algebras of countably generated $\sigma$-algebras?
What justifies algebraic manipulation in equations with only variables?
Count Exclusive Partitionings of Points in Circle, Closing Double Recurrence?
Show this $\int_0^\infty \frac{t\ln(2\sinh t)}{\left(3t^2+\ln^2(2\sinh t)\right)^2}~dt=0$
If A and B are ideals of a ring, show that A + B = $\{a+b|a \in A, b \in B\}$ is an ideal
Geometric proof for inequality
Nonlinear system Diophantus.
Find smallest number which is divisible to $N$ and its digits sums to $N$
Relation between root of a function and its derivative
Examples on product topology $ \gg $ box topology?

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:

- Last 3 digits of $7^{12341}$
- If $N = q^k n^2$ is an odd perfect number with Euler prime $q$, and $k=1$, does it follow that $\frac{\sigma(n^2)}{n^2} \geq 2 - \frac{5}{3q}$?
- Math olympiad 1988 problem 6: canonical solution (2) without Vieta jumping
- When does $A(x^2+y^2+z^2)=B(xy + yz + xz)$ have nontrivial integer solutions?
- The number of summands $\phi(n)$
- Let $p_k$ be the $k$th prime, can it be shown for $p \ge 5$, that there is not always a twin prime between $p_k^2$ and $p_{k+1}^2$?

```
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.

- Novel approaches to elementary number theory and abstract algebra
- Shall remainder always be positive?
- How to prove there are no solutions to $a^2 - 223 b^2 = -3$.
- Do Lipschitz/Hurwitz quaternions satisfy the Ore condition?
- A type of integer numbers set
- Proving that $ \gcd(a,b) = as + bt $, i.e., $ \gcd $ is a linear combination.
- If the sum of positive integers $a$ and $b$ is a prime, their gcd is $1$. Proof?
- Inclusion-Exclusion Convergence
- Use induction to prove that that $8^{n} | (4n)!$ for all positive integers $n$
- My formula for sum of consecutive squares series?

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

- “Long-division puzzles” can help middle-grade-level students become actual problem solvers, but what should solution look like?
- Show that we cannot have a prime triplet of the form $p$, $p + 2$, $p + 4$ for $p >3$
- If series $\sum a_n$ is convergent with positive terms does $\sum \sin a_n$ also converge?
- how do we assume there is infinity?
- Algebraic values of sine at sevenths of the circle
- Is this determinant identity true?
- Sieve of Eratosthenes Refinement
- An nth-order ODE has n linearly independent solutions
- Matrix-product-integrals?
- Use the definition of “topologically conjugate” to prove that $F(x)=4x^3-3x$ is chaotic.
- A semigroup with identity having exactly one idempotent is a group
- Product topology and standard euclidean topology over $\mathbb{R}^n$ are equivalent
- Find the density of the sum of two uniform random variables
- What is a good book for learning Stochastic Calculus?
- The categories Set and Ens