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
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.
You can still ask an expert for help

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question

Expert Answer

rogreenhoxa8
Answered 2021-02-07 Author has 109 answers

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(2)+(39),039<65
65=39(1)+26,026<39
26(1)+13,013<26
26=13(2)+00<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(6539)
13=39(2)65
13=(91+65(2))(2)65
13=91(2)+65(3)
Thus the integers m and n are 3 and 2.

Not exactly what you’re looking for?
Ask My Question

Expert Community at Your Service

  • Live experts 24/7
  • Questions are typically answered in as fast as 30 minutes
  • Personalized clear answers
Learn more

Solve your problem for the price of one coffee

  • Available 24/7
  • Math expert for every subject
  • Pay only if we can solve it
Ask Question