My Math Forum Bezout's Identity converse

 Abstract Algebra Abstract Algebra Math Forum

 January 5th, 2019, 10:56 AM #1 Banned Camp   Joined: Mar 2015 From: New Jersey Posts: 1,720 Thanks: 125 Bezout's Identity converse 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?
 January 5th, 2019, 11:04 AM #2 Senior Member   Joined: Oct 2009 Posts: 798 Thanks: 298 A partial converse is, if there are integers A and B such that Am+Bn=1, then gcd(m,n)=1. Thanks from zylo
January 7th, 2019, 11:01 AM   #3
Banned Camp

Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 125

Quote:
 Originally Posted by Micrm@ss 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"

 January 9th, 2019, 07:49 AM #4 Banned Camp   Joined: Mar 2015 From: New Jersey Posts: 1,720 Thanks: 125 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?

 Tags bezout, converse, identity

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Tangeton Algebra 3 April 8th, 2016 08:00 AM Tangeton Geometry 1 March 10th, 2016 07:40 PM RyanPowers Applied Math 3 September 17th, 2014 08:19 AM omoplata Applied Math 1 June 11th, 2011 05:59 AM Euzenius Number Theory 3 July 16th, 2009 10:41 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top