GCD : Why does the GCD of two numbers divides their difference?

Question

I was working my way through some number theoretic proofs and being a newbie am stuck on this proof :

Why does the gcd of two numbers , say (a,b) - also divides their difference : a-b

My Question :

As I am a novice to induction and proofs , in general , can someone help me out ?

Answer 1

That means we have integer numbers $m$, $n$, $c$ with $$ c = \gcd(a,b) $$ and $$ a = c \cdot m $$ and $$ b = c \cdot n $$ because $c$ is a common divisor (a divisor of both $a$ and $b$), which means that $$ a - b = c \cdot m - c \cdot n = c \cdot (m - n) $$ where $m - n$ is an integer as well. So $c$, the gcd, divides $a-b$ too.

As André Nicolas noted, the property, that it is the greatest of the common divisors is not needed.

Answer 2

Let $\dfrac aA=\dfrac bB=d=(a,b)\implies a=dA,b=dB$

$ax+by=d(Ax+By)\iff\dfrac{ax+by}d=Ax+By$ which is an integer for any integers $x,y$

Set $x=1,y=-1$

Answer 3

For any common divisor, $d$, of $a$ and $b$, there exist integers $x$ and $y$ such that $a=dx$ and $b=dy$. Then $a-b=dx-dy=d(x-y)$. S0 $d$ divides $a-b$.

Answer 4

It's good to start by introducing some notation that allows you to express some of the given information in the form of equations. For instance, "let $d$ be the gcd of $a$ and $b$" is a good start. Now, what does gcd mean? for one thing, it means that $d$ is a divisor of both $a$ and $b$, and you can use that to introduce some notation: "let $k$ and $\ell$ be integers such that $kd=a$ and $\ell d = b$". Now you can do the same thing to the statement that you are trying to prove: "we wish to show that, for some integer $m$, $m d = a-b$". Now you're almost done! Hint: find a general expression for $m$ in terms of $k$ and $\ell$. Then "let $m=$" your expression, and show why $md=a-b$, and that completes the proof.