My Math Forum  

Go Back   My Math Forum > College Math Forum > Abstract Algebra

Abstract Algebra Abstract Algebra Math Forum


Thanks Tree1Thanks
  • 1 Post By Micrm@ss
Reply
 
LinkBack Thread Tools Display Modes
January 5th, 2019, 10:56 AM   #1
Banned Camp
 
Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 126

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?
zylo is offline  
 
January 5th, 2019, 11:04 AM   #2
Senior Member
 
Joined: Oct 2009

Posts: 867
Thanks: 330

A partial converse is, if there are integers A and B such that Am+Bn=1, then gcd(m,n)=1.
Thanks from zylo
Micrm@ss is offline  
January 7th, 2019, 11:01 AM   #3
Banned Camp
 
Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 126

Quote:
Originally Posted by Micrm@ss View Post
A partial converse is, if there are integers A and B such that Am+Bn=1, then gcd(m,n)=1.
Answer correct but wrong question.

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 is offline  
January 9th, 2019, 07:49 AM   #4
Banned Camp
 
Joined: Mar 2015
From: New Jersey

Posts: 1,720
Thanks: 126

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?
zylo is offline  
Reply

  My Math Forum > College Math Forum > Abstract Algebra

Tags
bezout, converse, identity



Thread Tools
Display Modes


Similar Threads
Thread Thread Starter Forum Replies Last Post
Stating the converse, converse of if x=y then x^2 = y^2? Tangeton Algebra 3 April 8th, 2016 08:00 AM
Circle theorems and their converse Tangeton Geometry 1 March 10th, 2016 07:40 PM
Is there a statement equivalent to its own converse? RyanPowers Applied Math 3 September 17th, 2014 08:19 AM
Set theory. Is the converse true? omoplata Applied Math 1 June 11th, 2011 05:59 AM
Bezout's identity and odd co primes Euzenius Number Theory 3 July 16th, 2009 10:41 AM





Copyright © 2019 My Math Forum. All rights reserved.