1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Abstract algebra/elementary number theory: Express d as integer combination ra + sb

  1. Aug 11, 2012 #1
    RESOLVED


    1. The problem statement, all variables and given/known data

    Let a = 123, b = 321. Compute d = gcd(a,b) and express d as an integer combination of ra + sb.


    2. Relevant equations

    This is a question (3.1, page 70 of Michael Artin's Algebra). For those who do not have the book, this problem is relevant to the section on subgroups of the additive groups of integers.


    3. The attempt at a solution

    I quickly found d using the Euclidean algorithm (d=3). However, I'm unsure how to approach the 2nd part. So far, it just seems like brute-forcing integer multiples of a and b on a calculator and hoping the difference comes out as |3|.

    Any help or point in the right direction would be much appreciated.
     
    Last edited: Aug 11, 2012
  2. jcsd
  3. Aug 11, 2012 #2
    Re: Abstract algebra/elementary number theory: Express d as integer combination ra +

    Here's an exposition of a neat way to do it: http://www.millersville.edu/~bikenaga/number-theory/exteuc/exteuc.html [Broken]

    He gives a proof of the method, and then gives an example of it in action.
     
    Last edited by a moderator: May 6, 2017
  4. Aug 11, 2012 #3
    Re: Abstract algebra/elementary number theory: Express d as integer combination ra +

    Thanks !
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Abstract algebra/elementary number theory: Express d as integer combination ra + sb
Loading...