 |
Пункт 3. Взаимно простые числа.
|
|
|
|
Определение. Целые числа a и b называются взаимно простыми, если (a, b) = 1.
Вспоминая свойство 1 из предыдущего пункта, легко заметить, что два числа a и b являются взаимно простыми тогда и только тогда, когда найдутся целые числа u и v такие, что au + bv = 1.
Казалось бы, что особенного можно сказать о взаимно простых числах? Ну нет у них общих делителей, отличных от 1 и - 1, и все тут. Однако, зададимся вопросом: "Как часто встречаются пары взаимно простых чисел?", и постараемся ответить на него с довольно неожиданной точки зрения - в терминах теории вероятностей.
Пусть X = { x n | n = 1, 2,...} - произвольная строго возрастающая последовательность натуральных чисел (или, если угодно, X - произвольное подмножество натуральных чисел, упорядоченное естественным образом). Обозначим через x (N; X) число членов последовательности X, не превосходящих N.
Определение. Число
| r = | ___ lim N ®¥ | x (N; X) N |
называется (верхней асимптотической) плотностью последовательности X = { x n | n = 1, 2,...} в множестве N.
Пример 1. Пусть x n = 2 n, где n пробегает N, - последовательность всех четных чисел. Очевидно, что
| ___ lim N ®¥ | x (N; { x n }) N | = | . |
Между прочим, это хорошо согласуется с нашими интуитивными представлениями о том, что четных чисел - половина.
Пример 2. Пусть x n =2 n , где n пробегает N, - геометрическая прогрессия. Интуитивно ясно, что таких чисел в натуральном ряду мало, ибо чем "дальше в лес" по натуральному ряду, тем реже встречается степень двойки. Понятие плотности подтверждает это ощущение: x (2 k ; { x n }) = k, и, легко проверить, что
| ___ lim N ®¥ | x (N; { x n }) N | = | lim k ®¥ | k 2 k | = 0. |
Резонно считать, что плотность - это вероятность наугад вытащить из натурального ряда число, принадлежащее заданной последовательности. (Согласитесь, что вы всегда так и думали. Вероятность достать четное число есть 1/2, а вероятность напороться на степень двойки, особенно среди больших чисел, вообще говоря, ничтожно мала).
|
|
|
Аналогично определению плотности последовательности, можно дать определение плотности множества пар натуральных чисел. Пусть имеется произвольное множество Х упорядоченных пар натуральных чисел. Обозначим через x (N; X) число пар из множества Х, каждая компонента которых не превосходит N. Полезно представить себе пары чисел из множества Х как координаты точек на координатной плоскости, тогда x (N; X) есть просто число точек множества Х, попавших в квадрат {(x, y) | 0 < x £ N; 0 < y £ N }.
Определение. Число
| r = | ___ lim N ®¥ | x (N; X) N 2 |
называется (верхней асимптотической) плотностью множества пар Х в множестве N 2 .
Пример 3. Пусть Х - множество всех пар натуральных чисел, у которых первая компонента строго больше второй. Множеству Х соответствуют точки первой четверти координатной плоскости, лежащие под биссектрисой y = x. Плотность такого множества легко подсчитать:
| r = | ___ lim N ®¥ | x (N; X) N 2 | = | ___ lim N ®¥ | N (N -1)/2 N 2 | = | , |
что, опять-таки, согласуется с нашим интуитивным представлением о том, что упорядоченных пар, у которых первая компонента превосходит вторую примерно половина от общего количества всех пар натуральных чисел.
Пусть X - множество всех упорядоченных пар (u, v) натуральных чисел таких, что (u, v) = 1, т.е. множество всех пар взаимно простых чисел. (В этом месте я подумал о неудачности стандартного обозначения (u, v) для наибольшего общего делителя, но, раз уж я влип в эту коллизию, то, всякий раз в дальнейшем прийдется уповать на контекст, призванный вносить ясность в смысл обозначения.) Ответ на вопрос о частоте появления пары взаимно простых чисел дает удивительная теорема, открытая в 1881 году итальянцем Э. Чезаро.
|
|
|
Теорема (Чезаро). Вероятность выбрать из N пару взаимно простых чисел равна 6/ p 2 , точнее
| r = | ___ lim N ®¥ | x (N; X) N 2 | = | p 2 | . |
Таким образом, плотность взаимно простых чисел в множестве N 2 оказывается существует и равна 6/ p 2 » 0, 607... Примерно в 60% случаев вы вытащите из натурального ряда пару взаимно простых. И еще удивительно - в теореме Чезаро возникло число p, загадочное и вездесущее! Вот уж никак не ожидали мы встретить его посередь царства целых чисел!
Доказательство. Строгое доказательство теоремы Чезаро довольно сложно и громоздко. Но, как говорится, человека (а, в особенности, женщину) убеждает не строгая логика, а эмоция и правильно подобранные наводящие соображения. Вот и сейчас я схитрю и вместо строгого доказательства приведу некоторые эвристические рассуждения, призванные убедить читателя, почему эта теорема вообще должна быть правдоподобна.
Забудем, что существование вероятности (верхнего предела), строго говоря, нужно кропотливо доказывать. Предположим сразу, что существует вероятность p того, что случайно выбранные натуральные числа а и b взаимно просты.
Пусть d Î N. Через P { S } обозначим, как обычно, вероятность события S. Рассуждаем: Р {(a, b) = d } =
| = P{ d | a } · P{ d | b } · P | ì í î | æ ç è | a d | , | b d | ö ÷ ø | = 1 | ü ý þ | = |
| = | d | · | d | · p = | p d 2 | . |
Просуммировав теперь эти вероятности по всем возможным значениям d, мы должны получить единицу:
| 1 = | S d Î N | P {(a, d) = d } = | ¥ S d = 1 | p d 2 | , |
а сумма ряда
| ¥ S d = 1 | d 2 |
известна и равна p 2 /6 (см., напр., задачник Демидовича по матанализу, раздел "Ряды Фурье"). Итак,
| 1 = | p 2 | · p, |
следовательно, p = 6/ p 2 .
¨
Задачки 
| 1. Докажите своему другу, что из пяти последовательных целых чисел всегда можно выбрать одно, взаимно простое со всеми остальными.
2. Докажите своей подруге, что из 16 последовательных целых чисел всегда можно выбрать одно, взаимно простое со всеми остальными.
3. Докажите себе, что каждые два числа последовательности
являются взаимно простыми (1). 2961. (Из задачника Демидовича). Разложить функцию f (x) = x 2 в ряд Фурье: а) по косинусам кратных дуг в интервале (- p, p); б) по синусам кратных дуг в интервале (0, p);
в) в интервале (0, 2 p). Пользуясь этими разложениями, найти суммы рядов:
5. Найдите плотность последовательностей: a) x n = 5 n +2; б) x n = n 2 ; в) x n = n +1000. 6. Найдите плотность множества всех простых чисел (2). 7. Проверьте, что функция r (X), ставящая в соответствие каждому множеству X натуральных чисел его плотность, удовлетворяет стандартным аксиомам вероятности: 1) r (X) ³ 0 для всех X (неотрицательность); 2) r (N) = 1 (нормированность);
для попарно непересекающихся множеств X n (счетная аддитивность). 8. Найдите плотность множества пар вида: а) (3 n +1, 4 k +3), б) (2 n , 4 k +3), в) (2 n , 3 k ); где n и k независимо пробегают N. 9. Проверьте, что функция r (X), ставящая в соответствие каждому множеству X упорядоченных пар натуральных чисел его плотность, удовлетворяет стандартным аксиомам вероятности. 10. Уговорите своего товарища доказать или докажите сами, что если плотность последовательности строго больше нуля, то для любого натурального k, в этой последовательности найдутся k членов, образующих k -членную арифметическую прогрессию (3). |
(1) Между прочим, из утверждения этой задачи сразу следует бесконечность множества простых чисел. Действительно, если бы простых чисел было бы лишь конечное число, то не могло бы существовать бесконечно много чисел, попарно взаимно простых.
(2) Если эта задача вызывает затруднения, отложите ее в сторону, а после прочтения пункта 15 вернитесь к ее решению. Правильный ответ - ноль.
(3) Эта задачка - чистое издевательство, однако размышления над ней принесут вам немало пользы. Ут-верждение этой задачи в математическом мире известно как теорема Семериди, а наиболее короткое ее доказательство, использующее эргодическую теорию, содержит около 60 страниц. Теорема Семериди устанавливает, в некотором смысле, характеристическое свойство арифметических прогрессий: всякая бесконечная арифметическая прогрессия имеет ненулевую плотность и всякая последовательность нену-левой плотности содержит сколь угодно длинную арифметическую прогрессию. Прекрасный рассказ об этой теореме и ее элементарное доказательство для k =3 можно найти в книжке Р. Грэхема "Начала теории Рамсея". М., Мир, 1984.
|
|
|
|
|
|
