The GCD Lemma can be extended to more than two numbers at a time. The case of th

ID: 3406365 • Letter: T

Question

The GCD Lemma can be extended to more than two numbers at a time. The case of three is as follows: Suppose that n, m, r elementof N such that no natural number greater than 1 divides all three. Then there are integers A, B, C such that An + Bm + Cr = 1. Below is a sketch of the proof. Fill in the details. Let g = gcd (n, m). Then there exists P, Q elementof Z such that Pn + Qm = g. Show that g and r must be relatively prime. Once you complete (B), there must be two other integers U, V elementof Z such that Ug + Vr = 1. Using P, Q, U and V, find formulas for integers A, B and C such that An + Bm + Cr = 1.

Explanation / Answer

Proof: Givin that n,m,r belongs to N .such that no natural number grater than 1 divides all three

implise that n,m,r are prime number.

if A,B,C are non zero integer then their GCD is a linear combination n,m,r that is An+Bm+Cr = gcd(m,n,r).

Let g = gcd(m,n) then there is P,Q belongs to Z then linear combination of n,m can be writen as Pn+Qm = gcd(m,n)

sincs g is a least posative integer such that g / m end given that m is prime implise that g is prime.

since r is an natural number and any number grater than 1 and other than itself not divides r. so r is a prime number

and hence g and r are relative prime as gcd(g,r ) =1.

now we know that if gand r are relativ primes then there exist two non zero integer U,V belongs to Z such that linear combination of U,V can be writen as Ug+Vr =gcd(g,r).and gcd(g,r)=1

therefore Ug+ Vr = 1.

finialy ,we see that linear combation of P,Q with m,n is g.and linearcombation of U,V with g,r is 1.also g=1

which gcd(n,m) & gcd(g,r)=1 therefore gcd(m,n,r) =1 so there exist non zero integer A,B,C such that linearcombination of A,B,C with n,m,r is equal to gcd(n,m,r) that is An+Bm+Cr = gcd(m,n,r).

hence An+Bm+Cr = 1.

Navigate

The GASB defines a financial reporting entity as the primary government and the

The GCD(Ax,By) by definition divides Ax ;as a result Ax must be some multiple of

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.

The GCD Lemma can be extended to more than two numbers at a time. The case of th

Question

Explanation / Answer

Related Questions

Navigate