1
$\begingroup$

In my book, the definition for gcd(a,b) is the following:

$$\gcd (a,b) = \max \{ d \in \Bbb{Z} : d|a \, \land \, d|b \}$$

However, I don't understand why the set for $\gcd(a,b)$ is necessarily a subset of that of $\gcd(a,b-a)$.

$\endgroup$

3 Answers 3

1
$\begingroup$

Take any $d\in\{k\in\mathbb{Z}:k|a\land k|b\}$, then $d|(b-a)$, so...

$\endgroup$
0
$\begingroup$

$\gcd(a,b)=d$

$a=dk$ and $b=dn$, for $n,k \in \mathbb{N} $

Doesn't it $\implies$ $d|d(n-k) \implies d|a-b$?

$\endgroup$
0
$\begingroup$

This follows from the fact that if $d$ divides $a$ and $d$ divides $b$, then necessarily $d$ divides $b-a$. Namely, $$(b-a)/d = b/d - a/d$$ Since the quantity on the right hand side is an integer.

$\endgroup$

You must log in to answer this question.

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