2
$\begingroup$

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!

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ Generally, "every common divisor divides the greatest common divisor". $\endgroup$ – Daniel Fischer♦ Dec 14 '17 at 22:45
  • $\begingroup$ @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. $\endgroup$ – Alec Dec 14 '17 at 22:52
  • 1
    $\begingroup$ 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$. $\endgroup$ – Daniel Fischer♦ Dec 14 '17 at 22:58
  • $\begingroup$ @Alec Please, if you are ok, you can accept the answer and set it as solved. Thanks! $\endgroup$ – user Jan 26 '18 at 21:25
3
$\begingroup$

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!

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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

|cite|improve this answer
$\endgroup$
1
$\begingroup$

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)$$

|cite|improve this answer
$\endgroup$
  • $\begingroup$ @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)$ $\endgroup$ – zwim Dec 14 '17 at 23:16

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.