Show that if d is a common divisor of x and y, then d divides ax + by for every

Question

Show that if d is a common divisor of x and y, then d divides ax + by for every a, b in Z. (Note: ax + by is usually referred to as an integer linear comb y simply because a and b are integers.) Let q,x,y,r in Z such that x = qy + r. a) Show that if an integer d is a common divisor of x and y, the divisor of y and r. b) Show that if an integer d is a common divisor of y and r, the divisor of x and y. c) Show that gcd(x,y) = gcd (y, r). (You may assume that x, y Given that 221 and 7 are relatively prime, that is gcd(221, 7) b such that 221a + 7b = 1.

Explanation / Answer

if d divides x and y
then, we can write x=s*d and y=t*d where t and s are integers

=>ax+by=asd+tbd=(as+tb)d
cleary, (as+tb) is an integer as a,s,t,d are integers
which implies d divides ax+by

a)
x=qy+r
=>r=x-qy
if d divides x and y
then, we can write x=s*d and y=t*d where t and s are integers
=>r=sd-qtd=(a-qt)d
as (a-qt) is an integer, clearly d divides r
so d is common divisor of y and r
b)
x=qy+r

if d divides r and y
then, we can write r=s*d and y=t*d where t and s are integers
=>x=sd+qtd=(a+qt)d
as (a+qt) is an integer, clearly d divides x
so d is common divisor of x and y
c)
now let p=gcd(x,y)
z=gcd(y,r)

from a) part of the question it is proved that if p divides x,y
then p will divide y,r
from b)part of the question it is proved that if z divides y,r
then z divides x,y
=> the highest factor that divides x,y will also divide y,r and vice versa
so, it can be conluded that z=p
=>gcd(x,y)=gcd(y,r)

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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