Re: Euclidean Algorithm - a simple question
- From: Michael Press <rubrum@xxxxxxxxxxx>
- Date: Sun, 30 Mar 2008 21:58:10 -0700
In article
<c62c64fd-48bf-4195-96bd-12ea85b1ad48@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
Oliver Mertens <oliver_mertens@xxxxxxxxxxxxx> wrote:
Dear all,
That's actually a really simple question, but I got stuck:
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 would like to show that gcd(x, y) = gcd(x, r).
(That is needed to justify the Euclidean Algorithm to
find the largest commond divisor of two integers x and y).
If we set m = gcd(x, y) I have managed to show that
m divides r: As m divides x it also divides any multiple
of x. Hence m divides r = y - [y/x] x.
But that is not enough: I still need to show that for
all c with the property c|x and c|r implies c|m.
Here I got stuck.
Any help would be much appreciated.
Use gcd(a, b) = gcd(a, b-a).
For if d|a and d|b then d|(b-a).
The reverse implication is really
the forward implication in disguise.
--
Michael Press
.
- References:
- Euclidean Algorithm - a simple question
- From: Oliver Mertens
- Euclidean Algorithm - a simple question
- Prev by Date: Re: math : inaccessible cardinal
- Next by Date: Re: Point of intersection
- Previous by thread: Re: Euclidean Algorithm - a simple question
- Next by thread: kelley hazell full movie clips. Free galleries
- Index(es):
Relevant Pages
|
Loading
