Let a, b, c be integers, not all three equal to zero. The gcd of a,b,c denoted b

Question

Let a, b, c be integers, not all three equal to zero. The gcd of a,b,c denoted by gcd(a,b,c) is the positive integer d satisfying the following: 1) d|a, d|b, d|c 2) if m|a, m|b, and m|c, then m < or = d. Show that d is the smallest of the set S={au+bv+cw| au +bv+cw<0, u, v, w e Z} Let a, b, c be integers, not all three equal to zero. The gcd of a,b,c denoted by gcd(a,b,c) is the positive integer d satisfying the following: 1) d|a, d|b, d|c 2) if m|a, m|b, and m|c, then m < or = d. Show that d is the smallest of the set S={au+bv+cw| au +bv+cw<0, u, v, w e Z}

Explanation / Answer

consider S = { au + bv + cw / au + bv + cw > 0 and u,v,w are integers}
given d = gcd ( u,v, w)
putting u = 1, v= w = 0, we get au + bv + cw= a so, a is in S and so, S is non empty set of positive integers. by the consequence of Well ordering principle S must have the smallest element. let the smallest element of S is k. we have to show that k is the greatest common divisor of u , v , and w. since k is in S, by definition of S, there exists a pair of integers, p , q, r such that k = pu + qv + r w. now, k is the smallest of S and  a is the integer, by division algorithm, there exists integers t, s such that  a = kt + s where t, s are integers and 0 less than or equal to s < k. now, suppose s < k. since s = u - kt, where d and k are members of S, we get s < d is the member of S. since s is non negative and a linear combination of members of S, we get s is also in S. since s < k, we get s is the smallest element of S. this is a contradiction to the minimality of k in S. so, our supposition is wrong. ? a = kt. i.e. k | a. with a similar argument, we get k | b and k | c so, k is the common divisor of a,b,c. ---(2) we have to show that any common divisor of a,b,c divides k and claim that k is the smallest element of S. for, x is a common divisor of a,b, c, we have x | au , x | bv and x | cw for some integers u,v, and w. consequently, x | k. that means every common multiple of a,b,c divides k. so, the greatest common divisor k is the smallest member of S. that means d is greater than any other common divisor of u,v,w. so, d is the greatest common divisor of u,v,w. i.e. d is a multiple of k.

Related Questions

Navigate

• Browse (All)
• Browse L
• Subjects

---

---

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