Простые числа в арифметических прогрессиях


 

Займёмся теперь выяснением вопроса о количестве простых чисел. Следующая теорема впервые появилась в “Началах” Евклида и имеет множество различных доказательств, из которых приведём лишь одно.

Теорема (Евклида о бесконечности числа простых чисел). Простых чисел бесконечно много.

Доказательство.Предположим, вопреки доказываемому, что множество простых чисел конечно и состоит из элементов 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;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.038 сек.