|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Viktor Karev 2:5080/1003 20 Jun 2003 13:59:54
To : Karl Pech
Subject : Re: Euclid's algorithm (finding the greatest common divisor of 2 number
--------------------------------------------------------------------------------
numbers)
Приветствую, Karl Pech
> VK> HОД(a,b)=HОД(b,a) и HОД(a,b)=HОД(a-b,b)
>
> Thanks Viktor! I tried to prove your formula but
> it seems to be a bit difficult. :-(
> --
> Assume that x is the gcd of A and B.
> So A/a=x and B/b = x
> => (A-B)/(a-b) = x
>
> But how can I show that a-b = B ?
a-b =/= B !!!!!
gcd(a,a-b)=1 and gcd(b,a-b)=1
> [P.S. Can this algorithm be used for the problem:
> "finding the gcd of n numbers"?]
Yes.
--- ifmail v.2.15dev5
* Origin: Fidolook Express 2.000 www.fidolook.da.ru (2:5080/1003@fidonet)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
