Re: Euclidean Algorithm - a simple question

Arturo Magidin <magidin@xxxxxxxxxxxxxxxxx> wrote:
Oliver Mertens <oliver_mertens@xxxxxxxxxxxxx> wrote:

Let [x] denotes the integral part of x. Now, consider 1 < x < y.
Then we can write y = [y/x] x + r, where r denotes the remainder
when we >divide y by x. I'd like to show that gcd(x, y) = gcd(x, r).

So: you know that if m divides both y and x, then it divides r, so
it divides both x and r, hence divides gcd(x,r). So, gcd(x,y)|gcd(x,r).

Now you want to show that if m divides both x and r, then it divides y.
Well, y = [y/x]x + r, right? More generally: if m divides a and b, then
it divides ax+by for any x and y. So, gcd(a,b) = gcd(a,b+qa) for all q.

Indeed:, if x divides a and b, then it divides a and b+qa, so
gcd(a,b)|gcd(a,b+qa); by the same argument,
gcd(a,b+qa)|gcd(a,(b+qa)+(-q)a) = gcd(a,b). QED

The ESSENCE is much clearer when presented as follows.

One easily proves that gcd(x, qx+r) = gcd(x, r)

If d divides x then: d divides qx+r iff d divides r

which obviously implies that {x, qx+r} and {x, r}

have the same set of common divisors d, hence they
have the same greatest common divisor. QED

ALTERNATIVELY, in terms of ideals or Z-modules:

y = qx+r -> xZ + yZ = xZ + (qx+r)Z = xZ + rZ

If you don't know ideal theory you can read the above
as saying that {x,y} and {x,r} have the same set of
integer linear combinations, i.e. xZ + yZ = xZ + rZ,
hence the same gcd (= smallest elt > 0 in such a set).

--Bill Dubuque
.

Relevant Pages

  • Re: GCD(0,0)
    ... >>>When it comes to common divisors, ... >>>divides 0, and otherwise an integer never divides ... I'll start it off with Sierpinski ... ...
    (sci.math)
  • Re: GCD(0,0)
    ... >>>When it comes to common divisors, ... >>>divides 0, and otherwise an integer never divides ... >>my point of view the G in GCD says it all. ... The usual Euclidean Algorithm applied to 0 and 0 would require dividing ...
    (sci.math)
  • Re: GCD(0,0)
    ... >>When it comes to common divisors, ... >>divides 0, and otherwise an integer never divides ... I'll start it off with Sierpinski ... ... Sierpinski, Elementary Theory of Numbers, 1964 ...
    (sci.math)
  • Re: simple GCD question (but has me foxed)
    ... That's an awkward proof. ... Any integer that divides two of these things ... So the set of _all_ common divisors x and y is the ... as the set of common divisors of x and x-y. ...
    (sci.math)
  • Re: simple GCD question (but has me foxed)
    ... the GCD, ... Any integer that divides both x and y must also divide x-y, ... that both /sets/ of common divisors are exactly the same. ...
    (sci.math)
Loading