User Name Remember Me? Password

 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: 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? 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 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 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" 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? Tags bezout, converse, identity Thread Tools Show Printable Version Email this Page Display Modes Linear Mode Switch to Hybrid Mode Switch to Threaded 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      