Theorem 1.2 of Apostol Analytic Number Theory about common divisor I don't know why but the link needs to be refreshed to see the content

"Theorem 1.2 Each pair of integers a and b has a common divisor d of the form d = ax + by where x and y are integers. Moreover, every common divisor of a and b divides this d. "

His proof seems doesn't depend on y and x can be negative. So if we add a condition that $y \ge x \ge 0$ in the theorem, the proof still works. However, the result will not be true. I am wondering if I miss some points in author's proof?

Also he state this theorem before the greatest common divisor. And it should prove the existence of the GCD since every common divisor divides d. So I think he doesn't assume the GCD exists.


  • $\begingroup$ What theorem are you referring to? $\endgroup$ – DonAntonio Dec 14 '13 at 14:00
  • 1
    $\begingroup$ "not available for viewing" $\endgroup$ – Daniel Fischer Dec 14 '13 at 14:02
  • 4
    $\begingroup$ Please make your question self-contained. $\endgroup$ – Thomas Andrews Dec 14 '13 at 14:06
  • 1
    $\begingroup$ The statement in Apostol seems to be that $\gcd(a,b)$ can be written in the form $ax + by$ for integers $x,y$. So I would speculate the OP is asking why we cannot further restrict $x,y$ to be nonnegative integers, i.e. where in the proof is allowing negative coefficients a critical aspect. $\endgroup$ – hardmath Dec 14 '13 at 14:10
  • 2
    $\begingroup$ Hint $\ $ The reduction (descent) step of the proof is the same as that of the subtractive form of the Euclidean algorithm for the gcd, i.e. $\rm\ gcd(a,b) = gcd(a-b,b)\ $ for $\rm a\ge b.$ Then by $\rm\color{#c00}{induction}$ we have $\rm\ gcd(a,b) = gcd(a-b,b) \color{#c00}= (a-b) x + b y = a x + b(y-x).\ $ However, the induction step does not lift positivity, i.e. $\rm\ x,y \ge 0 \not\Rightarrow x,\,y\!-\!x \ge 0.\ $ $\endgroup$ – Bill Dubuque Dec 14 '13 at 14:56

If you examine the inductive step in Apostol's proof you will see that it does not generally lift-up any positivity of the coefficients. Namely, to get a linear common divisor of $\rm\,a,b\,$ it first obtains, by induction, a common divisor $\rm\,d\,$ of $\rm\, a-b,b\,$ of sought linear form $\rm\, d = (a-b)x+by.\,$ Since $\rm\,d\mid a-b,b\,\Rightarrow d\mid (a-b)+b = a,\,$ we infer that $\rm\,d\mid a,b,\,$ i.e. $\rm\,d\,$ is a common divisor of $\rm\,a,b.\,$ Rewriting it yields the desired form: $\rm\,d = (a−b)x+by=ax+b(y−x),\,$ i.e. linear in $\rm\,a,b.$ But this rewriting does not preserve coeff positivity, i.e. from $\rm\,x,y\ge 0\,$ we cannot infer $\rm\,x,y-x\ge 0.\,$

Remark $\ $ Readers familiar with the subtractive form of the Euclidean algorithm will note the analogy with the idncution step of the classical proof of the extended Euclidean algorithm

$$\rm gcd(a,b)\overset{\color{#c00}{law}}=gcd(a−b,b)\overset{induct}{=}(a−b)x+by=ax+b(y−x).$$

This gcd $\rm\color{#c00}{law}$ is the reduction (descent) step employed in this algorithm to reduce the given gcd to a "smaller" one, where the size measure used on gcd argument pairs $\rm\,(a,b)\,$ is their sum $\rm\,a+b.$

  • $\begingroup$ Thank you Bill. But he doesn't state anything about gcd in the proof. Actually, he uses this theorem to introduce the gcd. $\endgroup$ – Allitee Dec 15 '13 at 1:08
  • $\begingroup$ @Allitee I mention the gcd law only to give some intuition on how the proof works. Again you can ignore that if you like. All that matters is my remark that the positivity of the Bezout coefficient does not necessarily lift. You might find it helpful to work out some simple numerical examples to understand how the induction works. You can find some worked examples in some of my prior posts here on the extended Euclidean algorithm. $\endgroup$ – Bill Dubuque Dec 15 '13 at 1:19
  • $\begingroup$ In particular, Apostol's proof uses only one direction of said gcd equality, viz. that a common divisor of $\rm\,a-b,\, b\,$ is also a common divisor of $\rm\,a,b.\,$ Essentially he's working with common divisors, instead of greatest common divisors, delaying proof of the greatest aspect till later. $\endgroup$ – Bill Dubuque Dec 15 '13 at 1:33
  • 1
    $\begingroup$ So if we just consider his proof, in the basis case of P(1) the induction he says n=a+b=0, d=0 and x=y=0. So the theorem holds for P(1). And subsequently he assumes the theorem holds for each j=a+b between [0,n-1] and induces P(n). But if we add a further restriction "y≥x≥0" in the theorem to prove, the proof seems still work since the basis case is also true and the induction step doesn't depend on the sign of x,y. $\endgroup$ – Allitee Dec 15 '13 at 1:43
  • $\begingroup$ @Allitee Apostol is using a slightly different proof than I imagined. I just now rewrote my answer so it is clearer how it applies to his proof. The (complete) induction is on the sum $\rm\,n\,$ of the arguments of the gcd function. Induction lifts the proof for the "smaller" argument pair $\rm\,(a-b,b)\,$ of size $\rm\,n = (a-b)+b = a\,$ to the larger argument pair $\rm\,(a,b)\,$ of size $\rm\,n = a+b.\,$ $\endgroup$ – Bill Dubuque Dec 15 '13 at 2:08

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.