 # Find the greatest common divisor (a, b) and integers m and n such that (a, b) = am + bn. a = 65, b = -91 a.) Explain in your own words what this probl sibuzwaW 2021-02-06 Answered
Find the greatest common divisor (a, b) and integers m and n such that (a, b) = am + bn.
a = 65, b = -91
b.) Explain the meaning of any notation used in the problem and in your solution.
c.) Describe the mathematical concept(s) that appear to be foundational to this problem.
You can still ask an expert for help

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it rogreenhoxa8

Step 1
a) The objective of the question is to find the gcd of two numbers and also to represent the gcd as a linear combination of the two numbers
b) the mathematical concept that will be used here is the Euclid's algorithm. It states that, given integers a,b,c find all integers x,y such that
c=xa+yb
Let d = gcd(a,b), and let b = b'd,a=a'd.Since xa+yb is a multiple of d for any integers x,y,solutions exist only when d divides c.
c) Given numbers are a = 65, b = -91.
Expressing the numbers as their prime factors,
a = 65 = 5 * 13
b = -91 = -7 * 13
Clearly, G.C.D.(65, -91) = 13.
Now, we want to find integers m and n such that 13 = 65m - 91n.
We shall proceed with Euclid's Algorithm. $-91=65\left(-2\right)+\left(39\right),0\le 39<65$
$⇒65=39\left(1\right)+26,0\le 26<39$
$⇒26\left(1\right)+13,0\le 13<26$
$⇒26=13\left(2\right)+0\le 0<13$
Step 3
We have already established that the G.C.D.(65,-91) is 13.
Now, tracing back the steps we get,
13=39-26,
$⇒13=39-\left(65-39\right)$
$⇒13=39\left(2\right)-65$
$⇒13=\left(-91+65\left(2\right)\right)\left(2\right)-65$
$⇒13=-91\left(2\right)+65\left(3\right)$
Thus the integers m and n are 3 and 2.