Простые числа в арифметических прогрессиях
Займёмся теперь выяснением вопроса о количестве простых чисел. Следующая теорема впервые появилась в “Началах” Евклида и имеет множество различных доказательств, из которых приведём лишь одно.
Теорема (Евклида о бесконечности числа простых чисел). Простых чисел бесконечно много.
Доказательство.Предположим, вопреки доказываемому, что множество простых чисел конечно и состоит из элементов p1 = 2 < p2 = 3 < … < pn . Рассмотрим число N = p1×p2× … ×pn + 1 > 1. Оно, с одной стороны, раскладывается в произведение простых множителей (по основной теореме арифметики), а с другой – не может делиться ни на одно из простых чисел pi (1 £ i £ n): если pi | N , то pi | (N – p1× … ×pi× … ×pn) = 1) – противоречие.
Теорема доказана.
Эта теорема утверждает бесконечность числа простых чисел в арифметической прогрессии 1 + 1×n (n Î N0). Конечно, есть арифметические прогрессии a + b×n (n Î N0), в которых совсем нет простых чисел: такова, например, прогрессия 4 + 4×n (n Î N0), в которой каждое число делится на 4.
Вообще, если D = НОД(a, b), то на D делится любой член последовательности a + b×n (n Î N0), так что при составном D в такой арифметической прогрессии нет ни одного простого числа. Если D = p – простое, то любое число прогрессии делится на p, так что она может содержать только простое число p. Эта возможность реализуется только в том случае, когда a1 + b1×k = 1, где при некотором k Î N0. Например, прогрессия 49 + 7×n (n Î N0) не содержит простых чисел, а прогрессия 7 – 42×n (n Î N0) содержит простое число 7.
Условие a1 + b1×k = 1 будет выполнено для некоторого k Î N0 тогда и только тогда, когда либо a1 = 1, либо a1 – 1 M b1 и (a1 – 1)×b1 < 0. Таким образом, доказана
Теорема (об арифметических прогрессиях с малым числом простых). Если D = НОД(a, b) > 1, то арифметическая прогрессия a + b×n (n Î N0) содержит единственное простое число р в случае D = p = a или, если D = p, a1 – 1 M b1 , (a1 – 1)×b1 < 0. Если D составное число, то в арифметической прогрессии нет простых чисел.
Остаётся вопрос о количестве простых чисел в арифметической прогрессии a + b×n (n Î N0) со взаимно простыми начальным членом a и разностью b. Оказывается, имеет место следующая удивительная теорема:
Теорема (Дирихле). Любая арифметическая прогрессия вида a + b×n (n Î N0) со взаимно простыми a, b содержит бесконечно много простых чисел.
Без доказательства.
Примеры: 1.Арифметическая прогрессия 1 + 2×n (n Î N0) содержит все нечётные простые числа.
2. Любое простое число, большее 3, при делении на 3 даёт остаток 1 или 2. По этому одна из арифметических прогрессий 1 + 3×n или 2 + 3×n (n Î N0) содержит бесконечно много простых чисел (на самом деле, конечно, обе !). На самом деле любое простое число p > 3 можно записать в виде 3×n ± 1 (n Î N0). Это очевидно дляпростого числа p из арифметической прогрессии 1 + 3×n (n Î N0), а p = 2 + 3×n = 3 – 1 + 3×n = 3×(n+1) – 1, что и требовалось.
3. Любое простое число, большее 3, при делении на 4 даёт остаток 1 или 3 (остатки 0, 2 не могут встретиться, поскольку числа вида 4×q, 4×q + 2 являются чётными). Таким образом, одна из арифметических прогрессий 1 + 4×n или 3 + 4×n (n Î N0) содержит бесконечно много простых чисел (по теореме Дирихле – обе !). На самом деле любое простое число p > 3 можно записать в виде 4×n ± 1 (n Î N0). Это очевидно дляпростого числа p из арифметической прогрессии 1 + 4×n (n Î N0), а p = 3 + 4×n = = 4 – 1 + 4×n = 4×(n+1) – 1, что и требовалось.
4.Любое простое число, большее 5, при делении на 6 даёт остатки 1 или 5 (остатки 0, 2 и 3 не могут встретиться, поскольку числа вида 6×q, 6×q + 2 и 6×q + 3 делятся на 2 и на 3 соответственно). Таким образом, одна из арифметических прогрессий 1 + 6×n или 5 + 6×n (n Î N0) содержит бесконечно много простых чисел (по теореме Дирихле – обе !). На самом деле любое простое число p > 5 можно записать в виде 6×n ± 1 (n Î N0). Это очевидно дляпростого числа p из арифметической прогрессии 1 + 6×n (n Î N0), а p = 5 + 6×n = 6 – 1 + 6×n = 6×(n+1) – 1, что и требовалось.
Теорема (о простых числах в арифметических прогрессиях 4×n – 1, 6×n – 1). Арифметические прогрессии 4×n – 1 , 6×n – 1 (n Î N0) содержат бесконечно много простых чисел.
Доказательство. Проведём рассуждения от противного одновременно для обеих указанных прогрессий вида b×n – 1 (n Î N0), где b Î {4, 6},применив идею доказательства Евклида бесконечности простых чисел.
Предположим, вопреки доказываемому, что данная арифметическая прогрессия содержит конечное число простых членов p1 < p2 < … < pk и рассмотрим число N = b×p2×…×pk – 1 из этой прогрессии. По основной теореме арифметики, оно раскладывается в произведение простых множителей. Эти простые множители нечётны (т.к. b чётно) и не могут совпадать ни с одним из чисел p2 , … , pk : в противном случае –1 = N – b×p2×…×pk делилось бы на одно из чисел p2 , … , pk , что невозможно. Поскольку каждое нечётное простое число равно 3 или имеет вид b×n ± 1 (по приведённой выше классификации остатков простых чисел), то в разложении числа N могут участвовать только простые множители вида b×n + 1 (объясните, почему число N не делится на 3 ?!). Однако, произведение чисел вида b×n + 1 снова имеет этот же вид: (b×n + 1)×( b×m + 1) = b×s + 1, где s = n + m + b×n×m , и не может дать число b×n – 1 (?!).
Теорема доказана.
Примеры: 1. Найти все простые числа p, для которых p – 2, p + 3 простые.
Таких чисел нет, т.к. p = 2 не годится, а для нечётного p число p + 3 делится на 2.
2. Найти все простые числа p, для которых p + 2, p + 4 простые.
Ясно, что p = 3 годится, а p = 2 – нет. Если p > 3, то p = 3×n ± 1. Если p = 3×n + 1, то p + 2 = 3×n + 3 M 3. Если же p = 3×n – 1, то p + 4 = 3×n + 3 M 3.
3. Докажите, что для любого нечётного простого числа p > 3 число p2 – 1 делится на 24.
Нужно доказать, что p2 – 1 M 3 и p2 – 1 M 8. Запишем p2 – 1 = (p+1)×(p–1) и заметим, что для p = 3×n ± 1 одна из скобок делится на 3. Аналогично для p = 4×n ± 1 одна из скобок делится на 4, а другая – на 2.
О распределении простых чисел
Для каждого положительного действительного числа x обозначим через (x) количество простых чисел в интервале (–¥, x]. Таким образом, получаем отображение p : R N (называемое функцией Чебышева), значение которого можно вычислить для любого конкретного x Î R. Например, p(x) =0 при x < 2, p(2) = 1 = p(2,99), p(3) = 2, p(10) = 4 = p(7,001). Возникает вопрос о поведении функции p(x), более точно – о её порядке роста. Ограничимся только формулировками самых ранних и простых (но далеко не очевидных) результатов на эту тему:
Теорема (неравенства Чебышева). (1) Существуют такие константы 0 < a < 1 < b (например, годятся a = 0,92129, b = 1,0555), что для всех достаточно больших значений x Î R верны неравенства
.
Эта теорема была доказана в 1850 г. Кроме того, П.Л.Чебышевым было доказано, что если существует , то он равен 1. Существование же этого предела удалось доказать только спустя полвека, используя теорию функций комплексного переменного.
Теорема (Адамар, Валле-Пуссен) Предел существует и равен 1 (асимптотический закон распределения простых чисел).
В той же основополагающей работе П.Л.Чебышева, было дано доказательство следующей известной гипотезы
Теорема (постулат Бертрана). Для любого натурального числа n на отрезке [n; 2×n] содержится хотя бы одно простое число.
В то же время, как показывает следующая теорема, существуют сколь угодно длинные отрезки, не содержащие простых чисел.
Теорема (о сколь угодно длинных отрезках, не содержащих простых чисел). Для любого натурального п на отрезке [п! + 2, п! + п] нет ни одного простого числа.
Доказательство. Любое число из рассматриваемого отрезка имеет вид п! + k, где 2 £ k £ n , и делится на k.
Теорема доказана.
Хотя современная теория чисел продвинулась далеко вперёд, многие вопросы о простых числах остаются нерешёнными и по сей день. Например, до сих пор неизвестно – конечны ли множества простых чисел вида 1 + n2 и 1 + 2n (n Î Z).
Язык сравнений
Пусть a, b, m Î Z и m ¹ 0. Говорят, что числа a и b сравнимы по модулю m, если разность a – b делится нацело на m: a º b (mod m). Таким образом, a º b (mod m) Û $ t Î Za – b = m×t.
Примеры: 1. 5 º 17 (mod 6), т.к. 5 – 17 = –12 = 6×(–2),
3 º –5 (mod 4), т.к. 3 – (–5) = 8 = 4×2,
2. –3 –2 (mod 5), т.к. –3 – (–2) = 1 и 5 1,
28 15 (mod 3), т.к. 28 – 15 = 13 и 3 13.
Свойства сравнений
10. Числа a и b сравнимы по модулю m тогда и только тогда, когда они дают одинаковые остатки при делении на m.
Действительно, если a º b (mod m), а r и s – остатки от деления a и b на m соответственно, то a = m×q + r, b = m×p + s, 0 r < |m|, 0 s < |m| , причём a – b = m×(q – p) + (r – s) делится нацело на m. Это возможно лишь в том случае, когда m | (r – s), т.е. r = s (поскольку –m < r – s < m).
Обратно, есличисла a и b дают одинаковые остатки при делении на m, то a = m×q + r, b = m×p + r, 0 r < m. Поэтому a – b = m×(q – p) кратно m , что и требовалось доказать.
Следующие три свойства следуют из 10.
20. Условия a M b и a º 0 (mod b) эквивалентны.
В самом деле, a M b Û a – 0 M b Û a º 0 (mod b).
30. Любое целое число a сравнимо само с собой по любому модулю m (рефлексивность отношения сравнимости).
40. Если a º b (mod m), то b º a (mod m) (симметричность отношения сравнимости).
50. Если a º b (mod m) и b º с (mod m), то a º c (mod m) (транзитивность отношения сравнимости).
Вместе свойства 20-30 дают
60. Если a º b (mod m), то для любого целого числа c справедливо
a ± c º b ± c (mod m) , a×c º b×c (mod m).
В самом деле, если a – b = m×t, то (a ± c) – (b ± c) = a – b = m×t и аналогично a×c – b×c = (a – b)×c = m×t×c.
70. Если a º b (mod m) и c º d (mod m), то a ± c º b ± d (mod m).
Действительно, если a – b = m×t , c – d = m×s , то
(a ± c) – (b ± d) = (a – b) ± (c – d) = m×t – m×s = m×(t – s).
80. Если a º b (mod m) и c º d (mod m), то a×c º b×d (mod m).
В самом деле, если a – b = mt , c – d = ms, то
(a×c) – (b×d) = a×с – b×с + b×c – b×d = (a – b)×c + b×(c – d) =
= mt×c – b×ms = m× (tc – bs).
90. Если a º b (mod m), то для любого натурального k верно сравнение ak º bk (mod m).
При k = 1 сравнение верно по условию. Отсюда последовательно получаем, умножая на то же сравнение a º b (mod m):
a2 º b2 (mod m), a3 º b3 (mod m), … , ak º bk (mod m).
100. Если целые числа a, b, m делятся нацело на число d Î Z\ {0}, то a º b (mod m) тогда и только тогда, когда .
Действительно, если a = d×a1 , b = d×b1 , m = d×m1 ,то
a – b = m×t Û a1 – b1 = m1×t .
110. Если d×a º d×b (mod m) и НОД(d , m) = 1, то a º b (mod m).
В самом деле, если d×a – d×b = m×t , то d | m×t . Поскольку числа d и m взаимно простые, то по основному свойству взаимно простых чисел d | t , т.е. t = d×t1 для некоторого целого t1 . Значит, a – b = m×t1 .
Сравнения дают удобный язык для изучения делимости чисел. Связь сравнений с делимостью выявлена в свойстве 20.
Примеры: 1. Докажите, что если a при делении на 23 даёт остаток 5, то a4 – 8×a3 + 19 даёт остаток .
Действительно, если a º 5 (mod 23), то
a4 – 8×a3 + 19 º (a2)2 – 8×a×a2 + 19 º 22 – 8×5×2 + 19 º
º – 40×2 + (22 + 19) º –(–6)×2 + 0 º 12 (mod 23),
т.е. остатком будет 12.
2. Вычислить 18100 + 20 (mod 25).
18100 + 20 º (–7)25 – 5 º –(72)12×7 – 5 º –7×(–1)12 – 5 º
º –7 – 5 º –12 º 13 (mod 25).
Функция Эйлера
Для натурального n обозначим через j(n) количество взаимно простых с n натуральных чисел на отрезке [0, n – 1]. Таким образом, получается функция j: N® N, называемая функцией Эйлера.
Примеры: 1.Найдём j(1). Отрезок [0; 1–1] = [0; 0] содержит единственное целое число 0, которое взаимно просто с n = 1
Таким образом, j(1) = 1.
2. Найдём j(2). Для этого рассмотрим отрезок [0; 2–1] = [0; 1], содержащий два целых числа 0, 1, и посчитаем количество взаимно простых с n = 2 чисел в нём:
а | 0 | |
НОД(a, 2) | 2 | 1 |
Таким образом, j(2) = 1.
3. Найдём j(3). Для этого рассмотрим отрезок [0; 3–1] = [0; 2], содержащий три целых числа 0, 1, 2, и вычислим количество взаимно простых с n = 3 чисел в нём:
а | 0 | ||
НОД(a, 3) | 3 | 1 | 1 |
Таким образом, j(3) = 2.
4. Найдём j(6). Для этого рассмотрим отрезок [0; 6–1] = [0; 5], содержащий шесть целых чисел 0, 1, 2, 3, 4, 5, и вычислим количество взаимно простых с n = 6 чисел в нём:
а | 0 | 2 | 3 | 4 | ||
НОД(a, 6) | 6 | 1 | 2 | 3 | 2 | 1 |
Таким образом, j(6) = 2.
Теорема (о функции Эйлера). Для любого натурального числа n справедливы следующие утверждения:
(1) j(1) = 1,
(2) для простого числа p верно j(p) = p – 1,
(3) для любого простого числа p и натурального показателя a справедлива формула j(рa) = рa – рa–1 = pa–1×(p – 1) = pa×(1 – ),
(4) функция Эйлера мультипликативна, т.е. для любых взаимно простых чисел m и n верно j(m×n) = j(m)×j(n),
(5) если , то
.
Доказательство. Докажем лишь некоторые утверждения.
(1) уже доказано.
(2) Пусть p – простое число. Тогда на отрезке [0; p–1] содержатся p целых чисел: 0, 1, 2, … , p – 2, p – 1, из которых ровно одно – 0 делится на p, т.е. НОД(0, p) = p. Остальные не делятся на p, а значит НОД(a, p) = 1 (1 £ a £ p–1). Таким образом, j(p) = p – 1.
(3) Аналогично предыдущему: расположим pa целых чисел из отрезка [0; pa –1] в виде таблицы:
0 | 1 | … | p–2 | p–1 |
p | p+1 | … | 2×p–2 | 2×p–1 |
2×p | 2×p+1 | … | 3×p–2 | 3×p–1 |
… | … | … | … | … |
pa–p | pa–p+1 | … | pa–2 | pa–1 |
В каждом столбце все числа имеют одинаковые остатки при делении на p: числа 1-го столбца дают остаток 0, числа 2-го столбца – остаток 1, и.т.д., числа последнего столбца – остаток p – 1.
Среди этих чисел pa чисел делятся на p только числа первого столбца, т.е. 0×p, 1×p, … , (pa–1 – 1)×p, НОД(s×p, p) = p (0 £ s £ pa–1 –1), таких чисел pa–1 . Остальные pa – pa–1 чисел на p не делятся и взаимно просты с pa. Таким образом, j(pa) = pa – pa–1.
(5) следует из (3) и (4):
j(n) = j( ) = j( )×…×j( ) =
= .
Теорема доказана.
Примеры: 1.Вычислить j(15).
Находим каноническое разложение числа: 15 = 3×5. Значит,
j(15) = j(3)×j(5) = (3 – 1)×(5 – 1) = 8.
2. Вычислить j(775).
Находим каноническое разложение числа:
ni | 775 | 155 | 31 | 1 |
pi | 5 | 5 | 31 | |
28,… | 12,… | 5,… | stop |
Таким образом, 775 = 52×31. Значит,
j(775) = j(52)×j(31) = 5×(5 – 1)×(31 – 1) = 600.
3. Вычислить j(2400).
Находим каноническое разложение числа:
ni | 2400 | 1200 | 600 | 300 | 150 | 75 | 25 | 5 | 1 |
pi | 2 | 2 | 2 | 2 | 2 | 3 | 5 | 5 | |
48,… | 8,… | stop |
Таким образом, 2400 = 25×3×52. Значит,
j(155) = j(25)×j(3)×j(52) = 24×2×5×4 = 27×5 = 640.
4. Решить уравнение j(x) = 12.
Пусть x = 2a×pb×…×qg , где p, … , q – нечётные простые числа. Тогда при a, b , … , g > 0 получаем j(x) = 2a–1×(p–1)×…×(q–1)×pb–1×…×qg–1 = 12 = 22×3. Поскольку p – 1, q – 1 чётны и a > 0, то x = 2a×pb (иначе показатель двойки в левой части больше 2). Ясно, что p = 3, b = 2 и a = 2, т.е. x = 22×32.
Если a = 0, то (p–1)×…×(q–1)×pb–1×…×qg–1 = 22×3. Если среди p, … , q нет тройки, то b = … = g = 1 и (p–1)×…×(q–1) = 22×3. В левой части не более двух сомножителей. Если сомножитель один, то x = p = 13. Если сомножителей два, то (p–1)×(q–1) = 22×3, т.е. p – 1 = 2×r, q – 1 = 2×s и r×s = 3. Ясно, что либо r = 1, s = 3, p = 3, q = 7, x = 21, либо r = 3, s = 1, p = 7, q = 3, x = 21.
Таким образом, x = 36, x = 21, x = 13 – все решения уравнения.
Дата добавления: 2021-12-14; просмотров: 454;