English Deutsch Français Italiano Español Português 繁體中文 Bahasa Indonesia Tiếng Việt ภาษาไทย
All categories

Let a and b be integers not both 0, and let d be a natural number such that d divides a and d divides b. Prove that gcd(a,b)=d if and only if gcd(a/d,b/d)=1

2007-10-27 12:51:04 · 2 answers · asked by Anonymous in Science & Mathematics Mathematics

2 answers

If gcd(a/d, b/d) = f > 1
a/d = fm, b/d = fn, for some natural numbers m, n, where gcd(m,n) = 1
a = fd*m, b = fd*n
Thus, fd > d and fd is a common divisor of a and b ==> gcd(a,b) > d.
So, if gcd(a,b)=d, then gcd(a/d,b/d) must be 1.

If gcd(a/d, b/d) = 1, (assuming d divides both a and b)
a = dm, b = dn, for some natural numbers m, n, where gcd(m,n) = 1 (not related to above)
Thus, gcd(a,b) = d.

2007-10-27 13:21:08 · answer #1 · answered by back2nature 4 · 0 0

If if gcd(a/d,b/d) not = 1, then a and b are both divisible by some other number f < d.

2007-10-27 20:01:43 · answer #2 · answered by ironduke8159 7 · 0 0

fedest.com, questions and answers