Взаимно простые числа

Ключевые слова: теория чисел, лекции, взаємно прості числа.

Определение. Целые числа a и b называются взаимно простыми, если ( a , b ) = 1.

Два числа a и b являются взаимно простыми тогда и только тогда, когда найдутся целые числа u и v такие, что au + bv = 1.

Пусть X = { x_n | n = 1, 2,...} - произвольная строго возрастающая последовательность натуральных чисел (или, если угодно, X - произвольное подмножество натуральных чисел, упорядоченное естественным образом). Обозначим через ξ(N; X) число членов последовательности X, не превосходящих N .

Определение. Число

называется (верхней асимптотической) плотностью последовательности X = { x n | n = 1, 2,...} в множестве N .

Пример 1. Пусть x_n = 2n , где n пробегает N , - последовательность всех четных чисел. Очевидно, что

Между прочим, это хорошо согласуется с нашими интуитивными представлениями о том, что четных чисел - половина.

Пример 2. Пусть x_n =2ⁿ , где n пробегает N , - геометрическая прогрессия. Интуитивно ясно, что таких чисел в натуральном ряду мало, ибо чем "дальше в лес" по натуральному ряду, тем реже встречается степень двойки. Понятие плотности подтверждает это ощущение: ξ (2^k ; { x_n }) = k , и, легко проверить, что

Плотность - это вероятность наугад вытащить из натурального ряда число, принадлежащее заданной последовательности.

Аналогично определению плотности последовательности, можно дать определение плотности множества пар натуральных чисел. Пусть имеется произвольное множество Х упорядоченных пар натуральных чисел. Обозначим через ξ ( N ; X ) число пар из множества Х , каждая компонента которых не превосходит N . Полезно представить себе пары чисел из множества Х как координаты точек на координатной плоскости, тогда ξ ( N ; X ) есть просто число точек множества Х , попавших в квадрат {( x , y ) | 0 < x ≤ N ; 0 < y ≤ N }.

Определение. Число

называется (верхней асимптотической) плотностью множества пар Х в множестве N² .

Пример 3. Пусть Х - множество всех пар натуральных чисел, у которых первая компонента строго больше второй. Множеству Х соответствуют точки первой четверти координатной плоскости, лежащие под биссектрисой y = x . Плотность такого множества легко подсчитать:

Пусть X - множество всех упорядоченных пар ( u , v ) натуральных чисел таких, что ( u , v ) = 1, т.е. множество всех пар взаимно простых чисел.

Теорема (Чезаро). Вероятность выбрать из N пару взаимно простых чисел равна 6/π² , точнее Доказательство. Предположим сразу, что существует вероятность p того, что случайно выбранные натуральные числа а и b взаимно просты. Пусть d ∈ N . Через P { S } обозначим, как обычно, вероятность события S . Рассуждаем: Р

Просуммировав теперь эти вероятности по всем возможным значениям d , мы должны получить единицу:

Похожие материалы: