, . .
:
1. , (, ) = , (, ) = .
. .. Ù Þ = (, ). ( (, ) , ).
, , , , , . , = (, ).
.. Ù Þ = (, ). ( (, ) , ). , m = (, ) < , m , , (, ).
2. = q + r, (, ) = (, r).
. d - (, ), .. d Ù d. r = ( q) d , , (, r).
d ¢ - r, .. d ¢ Ù r d ¢. = q + r d ¢ . , d ¢ .
, , r, , , r . , r. (, ) = (, r). .
. .
, r 1, r 1, r 2, r 2 r 3 , , (, ).
. , , :
1) = q 1+ r 1, 0 ≤ r 1 < ,
2) = r 1 q 2+ r 2, 0 ≤ r 2 < r 1,
3) r 1= r 2 q 3+ r 3, 0 ≤ r 3 < r 2,
4) r 2= r 3 q 4 + r 4, 0 ≤ r 4 < r 3,
n 1) rn -3= rn -2 qn -1 + rn -1, 0 ≤ rn -1 < rn -2,
n) rn -2= rn -1 qn + rn, 0 ≤ rn < rn -1,
n + 1) rn -1= rnqn +1 + rn +1, rn +1 = 0.
, , , , .. r 1, r 2, r 3,
r 1 > r 2 > r 3>.. , . . rn +1, (n + 1) . rn.
|
|
, rn (, ). , 1), 2), , n 1), n), n + 1), 1 2, , (, ) = (, r 1) = (r 1, r 2) = (r 2, r 3) = = (rn -2, rn -1) = (rn -1, rn) = rn. .
, . (816, 323).
:
. (, ) .
, (120, 160) = 40. 120 160 40, .. 1, 2, 4, 5, 8, 10, 20, 40.
( ) 2, 2.
. (5912, 8868, 13302, 18475).
1) (5912, 8868) = 2956,
2) (2956, 13302) = 1478,
3) (1478, 18475) = 739,
4) (5912, 8868, 13302, 18475) = 739.
, ( 1, 2).
1. 21 3, 24 6, 15 5, 20 4 = 5.
2. :
, ?
3. 6 .
4. 10 , .
5. .
4