2
$\begingroup$

Can someone help me understand this statement:

If $ax+by=d$ then $\gcd(a,b)$ divides $d$.

Bezout's identity states that:

the greatest common divisor $d$ is the smallest positive integer that can be written as $ax + by$

However the definition of $\gcd(a, b)$ is the largest positive integer which divides both $a$ and $b$.

I'm am completely lost. If anyone could provide some sort of layout to help me sort this out I would be really happy.

$\endgroup$
  • $\begingroup$ What you say is true. What is exactly what you don't understand? Do you want a proof? Examples? Further explanations? $\endgroup$ – ajotatxe Jul 13 '15 at 19:15
  • $\begingroup$ Hint: write it out. that is, let g be gcd(a,b) and write a = gA and b = gB. $\endgroup$ – lulu Jul 13 '15 at 19:17
2
$\begingroup$

Take a common divisor $k$ of $a$ and $b$. That means that we can write $a=ka'$, $b=kb'$. Then, if $d=ax+by$, $$d=a'kx+b'ky=k(a'x+b'y)$$ so we see that $k$ also divides $d$. Since $\gcd(a,b)$ is a common divisor of $a$ and $b$ (namely, the greatest), it also holds the property. Actually, the idea behind this is very simple: the sum of two multiples of the same number is also a multiple of the same number.

Note that $\gcd(a,b)$ is, hence, the least positive integer that can be written as $ax+by$, because every number of the form $ax+by$ must be a multiple of any common divisor of $a$ and $b$, and in particular, must be a multiple of $\gcd(a,b)$ so $ax+by$ can't be smaller than it (being still positive, of course).

Example: let $a=60$, $b=75$. The gcd is $15$, so $ax+by=60x+75y$ must be a multiple of $15$, because it is the sum of two multiples of $15$.

I hope this helps a bit.

$\endgroup$
  • $\begingroup$ so in terms of expressing gcd(a, b) = 15, that means there is a $specific$ x,y that will make ax + by = 15? And 15 is the smallest possible number to come out of the linear combination of a and b? However the gcd(a,b) is also the greatest possible number to divide both a and b? So it is just two different ways of expressing it right? $\endgroup$ – Rdewolfe Jul 13 '15 at 19:31
1
$\begingroup$

Hint: For three numbers $a,b,c$, if $c$ divides $a$ and $c$ divides $b$, then $c$ divides $a+b$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.