For positive integers a and b, show that gcd(a, b) = gcd(a, a + b). Direction: L

Question

For positive integers a and b, show that gcd(a, b) = gcd(a, a + b). Direction: Let d = gcd(a, b). Using definition 2.7.6 show that d = gcd(a,a + b). Can be generalized to gcd(a, b) = gcd(a, ax + b), where x is any positive integer? If this extension is valid, prove it, if it is false, provide a counterexample. Given positive integers a and b, show that if gcd(a, b) = d, then gcd(a^2, b^2) = d^2. Generalize for any positive integer n. Justify each of the following statements for positive integers a, b, and c: If gcd(a, b) = 1, then gcd(a^2,b^2) = 1. Generalize for any positive integer n. If gcd(a, b) = 1, then gcd(a + b,ab) = 1. Direction: Let d = gcd(a + b, ab). Show that d|a^2 and d|b^2, and then use . If gcd(a, b) = 1 andgcd(a,c) = 1, then gcd(a, bc) = 1. If gcd(a, b) = 1 and ab is a square, then both a and b are squares. If gcd(a, b) = 1 and a|c and b|c, then ab|c. Prove: For positive integers a, b, and c, if gcd(a, b) = 1 and c|(a + b), then gcd(c,a) = 1 and gcd(c,b) = 1. Direction: Let di = gcd(c,a) and d_2 = gcd(c,b). Show that d_1 and d_2 are common divisors of a and b. Prove that gcd(ca,cb) = c. gcd(a, b), where a, b, and c are positive integers (cf., 2.8.4). Give one proof using prime factorization, and give an alternate proof analogous to the 1cm alternate argument presented in this section (cf., 2.8.3, alternate argument).

Explanation / Answer

8. (a)

Suppose gcd(a,b)=1 then you have ax+by=1,

cubing this, we get (ax+by)3=1

i.e., a3x3+b3y3+3a2x2by+3axb2y2=1

i.e., a2(ax3+3x2by)+b2(by3+3axy2)=1

i.e a2X+b2Y=1

i.e gcd(a2,b2)=1

(b)

Suppose gcd(a,b)=1 then you have ax+by=1

Squaring both sides, we see that

a2x2+2abxy+b2y2=1.

But notice that

a2x2+2abxy+b2y2=ab(2xyx2y2)+(a+b)(ax2+by2).

And hence, those same x,y

as above give

ab(2xyx2y2)+(a+b)(ax2+by2)=1.

So it must be that gcd(a+b,ab)=1

(c) Suppose gcd(a,b)=1and gcd(a,c)=1

then we have, there are x,y,u,v so that ax+by=1 and au+cv=1, we have

bycva(x+uaxu)+bcvy=(1ax)(1au)=1a(x+uaxu)=1

Therefore, (a,bc)=1

(e)Suppose a divides c and b divides c and gcd(a,b)=1

i.e c=as and c-bt and also ax+by=1

Implies c=acx+bcy=abxt+baxs=ab(xt+ys)

Implies ab divides c

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

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