10 points For integers x y and d we say that d is the greate

(10 points) For integers x, y, and d, we say that d is the greatest common divisor of x and y, written as d = gcd(x, y) if d is the largest number that divides both x and y. Note that it is always the case that gcd(x, y) 1. Show that if gcd(x, y) = d, then gcd( x d , y d ) = 1.

Solution

We prove by contradiction

Assume: gcd(x/d,y/d)=g>1

HEnce, x/d=mg

x=mgd

y/d=ng

y=ngd

HEnc, gd|y and gd|x

But, g>1 so gd>d. But , d is greatest common divisor of x and y.

Hence a contradiction

Hence, gcd(x/d,y/d)=1