6
$\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$
2
  • $\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, 2015 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, 2015 at 19:17

3 Answers 3

5
$\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$
1
  • $\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, 2015 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$
0
$\begingroup$

I'd like to offer a perspective from algebra that made it click for me. Consider John B. Fraleigh's definition from 'Introduction to Abstract Algebra':

Let $r$ and $s$ be two positive integers. The positive generator $d$ of the cyclic group $H = \{nr + ms \mid m,n \in \mathbb{Z}\}$ under addition is the $\textbf{greatest common divisor}$ of $r$ and $s$.

Let's consider a numeric example, same as above: $r = 60$ and $s = 75$. Their gcd is obviously $d = 15$ and all the multiples of $15$ are in $H$: $(k)(75)+(-k)(60) = 15k \in H, k \in \mathbb{N}$. Let's show that there are no integers smaller than $d$ in $H$.

Suppose to the contrary that there exists an integer $c \in \mathbb{N}$ such that $c < d$ and $c \in H$. Then $c = nr + ms$. Since $d$ divides $r$ and $s$, we can write $r = di$ and $s = dj$ for some $i,j \in \mathbb{N}$. Now $c = ndi + mdj$, which means $\frac{c}{d} = ni + mj \in \mathbb{Z}$, which is a contradiction as our assumption meant $0<\frac{c}{d} < 1$.

So there are no positive integers smaller than $d \in H$. Since $d$ divides every number of the form $nr + ms$ and is the smallest positive element, it generates the set.

$\endgroup$

You must log in to answer this question.

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