Find GCD of a and b: Express as Integer Combination

In summary, the conversation resolved around finding the greatest common divisor (gcd) of two integers, a and b, and expressing it as an integer combination of ra + sb. The Euclidean algorithm was used to quickly find the gcd, which was determined to be 3. However, there was uncertainty on how to approach the second part of the problem, which involved finding integer multiples of a and b to obtain the desired result. A helpful resource was provided, which explained a method to solve this problem in a systematic way. This method involves using a proof and example to demonstrate its effectiveness. "
  • #1
achacttn
7
0
RESOLVED

Homework Statement



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

Homework 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.

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:
Physics news on Phys.org
  • #2


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

He gives a proof of the method, and then gives an example of it in action.
 
Last edited by a moderator:
  • #3


Thanks !
 

Related to Find GCD of a and b: Express as Integer Combination

1. What is the GCD of two numbers?

The GCD (Greatest Common Divisor) of two numbers is the largest positive integer that divides both numbers without leaving a remainder.

2. How do you find the GCD of two numbers?

The GCD of two numbers can be found by using the Euclidean algorithm, which involves repeatedly dividing the larger number by the smaller number and using the remainder as the new divisor until the remainder is 0.

3. Can the GCD of two numbers be negative?

No, the GCD is always a positive integer. If the two numbers are negative, the GCD will still be positive.

4. What is an integer combination?

An integer combination of two numbers a and b is a linear combination of a and b, where the coefficients are integers. In the context of finding the GCD, the integer combination refers to the expression of the GCD as a linear combination of a and b.

5. Why is finding the GCD important?

Finding the GCD is important in many mathematical applications, such as simplifying fractions, reducing fractions to lowest terms, and solving linear Diophantine equations. It is also used in computer algorithms, such as the RSA encryption algorithm.

Similar threads

Proving gcd(a+b,ab) = 1 for Relatively Prime Numbers
Replies
4
Views
1K
Use the Euclidean algorithm to find integers ## a, b, c ##
Replies
5
Views
1K
Let d = gcd(a, b), prove kd = gcd(ka, kb)
Replies
1
Views
8K
Number Theory. If d=gcd(a,b,c) then d is a linear combination of a,b, and c
Replies
1
Views
3K
Proving the GCD Property: A Challenge for Algebra Students
Replies
1
Views
2K
O(log k) GCD Algorithm which yields x and y |GCD(a,b)=ax+by
Replies
1
Views
1K
Solve Modular Inverses Homework
Replies
2
Views
2K
MHB Representation of signed integers of base B
Replies
17
Views
1K
MHB Booth algorithm for multiplying signed numbers
Replies
1
Views
1K
Is This the Correct Approach to Finding GCD and LCM for Integer Pairs?
Replies
5
Views
2K

Hot Threads

Recent Insights

Back
Top