# Given $d \mid a$ and $d \mid b$ show that $d \mid \gcd(a, b-a)$

I can't seem to make this work.

I understand that $d \mid a \wedge d\mid b \Rightarrow d\mid b-a$, and I see that both $d$ and $\gcd(a, b-a)$ will divide $b-a$, but I can't seem to prove that $d \mid \gcd(a, b-a)$.

I've looked at examples, and it seems to be true, but as always, formulating a proof is harder. There has to be something elementary I'm overlooking.

Any help appreciated!

• Generally, "every common divisor divides the greatest common divisor". – Daniel Fischer Dec 14 '17 at 22:45
• @DanielFischer - Wow, didn't know that. That sounds like an interesting result. And it definitely pieces the puzzle together. Now I just need to grasp the proof of that lemma instead. – Alec Dec 14 '17 at 22:52
• If you know Bézout's lemma, it follows directly from that, since we can write the greatest common divisor of $x$ and $y$ as a linear combination (with integer coefficients) of $x$ and $y$, $\gcd(x,y) = kx + ny$. It also follows from the unique prime factorisation. $d$ is a common divisor of $x$ and $y$ if and only if each prime $p$ occurs in the factorisation of $d$ with an exponent not exceeding the smaller of the exponents of $p$ in the factorisations of $x$ and $y$. – Daniel Fischer Dec 14 '17 at 22:58
• @Alec Please, if you are ok, you can accept the answer and set it as solved. Thanks! – user Jan 26 '18 at 21:25

By using the assumptions, we have:

$d \mid a$ means that there exist $c_1$ such that $a = d c_1$.

$d \mid b$ means that there exist $c_2$ such that $b = d c_2$.

$b -a = d c_2 - d c_1 = d(c_2 - c_1)$, which means that $d \mid b-a.$

We claim that $\gcd(c_1 , c_2) = \gcd(c_2 - c_1, c_1)$.

Let $c_2 = p_{1}^{\beta_1} \ldots p_{n}^{\beta_n}$ and $c_1 = p_{i}^{\alpha_i} \ldots p_{m}^{\alpha_i}$ and without loss of generality we can assume that $n>m$ and $i\leq m$ and $1 < \alpha_i < l \leq k < \alpha_m < \beta_n$. And also we can assume that some of $p_i$'s in the prime decomposition of $c_1$ be also in the prime decomposition of $c_2$. (Else, if there is non of $p_i$'s of $c_1$ part of $p_j$'s in $c_2$, then we will have $\gcd(c_1 , c_2) = \gcd(c_2 - c_1, c_1) = 1$ )

So \begin{align}c_2 - c_1 &= p_{1}^{\beta_1} \ldots p_{n}^{\beta_n} - p_{i}^{\alpha_i} \ldots p_{m}^{\alpha_i} \\&= p_{l}^{\alpha_l} \ldots p_{k}^{\alpha_k} \left( p_{1}^{\beta_1} \ldots p_{l-1}^{\beta_{l-1}} \ldots p_{x}^{\beta_{x}} \ldots p_{k+1}^{\beta_{k+1}} \ldots p_{n}^{\beta_n} - p_{i}^{\alpha_i} \ldots p_{l-1}^{\alpha_{l-1}} \ldots p_{y}^{\alpha_{y}} \ldots p_{k+1}^{\alpha_{k+1}} \ldots p_{m}^{\alpha_i} \right)\end{align}

Which will give us that

$$\gcd(c_2 - c_1 , c_1) = p_{l}^{\min\{ \alpha_l , \beta_l\}} \ldots p_{k}^{\min\{ \alpha_k , \beta_k\}} = p_{l}^{\alpha_l} \ldots p_{k}^{\alpha_k} = \gcd(c_2 , c_1)$$ for $\alpha_s = \max\{ \alpha_i \mid i \in \{ l, \cdots , k \} \}$.

Then we have $\gcd(b-a , a) = \gcd(d c_1 , d(c_2 - c_1)) = d \gcd(c_1 , c_2 - c_1)$.

Which means that $d \mid \gcd(b-a , a)$.

And we are done!

$d|a$ , so $a = d\cdot k$. $d|b$ , so $b= d \cdot m$. What about $\gcd(dk,d(m-k)) ?$

Note that

$$a=h\cdot d$$ $$b=k\cdot d$$

For Bezout's theorem:

$$gcd(a,b)=a\cdot x+b\cdot y$$

thus

$$gcd(a,b-a)=gcd(a,b)=h\cdot d\cdot x+k\cdot d\cdot y \implies d|gcd(a,b-a)$$

• @Alec in fact once you get $d\mid \gcd(a,b)$ you also get $d\mid \gcd(a,b-na)$ because $\gcd(a,b)=\gcd(a,b \mod a)$ – zwim Dec 14 '17 at 23:16