Алгоритм Евклида

Поделись знанием:
Перейти к: навигация, поиск

Алгори́тм Евкли́да — эффективный алгоритм для нахождения наибольшего общего делителя двух целых чисел (или общей меры двух отрезков). Алгоритм назван в честь греческого математика Евклида, который впервые описал его в VII[1] и X[2] книгах «Начал». В самом простом случае алгоритм Евклида применяется к паре положительных целых чисел и формирует новую пару, которая состоит из меньшего числа и разницы между большим и меньшим числом. Процесс повторяется, пока числа не станут равными. Найденное число и есть наибольший общий делитель исходной пары.

Первое описание алгоритма находится в «Началах» Евклида (около 300 лет до н. э.), что делает его одним из старейших численных алгоритмов, используемых в наше время[3]. Оригинальный алгоритм был предложен только для натуральных чисел и геометрических длин (вещественных чисел). Однако в XIX веке он был обобщён на другие типы чисел, такие как целые числа Гаусса и полиномы от одной переменной. Это привело к появлению в современной общей алгебре такого понятия, как евклидово кольцо. Позже алгоритм Евклида также был обобщён на другие математические структуры, такие как узлы и многомерные полиномы.

Для данного алгоритма существует множество теоретических и практических применений. В частности, он является основой для криптографического алгоритма с открытым ключом RSA[4], широко распространённого в электронной коммерции. Также алгоритм используется при решении линейных диофантовых уравнений[5], при построении непрерывных дробей[6], в методе Штурма[7]. Алгоритм Евклида является основным инструментом для доказательства теорем в современной теории чисел, например таких как теорема Лагранжа о сумме четырёх квадратов[8] и основная теорема арифметики[9].





История

Древнегреческие математики называли этот алгоритм ἀνθυφαίρεσις или ἀνταναίρεσις — «взаимное вычитание». Этот алгоритм не был открыт Евклидом, так как упоминание о нём имеется уже в Топике Аристотеля[3]. В «Началах» Евклида он описан дважды — в VII книге для нахождения наибольшего общего делителя двух натуральных чисел[1] и в X книге для нахождения наибольшей общей меры двух однородных величин[2]. В обоих случаях дано геометрическое описание алгоритма, для нахождения «общей меры» двух отрезков.

Историками математики было выдвинуто предположение, что именно с помощью алгоритма Евклида (процедуры последовательного взаимного вычитания) в древнегреческой математике впервые было открыто существование несоизмеримых величин (стороны и диагонали квадрата, или стороны и диагонали правильного пятиугольника)[10]. Впрочем, это предположение не имеет достаточных документальных подтверждений. Алгоритм для поиска наибольшего общего делителя двух натуральных чисел описан также в I книге древнекитайского трактата Математика в девяти книгах.

Описание

Алгоритм Евклида для целых чисел

Пусть <math>a</math> и <math>b</math> — целые числа, не равные одновременно нулю, и последовательность чисел

<math> a > b > r_1 > r_2 > r_3 > r_4 > \cdots > r_n</math>

определена тем, что каждое <math>r_k</math> — это остаток от деления предпредыдущего числа на предыдущее, а предпоследнее делится на последнее нацело, то есть:

<math>a = bq_0 + r_1,</math>
<math>b = r_1q_1 + r_2,</math>
<math>r_1 = r_2q_2 + r_3,</math>
<math>\cdots</math>
<math>r_{k-2} = r_{k-1} q_{k-1} + r_k,</math>
<math>\cdots</math>
<math>r_{n-2} = r_{n-1}q_{n-1}+ r_n,</math>
<math>r_{n-1} = r_n q_n.</math>

Тогда НОД(a, b), наибольший общий делитель a и b, равен rn, последнему ненулевому члену этой последовательности[11].

Существование таких r1, r2, ..., rn, то есть возможность деления с остатком m на n для любого целого m и целого n ≠ 0, доказывается индукцией по m.

Корректность этого алгоритма вытекает из следующих двух утверждений[12]:

  • Пусть a = bq + r, тогда НОД (a, b) = НОД (b, r).
  • НОД(r, 0) = r для любого ненулевого r (так как 0 делится на любое целое число, кроме нуля).

Геометрический алгоритм Евклида

Пусть даны два отрезка длины a и b. Вычтем из большего отрезка меньший и заменим больший отрезок полученной разностью. Повторяем эту операцию, пока отрезки не станут равны. Если это произойдёт, то исходные отрезки соизмеримы, и последний полученный отрезок есть их наибольшая общая мера. Если общей меры нет, то процесс бесконечен. В таком виде алгоритм описан Евклидом[2] и реализуется с помощью циркуля и линейки.

Пример

Для иллюстрации алгоритм Евклида будет использован, чтобы найти НОД a = 1071 и b = 462. Для начала от 1071 отнимем кратное значение 462, пока не получим разность меньше, чем 462. Мы должны дважды отнять 462, (q0 = 2), оставаясь с остатком 147:

1071 = 2 × 462 + 147.

Затем от 462 отнимем кратное значение 147, пока не получим разность меньше, чем 147. Мы должны трижды отнять 147 (q1 = 3), оставаясь с остатком 21:

462 = 3 × 147 + 21.

Затем от 147 отнимем кратное значение 21, пока не получим разность меньше, чем 21. Мы должны семь раз отнять 21 (q2 = 7), оставаясь без остатка:

147 = 7 × 21 + 0.

Таким образом последовательность a > b > r1 > r2 > r3 > … > rn в данном конкретном случае будет выглядеть так:

1071 > 462 > 147 > 21.


Так как последний остаток равен нулю, алгоритм заканчивается числом 21 и НОД(1071, 462) = 21.

В табличной форме шаги были следующие:

Шаг k Равенство Частное и остаток
0 1071 = q0 462 + r0 q0 = 2 и r0 = 147
1 462 = q1 147 + r1 q1 = 3 и r1 = 21
2 147 = q2 21 + r2 q2 = 7 и r2 = 0; алгоритм заканчивается

Применения

Расширенный алгоритм Евклида и соотношение Безу

Формулы для <math>r_i</math> могут быть переписаны следующим образом:

<math>r_1 = a + b(-q_0)</math>
<math>r_2= b - r_1q_1 = a(-q_1)+b(1+q_1q_0)</math>
<math>\vdots</math>
НОД <math> (a,b) = r_n = as + bt</math>

Здесь s и t целые. Это представление наибольшего общего делителя называется соотношением Безу, а числа s и t — коэффициентами Безу[13]. Соотношение Безу является ключевым в доказательстве леммы Евклида и основной теоремы арифметики.

Цепные дроби

Алгоритм Евклида достаточно тесно связан с цепными дробями[6]. Отношение a/b допускает представление в виде цепной дроби:

<math>\frac ab=[q_0; q_1, q_2,\cdots,q_n]</math>.

При этом цепная дробь без последнего члена равна отношению коэффициентов Безу t/s, взятому со знаком минус:

<math>[q_0; q_1, q_2,\cdots,q_{n-1}] = -\frac ts</math>.

Последовательность равенств, задающая алгоритм Евклида, может быть переписана в форме:

<math>

\begin{align} \frac{a}{b} &= q_0 + \frac{r_0}{b} \\ \frac{b}{r_0} &= q_1 + \frac{r_1}{r_0} \\ \frac{r_0}{r_1} &= q_2 + \frac{r_2}{r_1} \\ & {}\ \vdots \\ \frac{r_{k-2}}{r_{k-1}} &= q_k + \frac{r_k}{r_{k-1}} \\ & {}\ \vdots \\ \frac{r_{N-2}}{r_{N-1}} &= q_N \end{align} </math>

Последнее слагаемое в правой части равенства всегда равно обратному значению левой части следующего уравнения. Поэтому первые два уравнения могут быть объединены в форме:

<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{r_1}{r_0}} </math>

Третье равенство может быть использовано, чтобы заменить знаменатель выражения r1/r0, получим:

<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{r_2}{r_1}}} </math>

Последнее отношение остатков rk/rk−1 всегда может быть заменено с использованием следующего равенства в последовательности, и так до последнего уравнения. Результатом является цепная дробь:

<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{\ddots + \cfrac{1}{q_N}}}} = [ q_0; q_1, q_2, \ldots , q_N ] </math>

В приведённом выше примере НОД(1071, 462) был посчитан и были найдены частные qk, равные 2, 3 и 7 соответственно. Поэтому 1071/462 может быть записана как:

<math>\frac{1071}{462} = 2 + \cfrac{1}{3 + \cfrac{1}{7}} = [2; 3, 7]</math>

Линейные диофантовы уравнения

Диофантово уравнение — это уравнение с целочисленными коэффициентами и с одним или несколькими переменными, причем ставится задача поиска лишь его целых корней. Такое уравнение может иметь бесконечно много решений, конечное число решений или не иметь их вовсе. Простейшее диофантово уравнение — линейное с двумя неизвестными:

<math>a \cdot x + b \cdot y = c,</math>

где a, b, c — целые числа. С помощью алгоритма Евклида может быть найдено полное решение уравнения такого типа[5]. Сначала с помощью этого алгоритма можно определить d = НОД(a, b). Затем, используя расширенный алгоритм Евклида, определяются такие k и l, что:

<math>a \cdot k + b \cdot l = d.</math>

То есть x = k и y = l - это частное решение уравнения при c = d. Получается, что если c = q⋅d, то x = q⋅k, y = q⋅l - частное решение исходного уравнения, так как:

<math>a \cdot x + b \cdot y = a \cdot (q \cdot k) + b \cdot (q \cdot l) = q \cdot (a \cdot k + b \cdot l) = q \cdot d = c.</math>

Обратно, если существует хотя бы одно решение уравнения, то c кратно d. Это следует из того, что d делит и a, и b (а значит, и всю левую часть), поэтому должно делить и c (правую часть). Таким образом, линейное диофантово уравнение имеет хотя бы одно решение тогда и только тогда, когда c кратно НОД(a, b).

Вариации и обобщения

Евклидово кольцо

Кольца, в которых применим алгоритм Евклида, называются евклидовыми кольцами[14]. К ним относятся, в частности, кольца целых чисел и кольца многочленов.

Обобщённый алгоритм Евклида для многочленов

Алгоритм Евклида и расширенный алгоритм Евклида естественным образом обобщается на кольцо многочленов k[x] от одной переменной над произвольным полем k, поскольку для таких многочленов определена операция деления с остатком. При выполнении алгоритма Евклида для многочленов аналогично алгоритму Евклида для целых чисел получается последовательность полиномиальных остатков (PRS)[15].


Ускоренные версии алгоритма

  • Одним из методов ускорения целочисленного алгоритма Евклида является использование симметричного остатка[16]:
<math>r_i \equiv r_{i-2} \pmod{r_{i-1}},</math>
где
<math>-\frac{r_{i-1}}{2}\leq r_i\leq\frac{r_{i-1}}{2}.</math>
  • Одна из версий ускоренного алгоритма Евклида для полиномов основывается на том, что промежуточные значения алгоритма в основном зависят от высоких степеней. Применение стратегии «разделяй и властвуй» позволяет уменьшить асимптотическую сложность алгоритма[16].

Напишите отзыв о статье "Алгоритм Евклида"

Примечания

  1. 1 2 Мордухай-Болтовской, 1949, с. 11—13.
  2. 1 2 3 Мордухай-Болтовской, 1949, с. 103—105.
  3. 1 2 Кнут, 2001, с. 378.
  4. Menezes, 1996, с. 286.
  5. 1 2 Курант, 2001, с. 74—76.
  6. 1 2 Виноградов, 1952, с. 14—18.
  7. Энгелер, 1987, с. 24—31.
  8. Тихомиров, 2003, с. 11—14.
  9. Калужин, 1969, с. 6—14.
  10. Цейтен, 1932, с. 112-114.
  11. Виноградов, 1952, с. 9-10.
  12. Курант, 2001, с. 67-70.
  13. Хассе, 1953, с. 29-30.
  14. Курош, 1973, с. 91-92.
  15. Панкратьев, 2007, с. 54-58.
  16. 1 2 Gathen, 2013, с. 313-326.

Литература

  • Начала Евклида / пер.с греч. и комм. Д. Д. Мордухая-Болтовского под ред. Выгодского М. Я. и Веселовского И. Н.. — ГИТТЛ, 1949. — Т. 2. — 511 с.
  • Виноградов И. М. [www.mccme.ru/free-books/djvu/vinogradov.djvu Основы теории чисел]. — М.-Л.: ГИТТЛ, 1952. — 180 с. — ISBN 978-5-811-40535-0.
  • Курант Р., Роббинс Г. Дополнение к главе I, § 4. // [www.mccme.ru/free-books/pdf/kurant.htm Что такое математика?] — 3-e изд., испр. и доп. — М., 2001. — 568 с. — ISBN 5-900916-45-6.
  • Ошибка Lua : attempt to index local 'entity' (a nil value).
  • Кнут Д. Э. Искусство программирования. — Вильямс, 2001. — Т. 2. — 829 с. — ISBN 5-8459-0081-6.
  • Menezes A., van Oorschot P., Vanstone S. Handbook of Applied Cryptography. — CRC-Press, 1996. — 816 с. — (Discrete Mathematics and Its Applications). — ISBN 0-8493-8523-7.
  • von zur Gathen J., Gerhard J. Modern Computer Algebra. — Cambridge University Press, 2013. — 808 с. — ISBN 978-1-107-03903-2.
  • Панкратьев Е. В. Элементы компьютерной алгебры. — ИНТУИТ, 2007. — 217 с. — ISBN 978-5-955-60099-4.
  • Тихомиров В. М. Великие математики прошлого и их великие теоремы. — 2-е изд., испр. — МЦНМО, 2003. — 16 с. — ISBN 5-94057-110-7.
  • Калужин Л. А. Основная теорема арифметики. — Популярные лекции по математике. — М.: Наука, 1969. — 33 с.
  • Хассе Г. Лекции по теории чисел. — Изд. иностранной литературы, 1953. — 527 с.
  • Энгелер Э. Метаматематика элементарной математики. — М.: Мир, 1987. — 128 с.
  • Цейтен Г. Г. История математики в Древности и в Средние века. — ГТТИ, 1932. — 232 с.
  • Ошибка Lua : attempt to index local 'entity' (a nil value).

Ссылки

  • Описание метода и коды программ [kvodo.ru/algoritm-evklida.html алгоритма Евклида].
  • [mathinfinity.net.ru/articles/all_math/algorithm_evklida Обоснование алгоритма Евклида]
  • [e-maxx.ru/algo/euclid_algorithm Алгоритм Евклида на e-maxx.ru]
  • [landrina.ru/development/c-realizaciya-rasshirennogo-algoritma-evklida C# реализация расширенного алгоритма Эвклида]

Отрывок, характеризующий Алгоритм Евклида

– Их сиятельство с ними в том же доме стоят.
«Стало быть, он жив», – подумала княжна и тихо спросила: что он?
– Люди сказывали, все в том же положении.
Что значило «все в том же положении», княжна не стала спрашивать и мельком только, незаметно взглянув на семилетнего Николушку, сидевшего перед нею и радовавшегося на город, опустила голову и не поднимала ее до тех пор, пока тяжелая карета, гремя, трясясь и колыхаясь, не остановилась где то. Загремели откидываемые подножки.
Отворились дверцы. Слева была вода – река большая, справа было крыльцо; на крыльце были люди, прислуга и какая то румяная, с большой черной косой, девушка, которая неприятно притворно улыбалась, как показалось княжне Марье (это была Соня). Княжна взбежала по лестнице, притворно улыбавшаяся девушка сказала: – Сюда, сюда! – и княжна очутилась в передней перед старой женщиной с восточным типом лица, которая с растроганным выражением быстро шла ей навстречу. Это была графиня. Она обняла княжну Марью и стала целовать ее.
– Mon enfant! – проговорила она, – je vous aime et vous connais depuis longtemps. [Дитя мое! я вас люблю и знаю давно.]
Несмотря на все свое волнение, княжна Марья поняла, что это была графиня и что надо было ей сказать что нибудь. Она, сама не зная как, проговорила какие то учтивые французские слова, в том же тоне, в котором были те, которые ей говорили, и спросила: что он?
– Доктор говорит, что нет опасности, – сказала графиня, но в то время, как она говорила это, она со вздохом подняла глаза кверху, и в этом жесте было выражение, противоречащее ее словам.
– Где он? Можно его видеть, можно? – спросила княжна.
– Сейчас, княжна, сейчас, мой дружок. Это его сын? – сказала она, обращаясь к Николушке, который входил с Десалем. – Мы все поместимся, дом большой. О, какой прелестный мальчик!
Графиня ввела княжну в гостиную. Соня разговаривала с m lle Bourienne. Графиня ласкала мальчика. Старый граф вошел в комнату, приветствуя княжну. Старый граф чрезвычайно переменился с тех пор, как его последний раз видела княжна. Тогда он был бойкий, веселый, самоуверенный старичок, теперь он казался жалким, затерянным человеком. Он, говоря с княжной, беспрестанно оглядывался, как бы спрашивая у всех, то ли он делает, что надобно. После разорения Москвы и его имения, выбитый из привычной колеи, он, видимо, потерял сознание своего значения и чувствовал, что ему уже нет места в жизни.
Несмотря на то волнение, в котором она находилась, несмотря на одно желание поскорее увидать брата и на досаду за то, что в эту минуту, когда ей одного хочется – увидать его, – ее занимают и притворно хвалят ее племянника, княжна замечала все, что делалось вокруг нее, и чувствовала необходимость на время подчиниться этому новому порядку, в который она вступала. Она знала, что все это необходимо, и ей было это трудно, но она не досадовала на них.
– Это моя племянница, – сказал граф, представляя Соню, – вы не знаете ее, княжна?
Княжна повернулась к ней и, стараясь затушить поднявшееся в ее душе враждебное чувство к этой девушке, поцеловала ее. Но ей становилось тяжело оттого, что настроение всех окружающих было так далеко от того, что было в ее душе.
– Где он? – спросила она еще раз, обращаясь ко всем.
– Он внизу, Наташа с ним, – отвечала Соня, краснея. – Пошли узнать. Вы, я думаю, устали, княжна?
У княжны выступили на глаза слезы досады. Она отвернулась и хотела опять спросить у графини, где пройти к нему, как в дверях послышались легкие, стремительные, как будто веселые шаги. Княжна оглянулась и увидела почти вбегающую Наташу, ту Наташу, которая в то давнишнее свидание в Москве так не понравилась ей.
Но не успела княжна взглянуть на лицо этой Наташи, как она поняла, что это был ее искренний товарищ по горю, и потому ее друг. Она бросилась ей навстречу и, обняв ее, заплакала на ее плече.
Как только Наташа, сидевшая у изголовья князя Андрея, узнала о приезде княжны Марьи, она тихо вышла из его комнаты теми быстрыми, как показалось княжне Марье, как будто веселыми шагами и побежала к ней.
На взволнованном лице ее, когда она вбежала в комнату, было только одно выражение – выражение любви, беспредельной любви к нему, к ней, ко всему тому, что было близко любимому человеку, выраженье жалости, страданья за других и страстного желанья отдать себя всю для того, чтобы помочь им. Видно было, что в эту минуту ни одной мысли о себе, о своих отношениях к нему не было в душе Наташи.
Чуткая княжна Марья с первого взгляда на лицо Наташи поняла все это и с горестным наслаждением плакала на ее плече.
– Пойдемте, пойдемте к нему, Мари, – проговорила Наташа, отводя ее в другую комнату.
Княжна Марья подняла лицо, отерла глаза и обратилась к Наташе. Она чувствовала, что от нее она все поймет и узнает.
– Что… – начала она вопрос, но вдруг остановилась. Она почувствовала, что словами нельзя ни спросить, ни ответить. Лицо и глаза Наташи должны были сказать все яснее и глубже.
Наташа смотрела на нее, но, казалось, была в страхе и сомнении – сказать или не сказать все то, что она знала; она как будто почувствовала, что перед этими лучистыми глазами, проникавшими в самую глубь ее сердца, нельзя не сказать всю, всю истину, какою она ее видела. Губа Наташи вдруг дрогнула, уродливые морщины образовались вокруг ее рта, и она, зарыдав, закрыла лицо руками.
Княжна Марья поняла все.
Но она все таки надеялась и спросила словами, в которые она не верила:
– Но как его рана? Вообще в каком он положении?
– Вы, вы… увидите, – только могла сказать Наташа.
Они посидели несколько времени внизу подле его комнаты, с тем чтобы перестать плакать и войти к нему с спокойными лицами.
– Как шла вся болезнь? Давно ли ему стало хуже? Когда это случилось? – спрашивала княжна Марья.
Наташа рассказывала, что первое время была опасность от горячечного состояния и от страданий, но в Троице это прошло, и доктор боялся одного – антонова огня. Но и эта опасность миновалась. Когда приехали в Ярославль, рана стала гноиться (Наташа знала все, что касалось нагноения и т. п.), и доктор говорил, что нагноение может пойти правильно. Сделалась лихорадка. Доктор говорил, что лихорадка эта не так опасна.
– Но два дня тому назад, – начала Наташа, – вдруг это сделалось… – Она удержала рыданья. – Я не знаю отчего, но вы увидите, какой он стал.
– Ослабел? похудел?.. – спрашивала княжна.
– Нет, не то, но хуже. Вы увидите. Ах, Мари, Мари, он слишком хорош, он не может, не может жить… потому что…


Когда Наташа привычным движением отворила его дверь, пропуская вперед себя княжну, княжна Марья чувствовала уже в горле своем готовые рыданья. Сколько она ни готовилась, ни старалась успокоиться, она знала, что не в силах будет без слез увидать его.
Княжна Марья понимала то, что разумела Наташа словами: сним случилось это два дня тому назад. Она понимала, что это означало то, что он вдруг смягчился, и что смягчение, умиление эти были признаками смерти. Она, подходя к двери, уже видела в воображении своем то лицо Андрюши, которое она знала с детства, нежное, кроткое, умиленное, которое так редко бывало у него и потому так сильно всегда на нее действовало. Она знала, что он скажет ей тихие, нежные слова, как те, которые сказал ей отец перед смертью, и что она не вынесет этого и разрыдается над ним. Но, рано ли, поздно ли, это должно было быть, и она вошла в комнату. Рыдания все ближе и ближе подступали ей к горлу, в то время как она своими близорукими глазами яснее и яснее различала его форму и отыскивала его черты, и вот она увидала его лицо и встретилась с ним взглядом.
Он лежал на диване, обложенный подушками, в меховом беличьем халате. Он был худ и бледен. Одна худая, прозрачно белая рука его держала платок, другою он, тихими движениями пальцев, трогал тонкие отросшие усы. Глаза его смотрели на входивших.
Увидав его лицо и встретившись с ним взглядом, княжна Марья вдруг умерила быстроту своего шага и почувствовала, что слезы вдруг пересохли и рыдания остановились. Уловив выражение его лица и взгляда, она вдруг оробела и почувствовала себя виноватой.
«Да в чем же я виновата?» – спросила она себя. «В том, что живешь и думаешь о живом, а я!..» – отвечал его холодный, строгий взгляд.
В глубоком, не из себя, но в себя смотревшем взгляде была почти враждебность, когда он медленно оглянул сестру и Наташу.
Он поцеловался с сестрой рука в руку, по их привычке.
– Здравствуй, Мари, как это ты добралась? – сказал он голосом таким же ровным и чуждым, каким был его взгляд. Ежели бы он завизжал отчаянным криком, то этот крик менее бы ужаснул княжну Марью, чем звук этого голоса.
– И Николушку привезла? – сказал он также ровно и медленно и с очевидным усилием воспоминанья.
– Как твое здоровье теперь? – говорила княжна Марья, сама удивляясь тому, что она говорила.
– Это, мой друг, у доктора спрашивать надо, – сказал он, и, видимо сделав еще усилие, чтобы быть ласковым, он сказал одним ртом (видно было, что он вовсе не думал того, что говорил): – Merci, chere amie, d'etre venue. [Спасибо, милый друг, что приехала.]
Княжна Марья пожала его руку. Он чуть заметно поморщился от пожатия ее руки. Он молчал, и она не знала, что говорить. Она поняла то, что случилось с ним за два дня. В словах, в тоне его, в особенности во взгляде этом – холодном, почти враждебном взгляде – чувствовалась страшная для живого человека отчужденность от всего мирского. Он, видимо, с трудом понимал теперь все живое; но вместе с тем чувствовалось, что он не понимал живого не потому, чтобы он был лишен силы понимания, но потому, что он понимал что то другое, такое, чего не понимали и не могли понять живые и что поглощало его всего.
– Да, вот как странно судьба свела нас! – сказал он, прерывая молчание и указывая на Наташу. – Она все ходит за мной.
Княжна Марья слушала и не понимала того, что он говорил. Он, чуткий, нежный князь Андрей, как мог он говорить это при той, которую он любил и которая его любила! Ежели бы он думал жить, то не таким холодно оскорбительным тоном он сказал бы это. Ежели бы он не знал, что умрет, то как же ему не жалко было ее, как он мог при ней говорить это! Одно объяснение только могло быть этому, это то, что ему было все равно, и все равно оттого, что что то другое, важнейшее, было открыто ему.
Разговор был холодный, несвязный и прерывался беспрестанно.
– Мари проехала через Рязань, – сказала Наташа. Князь Андрей не заметил, что она называла его сестру Мари. А Наташа, при нем назвав ее так, в первый раз сама это заметила.
– Ну что же? – сказал он.
– Ей рассказывали, что Москва вся сгорела, совершенно, что будто бы…
Наташа остановилась: нельзя было говорить. Он, очевидно, делал усилия, чтобы слушать, и все таки не мог.
– Да, сгорела, говорят, – сказал он. – Это очень жалко, – и он стал смотреть вперед, пальцами рассеянно расправляя усы.
– А ты встретилась с графом Николаем, Мари? – сказал вдруг князь Андрей, видимо желая сделать им приятное. – Он писал сюда, что ты ему очень полюбилась, – продолжал он просто, спокойно, видимо не в силах понимать всего того сложного значения, которое имели его слова для живых людей. – Ежели бы ты его полюбила тоже, то было бы очень хорошо… чтобы вы женились, – прибавил он несколько скорее, как бы обрадованный словами, которые он долго искал и нашел наконец. Княжна Марья слышала его слова, но они не имели для нее никакого другого значения, кроме того, что они доказывали то, как страшно далек он был теперь от всего живого.
– Что обо мне говорить! – сказала она спокойно и взглянула на Наташу. Наташа, чувствуя на себе ее взгляд, не смотрела на нее. Опять все молчали.
– Andre, ты хоч… – вдруг сказала княжна Марья содрогнувшимся голосом, – ты хочешь видеть Николушку? Он все время вспоминал о тебе.
Князь Андрей чуть заметно улыбнулся в первый раз, но княжна Марья, так знавшая его лицо, с ужасом поняла, что это была улыбка не радости, не нежности к сыну, но тихой, кроткой насмешки над тем, что княжна Марья употребляла, по ее мнению, последнее средство для приведения его в чувства.
– Да, я очень рад Николушке. Он здоров?

Когда привели к князю Андрею Николушку, испуганно смотревшего на отца, но не плакавшего, потому что никто не плакал, князь Андрей поцеловал его и, очевидно, не знал, что говорить с ним.
Когда Николушку уводили, княжна Марья подошла еще раз к брату, поцеловала его и, не в силах удерживаться более, заплакала.
Он пристально посмотрел на нее.
– Ты об Николушке? – сказал он.
Княжна Марья, плача, утвердительно нагнула голову.
– Мари, ты знаешь Еван… – но он вдруг замолчал.
– Что ты говоришь?
– Ничего. Не надо плакать здесь, – сказал он, тем же холодным взглядом глядя на нее.

Когда княжна Марья заплакала, он понял, что она плакала о том, что Николушка останется без отца. С большим усилием над собой он постарался вернуться назад в жизнь и перенесся на их точку зрения.
«Да, им это должно казаться жалко! – подумал он. – А как это просто!»
«Птицы небесные ни сеют, ни жнут, но отец ваш питает их», – сказал он сам себе и хотел то же сказать княжне. «Но нет, они поймут это по своему, они не поймут! Этого они не могут понимать, что все эти чувства, которыми они дорожат, все наши, все эти мысли, которые кажутся нам так важны, что они – не нужны. Мы не можем понимать друг друга». – И он замолчал.

Маленькому сыну князя Андрея было семь лет. Он едва умел читать, он ничего не знал. Он многое пережил после этого дня, приобретая знания, наблюдательность, опытность; но ежели бы он владел тогда всеми этими после приобретенными способностями, он не мог бы лучше, глубже понять все значение той сцены, которую он видел между отцом, княжной Марьей и Наташей, чем он ее понял теперь. Он все понял и, не плача, вышел из комнаты, молча подошел к Наташе, вышедшей за ним, застенчиво взглянул на нее задумчивыми прекрасными глазами; приподнятая румяная верхняя губа его дрогнула, он прислонился к ней головой и заплакал.
С этого дня он избегал Десаля, избегал ласкавшую его графиню и либо сидел один, либо робко подходил к княжне Марье и к Наташе, которую он, казалось, полюбил еще больше своей тетки, и тихо и застенчиво ласкался к ним.
Княжна Марья, выйдя от князя Андрея, поняла вполне все то, что сказало ей лицо Наташи. Она не говорила больше с Наташей о надежде на спасение его жизни. Она чередовалась с нею у его дивана и не плакала больше, но беспрестанно молилась, обращаясь душою к тому вечному, непостижимому, которого присутствие так ощутительно было теперь над умиравшим человеком.


Князь Андрей не только знал, что он умрет, но он чувствовал, что он умирает, что он уже умер наполовину. Он испытывал сознание отчужденности от всего земного и радостной и странной легкости бытия. Он, не торопясь и не тревожась, ожидал того, что предстояло ему. То грозное, вечное, неведомое и далекое, присутствие которого он не переставал ощущать в продолжение всей своей жизни, теперь для него было близкое и – по той странной легкости бытия, которую он испытывал, – почти понятное и ощущаемое.
Прежде он боялся конца. Он два раза испытал это страшное мучительное чувство страха смерти, конца, и теперь уже не понимал его.
Первый раз он испытал это чувство тогда, когда граната волчком вертелась перед ним и он смотрел на жнивье, на кусты, на небо и знал, что перед ним была смерть. Когда он очнулся после раны и в душе его, мгновенно, как бы освобожденный от удерживавшего его гнета жизни, распустился этот цветок любви, вечной, свободной, не зависящей от этой жизни, он уже не боялся смерти и не думал о ней.