×

# GCD property

Questions asks to confirm the property.

Note by Shivamani Patil
2 years, 3 months ago

Sort by:

$$c | (a+b) \rightarrow c|a \wedge c|b$$ is wrong. Easily counterexample as $$a = 4, b = 5, c = 3)$$. · 2 years, 3 months ago

Hint: use Bezout's identity · 2 years, 3 months ago

Another hint: $$(a,b) = 1$$ if and only if $$ax+by = 1$$. · 2 years, 3 months ago

Hey,@Samuraiwarm Tsunayoshi check my sol in Kartik Sharma's solution's replay box. · 2 years, 3 months ago

Let $$a = {{p}_{1}}^{{e}_{1}}{{p}_{2}}^{{e}_{2}}{{p}_{3}}^{{e}_{3}}..... {{p}_{n}}^{{e}_{n}}$$

Now, $$a = 0 mod {p}_{i}$$

We know that gcd(a,b) = 1, so none of the $${p}_{i}$$ divide b

$$cn = a + b$$

$$cn mod {p}_{1} = 0 + x$$

$$cn = x mod {p}_{1}$$

And so on, till $${p}_{n}$$ which tells us that $${p}_{i}$$ doesn't divide c. Therefore there is no common divisor of c and a, so, $$gcd(a,c) = 1$$

Similarly we can show for b.

@shivamani patil Check out and now I think it is fine. · 2 years, 3 months ago

If gcd(a,b) then $$ax+by=1$$ also $$cn=a+b$$ for some $$n$$ because $$c|a+b$$.Therefore $$cn-b=a$$,substituting $$cn-b=a$$ in first equation we get $$x(cn-b)+by=1=cnx-bx+by=c(nx)+b(y-x)$$ which implies gcd(c,b)=1.Similarly gcd(c,a)=1.@Kartik Sharma how is it??Your's is good. · 2 years, 3 months ago

But I solved it independently @Kartik Sharma · 2 years, 3 months ago

Yep, looks good. · 2 years, 3 months ago

Note that $$a|b$$ implies that there exists an integer $$k$$ suck that $$ka = b$$, not $$kb = a$$. So your assumption that $$c = n(a+b)$$ is wrong. It should be $$cn = a+b$$. · 2 years, 3 months ago

Oh damn yes ! I knew it but just a silly mistake. Now, I am gonna edit it. · 2 years, 3 months ago