1
$\begingroup$

Let $\gcd(a,b,c)\mid e$ . Show that there exists integers $w,z$ such that $\gcd(a,b)w+cz=e$

Assume that $\gcd(a,b)=d$ then $a=dp,b=dq$.

Also there exists integers $m,n$ such that $am+nb=d$.

How to find integers $w,z$ such that $dw+cz=e$?

Can someone please give some hint?

$\endgroup$
1

1 Answer 1

2
$\begingroup$

It is known that (see wiki-page) the linear Diophantine equation $dw+cz=e$ has a solution $(w,z)$ if and only if $\gcd(d,c)$ divides $e$. But this is true because $$\gcd(d,c)=\gcd(\gcd(a,b),c)=\gcd(a,b,c).$$

$\endgroup$
7
  • $\begingroup$ I dont get it.can you elaborate? $\endgroup$
    – Charlotte
    Aug 16, 2019 at 14:33
  • $\begingroup$ What is your doubt? $\endgroup$
    – Robert Z
    Aug 16, 2019 at 14:34
  • $\begingroup$ Why is $\gcd(\gcd(a,b),c)=\gcd(a,b,c)$ $\endgroup$
    – Charlotte
    Aug 16, 2019 at 14:50
  • $\begingroup$ This is a known property of $\gcd$. See the 11th one here: en.wikipedia.org/wiki/Greatest_common_divisor#Properties $\endgroup$
    – Robert Z
    Aug 16, 2019 at 14:55
  • $\begingroup$ Oh okay,thank you so much sir $\endgroup$
    – Charlotte
    Aug 16, 2019 at 14:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .