OpenCart Templates
Saturday , July 22 2017
Home / Elementary Number Theory / If gcd(a, b) = d, then gcd(a/d, b/d) = 1

If gcd(a, b) = d, then gcd(a/d, b/d) = 1

Proof: Before starting with the proof proper, we should observe that although a/d and b/d have the appearance of the functions, in fact, they are integers because d is a divisor both of a and of b. Now, knowing that gcd(a, b) = d, it is possible to find integers x and y such that d = ax + by. Upon dividing each side of this equation by d, we obtain the expression

1 = (a/d)x + (b/d)y

Because a/d and b/d are integers, an appeal to the theorem is legitimate. The conclusion is that a/d and b/d are relatively prime. (Proved)

Check Also

Application of Euclidian’s algorithm in Diophantine equation

Problem-1: Which of the following Diophantine equations cannot be solved –   a) 6x + ...

Leave a Reply

Your email address will not be published. Required fields are marked *