2
$\begingroup$

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.

Thanks

$\endgroup$
5
  • 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, 2013 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, 2013 at 14:56
  • $\begingroup$ Hi Bill, Sorry I just read the book so haven't learned Euclidean algorithm. And he doesn't assume the GCD exist in the theorem. Could you give a more direct hint about the proof? And I have edited the question to make it clear. $\endgroup$
    – Allitee
    Dec 14, 2013 at 23:12
  • $\begingroup$ @hardmath, Yes that's what I am asking. And the proof seems don't depend on the x,y to be integer. So x, y may be rational number as well?. Any suggestions? $\endgroup$
    – Allitee
    Dec 14, 2013 at 23:32
  • $\begingroup$ @Allitee You can safely ignore the remark about the relationship to the Euclidean algorithm - see my answer. Please feel welcome to ask for elaboration in comments if anything is unclear. $\endgroup$
    – Bill Dubuque
    Dec 15, 2013 at 0:34

1 Answer 1

Reset to default
3
$\begingroup$

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

$\endgroup$
11
  • 1
    $\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, 2013 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, 2013 at 1:19
  • 2
    $\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, 2013 at 1:43
  • 1
    $\begingroup$ I see. But if we add a≥b, can we prove the above statement using his proof? If we can, for a=3,b=2, we can't get the common divisor d = 3x + 2y for y≥x≥0, which should be 1? $\endgroup$
    – Allitee
    Dec 15, 2013 at 2:41
  • 1
    $\begingroup$ Sorry I don't understand what the possible swapping means. If we fix y be the coefficient on b and x be the coefficient on a. Add a ≥ b, y≥x≥0 to the statement. Since the basis case is true and the induction step infers the final n case. Should the original proof be applicable as well? $\endgroup$
    – Allitee
    Dec 15, 2013 at 3:08

You must log in to answer this question.

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