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}\)</span>

\(\Rightarrow{65}={39}{\left({1}\right)}+{26},{0}\le{26}<{39}\)</span>

\(\Rightarrow{26}{\left({1}\right)}+{13},{0}\le{13}<{26}\)</span>

\(\Rightarrow{26}={13}{\left({2}\right)}+{0}\le{0}<{13}\)</span>

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,

\(\Rightarrow{13}={39}-{\left({65}-{39}\right)}\)

\(\Rightarrow{13}={39}{\left({2}\right)}-{65}\)

\(\Rightarrow{13}={\left(-{91}+{65}{\left({2}\right)}\right)}{\left({2}\right)}-{65}\)

\(\Rightarrow{13}=-{91}{\left({2}\right)}+{65}{\left({3}\right)}\)

Thus the integers m and n are 3 and 2.

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}\)</span>

\(\Rightarrow{65}={39}{\left({1}\right)}+{26},{0}\le{26}<{39}\)</span>

\(\Rightarrow{26}{\left({1}\right)}+{13},{0}\le{13}<{26}\)</span>

\(\Rightarrow{26}={13}{\left({2}\right)}+{0}\le{0}<{13}\)</span>

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,

\(\Rightarrow{13}={39}-{\left({65}-{39}\right)}\)

\(\Rightarrow{13}={39}{\left({2}\right)}-{65}\)

\(\Rightarrow{13}={\left(-{91}+{65}{\left({2}\right)}\right)}{\left({2}\right)}-{65}\)

\(\Rightarrow{13}=-{91}{\left({2}\right)}+{65}{\left({3}\right)}\)

Thus the integers m and n are 3 and 2.