# Bezout's Identity converse

#### zylo

Bezout's Identity:

If d = gcd(m,n), there exist integers A and B st d=Am+Bn. (proved by Euclid's algorithm}

1) Is there a converse?
2) How would you express it?
3) How would you prove it?

#### [email protected]

A partial converse is, if there are integers A and B such that Am+Bn=1, then gcd(m,n)=1.

• 1 person

#### zylo

A partial converse is, if there are integers A and B such that Am+Bn=1, then gcd(m,n)=1.

The following theorem is copied from Meserve, Fundamental Concepts of Algebra:
"Theorem 2-11. The greatest common divisor of any two positive integers m and n can be found as the last non-vanishing remainder n$$\displaystyle _{k}$$ in the Euclidean Algorithm. There exist integers A and B such that
(2-10) (m,n) = n$$\displaystyle _{k}$$ = Am + Bn"

For example: m=22, n=24
22=1x16+6, (22,16)=(16,6)
16=2x6+4, (16,6)=(6,4)
6=1x4+2, (6,4)=(4,2)=2
4=2x2, from which:
6=22-1x16
4=16-2x6=16-2x(22-1x6)=3x16-2x22
2=6-1x4=22-1x16-1x(3x16-2x22)=3x22-4x16=Ax22+Bx16
In this case n$$\displaystyle _{k}$$ is 2

Now the question. Again fron Meserve:
"The equation (2-10) is both necessary and sufficient for n$$\displaystyle _{k}$$ to be the greatest common divisor of m and n. It is necessary because of Theorem 2-11, and sufficient since if (2-10) holds, every common factor of m and n divides n$$\displaystyle _{k}$$."

What is this saying, ie, translate it into:
If "R" then "S".
If "S" then "R".
What are "R" and "S"

#### zylo

If n$$\displaystyle _{k}$$ is last non-zero remainder in Euclidean Algorithm, then n$$\displaystyle _{k}$$ is (m,n) and A and B exist st (m,n)=Am+Bn.

If n$$\displaystyle _{k}$$ is (m,n) and A and B exist st (m,n)=Am+Bn, then n$$\displaystyle _{k}$$ is last non-zero remainder in Euclidean Algorithm.

What's the point? n$$\displaystyle _{k}$$ is unique but A and B aren't.

Best I could come up with. Got a better idea?