sibuzwaW

2021-02-06

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 problem is asking.
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.

### Answer & Explanation

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.

Do you have a similar question?

Recalculate according to your conditions!