WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 45 | 46 || 48 | 49 |   ...   | 65 |

31.63. а) Пусть остаток x принадлежит показателю d. Тогда d остатков 1, x, x2, x3,..., xd-1 различны и все они удовлетворяют уравнению Xd (mod p). Поэтому никаких других остатков, удовлетворяющих этому уравнению степени d, нет (задача 31.33). Любой остаток y, принадлежащий показателю d, удовлетворяет уравнению yd 1 (mod p). Следовательно, y это один из остатков 1, x, x2, x3,..., xd-1. Но xk принадлежит показателю d тогда и только тогда, когда числа d и k взаимно просты. Действительно, остатки xk, x2k,..., x(d-1)k не равны 1 тогда и только тогда, когда числа k, 2k,..., (d - 1)k не делятся на d.

Мы доказали, что если показателю d принадлежит хотя бы один остаток, то ему принадлежит ровно (d) остатков.

б) Каждый остаток x принадлежит некоторому показателю d, делящему p - 1. Согласно задаче а) показателю d принадлежит не более (d) остатков.

Поэтому p - 1 (d), где суммирование ведётся по всем числам d, делящим p - 1. При этом если хотя бы одному показателю d, делящему - 1, p принадлежит менее (d) остатков, то неравенство строгое: p - 1 < (d).

С другой стороны, согласно задаче 31.10 p - 1 = (d). Поэтому каждому показателю d, делящему p - 1, принадлежит ровно (d) остатков.

в) Непосредственно следует из задачи б): достаточно положить d = p - 1.

31.64. а) Предположим сначала, что n = p2q. Пусть x = pq. Тогда x (mod n), но xd+1 0 (mod n) для любого натурального числа d.

Предположим теперь, что n = p1... pk, где p1,..., pk попарно различные простые числа. Тогда если число xd+1 - x делится на p1,..., pk, то оно делится и на n. Если число p простое, то согласно малой теореме Ферма xp-1 1 (mod p), поэтому x(p-1)m+1 x (mod p). Значит, xd+1 x (mod p) для любого числа d, делящегося на p - 1. Таким образом, в качестве d можно взять НОК(p1 - 1,..., pk - 1).

б) В решении задачи а) уже доказано, что если d = НОК(p1 -1,..., pk -1), то xd+1 x (mod n) для всех x. Остаётся доказать, что если xd+1 x (mod n) для всех целых x, то d делится на НОК(p1 - 1,..., pk - 1). Для этого достаточно доказать, что d делится на каждое из чисел p1 - 1,..., pk - 1.

Если xd+1 x (mod n), то xd+1 x (mod pi). Пусть xi первообразный корень по модулю pi. В таком случае xr 1 (mod pi) тогда и только тогда, i 388 Глава 31. Элементы теории чисел когда r делится на pi - 1. Если xd+1 xi (mod pi), то i xd xd+pi-1 xd+1+(pi-2) xi · xpi-2 xpi-1 1 (mod pi).

i i i i i Поэтому d делится на pi - 1 (задача 31.62).

31.65. а) Пусть q нечётный простой делитель числа ap -1. Тогда ap (mod q). Поэтому согласно задаче 31.62 показатель d числа a по модулю q является делителем числа p, т.е. d = 1 или d = p. Если d = 1, то a 1 (mod q), поэтому q делитель числа a - 1. Если d = p, то согласно задаче 31.61 p делитель числа q - 1. Учитывая, что число q - 1 чётно, получаем q - 1 = 2px.

б) Пусть q нечётный простой делитель числа ap + 1. Тогда ap -(mod q). Поэтому a2p 1 (mod q). Следовательно, показатель d числа a по модулю q является делителем числа 2p. Ясно, что a 1 (mod q) и ap (mod q), поэтому d = 2 или d = 2p. Если a2 1 (mod q), то a -1 (mod q), т.е. q делитель числа a + 1. Если d = 2p, то 2p делитель числа q - 1.

Поэтому q - 1 = 2px.

31.66. Прежде всего заметим, что такие простые числа есть: согласно задаче 31.65 а) все простые делители числа 2p - 1 имеют такой вид. Предположим, что существует лишь конечное число простых чисел вида 2px + 1, а именно, числа p1,..., pn. Рассмотрим число (p1... pn)p - 1. Согласно задаче 31.65 а) это число имеет простой делитель вида 2px + 1. Действительно, пусть a = p1... pn. Тогда a 1 (mod p), т.е. a = 1 + px. Число ap - 1 p - 1 (p - 1)(p - 2) = 1 + px + p2x2 +...

p2x 2 3! взаимно просто с px = a - 1, поэтому у числа ap - 1 должны быть делители, отличные от a - 1. Ясно также, что число (p1... pn)p - 1 взаимно просто с p1,..., pn. Мы получили простое число вида 2px + 1, отличное от p1,..., pn, что противоречит предположению.

n n 31.67. Пусть q простой делитель числа 22 +1. Тогда 22 -1 (mod q), n+поэтому 22 1 (mod q). Согласно задаче 31.62 показатель d числа 2 по модулю q является делителем числа 2n+1. Следовательно, d = 2n+1, поскольку n 22 1 (mod q). Таким образом, число 2n+1 является делителем числа q - (задача 31.61).

31.68. При n > 1 числа 3 и p взаимно простые. Согласно задаче 31.46 б) 3 n-= -1, поэтому 32 -1 (mod 2n + 1). Показатель числа 3 по модулю p 2n + 1 является делителем числа 2n, причём он больше 2n-1. Следовательно, показатель числа 3 по модулю 2n + 1 равен 2n.

31.69. Если n делится на p - 1, то an 1 (mod p) для любого a, взаимно простого с p. Значит, S p - 1 -1 (mod p).

Предположим теперь, что n не делится на p-1. Пусть x первообразный корень по модулю p. Тогда согласно задаче 31.62 xn 1 (mod p). Число x взаимно просто с p, поэтому набор остатков при делении на p чисел x, 2x, Глава 31. Элементы теории чисел 3x,..., (p - 1)x совпадает с набором 1, 2,..., p - 1. Следовательно, S xnS (mod p). Учитывая, что xn 1 (mod p), получаем S 0 (mod p).

31.70. Докажем сначала, что если r 1, то (1 + kmr)m 1 (mod mr+1).

m m Действительно, (1+kmr)m = 1+ kmr + k2m2r +... В этой сумме сла1 m гаемое kmr = kmr+1 делится на mr+1. Последующие слагаемые делятся на m2r, поэтому они тоже делятся на mr+1. Таким образом, (1 + kmr)m = 1 + + k1m2, (1 + kmr)m = (1 + k1m2)m = 1 + k2m3 и т.д.

31.71. Если x первообразный корень по модулю p, то не существует натурального числа s < p-1(p - 1), для которого xs 1 (mod p). Предположим, что xt 1 (mod p) для некоторого натурального t < p - 1. Тогда -согласно задаче 31.70 xtp 1 (mod p). Получено противоречие, поэтому x первообразный корень по модулю p.

31.72. Пусть k наименьшее натуральное число, для которого xk (mod p). Тогда p-1(p - 1) делится на k (задача 31.12). Ясно, что xk (mod p), поэтому k делится на p - 1. Таким образом, k = p(p - 1), где 0 -1. Предположим, что -2. Тогда, возведя обе части сравнения -xp (p-1) 1 (mod p) в степень p-2-, получим xp (p-1) 1 (mod p), что противоречит условию. Следовательно, = p - 1, т.е. k = p-1(p - 1) = = (p).

31.73. Предположим, что числа x и x + p не являются первообразными корнями по модулю p2. Оба эти числа являются первообразными корнями по модулю p, поэтому согласно задаче 31.72 xp-1 1 (mod p2) и (x + +p)p-1 1 (mod p2). Следовательно, число (x + p)p-1 - xp-1 = (p - 1)xp-2p + p - + xp-3p2 +... делится на p2, а значит, p(p - 1)xp-2 делится на p2, т.е.

(p - 1)xp-2 делится на p. Но это противоречит тому, что p - 1 и x взаимно просты с p.

31.74. Числа x и p взаимно простые, поэтому согласно малой теореме Ферма xp-1 1 (mod p), т.е. xp-1 = 1 + pt. Наименьшее натуральное k, для которого xk 1 (mod p2), равно p(p - 1), поэтому t не делится на p.

Возведём равенство xp-1 = 1 + pt в степень n = p-2, где > 2. В результате получим -n n xp (p-1) = (1 + pt)n = 1 + npt + p2t2 +... + pntn.

2 n n Согласно задаче 14.33 ps делится на p при s 2. С другой стороны, s -npt = p-1t не делится на p. Поэтому xp (p-1) 1 + npt 1 (mod p).

Значит, согласно задаче 31.72 число x первообразный корень по модулю p.

31.75. Ясно, что (2p) = (p). Пусть x первообразный корень по модулю p. Заменив при необходимости x на x + p, можно считать, что число x нечётно. Достаточно доказать, что xk 1 (mod p) тогда и только 390 Глава 31. Элементы теории чисел тогда, когда xk 1 (mod 2p). Если xk 1 (mod p) и xk 1 (mod 2), то xk 1 (mod 2p). Утверждение в обратную сторону очевидно.

31.76. Числа 1 и 3 являются первообразными корнями по модулям 2 и 4.

Остаётся доказать, что если n 3, то первообразного корня по модулю 2n не существует.

n-Поскольку (2n) = 2n-1, достаточно доказать, что x2 1 (mod 2n) при n 3 для любого нечётного x. Пусть x = 1 + 2t. Тогда x2 = 1 + 4t(t + + 1) 1 (mod 8). При n = 3 требуемое утверждение доказано. Предположим n-2 n-теперь, что x2 = 1 + 2nt, где n 3. Тогда x2 = (1 + 2nt)2 = 1 + 2n+1t + + 22nt2 1 (mod 2n+1).

31.77. Предположим, что x число, взаимно простое с m. Согласно задаче 31.14 xL(m) 1 (mod m), где L(m) обобщённая функция Эйлера. Поэтому достаточно доказать, что если число m не имеет указанного в условии задачи вида, то L(m) < (m).

Если число m имеет два различных нечётных простых делителя p1 и p2, то числа p1 - 1 и p2 - 1 имеют нетривиальный общий делитель. Поэтому НОК(p1 - 1, p2 - 1) < (p1 - 1)(p2 - 1), а значит, L(m) < (m).

Если m = 2p, где 2, 1 и p нечётное простое число, то (m) = = 2-1p-1(p-1) и L(m) = НОК 2-1, p-1(p-1). Числа 2-1 и p-1 имеют общий делитель 2, поэтому L(m) < (m).

31.78. Для каждого натурального числа n можно выбрать натуральное число k так, что 22k-2 < n 22k. Тогда (n)/n (22k)/n < (22k)/22k-2 = 4(22k)/22k.

Поэтому достаточно доказать, что limk (22k)/22k = 0.

Каждое простое число p, удовлетворяющее неравенствам 2m-1 < p 2m, 2m (2m)! является делителем биномиального коэффициента =, по 2m-1 (2m-1)! этому m m 2m 22 p (2m-1)(2 )-(2m-1).

2m-2m-1

k k Ясно также, что (2k) 2k. Поэтому (22k) 2k 22k+1 1 + = +.

22k 22k k22k 2k k Глава 31. Элементы теории чисел n 31.79. Согласно задаче 14.34, если pm делит, то pm n. Поэтому k n = pm n(n). Запишем такие неравенства для всех биномиальных p n k коэффициентов с фиксированным n и сложим их. В результате получим n n 2n = (1 + 1)n = (n + 1)n(n), k k=n ln 2 - ln(n + 1) т.е. (n). Поэтому достаточно доказать, что если n 201, ln n 2 2 ln(n + 1) то n ln 2 - ln(n + 1) > n, т.е. ln 2 - >. При x > 2 производная 3 3 n ln(x + 1) функции отрицательна, поэтому указанное неравенство достаточx но проверить для n = 201. Это делается непосредственными вычислениями:

2 ln ln 2 - 0, 02648 и 0, 02641.

3 31.80. Каждое число p, удовлетворяющее неравенствам n < p 2n, яв 2n ляется делителем биномиального коэффициента, поэтому n 2n n(2n)-(n) p < 22n.

n n

ln n ln n ln n 2n Мы хотим доказать неравенство (2n) < 3 ln 2. Для этого достаточно ln(2n) доказать неравенство n 2n 5 5 ln 2 3 ln 2, т.е..

ln n ln(2n) ln n ln 2 + ln n Последнее неравенство переписывается в виде ln n 5 ln 2. Оно выполняется при n 25.

Чтобы можно было применить индукцию, нужно ещё доказать неравенство 2n + (2n + 1) < 3 ln 2.

ln(2n + 1) Заметим, что из неравенства (1) и очевидного неравенства (2n+1) (2n)+ + 1 следует, что 2n ln 2 3n ln 2 2n ln (2n + 1) < (n) + + 1 < + + 1.

ln n ln n ln n 392 Глава 31. Элементы теории чисел Таким образом, достаточно доказать неравенство n 2n + 5 ln 2 + 1 < 3 ln 2, ln n ln(2n + 1) т.е.

ln n 2n + 1 ln n 5 + < 3.

n ln 2 n ln(2n + 1) 2n + Ясно, что 3 > 6, поэтому достаточно доказать неравенство n ln n ln n 5 + < 6.

n ln 2 ln(2n + 1) Если n 55, то выражение в правой части больше 5, 1053, а выражение в левой части меньше 5, 1052 (монотонность обоих выражений доказывается дифференцированием).

Чтобы завершить доказательство, нужно непосредственно проверить, что утверждение верно для всех n от 55 до 109. После этого можно воспользоваться тем, что если утверждение верно для некоторого n, то оно верно для 2n и 2n + 1.

Глава 32.

Многочлены II Основная теорема алгебры заключается в том, что любой многочлен имеет по крайней мере один (комплексный) корень. Из этого с помощью теоремы Безу (задача 10.2) легко выводится, что многочлен степени n имеет ровно n корней с учётом их кратностей.

У основной теоремы алгебры есть много разных доказательств. Одно из возможных использует следующую теорему Руше, которая имеет и самостоятельный интерес.

32.1. Пусть f и g многочлены и замкнутая несамопересекающаяся кривая на комплексной плоскости. Докажите, что если f(z) - g(z) < f(z) g(z) + (1) при всех z, то внутри кривой расположено одинаковое количество корней многочленов f и g с учётом их кратностей (Руше).

32.2. Пусть f(z) = zn+a1zn-1+...+an, где ai комплексные числа.

Докажите, что тогда внутри круга |z| = 1 + max |ai| расположено ровно i n корней многочлена f (с учётом их кратностей).

32.1. Разделение корней Здесь мы обсудим различные утверждения, позволяющие вычислить или хотя бы оценить сверху количество вещественных корней многочлена, расположенных на интервале (a, b). Формулировки таких теорем часто используют понятие числа перемен знака в последовательности a0, a1,..., an, где a0an = 0. Это число определяется следующим образом.

394 Глава 32. Многочлены II Все нулевые члены рассматриваемой последовательности исключаются, а для оставшихся ненулевых членов вычисляется количество пар соседних членов разного знака.

32.3. Пусть N(x) число перемен знака в последовательности f(x), f (x),..., f(n)(x), где f многочлен степени n. Докажите, что тогда число корней многочлена f (с учётом их кратности), заключённых между a и b, где f(a) = 0, f(b) = 0 и a < b, не превосходит N(a) - N(b), причём число корней может отличаться от N(a) - N(b) лишь на чётное число (Фурье–Бюдан).

32.4. а) Докажите, что количество положительных корней многочлена f(x) = a0xn + a1xn-1 +... + an, где an = 0, не превосходит числа перемен знака в последовательности a0, a1,..., an (правило Декарта).

б) Докажите, что количество отрицательных корней многочлена f(x) = a0xn +a1xn-1 +...+an, где an = 0, не превосходит числа перемен знака в последовательности (-1)na0, (-1)n-1a1,..., an.

32.5. Докажите, что если в многочлене f(x) = a0xn + a1xn-1 +... + + an, где an = 0, отсутствуют 2m последовательных членов (т.е. ко эффициенты при этих членах равны нулю), то у этого многочлена не менее 2m мнимых (не вещественных) корней, а если отсутствуют 2m + + 1 последовательных членов, то в случае, когда их заключают члены разного знака, многочлен имеет не менее 2m мнимых корней, а в случае, когда их заключают члены одного знака, многочлен имеет не менее 2m + 2 мнимых корней (де Гуа).

Рассмотрим многочлены f(x) и f1(x) = f (x). Будем искать наибольший общий делитель многочленов f и f1 по алгоритму Евклида:

f = q1f1 - f2, f1 = q2f2 - f3,......

fn-2 = qn-1fn-1 - fn, fn-1 = qnfn.

Последовательность f, f1,..., fn-1, fn называют последовательностью Штурма многочлена f.

Pages:     | 1 |   ...   | 45 | 46 || 48 | 49 |   ...   | 65 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.