Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By Idea

Thread: Proof if gcf (a, b) = 1

  1. #1
    Ell
    Ell is offline
    Newbie
    Joined
    Oct 2017
    From
    Helsinki
    Posts
    2

    Proof if gcf (a, b) = 1

    Is it correct that if there exists coefficients m and n such that ma + nb = 1, gcf (a, b) = 1? I assume it's right but I wanted to double check...
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    742
    Thanks
    341

    Re: Proof if gcf (a, b) = 1

    it is correct
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    11,071
    Thanks
    708
    Awards
    1

    Re: Proof if gcf (a, b) = 1

    Quote Originally Posted by Ell View Post
    Is it correct that if there exists coefficients m and n such that ma + nb = 1, gcf (a, b) = 1? I assume it's right but I wanted to double check...
    Ach! I finally recalled the name of it. You are looking for the Euclidean algorithm, specifically the section on Euclid's lemma.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Jun 2013
    From
    Lebanon
    Posts
    742
    Thanks
    341

    Re: Proof if gcf (a, b) = 1

    Theorem: ma+nb=1 implies gcd(a,b)=1
    Proof:
    If d divides a and b, then d divides 1 using basic properties of divisibility and therefore gcd(a,b)=1

    conversely,
    Given gcd(a,b)=1 there exist integers m,n such that ma+nb=1

    to find m and n we can use the division algorithm
    Thanks from topsquark
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 4
    Last Post: Feb 21st 2015, 06:44 AM
  2. [Abstract Algebra] Anyone care to proof-read a proof?
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: Dec 4th 2012, 02:13 PM
  3. Replies: 5
    Last Post: Oct 19th 2010, 11:50 AM
  4. Replies: 0
    Last Post: Jun 29th 2010, 09:48 AM
  5. proof that the proof that .999_ = 1 is not a proof (version)
    Posted in the Advanced Applied Math Forum
    Replies: 4
    Last Post: Apr 14th 2008, 05:07 PM

/mathhelpforum @mathhelpforum