«ЗАД АЧИ П О АЛГЕ БР Е, АР И Ф МЕ Т И КЕ И АН АЛИ ЗУ Учебное пособие Москва Издательство МЦНМО 2007 УДК 512.1+517.1+511.1 ББК 22.141+22.161 П70 Прасолов В. В. П70 Задачи по алгебре, арифметике и анализу: Учебное пособие. ...»

Поэтому если a < 0, то f (x) > 0 для всех x. В этом случае функция f(x) возрастает от до +, поэтому f(x) = 0 ровно для одного значения x. При a = 0 получаем уравнение ex = 0, которое не имеет решений. Пусть теперь a > 0. Тогда уравнение f (x) = 0 имеет единственное решение x0 = ln a. При этом f(x0 ) = a(1 ln a); значит, f(x0 ) > 0 при a < e, f(x0 ) = 0 при a = e и f(x0 ) < 0 при a > e. Функция f(x) сначала монотонно убывает от + до f(x0 ), потом возрастает от f(x0 ) до +.

28.65. О т в е т: при a > e1/e решений нет; при 0 < a 1 или a = e1/e решение одно; при 1 < a < e1/e два решения.

Рассмотрим функцию f(x) = ax x. Ясно, что f (x) = ax ln a 1.

Если 0 < a < 1, то функция f(x) монотонно убывает от + до.

При a = 1 решение единственно: x = 1. Если a > 1, то уравнение f (x0 ) = 0 имеет единственный корень x0 = loga (ln a). При этом Функция f(x) сначала монотонно убывает от + до f(x0 ), потом монотонно возрастает от f(x0 ) до +.

Ясно, что f(x0 )=0 тогда и только тогда, когда a1/ ln a =aloga (1/ ln a), т. е. ln 28.66. О т в е т: при 0 < a < ee три решения; при 1 < a < e1/e два решения; при a = e1/e или ee a < 1 одно решение; при a > e1/e решений нет.

Рассмотрим сначала случай a > 1. В этом случае Поэтому количество решений уравнения ax = loga x равно количеству решений уравнения ax = x. Это уравнение исследовано в решении задачи 28.65.

Рассмотрим теперь случай, когда 0 < a < 1. Пусть f(x) = loga x ax. При изменении x от 0 до + функция f(x) изменяется от + до. Поэтому если f (x) < 0 для всех x > 0, то рассматриваемое уравнение имеет единственное решение.

Если x > 0, то знак числа совпадает со знаком числа g(x) = (ln a)2 xax 1, поскольку ln a < 0.

Далее, Значит, g (x) обращается в нуль в точке x0 = 1/ ln a. При этом g(x0 ) = g(x) < 0 для всех x > 0, поэтому функция f(x) строго монотонна, и рассматриваемое уравнение имеет единственное решение. При a = ee функция f(x) тоже монотонна.

Остаётся рассмотреть случай, когда 0 < a < ee. Решение уравнения ax = x всегда будет решением рассматриваемого уравнения.

При 0 < a 1 это уравнение имеет единственное решение x1. Докажем, что g(x1 ) > 0, т. е. (ln a)2 x1 ax1 > 1. Поскольку ax1 = x и a = x1/x1, получаем ln a = ln x1 и x1 ax1 = x2. Таким образом, приходим к неравенству (ln x1 )2 > 1. Поэтому достаточно доказать, что x1 < 1/e.

Рассмотрим вспомогательную функцию (x) = x1/x. Ясно, что (x1 ) = x1 1 = a и (1/e) = ee. При 0 < x < 1/e функция (x) возрастает, поскольку Кроме того, 0 < a < e, т. е. 0 < (x1 ) < (1/e). Значит, x1 < 1/e.

При изменении x от 0 до x0 = 1/ ln a функция g(x) монотонно возрастает от до g(x0 ); затем она монотонно убывает до.

Поэтому неравенство g(x1 ) > 0 показывает, что g(x) обращается в нуль в двух точках x2 и x3, причём x2 < x1 < x3. Следовательно, f(x2 ) < 0 и f(x3 ) > 0. Учитывая то, что мы знаем о знаке f (x), получаем, что f(x) обращается в нуль ровно в трёх точках: x1, 28.67. О т в е т: три. Легко угадываются “ ” x1 = 1/2 и x2 = =1/4. Кроме того, есть корень уравнения x=. А больше трёх корней это уравнение иметь не может согласно задаче 28.66.

З а м е ч а н и е. Если попытаться решить это уравнение графически, то может показаться, что у него только один корень.

Но в действительности графики пересекаются не в одной точке, а в трёх.

28.68. Прежде всего заметим, что многочлен fn (x) не имеет кратных корней (задача 28.18). Предположим, что требуемое утверждение доказано для n = 0, 1,..., 2k. (Мы начинаем с k = 0:

для многочлена f0 (x) = 1 утверждение очевидно.) Докажем, что многочлен f2k+1 (x) имеет ровно один вещественный корень. Степень этого многочлена нечётна, поэтому один корень у него есть, а если бы у него было два корня, то между ними был бы корень производной f2k+1 (x) = f2k (x), чего не может быть.

Докажем теперь, что многочлен f2k+2 (x) не имеет вещественных корней. Между любыми двумя корнями многочлена f2k+2 (x) должен быть корень его производной f2k+2 (x) = f2k+1 (x), поэтому у многочлена f2k+2 (x) не более двух корней. Степень многочлена f2k+2 (x) чётна, поэтому у него не может быть ровно один корень.

Итак, предположим, что у многочлена f2k+2 (x) есть ровно два корня x1 и x2. Между ними расположен корень x0 многочлена Но x0 — точка минимума функции f2k+2 (x). Поэтому f2k+2 (x) для всех x. Это противоречит тому, что у f2k+2 (x) есть два корня.

28.69. Положим g(x) = f(x + T), где T — постоянное число. Тогда g (x) = (x + T) f (x + T) = f (x + T). Поэтому если f(x + T) = f(x), то g (x) = f (x) и f (x) = f (x + T).

28.70. Предположим, что функция f(x) = sin x + sin x периодическая. Тогда согласно задаче 28.69 функция f (x) = cos x+ cos x тоже периодическая. Но согласно задаче 26.2 эта функция непериодическая.

28.71. Пусть Тогда С другой стороны, 28.72. Применим индукцию по n. При n = 2 нужно докаx1 + x Достаточно рассмотреть случай, когда x1 < x2 <... < xn. В этом случае у производной многочлена (x x1 )... (x xn ) есть n положительный корень y1 < y2 <... < yn1. Согласно задаче 28. k (x1,..., xn ) = k (y1,..., yn1 ). Поэтому, применив к набору чисел y1,..., yn1 предположение индукции, мы получим все требуемые неравенства, кроме неравенства n1 n1 (x1,..., xn ) Возведём обе части этого неравенства в степень n 1, а затем поделим на r1... xn. В результате перейдём к неравенству средним арифметическим и средним геометрическим для чисел 28.73. Применим индукцию по n. При n = 2 нужно доказать очевидное неравенство (x1 + x2 )2 4x1 x2. Пусть теперь n 3.

Достаточно рассмотреть случай, когда x1 < x2 <... < xn. В этом случае у производной многочлена (x x1 )... (x xn ) есть n корень y1 < y2 <... < yn1. Согласно задаче 28.71 k (x1,..., xn ) = = k (y1,..., yn1 ). Поэтому, если k n 2, то можно применить предположение индукции к набору чисел y1,..., yn1 и получить требуемое неравенство.

Остаётся доказать, что Здесь n (x1,..., xn ) = x1... xn. Поэтому можно считать, что произведение x1... xn отлично от нуля. Ясно, что Поэтому мы переходим к неравенству 28.74. Предположим, что причём P0 (x) = 0 и n — наименьшее натуральное число, для которого имеет место тождество такого вида. Из минимальности n следует, что Pn (x) = 0. С другой стороны, если x = k, где k — целое число, то sin x = 0, поэтому Pn (k) = 0 для всех целых k. Но многочлен Pn не может иметь бесконечно много корней. Получено противоречие.

28.75. П е р в о е р е ш е н и е. Предположим, что причём P0 (x) = a0 x + a1 x +... + ak, a0 = 0. Рассмотрим функцию G(x) = k nx (P0 (x)enx + P1 (x)e(n1)x +... + Pn (x)). С одной стороны, lim x = 0. Получено противоречие.

В т о р о е р е ш е н и е. Предположим, что выполняется тождество (1), причём из всех тождеств такого вида выбрано то, для которого n минимально. Из минимальности n следует, что многочлен Pn (x) отличен от нуля. Поделив обе части тождества (1) на Pn (x), получим где R0 (x),..., Rn1 (x) — рациональные функции, причём R0 (x)=0.

Продифференцировав это тождество и поделив обе части на ex, получим тождество (R + nR0 )e(n1)x + (R + (n 1)R1 )e(n2)x +... + (R + Rn1 ) = 0.

Из этого тождества легко получить тождество для многочленов:

достаточно умножить обе части на общий знаменатель рациональных функций. Поэтому из минимальности n следует, что R + nR0 = 0,..., R + Rn1 = 0. Пусть R0 = P/Q, где P и Q — взаn имно простые многочлены (мы знаем, что P = 0). Из равенства R + nR0 = 0 следует, что P Q PQ + nPQ = 0. Многочлены P Q и PQ делятся на Q, поэтому PQ делится на Q, а значит, Q делится на Q.

Это возможно лишь в том случае, когда Q — константа. Аналогично доказывается, что P — константа. Поэтому R = 0, а значит, R0 = R /n = 0. Получено противоречие.

28.76. а) Достаточно заметить, что б) Чтобы найти A0, положим x = a. В результате получим f(a) = A0. Продифференцировав выражение для f(x), получим Положив x = a, получаем f (a) = A1. Теперь дифференцируем выражение для f (x):

Снова подставляя x = a, получаем f (a) = 1 · 2A2. Продолжая эти 28.77. Ясно, что T(a) = f(a). Далее,.........................................................

Поэтому T(a)=f(a), T(a)=f(a),..., T(n) (a)=f(n) (a) и T(n+1) (x)= Рассмотрим вспомогательную функцию (x) = f(x) T(x). Для неё (a) = (a) = (a) =... = (n) (a) = 0 и (n+1) (x) = f(n+1) (x).

ни сама функция ни её производные до (n + 1)-й включительно не обращаются в нуль в точках, отличных от a.

Фиксируем точку x = a. Из равенств (a) = = 0 следует, что (x) = (x) (a). Поэтому по теореме Коши (задача 28.44) существует точка x1 между a и x, для которой равенств (a) = (a) = 0 следует, что между a и x), для которой дения, получаем где точка xn+1 лежит между a и x.

= xn+1. Тогда 28.78. Эти утверждения непосредственно следуют из формулы Тейлора для a = 0 и соответствующих функций f(x).

ИНТЕГРАЛ

Функцию F(x), для которой F (x) = f(x), называют первообразной или неопределённым интегралом функции f(x). Для функции, определённой на отрезке (или на всей вещественной прямой), её первообразная определена с точностью до прибавления некоторой константы C. Действительно, если F1 (x) и F2 (x) — первообразные функции f(x), а (x) = F1 (x) F2 (x), то (x) = 0. Поэтому согласно задаче 28.38 функция (x) постоянна.

Первообразную функции f(x) обозначают f(x) dx.

29.2. Пусть F(x) — первообразная функции f(x) на отрезке [a, b], (y) — дифференцируемая функция на отрезке [p, q], причём a (y) b для всех y из отрезка [p, q] и у любой точки y0 из отрезка [p, q] есть такая окрестность U(y0 ), что если y принадлежит U(y0 ) и y = y0, то (y) = (y0 ). Докажите, что тогда F( (y)) — первообразная функции f( (y)) (y).

Результат задачи 29.2 можно сформулировать следующим образом: если f(x) dx = F(x) + C, то f( (y)) (y) dy = F( (y)) + C.

Удобно ввести обозначение (y) dy = d (y).

29.4. Вычислите tg x dx.

29.5. Докажите, что f(x) dx можно вычислить следующим образом. Пусть x = (y) — дифференцируемая функx).

ция, имеющая обратную функцию y = Вычислим f( (y)) (y) dy=F(y) и положим y=(x). Тогда F((x)) — искомый интеграл.

29.6. Вычислите 29.7. Вычислите 29.9. Докажите, что (формула интегрирования по частям).

29.10. Вычислите с помощью интегрирования по частям:

а) x3 ln x dx; б) arctg x dx; в) x cos x dx; г) xex dx.

29.13. Докажите, что 29.14. Пусть P(x) — многочлен. Вычислите интегралы:

P(x)eax dx; б) P(x) sin ax dx; в) P(x) cos ax dx.

Пусть на отрезке [a, b] задана функция f(x). Разобьём этот отрезок на части точками x0 = a < x1 < x2 <... < xn1 < < b = xn. На каждом отрезке [xk, xk+1 ] выберем произвольную точку k и рассмотрим так называемую интегральную сумму f(k )(xk+1 xk ). Оказывается, что если функция f(x) непреk= рывна и наибольшая длина отрезка разбиения стремится к нулю, то интегральные суммы имеют конечный предел, который не зависит от выбора разбиения и от выбора точек k. Этот предел называют определённым интегралом от функции f(x) по отрезку [a, b] и обозначают f(x) dx.

Функцию f(x) называют интегрируемой на отрезке [a, b], если для неё существует указанный предел интегральных сумм.

Интегрируемыми могут быть не только непрерывные функции, но нас в основном будут интересовать непрерывные функции.

Чтобы доказать интегрируемость непрерывных функций, введём следующие вспомогательные понятия. Пусть на отрезке [a, b] задана непрерывная функция f(x) и задано некоторое разбиение этого отрезка. Для каждого отрезка [xk, xk+1 ] рассмотрим Mk и mk — наибольшее и наименьшее значения функции f(x) на этот отрезке. Суммы назовём верхней и нижней интегральными суммами; они зависят только от разбиения и не зависят от выбора точек k.

Ясно, что каждая интегральная сумма заключена между верхней и нижней интегральными суммами для того же самого разбиения.

29.15. Докажите, что при добавлении новых точек разбиения нижняя интегральная сумма не уменьшается, а верхняя не увеличивается.

29.16. Докажите, что любая нижняя интегральная сумма не больше любой верхней интегральной суммы.

29.17. Пусть I — точная верхняя грань нижних интегральных сумм, — произвольная интегральная сумма, s и S — нижняя и верхняя интегральные суммы, соответствующие тому же разбиению, что и Докажите, что 29.18. Докажите, что любая непрерывная функция f(x) на отрезке [a, b] интегрируема.

29.19. Пусть f(x) — непрерывная функция на отрезке [a, b]. Докажите, что на отрезке [a, b] существует точка для которой f(x) dx = f()(b a).

29.20. Докажите, что если непрерывная функция f(x) го, если f(x0 ) > 0 для некоторой точки x0 отрезка [a, b], то Часто бывает удобно рассматривать определённые интегралы При таких соглашениях остаются верными формулы замены переменных и соотношение 29.21. Пусть f(x) — непрерывная функция на отрезке [a, b] и F(x) = F(x) — первообразная функции f(x).

29.22. Пусть f(x) — непрерывная функция на отрезке [a, b]. Докажите, что где F(x) — первообразная функции f(x) (формула Ньютона– Лейбница).

Для разности F(b) F(a) мы будем использовать обозначение всех натуральных чисел, не превосходящих n и имеющих с n одинаковую чётность.

лиса).

29.25. Пусть f1 (x) = f(t) dx, f2 (x) = f1 (t) dx,..., fn (x) = = fn1 (t) dx. Докажите, что Пусть функция f(x) на отрезке [a, b] неотрицательна. Член f(k )(xk1 xk ) интегральной суммы заключён между m(xk1 xk ) и M(xk1 xk ), где m и M — наибольшее и наименьшее значения функции f(x) на отрезке [xk, xk+1 ]. Таким образом, этот член заключён между площадью прямоугольника, содержащегося в фигуре под графиком функции y = f(x), и площадью прямоугольника, содержащего часть этой фигуры, расположенную над отрезком [xk, xk+1 ]. Поэтому определённый интеграл f(x) dx — это площадь фигуры, ограниченной графиком y = f(x) 29.26. Вычислите площадь круга радиуса 1 с помощью определённого интеграла.

29.27. Вычислите площадь под графиком функции y = = sin x на отрезке от 0 до Пусть тело расположено в пространстве с прямоугольными координатами Oxyz, причём проекция этого тела на ось Ox — это отрезок [a, b]. Предположим, что плоскость, проходящая через точку x отрезка [a, b] перпендикулярно оси Ox, высекает на этом теле фигуру площади S(x). Тогда объём этого тела определяется 29.28. Вычислите с помощью определённого интеграла объём V конуса с радиусом R и высотой h.

29.29. Вычислите с помощью определённого интеграла объём V шара радиуса R.

29.30. Найдите объём фигуры, образованной при пересечении двух прямых круговых цилиндров радиуса R, оси которых перпендикулярны и пересекаются.

29.31. Найдите объём фигуры, отсекаемой от цилиндра плоскостью, проходящей через диаметр его основания. Известны радиус цилиндра R и высота полученной фигуры h.

Рассмотрим кривую y = f(x), где f(x) — непрерывная функция на отрезке [a, b]. Пусть x0 = a < x1 <... < xn1 < b = xn — точки на этом отрезке. Рассмотрим ломаную с вершинами Ak = (xk, f(xk )), k = 0, 1,..., n. Если длина этой ломаной стремится к конечному пределу l, когда длина наибольшего звена ломаной стремится к нулю, то это число l называют длиной кривой.

29.32. Докажите, что если функция f(x) на отрезке [a, b] имеет непрерывную производную, то кривая y = f(x) имеет длину 29.33. Вычислите с помощью определённого интеграла длину окружности радиуса R.

29.34. Вычислите длину дуги параболы 2y = x2 от точки (0, 0) до точки x0, 0.

29.35. Вычислите длину дуги кривой y = ch x, заключённой между точками (x1, y1 ) и (x2, y2 ).

29.36. Пусть график функции y = f(x) на отрезке [a, b] параметризован параметром t, т. е. задана монотонно возрастающая функция x(t), причём a = x(t0 ) и b = x(t1 ), и мы полагаем y(t) = f(x(t)). Докажите, что длина этого графика равна 29.37. Вычислите длину астроиды, заданной уравнением x2/3 + y2/3 = a2/3.

29.38. Вычислите длину ветви циклоиды Пусть f(x) — непрерывная положительная функция на отрезке [a, b], x0 = a < x1 <... < xn1 < b = xn — некоторые точки на отрезке [a, b]. Будем вращать кривую y = f(x) вокруг оси Ox.

Ломаная с вершинами Ak = (xk, f(xk )) заметает при этом некоторую поверхность, состоящую из усечённых конусов. Если сумма площадей боковых поверхностей этих конусов имеет предел, когда длина наибольшего из отрезков Ak Ak+1 стремится к нулю, то этот предел называют площадью поверхности вращения, заметаемой кривой y = f(x).

29.39. Докажите, что если положительная функция f(x) на отрезке [a, b] имеет непрерывную производную, то площадь поверхности вращения, заметаемой кривой y = f(x), равна 29.40. Докажите, что площадь поверхности шара радиуса R, заключённой между двумя параллельными плоскостями (пересекающими шар), равна 2Rh, где h — расстояние между этими плоскостями.

29.41. Пусть t > 0.

б) Докажите, что 29.42. Докажите, что если 0 < t 29.43. Докажите, что если 0 0.

29.45. Пусть t > 0. Докажите, что 29.46. Докажите, что для любого t > если расстояние между точками x и x отрезка [a, b] меньше, то |f(x ) f(x )| <. Поэтому если наибольшая длина отрезка разбиения меньше, то Mk mk <, а значит, Таким образом, если наименьшая длина отрезка разбиения стремится к нулю, то разность S s стремится к нулю.

29.19. Пусть M и m — наибольшее и наименьшее значения функции f(x) на отрезке [a, b]. Тогда каждая интегральная сумма где число c заключено между m и M. Непрерывная функция на отрезке принимает все значения между m и M, поэтому c = f() для некоторой точки отрезка [a, b].

29.20. Если f(x) 0 для всех точек отрезка [a, b], то все интегральные суммы неотрицательны, поэтому их предел тоже неотрицателен.

Предположим теперь, что f(x0 ) = c > 0. Можно считать, что x0 — внутренняя точка отрезка [a, b]. Выберем > 0 так, что f(x) > c/2 при |x x0 | <. Можно считать, что a0 + x0 b.

Тогда Два крайних интеграла неотрицательны, а средний интеграл больше 2 · c/2 = c > 0.

29.21. Пусть точки x и x + x лежат на отрезке [a, b]. Тогда F(x + x) F(x) = равен f()x, где = f(x) dx. Кроме того, согласно задаче 29.21 (x)=f(x). Поэтому (x) тоже первообразная, а значит, (x) = F(x) + C, где C — некоторая константа. Заметим, что (a) = 0. Поэтому F(a) = C. Следовательно, Тогда, интегрируя по частям, получаем Первый член равен нулю, поэтому Un = (n 1) чит, Un2 = Un4 и т. д. Последовательно применяя эту форn мулу, получаем требуемое.

поэтому U2n+2 < U2n+1 < U2n. Используя формулы из задачи а), получаем Следовательно, 29.37. О т в е т: 6a. Астроиду можно задать параметрически:

x = a sin3 t, y = a cos3 t. Достаточно вычислить длину четверти астроиды, для которой x и y неотрицательны. Ясно, что x = =3a cos t sin2 t и y =3a sin t cos2 t. Поэтому x 2 +y 2 =3a sin t cos t, а значит, длина четверти астроиды равна Длина всей астроиды равна 6a.

29.38. О т в е т: 8a. Ясно, что Поэтому длина ветви циклоиды равна 29.39. Мы предполагаем известным из стереометрии, что площадь боковой поверхности усечённого конуса равна произведению образующей на длину среднего сечения. Площадь боковой поверхности конуса, образованного вращением звена Ak Ak+1, равна По формуле Лагранжа для некоторой точки k отрезка [xk, xk+1 ]. Поэтому сумма площадей боковых поверхностей конусов равна Нужно сравнить эту сумму с интегральной суммой Это сравнение несложно получить, используя равномерную непреp рывность функции f(x) и ограниченность функции 1+(f (x))2.

29.40. Мы рассматриваем поверхность шара как фигуру, обраx зованную при вращении кривой y= R2 x2. Ясно, что y = p и 1 + y 2 = p. Поэтому рассматриваемая площадь равна (задача 29.41). Из первого неравенства следует, что Это неравенство эквивалентно неравенству При 0 < t Поэтому согласно задаче 29.42 f (t) > 0, т. е. на рассматриваемом интервале функция f(t) монотонно возрастает. Значит, f(t) f, 29.44. Согласно задаче 29. выполняется. С другой стороны, требуемое неравенство очевидным образом выполняется, если 2t > 3, т. е. t > 3/2.

29.45. Если x > 0, то Действительно, имеем неравенства Интегрируя эти неравенства, получаем требуемое.

1 + x ex 1 + ea x аналогично получаем 1 + t + et 1 + t + ea и т. д.

б) Доказательство аналогично. При 0 x t получаем 1 e e.

неравенство переписывается в виде t и т. д.

29.48. Предположим, что если a x b, то f (x) (f(x)) 1, мает лишь значения, заключённые между /2 и /2, поэтому F(b) F(a) <. Получено противоречие.

29.49. О т в е т: /4. Рассматриваемую сумму можно запиP 29.50. О т в е т: Рассматриваемую сумму можно запиr “ k ” равна З а м е ч а н и е. Другое доказательство можно найти в решении задачи 30.8 а).

Требуемое тождество получается интегрированием этого тождества от 0 до 1. Действительно, (1 t)k dt = xk dx = и 29.54. а) Подынтегральную функцию можно записать в виде P(x)(x + 1)n, где P(x) = (x 1)n. Воспользовавшись формулой из задачи 29.13, получим При x = 1 все члены обращаются в нуль, а при x = 1 обращаются в нуль все члены, кроме последнего. Поэтому интегрируем это выражение почленно. Остаётся приравнять полученное выражение выражению из задачи а).

29.55. У многочлена f(x) нет кратных корней, поэтому эквиa лучим следующее условие: F(a2 ) F(a1 ) = F(a2 ) F(a3 ) = F(a4 ) = F(a4 ) = F(a6 ) =...

Покажем, что если F(x) = Tn+1 (x) — многочлен Чебышева, то F обладает требуемым свойством. Из равенства Tn+1 (cos ) = = cos(n + 1) следует, что sin T (cos ) = (n + 1) sin(n + 1).

Поэтому если T (cos ) = 0, то sin(n + 1) = 0, а значит, Tn+1 (cos ) = cos(n + 1) = ±1. Ясно также, что при прохождении через корень F(x) меняет знак.

29.57. Интегрируя по частям, получаем Поэтому для Jk = Jk = kJk1. Остаётся заметить, что Пусть {an } — некоторая последовательность, bn = a1 + a2 +... + an.

Если последовательность {bn } имеет предел, то говорят, что ряд an сходится (в противном случае — расходится). Число lim bn называют при этом суммой ряда.

дого натурального k. n= 30.3. Пусть |x| < 1. Вычислите сумму ряда 30.2. Вычисление бесконечных произведений называют гармоническим. Этот ряд расходящийся (заРяд дача 30.6). Мы будем использовать обозначение 30.6. Докажите, что для любого натурального n 30.7. Докажите, что ряд 1 ++ + +... расходится.

lim an.

lim bn = ln 2.

30.9. а) Докажите, что б) Докажите, что 30.10. Докажите, что Докажите, что lim an = ln 2.

30.12. Докажите, что 30.13. Докажите, что 30.14. Докажите, что 30.15. Пусть p1 = 2, p2 = 3,... — последовательные простые числа.

а) Докажите, что 30.16. Докажите, что существует предел = 0,5772157... из задачи 30.16 называют постоянной Предел Эйлера.

Эйлера.

30.18. Докажите, что если 1 < x < 1, то 30.19. Докажите, что если 1 < x < 1, то 30.20. а) Докажите, что для любого натурального n б) Докажите, что 30.21. а) Докажите, что согласно задаче 30.6 этот ряд расходится.

при n.

30.19. Вычитая почленно из ряда ряд получаем требуемое.

б) Непосредственно следует из а) при n = 1, поскольку ln 1 = 0.

30.21. а) Формулу из задачи 30.20 а) можно переписать в виде Остаётся заметить, что сумма этого ряда меньше б) и в) Неравенство из задачи а) можно переписать в виде то из неравенств (1) получаем Таким образом, an e 12n < an+1 e 12(n+1) и an > an+1. Поэтому последовательность {an e 12n } возрастает, а последовательность {an } убывает. При этом a1 e 12 < an e 12n < an < a1, поэтому обе последовательности имеют предел. Поскольку e 12n 1, эти пределы равны одному и тому же числу a. Ясно, что an e 12n < a < an, т. е. a = an e 12n для некоторого между 0 и 1. Таким образом, 30.22. Формулу Валлиса (задача 29.23) можно переписать слеn)!!

Выразим n! и (2n)! как an nn+1/2 en и a2n (2n)2n+1/2 e2n и подставим эти выражения в формулу Валлиса:

В результате получим a = 2.

30.23. Ясно, что lim (a2k1 a2k ) = 0, поэтому достаточно реn шить задачу б). Из тождества следует, что Воспользовавшись после этого результатом задачи 23.7, получим т. е.

Эти неравенства показывают, что последовательность pn невозрастающая и pn > pN1 /2 > 0. Поэтому предел lim pn существует и не равен нулю.

По условию существует предел lim Pn, поэтому ряд (Pn Pn1 ) сходится. Но в таком случае должен сходиться и ряд (pn pn1 ), поэтому существует предел lim pn. Нужно лишь проверить, что этот предел отличен от нуля. Рассмотрим для этого ряд.

Он сходится, поскольку сходится ряд |ak | и последовательность 1 + ak имеет“предел, равный 1. Следовательно, бесконечное проak ” изведение 1 сходится абсолютно, поэтому, как только что было доказано, последовательность qn = 1 имеет конечный предел. Но qn = p1, поэтому lim pn = 0.

ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ

31.1. Докажите, что если p — простое число и a не делится на p, то (малая теорема Ферма).

31.2. Пусть p = 4k + 3 — простое число. Докажите, что если a2 + b2 делится на p, то оба числа a и b делятся на p.

31.3. Докажите, что существует бесконечно много простых чисел вида 4k + 1.

31.4. а) Пусть p — простое число. Докажите, что если q — простой делитель числа 2p 1, то q 1 делится на p.

б) Приведите пример простого числа p, для которого число 2p 1 не простое.

Согласно малой теореме Ферма для любого простого p число 2p 2 делится на p. Натуральное число n > 1 называют псевдопростым, если 2n 2 делится на n.

31.5. Докажите, что число 341 = 11 · 31 является псевдопростым.

31.6. Докажите, что если n — псевдопростое число, то число 2n 1 тоже псевдопростое.

З а м е ч а н и е. Существуют и чётные псевдопростые числа.

Например, число 161 038 псевдопростое.

400 Глава 31. Элементы теории чисел Функция Эйлера (n) равна количеству тех из чисел 1, 2,...

..., n 1, которые взаимно просты с n. Например, если p — простое число, то (p) = p 1.

31.7. а) Докажите, что если p — простое число, то (pn ) = = pn pn1.

б) Докажите, что если числа m и n взаимно простые, то (mn) = (m) (n).

31.8. Докажите, что если число a взаимно просто с n, то a (n) 1 (mod n) (теорема Эйлера).

31.9. Числа a и n взаимно простые. Докажите, что для некоторого натурального числа m число am 1 делится на n.

31.10. Докажите, что n = (d), где суммирование ведётся по всем числам d, делящим n.

31.11. а) Найдите остаток от деления 1712147 на 52.

б) Найдите остаток от деления 1261020 на 138.

31.12. Пусть a и m — взаимно простые числа, k — наименьшее натуральное число, для которого ak 1 (mod m).

Докажите, что (m) делится на k.

31.13. Пусть a 2 и n — натуральные числа. Докажите, что (an 1) делится на n.

Пусть n = p1 1 p2 2... pk k — разложение натурального числа n на простые множители. Назовём обобщённой функцией Эйлера функцию L(n), которая равна 1 при n = 1 и НОК(p1 1 (p1 1),...

31.14. Докажите, что если числа x и n взаимно простые, то xL(n) 1 (mod n).

31.15. а) Докажите, что (p 1)! + 1 делится на p тогда и только тогда, когда число p простое (теорема Вильсона).

б) Докажите, что 31.16. Пусть a(n) и b(n) — остатки от деления чисел ((n 1)!)2 и ((n 1)! + 1)2 на n. Докажите, что f(n) = na(n) + + 2b(n) — простое число, причём любое простое число можно представить в таком виде.

31.17. Докажите, что если выполняются сравнения a = НОК(n1,..., nn ).

31.18. Пусть p — простое число, n и a — натуральные числа, не делящиеся на p. Докажите, что если сравнение xn a (mod p) имеет решение, то сравнение xn a (mod pr ) имеет решение для любого натурального r.

31.19. Докажите, что если a b (mod pn ), где p — простое число, то ap bp (mod pn+1 ).

31.20. Пусть a 2 и n — натуральные числа. Докажите, что ak 1 (mod an 1) тогда и только тогда, когда k делится на n.

31.21. Пусть p — простое число, f(x1,..., xn ) — многочлен с целыми коэффициентами, степень которого по каждой переменной меньше p. Докажите, что если для всех целых x1,..., xn выполняется сравнение f(x1,..., xn ) 0 (mod p), то все коэффициенты многочлена f(x1,..., xn ) делятся на p.

31.22. Пусть p — простое число, f(x1,..., xn ) — многочлен с целыми коэффициентами, для которого сравнение f(x1,..., xn ) 0 (mod p) выполняется для всех целых x1,...

..., xn. Заменим в каждом мономе этого многочлена xm, i где m p, на xr, где r — остаток от деления m на p. Докаi жите, что в результате получится тождественное сравнение 0 0 (mod p).

31.23. Пусть f(x1,..., xn ) — многочлен с целыми коэффициентами и со свободным членом, равным нулю. ДоГлава 31. Элементы теории чисел кажите, что если степень этого многочлена меньше n, то сравнение f(x1,..., xn ) 0 (mod p), где p — простое число, имеет решение, отличное от (0, 0,..., 0) (Шевалле).

31.24. Пусть a, b, c — целые числа. Докажите, что сравнение ax2 + by2 + cz2 0 (mod p) имеет решение (x, y, z) = = (0, 0, 0) для любого простого числа p.

Пусть d1, d2,... — различные делители числа n, включая 1 и n.

Функция k (n) определяется как сумма dk + dk +... В частности, 0 (n) — количество делителей числа n, 1 (n) — сумма делителей числа n. Обычно используется обозначение = 1 (n).

31.25. а) Докажите, что если p — простое число, то б) Докажите, что если числа m и n взаимно простые, то k (mn) = k(m)k (n).

Число n называют совершенным, если т. е. сумма всех делителей числа n, отличных от n, равна самому числу n.

31.26. а) Докажите, что если число 2p 1 простое, то число 2p1 (2p 1) совершенное (Евклид).

б) Докажите, что если n — чётное совершенное число, то существует простое число вида 2p 1, для которого n = 2p1 (2p 1) (Эйлер).

31.27. Докажите, что если n — нечётное число, у котороn) го есть ровно два разных простых делителя, то < 2n.

31.28. Докажите, что натуральное число n можно выn)/n брать так, что отношение будет сколь угодно велико.

31.29. а) Приведите пример чисел m = n, для которых (n) = (m).

б) Докажите, что если m = n, то n (n) = m (m).

в) Приведите пример чисел m = n, для которых n(n) = = m(m).

31.30. Докажите, что Функция Мёбиуса определяется следующим образом:

где сумма берётся по всем делителям d числа n (Мёбиус).

31.32. Докажите, что если F(n) = f(d), то 31.33. Пусть p — простое число, f(x) = xn + a1 xn1 +...

... + an — многочлен с целыми коэффициентами. Докажите, что существует не более n различных целых чисел xi, для которых 0 xi p 1 и f(xi ) делится на p (Лагранж).

Целое число a называют квадратичным вычетом по модулю p, если a b2 (mod p) для некоторого целого числа b. В противном случае число a называют квадратичным невычетом.

31.34. Пусть p > 2 — простое число. Докажите, что среди чисел 1, 2,..., p 1 ровно половина квадратичных вычетов и ровно половина квадратичных невычетов по модулю p.

31.35. Пусть 1 a p 1, где p > 2 — простое число. Докажите, что число a является квадратичным вычетом по модулю p тогда и только тогда, когда a(p1)/2 1 (mod p) (Эйлер).

404 Глава 31. Элементы теории чисел 31.36. Пусть p > 2 — простое число. Докажите, что число 1 является квадратичным вычетом по модулю p тогда и только тогда, когда p 1 (mod 4).

31.37. Пусть r — это 2 или нечётное число, p1,..., pr — различные простые числа вида 4k + 1. Предположим, что = 1 для всех i = j. Докажите, что уравнение x2 dy2 = = 1, где d = p1... pr, имеет решение в целых числах.

31.8. Квадратичный закон взаимности Для простого числа p символ Лежандра определяется слеp дующим образом:

Символ Лежандра мы иногда будем обозначать (a/p).

Согласно задаче 31.35, если p — нечётное простое число, то (a/p) a(p1)/2 (mod p). Следовательно, (ab/p) = (a/p)(b/p) и Квадратичный закон взаимности заключается в следующем. Пусть p и q — различные нечётные простые числа. Тогда Кроме того, если p — нечётное простое число, то = = (1)(p 1)/8.

Впервые квадратичный закон взаимности был доказан Гауссом. Сейчас известно много разных доказательств квадратичного закона взаимности. Как правило, они используют какие-то интерпретации символа Лежандра. Мы приведём две такие интерпретации, принадлежащие Гауссу (задача 31.38) и Золотарёву (задача 31.39).

31.38. Пусть p — нечётное простое число, а q — натуральное число, не делящееся на p. Для каждого натуральУсловия задач здесь минусов. Докажите, что 31.39. Пусть p — нечётное простое число, a — число, взаимно простое с p, и a,p : iai (mod p) — перестановка остатков от деления на p. Докажите, что тогда sgn a,p =(a/p), где sgn = 1 для чётной перестановки и sgn = 1 для нечётной перестановки (Золотарёв).

31.40. Докажите квадратичный закон взаимности с помощью леммы Гаусса (задача 31.38) и тождества из задачи 5.29.

31.41. а) Докажите квадратичный закон взаимности с помощью задачи 31.39.

б) Пусть m — нечётное простое число. Докажите, что 31.42. Докажите квадратичный закон взаимности с помощью леммы Гаусса и тождества из задачи 11.31 (Эйзенштейн).

31.44. Пусть p — простое число. Докажите, что = 31.45. Докажите, что существует бесконечно много простых чисел вида 6k + 1.

31.46. а) Пусть p = 2n 1 — простое число, причём p > 3.

б) Пусть p = 2n + 1 — простое число, причём p > 3. Докажите, что = 1.

31.47. Докажите, что 3n 1 не делится на 2n 1 при n > 1.

Пусть p — нечётное простое число, + i sin(2/p). Для каждого целого числа a можно рассмотреть но, что ga зависит только от остатка от деления a на p (и от самого числа p).

31.48. Докажите, что g0 = 0.

31.50. Докажите, что 31.52. Для каждого натурального n p 2 пара (n, n + 1) имеет один из четырёх видов: (R, R), (N, N), (N, R), (R, N), где R означает вычет, а N — невычет. Пусть RR, NN, NR, RN — количество всех пар соответствующего вида.

а) Докажите, что RR + NN RN NR = 1.

б) Пусть = (1)(p1)/2. Докажите, что в) Докажите, что Здесь мы доказываем, что любое простое число p = 4k + 1 можно представить в виде суммы квадратов двух целых чисел.

Различные подходы приведены в задачах 31.53– 31.55. Другие доказательства этого утверждения можно найти в решении задачи 36.19 а) и на с. 546.

Представление простого числа p = 4k + 1 в виде суммы двух квадратов единственно (задача 31.56).

Напомним, что простое число p = 4k + 3 нельзя представить в виде суммы двух квадратов (задача 4.45 а). Кроме того, произведение двух чисел, представимых в виде суммы двух квадратов, само представимо в виде суммы двух квадратов (задача 5.11).

31.53. Пусть p = 4k + 1 — простое число.

а) Докажите, что существует целое число x, для которого x2 + 1 делится на p.

б) Докажите, что можно выбрать целые числа 0 r1, r2 < < p и 0 s1, s2 < p так, что числа r1 x + s1 и r2 x + s будут давать одинаковые остатки при делении на p, причём (r1, s1 ) = (r2, s2 ).

в) Докажите, что p = (r1 r2 )2 + (s1 s2 )2.

31.54. Докажите, что любое простое число p = 4k + 1 можно представить в виде суммы квадратов двух целых чисел, воспользовавшись задачей 17.12.

31.55. Пусть p = 4k + 1 — простое число.

а) Докажите, что уравнение x2 + y2 = mp имеет решение в натуральных числах x, y, m.

б) Докажите, что если m > 1, то можно построить решение с меньшим m.

31.56. Докажите, что представление простого числа p = = 4k + 1 в виде суммы двух квадратов целых чисел единственно. (Мы не различаем представления p = x2 + y2, отличающиеся только перестановкой x и y или заменами знака x и y.) 31.57. Докажите, что если каждое из чисел a и b является суммой четырёх квадратов целых чисел, то их произведение ab тоже является суммой четырёх квадратов целых чисел.

408 Глава 31. Элементы теории чисел 31.58. Пусть p — нечётное простое число. Докажите, что существуют целые числа x, y и m, для которых 1 + x2 + y2 = = mp, причём 0 < m < p.

31.59. Пусть p — нечётное простое число.

а) Докажите, что можно выбрать натуральное число m 1.

31.69. Пусть p — простое число и S = 1n + 2n +... + (p 1)n.

Докажите, что 31.13. Первообразные корни по составному модулю Первообразные корни можно рассмотреть и для составного модуля m. Будем называть число x первообразным корнем по модулю m, если числа x, x2,..., x (m) — это все различные остатки, взаимно простые с m. В серии задач 31.71– 31.77 доказывается, что первообразный корень по модулю m существует тогда и только тогда, когда m = 2, 4, p или 2p, где p — нечётное простое число.

31.70. Докажите, что (1 + km)m 1 (mod m ) для любого m.

31.71. Пусть p — простое число. Докажите, что первообразный корень по модулю p является также первообразным корнем по модулю p.

31.72. Пусть x — первообразный корень по простому модулю p. Предположим, что xp (p1) 1 (mod p ), где 2.

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

31.73. Пусть x — первообразный корень по нечётному простому модулю p. Докажите, что по крайней мере одно из чисел x и x + p является первообразным корнем по модулю p2.

31.74. Докажите, что если x — первообразный корень по модулю p2, где p — нечётное простое число, то x — первообразный корень по модулю p для любого 2.

31.75. Пусть p — нечётное простое число. Докажите, что для любого натурального существует первообразный корень по модулю 2p.

31.76. Докажите, что первообразный корень по модулю 2n существует тогда и только тогда, когда n 2.

31.77. Докажите, что если m — это не число вида 2, 4, p или 2p, где p — нечётное простое число, то первообразных корней по модулю m не существует.

31.14. Теорема Чебышева о простых числах (n) — количество простых чисел, не превосходящих n.

Пусть 31.78. Докажите, что lim 31.79. Докажите, что 31.80. Докажите, что (n) < 3 ln З а м е ч а н и е. Чебышев доказал, что для достаточно больших n выполняются более точные неравенства 31.1. П е р в о е р е ш е н и е. Согласно задаче 4.62 набор остатков от деления на p чисел a, 2a,..., (p 1)a совпадает с набором Число b = 1 · 2 ·... · (p 1) не делится на p, поэтому ap1 1 (mod p).

Чтобы доказать это, нужно умножить обе части равенства на число b, для которого bb 1 (mod p).

В т о р о е р е ш е н и е. Покажем, что для любого натурального n число np n делится на p. Применим индукцию по n. При n = 1 утверждение очевидно. Предположим, что np n делится на p. Тогда число (n + 1)p (n + 1) = C1 np1 + C2 np2 +... + Cp1 n тоже делится на p, поскольку все числа Ck, где 1 k p 1, делятся на p (задача 14.30).

Если число n не делится на p, то из того, что np n = n(np1 1) делится на p, следует, что np1 1 делится на p.

31.2. Предположим, что одно из чисел a и b не делится на p.

Тогда другое число тоже не делится на p. Поэтому согласно малой теореме Ферма ap1 1 (mod p) и bp1 1 (mod p). Значит, ap1 + bp1 2 (mod p). С другой стороны, число ap1 + bp1 = a4k+2 + + b4k+2 = (a2 )2k+1 + (b2 )2k+1 делится на a2 + b2, поэтому оно делится на p.

31.3. Предположим, что p1,..., pr — все различные простые числа вида 4k + 1. Рассмотрим число (2p1... pr )2 + 1. Оно нечётно, поэтому все его простые делители имеют вид 4k ± 1. Согласно задаче 31.2 у этого числа не может быть простых делителей вида 4k 1. Остаётся заметить, что рассматриваемое число не делится 31.4. а) Предположим, что 2p 1 (mod q), где q — простое число. Ясно, что q = 2. Если q 1 не делится на p, то наибольший общий делитель чисел q 1 и p равен 1, поэтому существуют целые числа a и b, для которых ap + b(q 1) = (см. с. 43). Согласно малой теореме Ферма 2q1 1 (mod q). Поэтому 2 2ap+b(q1) (2p )a (2q1 )b 1 (mod q). Приходим к противоречию.

31.5. Число 2341 2 = 2(2340 2) = 2((210 )34 1) делится на 2 1 = 1023. Далее, 1023 = 3 · 341.

31.6. По условию 2n n 2 = na для некоторого натурального a.

Поэтому 22 1 2 = 2(22 2 1) = 2(2na 1). Это число делится на 31.7. а) Среди чисел 1, 2,..., pn 1 на p делятся pn1 1 чисел, а именно, числа p, 2p,..., p(pn1 1). Поэтому (pn ) = pn б) Числа m и n взаимно простые, поэтому существуют целые числа u и v, для которых um + vn = 1 (эти числа можно найти с помощью алгоритма Евклида). Пусть a и b — некоторые остатки от деления на m и n, т. е. 0 a m 1 и 0 b n 1. Сопоставим паре (a, b) число c, которое является остатком от деления числа avn+bum на mn. Ясно, что cavna (mod m) и cbumb (mod n).

Поэтому, в частности, разным парам (a, b) сопоставляются разные числа c. Мы получили взаимно однозначное отображение остатков от деления на m и n на остатки от деления на mn. При этом НОД(c, m) = НОД(a(1 um) + bum, m) = НОД(a, m) и НОД(c, n) = = НОД(b, n). Поэтому числа c и mn взаимно простые тогда и только тогда, когда числа a и m взаимно простые и числа b и n тоже взаимно простые.

З а м е ч а н и е. Используя задачи а) и б), легко получить формулу для (n), где n = pa1... pak. Другое доказательство этой форk мулы приведено в решении задачи 14.36.

31.8. Пусть a1, a2,..., a (n) — все числа от 1 до n 1, которые взаимно просты с n. Сопоставим числу ai остаток от деления числа aai на n. Число aai взаимно просто с n, поэтому мы снова получим одно из чисел a1, a2,..., a (n). При этом число a(ai aj ) при i = j не может делиться на n. Значит, мы получаем некоторую перестановку чисел a1, a2,..., a (n). Поэтому Умножение на число b = a1... a (n) тоже задаёт некоторую перестановку чисел a1, a2,..., a (n). Поэтому bb 1 (mod n) для некоторого числа b = ai. Умножив обе части сравнения (1) на b, получим требуемое.

31.9. Согласно теореме Эйлера (задача 31.8) можно положить m = (n).

31.10. П е р в о е р е ш е н и е. Рассмотрим дроби 1/n, 2/n, 3/n,..., n/n; их количество равно n. Заменим каждую из этих дробей на соответствующую несократимую дробь. При этом получатся дроби, знаменателями которых являются делители числа n, причём количество дробей со знаменателем d равно (d).

В т о р о е р е ш е н и е. Запишем разложение числа n на простые множители: n = p1 1 p2 2... pk k. Любой делитель d числа n имеет свойства мультипликативности функции Эйлера (задача 31.7 б) Действительно, в правой части после раскрытия скобок мы получаем сумму всех слагаемых вида (p1 1 )... (pk k ) = (p1 1... pk k ).

Остаётся заметить, что 31.11. а) О т в е т: 7. Числа 171 и 52 взаимно простые, поэтому 171 (52) 1 (mod 52). Далее, (52) = (4) (13) = 24. Поэтому 1712147 1524·89+11 1511 7 (mod 52).

б) О т в е т: 54. Числа 126 и 138 не взаимно простые: их НОД равен 6. Мы воспользуемся тем, что если a b (mod 23), то 6a 6b (mod 138). Пусть a = 21 · 1261019. Тогда a 21 · 1122·46+ 2 · 117 9 (mod 23). Поэтому 1261020 = 6a 54 (mod 138).

31.12. Согласно теореме Эйлера a (m) 1 (mod m). Поделим (m) на k с остатком: (m) = kq + r, где 0 r < k. Тогда 1 a (m) (ak )q ar ar (mod m). Следовательно, r = 0, поскольку иначе мы получили бы противоречие с минимальностью числа k.

31.13. Числа a и an 1 взаимно простые. Поэтому согласно теоn реме Эйлера a (a 1) 1 (mod an 1). Из этого следует, что число (an 1) делится на n (см. задачу 31.20).

целое, поскольку L(n) делится на pi i 1 (pi 1)). В результате получим xL(n) 1 (mod pi i ). Следовательно, число xL(n) 1 делится на p1 1,..., pk k, поэтому оно делится на n.

31.15. а) Предположим, что число p простое и p > 2 (для p = требуемое утверждение очевидно). Пусть a — одно из чисел 1, 2, 3,..., p 1. Для него существует единственное число a, 1 a p 1, для которого aa 1 (mod p) (см. решение задачи 4.63). Если a = a, то a2 1 = (a 1)(a + 1) делится на p, поэтому a = 1 или p 1.

Таким образом, числа 2, 3,..., p 2 разбиваются на пары, произведения которых дают остаток 1 при делении на p. Значит, Предположим теперь, что p = qr, где 1 < r, q < p. Тогда (p 1)!

делится на q, поэтому (p 1)! 1 (mod p).

б) Предположим, что p = qr, где 1 < r < q < p. Тогда (p 1)!

делится на qr = p. Остаётся рассмотреть случай, когда p = q2, где q — простое число. Если q = 2, то q2 = 4 и (3!)2 = 36 делится на 4.

Если же q > 2, то (p 1)! делится на q и на 2q, поэтому даже само число (p 1)!, а не только его квадрат, делится на q2 = p.

31.16. Если число n простое, то согласно теореме Вильсона (задача 31.15 а) a(n) = 1 и b(n) = 0, поэтому f(n) = n. Если же число n составное, то, как следует из решения задачи 31.15 б), ((n 1)!)2 0 (mod n) и 2(n 1)! 0 (mod n). Поэтому a(n) = и b(n) = 1, значит, f(n) = 2.

31.17. Число a b делится на n1, n2,..., nk, поэтому оно делится и на наименьшее общее кратное этих чисел.

31.18. Применим индукцию по r. Предположим, что xn =a+mpr. r Будем искать целое число t так, чтобы для числа xr+1 = xr + tpr выполнялось сравнение xn a (mod pr+1 ). Ясно, что Здесь многоточием обозначены члены, делящиеся на pr+1. Таким образом, нужно выбрать t так, чтобы число mpr + nxr tpr делиn лось на pr+1, т. е. число m + nxr t делилось на p. По условию числа n и a не делятся на p. Поэтому число nxr тоже не делится на p. В таком случае для любого числа m можно выбрать число t так, что nxr t m (mod p).

31.19. По условию a = b + mpn, где m — целое число. Поэтому Все слагаемые pbp1 mpn, 31.20. Запишем k в виде k = pn + r, где 0 r < n. Ясно, что an 1 (mod an 1), поэтому ak ar (mod an 1). Но если r > 0, то a ar an1 < an 1. Поэтому ar 1 (mod an 1) тогда и только тогда, когда r = 0, т. е. число k делится на n.

31.21. Применим индукцию по n. При n = 1 утверждение верно.

Действительно, если не все коэффициенты многочлена f(x) делятся на p, то cf(x) xm + a1 xm1 +... + am (mod p) для некоторого целого числа c; здесь m < p. Поэтому согласно теореме Лагранжа (задача 31.33) сравнение cf(x) 0 (mod p) имеет место не более чем для m различных по модулю p значений x. Поскольку m < p, найдётся x, для которого f(x) 0 (mod p).

Предположим, что требуемое утверждение доказано для некоторого n. Рассмотрим тождественное сравнение f(x1,..., xn, xn+1 ) 0 (mod p), у которого степень по каждой переменной меньше p.

Запишем f(x1,..., xn, xn+1 ) в виде Для фиксированных x1,..., xn положим am = gm (x1,..., xn ),...

..., a0 = g0 (x1,..., xn ). Сравнение am xm +... + a0 0 (mod p) выn+ полняется для всех целых xn+1, поэтому a0... am 0 (mod p).

Таким образом, gi (x1,..., xn )0 (mod p) для всех целых x1,..., xn.

Поэтому по предположению индукции все коэффициенты многочлена gi (x1,..., xn ) делятся на p.

31.22. Согласно малой теореме Ферма xp xi (mod p), поэтоi му xm xr (mod p). Значит, после указанных замен мы получим многочлен g(x1,.. ., xn ), степень которого по каждой переменной строго меньше p, причём g(x1,..., xn ) 0 (mod p) для всех целых x1,..., xn. Согласно задаче 31.21 все коэффициенты многочлена g(x1,..., xn ) делятся на p.

31.23. Предположим, что сравнение f(x1,..., xn ) 0 (mod p) имеет только решение (0,..., 0). Тогда сравнение выполняется тождественно. При (x1,..., xn ) = (0,..., 0) это очевидно, а при (x1,..., xn ) = (0,..., 0) это следует из малой теоремы Ферма.

Применим к обеим частям сравнения (1) замены, описанные в условии задачи 31.22. С одной стороны, согласно этой задаче в результате мы должны получить тождественное сравнение.

С другой стороны, в правой части вообще никаких замен не делается, поэтому в правой части после замен стоит многочлен, моном высшей степени которого равен ±xp1... xn. В левой же части первоначально стоит многочлен степени меньше n(p 1); после указанных замен его степень может только уменьшиться. Получено противоречие.

31.24. Это утверждение очевидным образом следует из теоремы Шевалле (задача 31.23), поскольку степень рассматриваемого многочлена строго меньше числа его переменных.

31.25. а) Делителями числа pa являются числа 1, p, p2,..., pa.

б) Пусть d и d — делители чисел m и n. Тогда dd — делитель числа mn. Для взаимно простых чисел m и n верно и обратное:

любой делитель числа mn однозначно представляется в виде P проak изведенияP делителей чиселP и n. `Поэтому если k (m) = 31.26. а) Числа 2p1 и (2p 1) взаимно простые, поэтому соp гласно задаче 31.25 б) согласно задаче 31.25 а) б) Пусть n = 2p1 m, где m нечётно, — чётное совершенное чисn) ( m делится на 2p 1. Пусть m= (2p 1)m. Тогда 2p (2p 1)m = 2p m= равенства m= (2p 1)m следует, что m+ m = 2p m = С другой стороны, оба числа m и m являются делителями числа m. Поэтому равенство m + m = может выполняться лишь в том случае, когда число m простое и m = 1.

31.27. Пусть n = p11 p22, где p1 и p2 — простые числа, причём p1 3 и p2 5. Тогда из неравенства следует, что 31.28. Число является суммой всех чисел вида d/n, где d — делитель числа n. Но d/n = d, где d — некоторый делитель числа n, причём когда d пробегает все делители P пробегает все делители числа n. Значит, 1/d, где сумма Положим n = N!. Тогда поскольку числа 1, 2, 3,..., N являются делителями числа n. Остатся заметить, что гармонический ряд расходится (задача 30.6).

и наибольшее простое число, на которое делится n (n), равно p1. При этом максимальная степень числа p1, на которую делится n (n), равна 2a1 1. Таким образом, если известно число n (n), то известны числа p1 и a1. Пусть n = pa1 n2. Тогда вательно, также, что f(1) = 1.

31.31. Прежде всего проверим, что при всех n > 1 выполняется Ясно, что Пусть n/d1 = m. Тогда 31.32. Непосредственно сводится к задаче 31.31 с помощью логарифмирования.

31.33. Применим индукцию по n. При n = 1 утверждение очевидно. Пусть числа f(x1 ) и f(x) делятся на p (x — целое число).

Тогда число f(x) f(x1 ) = xn xn + a1 (xn1 x1 ) + an1 (x x1 ) = =(xx1 )g(x) делится на p. При этом g(x)=x +b1 xn2 +...+bn1 — многочлен с целыми коэффициентами, зависящими только от на p. Поэтому на p должно делиться число g(x), и мы можем воспользоваться предположением индукции.

31.34. Сопоставим каждому целому числу x, где 1 x p 1, остаток от деления на p числа x2. Числам x и p x сопоставляется одно и то же число, причём x = p x. Кроме того, согласно теореме Лагранжа (задача 31.33) сравнение x2 c (mod p) не может иметь больше двух решений. Поэтому образ рассматриваемого отображения состоит из (p 1)/2 элементов. А этот образ как раз и состоит из квадратичных вычетов.

31.35. Если ab2 (mod p), то согласно малой теореме Ферма (задача 31.1) a(p1)/2 bp1 1 (mod p). Поэтому любой квадратичный вычет является решением уравнения x(p1)/2 1 (mod p). Согласно теореме Лагранжа (задача 31.33) количество решений этого сравнения не превосходит (p 1)/2, а согласно задаче 31.34 количество квадратичных вычетов равно (p 1)/2. Поэтому квадратичные вычеты — это в точности решения сравнения x(p1)/2 1 (mod p).

Если a — квадратичный невычет, то a(p1)/2 1 (mod p). Действительно, сравнение x2 1 (mod p) имеет только два решения:

x ±1 (mod p), а мы знаем, что (a(p1)/2 )2 = ap1 1 (mod p).

31.36. Воспользуемся критерием Эйлера (задача 31.35). Если p = 4k + 1, то (1)(p1)/2 = (1)2k = 1, а если p = 4k + 3, то (1)(p1)/2 = (1)2k+1 = 1.

31.37. Предположим, что уравнение x2 dy2 = 1 не имеет решений в целых числах. Пусть (, ) — фундаментальное решение уравнения Пелля x2 dy2 = 1. Число d тоже имеет вид 4k + 1, поэтому 2 ( 2 + 1) (mod 4). Квадрат нечётного числа целого числа) можно представить в виде произведения двух квадратов целых чисел: u2 = и v2 =, где d1 и d2 — делители числа d. Натуральные числа u и v взаимно простые, потому что НОД( 1, + 1) = 2. Кроме того, u = 0, поскольку = 1. Далее, Предположим, что d1 = 1 и d2 = 1. По условию r = 2 или нечётно, поэтому d1 или d2 — произведение нечётного числа простых чисел.

С л у ч а й 1. d1 — произведение нечётного числа простых чисел.

Пусть p — произвольный простой делитель числа d2. Тогда Но это противоречит тому, что d1 u2 1 (mod p), поскольку является квадратичным вычетом по модулю p.

С л у ч а й 2. d2 — произведение нечётного числа простых чисел.

Снова для произвольного простого делителя p числа d1 получаd ” = 1. Но это противоречит тому, что d2 v2 1 (mod p).

Полученные противоречия показывают, что либо d1 = 1 и d2 = d, либо d1 = d и d2 = 1.

Это противоречит предположению о том, что уравнение x dy2 = 1 не имеет решений.

Таким образом, (v, u) — решение уравнения Пелля x2 dy2 = 1.

u <. Но это противоречит тому, что было выбрано фундаментальное решение.

31.38. Прежде всего заметим, что если l и k — различные натуp то (l ± k)q делится на p, поэтому l ± k делится на p. Но |l ± k| p 1.

Таким образом, набор чисел r1, r2,..., r(p1)/2 совпадает с набоp ром 1, 2,...,. Поэтому, перемножив сравнения получим Следовательно, q 2 (1) (mod p). Но q на 12 даёт остаток ±1 или ±5. У числа 2n 1 должен быть простой делитель p > 3, дающий при делении на 12 остаток ±5.

Предположим, что 3n 1 делится на 2n 1. Тогда, в частности, 3 1 делится на p. Следовательно, 32(m+1) = 3n+1 3 (mod p). Таn ким образом, = 1. Но это противоречит квадратичному закону взаимности (см. задачу 31.43).

являются квадратичными вычетами, а остальные — невычетами.

31.49. Ясно, что При фиксированном l отображение k kl является перестановкой остатков от деления на p, поэтому поскольку при фиксированном k = 1 остатки от деления чисел l(k + 1) на p образуют” получим g1 = ± 5, а для p = 7 получим g1 = ±i 7. Легко видеть, что это и есть требуемые тождества с точностью до знака. Знак в обоих случаях легко выясняется.

31.51. Для каждого натурального числа n p 1 существует единственное натуральное число n p 1, для которого nn 1 (mod p). При этом p 1 = p 1. Поэтому когда n пробегает числа от 1 до p 2, n тоже пробегает числа от 1 до p 2 (в другом порядке). Ясно также, что n2 (1 + n) n2 + n n(n + 1) (mod p), поэтому поскольку g0 = 0 (задача 31.48).

чаях NR и RN это произведение равно 1. Следовательно, RR + татом задачи 31.51.

б) Количество вычетов среди чисел 2, 3,..., p1 равно RR+NR, а количество невычетов равно RN + NN. Среди чисел 1, 2, 3,...

..., p 1 вычетов и невычетов поровну. Кроме того, 1 — вычет.

Поэтому RN + NN = (p 1) и RR + NR = (p 1) 1.

Количество вычетов среди чисел 1, 2,..., p 2 равно “ + RN, а количество невычетов равно NR + NN. Кроме того, = =. Поэтому RR+RN= (p2 ) и NR+NN= (p2+ ).

в) Сложим равенства RR+NNRNNR=1, RR+RN= (p2 ) и NR + NN = (p 2 + ). В результате получим RR + NN = (p 3).

Вычитая из равенства RR + RN = (p 2 ) равенство RN + NN = (p 1), получаем RR NN = ( + 1). Следовательно, RR = З а м е ч а н и е. Равенства из задачи б) не являются независимыми: сумма равенств с равна RR + NN + RN + NR = p 2; сумма равенств без та же самая.

31.53. а) Непосредственно следует из задачи 31.36. б) Если целое число r удовлетворяет неравенствам 0 r < p, то r может принимать больше p различных значений (поскольку r может принимать значение 0). Таким образом, количество различных допустимых пар (r, s) больше p · p = p. Следовательно, для каких-то двух пар числа rx + s дают одинаковые остатки при делении на p.

в) Пусть r1 x+s1 r2 x+s2 (mod p), т. е. (r1 r2 )x(s2 s1 ) (mod p).

Положим u = |r1 r2 | и v = |s1 s2 |. По построению числа и v не могут быть одновременно равны нулю; кроме того, u, v < p. Так как ux ±v (mod p), то u2 x2 v2 (mod p). Но x2 + 1 0 (mod p), поэтому 0 (x2 + 1) u2 x2 + u2 v2 + u2 (mod p). С другой стороны, u + v < ( p)2 + ( p)2 = 2p, поэтому u2 + v2 = p.

31.54. Согласно задаче 31.36 можно выбрать натуральное число q так, что q2 1 (mod p). Рассмотрим число = q/p. Пусть C = p. Согласно задаче 17.12 можно выбрать натуральное число x < C = p и целое число y так, что |x y| 1/C, т. е. x y.

довательно, 0 < x2 + r2 < 2p. С другой стороны, x2 + r2 x2 + x2 q x2 (1 + q2 ) 0 (mod p). Поэтому x2 + r2 = p.

31.55. а) Согласно задаче 31.36 можно выбрать натуральное число x так, что x2 1 (mod p), т. е. x2 + 1 = mp. Таким образом, мы нашли требуемое решение, даже с дополнительным условием y = 1.

б) Пусть m0 — наименьшее натуральное число, для которого имеет место равенство К x и y можно добавлять кратные p, поэтому можно считать, что |x| x (в зависимости от того, имеют ли F(x0 ) и G(x0 ) один и тот же знак или разные знаки). Итак, при чётном r изменение числа перемен знака равно r, а при нечётном r изменение числа перемен знака равно r ± 1. В обоих случаях это изменение чётно и неотрицательно.

32.4. а) Так как f(r) (0) = r! anr, то N(0) совпадает с числом перемен знака в последовательности коэффициентов многочлена f.

Ясно также, что N(+) = 0.

б) Достаточно применить правило Декарта к многочлену f(x) = b0 xn + b1 xn1 +... + bn, где bk = (1)nk ak.

32.5. Оценим количество положительных и отрицательных корней данного многочлена по правилу, сформулированному в задаче 32.4. Предположим, что между двумя членами ank xk и ank+2m+1 xk2m1 отсутствуют 2m промежуточных членов. Если бы они не отсутствовали, то для положительных и отрицательных корней они дали бы 2m + 1 перемен знака. Вместо этого мы получаем только одну перемену знака (если числа ank и ank+2m+ разного знака, то для положительных корней, а если эти числа одного знака, то для отрицательных корней). Таким образом, оценка общего числа положительных и отрицательных корней уменьшается на 2m, и мы получаем по крайней мере 2m мнимых корней.

Предположим теперь, что между ank xk и ank+2m+2 xk2m2 отсутствуют 2m + 1 промежуточных членов. Тогда вместо 2m + перемен знака мы получили бы либо две перемены знака (если числа ank и ank+2m+2 разного знака), либо ни одной перемены знака (если эти числа одного знака). Таким образом, число вещественных корней уменьшается либо на 2m, либо на 2m + 2.

32.6. Рассмотрим сначала случай, когда многочлен f не имеет кратных корней (т. е. многочлены f и f не имеют общих корней).

В таком случае fn — некоторая ненулевая константа.

Проверим сначала, что если мы проходим через один из корней многочленов f1,..., fn1, то число перемен знака не изменяется.

В рассматриваемом случае соседние многочлены не имеют общих корней, т. е. если fr ( ) = 0, то fr±1 ( ) = 0. Кроме того, из равенства fr1 = qr fr fr+1 следует, что fr1 ( ) = fr+1 ( ). Но в таком случае число перемен знака в последовательности fr1 ( ),, fr+1 ( ) равно 2 как при > 0, так и при < 0.

Будем двигаться от a к b. Если мы проходим через корень x многочлена f, то сначала числа f(x) и f (x) будут разного знака, а потом эти числа будут одного знака. Таким образом, количество перемен знака в последовательности Штурма уменьшается на 1.

Все остальные перемены знака, как уже было показано, при прохождении через точку x0 сохраняются.

Рассмотрим теперь случай, когда многочлен f имеет корень x кратности m. В таком случае f и f1 имеют общий делитель (x x0 )m1, поэтому многочлены f1,..., fr делятся на (x x0 )m1.

Поделив f, f1,..., fr на (x x0 )m1, получим последовательность Штурма, 1,..., r для многочлена (x) = f(x)/(x x0 )m1. Многочлен имеет некратный корень x0, поэтому при прохождении через x0 число перемен знака в последовательности, 1,..., r увеличивается на 1. Но при фиксированном x последовательность f, f1,..., fr получается из последовательности, 1,..., r умножением на константу, поэтому число перемен знака в этих последовательностях одно и то же.

32.7. Пусть P(z) = (z z1 )... (z zn ). Легко проверить, что Предположим, что P (w) = 0, P(w) = 0 и w не принадлежит выпуклой оболочке точек z1,..., zn. Тогда через точку w можно провести прямую, не пересекающую выпуклой оболочки точек z1,..., zn.

Поэтому векторы w z1,..., w zn лежат в одной полуплоскости, заданной этой прямой. Следовательно, в одной полуплоскости леz w принадлежит выпуклой оболочке корней многочлена P.

32.8. Пусть z1 < z2 <... < zn1 — корни производной многочлена с корнями x1,..., xn, а z < z <... < zn1 — корни производной ношение (1) из решения задачи 32.7 принимает вид Предположим, что утверждение неверно, т. е. z < zk для некоk торого k. Тогда z x < zk xi. При этом числа z x и zk xi одного знака. В самом деле, zj < xi, z < x при j i 1 и zj > xi, коэффициенты, не делящиеся на p. Пусть ar — первый коэффициент многочлена f, не делящийся на p, bs — первый коэффициент многочлена g, не делящийся на p. Тогда cr+s = ar bs + ar+1 bs1 + ar+2 bs2 +... + ar1 bs+1 + ar2 bs+2 +...

так как Получено противоречие.

32.12. Пусть f — многочлен с целыми коэффициентами и f = gh, где g, h — многочлены с рациональными коэффициентами. Можно считать, что cont(f) = 1. Выберем для многочлена g натуральное число m так, что многочлен mg имеет целые коэффициенты.

Пусть n = cont(mg). Тогда рациональное число r = m/n таково, что многочлен rg имеет целые коэффициенты и cont(rg) = 1. Аналогично выберем положительное рациональное число s для многоРешения задач члена h. Покажем, что в таком случае rs = 1, т. е. разложение f = (rg)(sh) является разложением над кольцом целых чисел. Действительно, согласно лемме Гаусса cont(rg) cont(sh) = cont(rsgh), т. е. 1 = cont(rsf). Учитывая, что cont(f) = 1, получаем rs = 1.

32.13. Предположим, что причём g и h — многочлены положительной степени с целыми коэффициентами. Число b0 c0 = a0 делится на p, поэтому одно из чисел b0 и c0 делится на p. Пусть, для определённости, b0 делится на p. Тогда c0 не делится на p, так как a0 = b0 c0 не делится на p2.

Если все числа bi делятся на p, то an делится на p. Поэтому bi не делится на p при некотором i, где 0 < i deg g < n; можно считать, что i — наименьший номер числа bi, не делящегося на p. С одной стороны, по условию число ai делится на p. С другой стороны, ai = bi c0 + bi1 c1 +... + b0 ci, причём все числа bi1 c1,..., b0 ci делятся на p, а число bi c0 не делится на p. Получено противоречие.

32.14. К многочлену можно применить признак Эйзенштейна, поскольку все числа C1 xp2,..., Cp1 делятся на p (задача 14.30).

32.15. Пусть k — k-я элементарная симметрическая функция от a, b, c, d. По условию 1 = 2 и 3 = 24. Поэтому 32.16. Производящие функции и p(t) связаны соотношениt)p(t)=1. Приравнивая коэффициенты при tn, n 1, в левой и правой части, получаем требуемое.

32.17. Производящая функция s(t) выражается через p(t) следующим образом:

Приравнивая коэффициенты при tn1, получаем требуемое.

32.18. П е р в о е р е ш е н и е. Требуемое равенство можно переписать в виде Произведение snk k состоит из членов вида xi xj1... xjk. Если i совпадает с одним из чисел j1,..., jk, то этот член сокращаетnk+ вол xi означает, что число xi исключено из произведения), а есb ли i отлично от j1,..., jk, то этот член сокращается с членом xnk1 (xi xj1... xjk ) произведения snk1 k+1.

В т о р о е р е ш е н и е. Производящая функция s(t) выражаетt) ся через следующим образом:

Приравнивая коэффициенты при tn1, получаем + yk + zk. Запишем формулы Ньютона для n = 1, 2 и 4, учитывая при этом, что 1 = s1 = 0. В результате получим 22 = s и s4 + s2 2 = 0. Значит, 2s4 = s2 (22 ) = s2.

32.20. Запишем формулы Ньютона 1 = s1 и 22 = s1 1 s2. По условию числа 1 = s1 и s2 делятся на n. Значит, 22 тоже делится на n. А так как число n нечётно, то 2 делится на n. Запишем теперь формулу Ньютона 55 = s1 4 s2 3 + s3 2 s4 1 + s5. Числа s1 4, s2 3, s3 2, s4 1 делятся на n, поэтому s5 55 делится на n.

32.21. Равенство xn+3 + pxn+1 + qxn = 0 показывает, что имеет место рекуррентное соотношение sn+3 + psn+1 + qsn = 0. Ясно также, =. Теперь можно вычислять sn, пользуясь известными значеq ниями s1, s0, s1 и рекуррентным соотношением. В результате получим s2 = 2p, s3 = 3q, s4 = 2p2, s5 = 5pq, s6 = 2p3 + 3q2, s7 = 7p2 q, s8 = 2p4 8pq2, s9 = 9p3 q 3q3, s10 = 2p5 + 15p2 q2.

32.22. Ясно, что p1 = x1 x2 + (x1 + x2 )x3 = x1 x2 x2 = (b + c + d) p1 p2 = 3(ad bc).

32.23. Определим числа x1, x2, x3, y1, y2, y3 и многочлены t3 + p1 t + q1 и t3 + p2 t + q2, как в условии задачи 32.22. Согласно этой задаче p1 = p2, поскольку ad = bc. Положим p1 = p2 = p.

даче 32.21 получены выражения для sn при n 10. Воспользуемся этими выражениями. Числа s2 и s4 зависят только от p, поэтому f2 = f4 = 0. Далее, f6 = 3(q2 q2 ), f8 = 8p(q2 q2 ) и f10 = 15p2 (q2 q2 ).

Поэтому 64f6 f10 = 45(8p(q2 q2 ))2 = 45f8. 32.24. а) Многочлен f(x1,..., xn ) = ak1,...,kn x11... xkn называют однородным многочленом степени m, если k1 +... + kn = m для всех его мономов. Достаточно рассмотреть случай, когда f — однородный многочлен. Будем говорить, что моном x1 1... xn имеет более и k+1 > k+1 (возможно, k = 0). Пусть ax1... xn — старший моn ном многочлена f. Тогда 1... n. Рассмотрим симметрический многочлен Старший член монома 1 1 2... n n равен поэтому порядок старшего монома многочлена f1 строго ниже порядка старшего монома многочлена f. Применим к многочлену f снова операцию (1) и т. д. Ясно, что после конечного числа таких операций придём к нулевому многочлену.

Докажем теперь единственность представления f(x1,..., xn ) = = g(1,..., n ). Достаточно проверить, что если — ненулевой многочлен, то после подстановки y1 = 1 = x1 +...

... + xn,..., yn = n = x1... xn этот многочлен останется ненулевым.

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

б) Это непосредственно видно из решения задачи а).

32.25. Достаточно проверить, что f делится на. В самом деле, если f/ — многочлен, то этот многочлен по очевидным причинам симметрический. Покажем, например, что f делится на x1 x2.

Сделаем замену x1 = u + v, x2 = v u. В результате получим где f1 — некоторый многочлен. Если x1 = x2, то u = 0. Поэтому f1 (0, v, x3,..., xn ) = 0. Это означает, что многочлен f1 делится на u, т. е. многочлен f делится на x1 x2. Аналогично доказывается, что f делится на xi xj при всех i < j.

32.26. Предположим сначала, что требуемое неравенство выполняется при всех x > 0. Пусть x1 =... = xk = a и xk+1 =... = xn = 1.

Тогда 1 lim M (x)/M (x) = lim (a1 +...+k /a1 +...+k ).

При k = n, положив x1 =... = xn = a, получаем равенство При a > 1, как и ранее, получим || ||. А при 0 < a < 1 получим || ||.

Доказательство утверждения в обратную сторону более сложно.

Оно использует следующее преобразование Rij. Пусть i j > 0, где i < j. Положим Rij k = i, j. Легко проверить, что > и | | = ||.

ство достигается лишь в том случае, когда x1 =... = xn. (Предполагается, что числа x1,..., xn положительны.) Для каждой пары индексов p, q, где 1 p i. Равенство || = || означает, что (k k ) = 0, поэтому j < j для некоторого индекса j. Ясно, что i < j и j > 0. Поэтому к можно применить преобразование Rij. В результате получим последовательность для которой и j < j, получаем Таким образом, т. е. с помощью преобразования Rij нам удалось уменьшить на величину |k k |. Поэтому с помощью некоторого числа преобразований Rij эту величину можно сделать равной нулю.

Из лемм 1 и 2 неравенство Мюрхеда следует очевидным образом.

32.27. Формула показывает, что Многочлены Tn (x), определённые этим рекуррентным соотношением и начальными условиями T0 (x) = 1 и T1 (x) = x, обладают нужным свойством.

T4 (x) = 8x4 8x2 + 1, T5 (x) = 16x5 20x3 + 5x.

32.29. Это следует из того, что Tn (x) = cos n при x = cos.

32.30. Это следует из рекуррентного соотношения Tn+1 (x) = = 2xTn (x) Tn1 (x), которое доказано при решении задачи 32.27.

32.31. Мы воспользуемся лишь одним свойством многочлена Tn (x)=2n1 xn +..., а именно тем, что Tn (cos(k/n))=cos k=(1)k при k=0, 1,... , n. Рассмотрим многочлен Q(x)= Tn (x)Pn (x).

Его степень не превосходит n 1, поскольку старшие члены многочленов Tn (x) и Pn (x) равны. Из того, что |Pn (x)| при |x| 1 следует, что в точке xk = cos(k/n) знак числа Q(xk ) совпадает со знаком числа Tn (xk ). Таким образом, в концах каждого отрезка [xk+1, xk ] многочлен Q(x) принимает значения разного знака, поэтому у многочлена Q(x) на этом отрезке есть корень.

Чуть более аккуратные рассуждения нужны в том случае, когда Q(xk ) = 0. В этом случае либо xk — двукратный корень, либо внутри одного из отрезков [xk+1, xk ] и [xk, xk1 ] есть ещё один корень.

Это следует из того, что в точках xk+1 и xk1 многочлен Q(x) принимает значения одного знака (рис. 32.1).

Количество отрезков [xk+1, xk ] равно n, поэтому многочлен Q(x) имеет по крайней мере n корней. Для многочлена степени не более n 1 это означает, что он тождественно равен нулю, т. е. Pn (x) = n1 Tn (x).

З а м е ч а н и е. По поводу другого решения см. задачу 11.38.

32.32. Пусть x = cos. Тогда Tn (x) = cos(n ) = y и Tm (y) = =cos m(n ), поэтому Tm (Tn (x))=cos mn. Аналогично Tn (Tm (x))= = cos mn. Таким образом, равенство Tn (Tm (x)) = Tm (Tn (x)) выполняется при |x| < 1, а значит, это равенство выполняется при всех x.

Tk (cos )=cos(k+1) cos k. При этом (k+1) +k =(2k+1) = = 2l. Значит, cos(k + 1) = cos k.

б) Пусть n = 2k и = 2l/n. Тогда Tk+1 (cos ) Tk1 (cos ) = = cos(k + 1) cos(k 1). При этом (k + 1) + (k 1) = 2k = 2l.

Значит, cos(k + 1) = cos(k 1).

32.34. а) Пользуясь результатом задачи 32.28, получаем T б) Согласно задаче 32.33 числа cos 0=1, cos и cos являются корнями многочлена T3 T2. Поделив этот многочлен на x 1, получим требуемый многочлен.

корнями многочлена T5 T4. Поделив этот многочлен на (2x + 1) (x 1) = 2x2 x 1, получим требуемый многочлен.

32.35. Пусть = m/n — несократимая дробь. Положим x0 = =2 cos t, где t= Тогда Pn (x0 )=2 cos(nt)=2 cos(n = ±2. Поэтому x0 — корень многочлена Pn (x) 2 = xn + b1 xn1 +...

... + bn с целыми коэффициентами. Пусть x0 = 2 cos( = p/q — несократимая дробь. Тогда pn + b1 pn1 q +... + bn qn = 0, а значит, pn делится на q. Но числа p и q взаимно простые, поэтому q = ±1, т. е. 2 cos( — целое число.

32.36. Число y0 = a0 x0 является корнем многочлена При a0 = 0 это очевидно, а при a0 = 0 нужно положить y = a0 x;

после сокращения на a0 получим исходный многочлен.

32.37. Если | p/q| 1, то требуемое неравенство выполняется при c = 1. Поэтому будем считать, что | p/q| < 1, а значит, |p/q| < | | + 1. Запишем многочлен f(x) в виде f(x) = an (x i ), где c = c1.

2 = p/q, где p — целое число и q = 2n!. При этом Предположим, что — алгебраическое число степени N. Тогда согласно задаче 32. а значит, 2qn1 > cqN, т. е. c < 2qNn1 = 2 · 2n! (Nn1). Но lim 2n! (Nn1) = 0. Приходим к противоречию.

32.39. а) Пусть { 1,..., n } и { 1,..., m } — наборы чисел, сопряжённых с и соответственно. Рассмотрим многочлен Коэффициенты этого многочлена являются симметрическими функциями от 1,..., n и 1,..., m. Поэтому они являются рациональными числами.

б) Решение аналогично.

32.40. Пусть { 1,..., n } и { 1,..., m } — наборы чисел, сопряжённых с и соответственно. Рассмотрим многочлен Коэффициенты этого многочлена рациональны и f( ) = 0. Поэтому f(x) делится на (x i ), а значит, f( i ) = 0, т. е. ( i, j ) = 0 для некоторого j.

32.41. Рассмотрим многочлен где { n1,i },..., { 0,l } — все числа, сопряжённые с n1,..., соответственно. Легко проверить, что коэффициенты многочлена F — целые числа. Ясно также, что — корень многочлена F.

где число 1 сопряжено с. Число удовлетворяет уравнению xn 1=0, поэтому 1 тоже будет корнем этого уравнения, а значит, 1 = exp(l/n). В таком случае число 1 = 2 cos(l/n) вещественно.

32.43. Ясно, что все числа указанного вида должны входить в k( ). Поэтому достаточно доказать, что числа указанного вида образуют поле. Для этого, в свою очередь, достаточно доказать, что произведение чисел такого вида имеет такой же вид и обратный элемент для числа такого вида тоже имеет такой вид (ясно, что сумма чисел указанного вида имеет требуемый вид). Мы доx) кажем более общее утверждение: если (x) и — многочлены для некоторых чисел c0,..., cn1 из поля k.

Многочлен f(x) неприводим над k, поэтому он не имеет общих делителей с Значит, найдутся многочлены a(x) и b(x) с коэффициентами их поля k, для которых a(x)(x) + b(x)f(x) = (x)a(x) = q(x)f(x) + r(x), где r(x) — многочлен степени не выше 32.44. Пусть bm = cm dm. Нужно доказать, что если = 0, где b0,..., bn1 — числа из поля k, то b0 = b1 =... = bn1 = 0.

Многочлен g(x) = bn1 xn1 +... + b0 имеет общий корень с неприводимым многочленом f(x), поэтому g(x) делится на f(x). Но степень g(x) меньше степени f(x), поэтому g(x) = 0, т. е. b0 = b1 =...

... = bn1 = 0.

АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ

Когда дело доходит до конкретных вычислений, бывает важно выбрать наиболее быстрый способ вычислений. При этом нужно иметь в виду, что умножение двух больших чисел занимает больше времени, чем сложение.

Иррациональные числа обычно вычисляются приближённо, поэтому при таких вычислениях важно оценить погрешность вычислений. Это относится и к приближённому представлению десятичными дробями рациональных чисел с большими числителями и знаменателями.

33.1. Вычисления некоторых чисел 33.1. Докажите, что дробь начинается с цифр 0,239.

33.2. Докажите, что если квадрат числа начинается с 0,999... 9 (100 девяток), то и само число начинается с 0,999... 9 (100 девяток).

33.3. Вычислите с точностью до 0,00001 произведение Поэтому 1 > a > 0,9.{z. 9 (предполагается, что число a положительно). ... 1 99. Непосредственные вычисления показывают, что (1x)(1y)>1xy. Поэтому b>1 6 7... 99 >1 6.

Следовательно, 33.4. Мы воспользуемся тождеством (задача 11.11) и неравенствами для арктангенса, доказанными в задаче 29.46. Из этих неравенств следует, что y, то числа x и y мы больше никогда друг с другом не сравниваем, потому что такое сравнение можно было бы просто пропустить.

Достаточно доказать, что при сравнении любой пары чисел может случиться, что fk fk+1 1. Действительно, складывая неравенства f0 f1 1, f1 f2 1,..., fm fm1 1, получаем f0 fm m, т. е. 3n 2 m. Требуемое утверждение доказывается прямым перебором.

1) Если сравниваются два числа из группы ak, то ничего не меняется: fk+1 = fk.

2) Пусть сравниваются число a из группы ak и число b из группы bk. Может случиться, что a < b. Тогда ak+1 = ak + 1 и bk+1 = bk 1, поэтому fk fk+1 = 1.

3) Аналогично может случиться, что a > c. Тогда ak+1 = ak + и ck+1 = ck 1, поэтому fk fk+1 = 1.

4) При сравнении чисел a и d одно из чисел bk или ck увеличивается на 1, а число dk уменьшается на 1, поэтому fk fk+1 = 1/2.

468 Глава 33. Алгоритмы и вычисления 5) При сравнении двух чисел из группы bk число ak увеличивается на 1, а bk уменьшается на 1, поэтому fk fk+1 = 1.

6) Может случиться, что b < c. Тогда ничего не меняется.

7) Может случиться, что b < d. Тогда ck увеличивается на 1, а dk уменьшается на 1, поэтому fk fk+1 = 1/2.

8) При сравнении двух чисел из группы ck число ak увеличивается на 1, а ck уменьшается на 1, поэтому fk fk+1 = 1.

9) Может случиться, что c > d. Тогда bk увеличивается на 1, а dk уменьшается на 1, поэтому fk fk+1 = 1/2.

10) При сравнении двух чисел из группы dk оба числа bk и ck увеличиваются на 1, а dk уменьшается на 2, поэтому fk fk+1 = 1.

33.13. а) Будем последовательно делить набор из n чисел примерно пополам, как это описано в задаче 33.10. Согласно решению этой задачи процесс останавливается после m шагов. Группы, полученные на (m 1)-м шаге, состоят из пар чисел и отдельных чисел. В каждой такой группе сравним числа и найдём среди них наибольшее (отдельные числа пока ни с чем не сравниваются). Затем аналогично найдём наибольшее число в каждой группе, полученной на (m 2)-м шаге, и т. д. В результате найдём наибольшее число. При этом будет сделано n 1 сравнений. Действительно, при каждом сравнении отсеивается один кандидат на звание наибольшего числа, причём в результате будет отсеяно n 1 число.

Займёмся теперь поиском второго по величине числа. Ясно, что оно выбыло из дальнейшей борьбы в результате сравнения с наибольшим числом, поскольку у любого другого числа оно бы выиграло. Таким образом, второе по величине число нужно искать среди тех чисел, которые сравнивались непосредственно с самым большим числом. Таких чисел не более m. Выбрать из них наибольшее можно за m 1 сравнений.

б) Будем говорить, что число проигрывает сравнение, если оно оказывается меньше числа, с которым оно сравнивается. Пусть ki — количество чисел, проигравших не менее i сравнений (косвенные проигрыши, когда из неравенств a < b и b < c делается вывод, что a < c, не учитывается; количество всех проигрышей равно количеству всех сравнений). Тогда сумма всех чисел ki равна количеству всех сравнений, поскольку после каждого сравнения ровно одно из чисел ki увеличивается на 1. Действительно, пусть при очередном сравнении проигрывает число, которое уже проиграло j сравнений. Тогда kj+1 увеличивается на 1, а остальные числа ki не изменяются.

Достаточно доказать, что при любом алгоритме сравнений может получиться так, что после того как удалось выявить наибольРешения задач шее число и следующее за ним, будет выполняться неравенство k1 + k2 n + m 2. Прежде всего заметим, что после того как алгоритм закончит работу, будет выполняться неравенство k1 n 1, поскольку все числа, кроме одного, должны были кому-то проиграть (если бы два числа никому не проиграли, то мы не знали бы, какое из них больше другого). Остаётся доказать, что при неудачных исходах может выполняться неравенство k2 m 1.

На каждом шаге работы алгоритма будем называть лидером число, которое пока никому не проиграло. Покажем, что неравенство k2 m 1 выполняется, если исходы сравнений следующие:

(1) при сравнении двух не лидеров результат произвольный;

(2) при сравнении лидера с не лидером всегда выигрывает лидер;

(3) при сравнении двух лидеров выигрывает тот, у кого было больше выигрышей (если выигрышей было поровну, то результат произвольный).

Такие исходы сравнений возможны потому, что на лидера нет никаких ограничений сверху: если его увеличить, то результат предыдущих сравнений не изменится.

Введём теперь понятие подчинения лидеру. Первоначально все числа подчинены только самим себе. При сравнениях типа (1) и (2) подчинение лидерам не изменяется. При сравнении типа (3) проигравший и все его подчинённые переподчиняются новому лидеру.

Покажем индукцией по k, что если лидер выиграл k сравнений, то ему подчинено (вместе с ним самим) не более 2k чисел. При k = 0 лидеру подчинён только он сам. Пусть лидер, выигравший k сравнений, выигрывает у кого-то в очередной раз. Тот, у кого он выиграл, по нашему соглашению о сравнениях типа (3) выиграл не более k сравнений. Поэтому как выигравшему, так и проигравшему подчинено не более 2k чисел; при объединении этих двух групп получается не более 2k+1 чисел, что и требовалось.

Итак, наибольшее число выиграло по крайней мере m сравнений, поскольку ему в итоге будут подчинены все n чисел. Среди m чисел, проигравших наибольшему числу, есть только одно число, которое больше никому не проиграло (иначе мы не будем знать второе по величине число). Следовательно, k2 m 1.

ФУНКЦИОНАЛЬНЫЕ УРАВНЕНИЯ

Метод подстановки позволяет решать довольно узкий класс функциональных уравнений. Он заключается в следующем.

Пусть (x) — функция, которая обладает таким свойством: если 1 (x) = (x) и k+1 (x) = ( k (x)) при k 1, то n (x) = x для некоторого n. Например, если (x) = 1 x, то 2 (x) = x.

Предположим, что функциональное уравнение содержит только функции f(x), f( (x)),..., f( n1 (x)). Тогда вместо x можно подставить 1 (x), 2 (x),..., n1 (x) и получить систему уравнений, которую иногда удаётся решить.

34.1. Найдите все функции f(x), для которых 2f(1 x) + + 1 = xf(x).

34.2. Найдите все функции f(x), которые определены при x = 1 и удовлетворяют соотношению 34.3. Найдите все функции f(x), которые определены для всех x = 0, ±1 и удовлетворяют соотношению 34.2. Функциональные уравнения 34.4. а) Предположим, что каждому рациональному числу x сопоставлено действительное число f(x) так, что f(x + y) = f(x) + f(y) и f(xy) = f(x)f(y). Докажите, что либо f(x) = x для всех x, либо f(x) = 0 для всех x.

б) Решите ту же самую задачу в случае, когда число f(x) сопоставляется не только рациональным числам, но и всем действительным числам.

34.5. Найдите все функции f(x), которые определены для всех x и удовлетворяют соотношению для всех x, y.

34.6. Найдите функцию f(x), которая определена для всех x, в некоторой точке отлична от нуля и для всех x, y удовлетворяет уравнению f(x)f(y) = f(x y).

34.7. Докажите, что не существует функции f(x), которая определена для всех x и удовлетворяет соотношению f(f(x)) = x2 2.

34.3. Функциональные уравнения 34.8. Непрерывная функция f(x) определена для всех x и удовлетворяет соотношению Докажите, что f(x) = Cx, где C = f(1).

34.9. Найдите все непрерывные функции, которые определены для всех x и удовлетворяют соотношению f(x) = = ax f(x/2), где a — фиксированное положительное число.

34.10. Непрерывная функция f(x) определена для всех x, причём f(x0 ) = 0 для некоторого x0. Докажите, что если выполнено соотношение то f(x) = a для некоторого a > 0.

34.11. Непрерывная функция f(x) определена для всех x > 0 и удовлетворяет соотношению а) Докажите, что если f(a) = 1 для некоторого a, то f(x) = loga x.

472 Глава 34. Функциональные уравнения б) Докажите, что если f(x0 ) = 0 для некоторого x0, то f(a) = 1 для некоторого a.

34.12. Найдите все непрерывные решения функционального уравнения 34.13. Найдите все непрерывные решения функционального уравнения (Лобачевский).

34.14. Найдите все дифференцируемые функции f, для которых f(x)f (x) = 0 для всех x.

34.5. Функциональные уравнения для многочленов 34.15. Найдите все многочлены P(x), для которых справедливо тождество xP(x 1) = (x 26)P(x).

34.16. Многочлен P(x, y) обладает следующим свойством:

P(x, y) = P(x + 1, y + 1) для всех x и y. Докажите, что P(x, y) = Согласно задаче 28.76 для многочлена f степени n + 1 выполняется равенство При этом f(n+1) — константа, а значит, Таким образом, у функционального уравнения есть решение следующего вида:

(а) f — многочлен степени не выше n + 1;

(в) gn (y) = f(n) (y)/n! yf(n+1) (y)/(n + 1)! c;

(г) h(x) = xf(n+1) (x)/(n + 1)! + c.

34.17. Пусть f, g0,..., gn, h — произвольные функции, которые при всех вещественных x, y, x = y, удовлетворяют уравнению (1). Докажите, что тогда эти функции имеют указанный выше вид (а)– (г). – 34.18. а) Пусть функция f(x) дифференцируема n раз и при всех вещественных x, y, x = y, выполняется равенство Докажите, что тогда f — многочлен степени не выше n.

б) Докажите, что если при всех вещественных x, y, x = y, выполняется равенство то f — многочлен степени не выше 2, g = f и = f.

34.19. Докажите, что функциональное уравнение сводится к функциональному уравнению (2) 34.20. а) Найдите полиномиальные решения функционального уравнения f( x + ) = f(x) при = ±1.

б) Докажите, что если решением функционального уравнения f( x + ) = f(x) является многочлен степени n, то = 1. (В частности, если = ±1, то n 3).

34.21. Пусть многочлен f степени n 3 удовлетворяет соотношению f( x + ) = f(x), где = ±1 и n = 1. Докажите, 474 Глава 34. Функциональные уравнения что тогда 34.1. Подставив 1x вместо x, получим 2f(x)+1=(1x)f(1x).

Исходное уравнение показывает, что f(1 x) =. Подставим это выражение в новое соотношение, получим 2f(x) + 1 = = (1 x) проверка показывает, что эта функция удовлетворяет требуемому Поэтому получаем систему уравнений Сложим первое уравнение с третьим и вычтем из них второе уравнение. В результате получим Непосредственная проверка показывает, что эта функция удовлетворяет требуемому соотношению.

Чтобы сократить вычисления, поступим следующим образом.

Умножим третье уравнение на 2x и сложим его со вторым уравнением. Затем к полученному уравнению прибавим первое уравнеx ние, умноженное на, и последнее уравнение, умноженное верка показывает, что эта функция f(x) удовлетворяет требуемому соотношению.

34.4. а) Предположим, что f(x) = 0 хотя бы для одного числа x.

Тогда из равенства f(x · 1) = f(x)f(1) следует, что f(1) = 1. Далее, f(0) = f(0 + 0) = f(0) + f(0), поэтому f(0) = 0.

Из равенства f(x + y) = f(x) + f(y) следует, что если n — натуральное число, то f(nx) = nf(x). Значит, f(n) = n, f(1) = nf(1/n), т. е. f(1/n) = 1/n, и f(m/n) = mf(1/n) = m/n для любого натурального числа m. Наконец, f(x) + f(x) = f(x x) = f(0) = 0.

б) Докажем, что если x y, то f(x) f(y). Действительно, если x> y, то x= y + t2 для некоторого действительного числа t. Поэтому f(x) = f(y) + f(t2 ) = f(y) + (f(t))2 f(y).

Предположим, что f(x) = x для некоторого действительного числа x (мы рассматриваем случай, когда f(x) = 0 хотя бы для одного числа x). Пусть, например, f(x) > x. Тогда существует рациональное число r, для которого f(x) > r > x. Из неравенства r > x следует, что f(r) f(x), т. е. r f(x). Получено противоречие. Если f(x) < x, то рассуждения аналогичны.

34.5. Положим x = y. Тогда получим 2xf(x) = 2x(f(x))2. Если x = 0, то f(x) = 0 или 1.

Предположим, что f(a) = 0 для некоторого a = 0. Положив x = a, получим af(y) = 0 для всех y, т. е. f = 0.

Предположим, что f(a) = 1 для некоторого a = 0. Положив x = a, получим af(y) + y = (a + y)f(y), т. е. y = yf(y). Значит, f(y) = 1 для всех y = 0.

В результате получаем, что либо f(x) = 0 для всех x, либо f(x) = 1 для всех x = 0 и f(0) = c — произвольное число.

34.6. Возьмём точку x0, для которой f(x0 ) = 0, и положим y = 0.

Тогда f(x0 )f(0) = f(x0 ), поэтому f(0) = 1. Положив x = y, получаем (f(x))2 = f(0) = 1. Значит, f(x) = ±1. Наконец, положив y = x/2, получим f(x)f(x/2)=f(x/2), причём f(x/2)=±1=0. Поэтому f(x)=1.

476 Глава 34. Функциональные уравнения 34.7. Рассмотрим функции g(x) = x2 2 и h(x) = g(g(x)) = x 4x2 + 2. Корни уравнения g(x) = x равны 1 и 2. Оба эти числа являются также и корнями уравнения h(x) = x. Чтобы найти остальные корни этого уравнения, поделим x4 4x2 x + 2 на x2 x 2. В результате получим трёхчлен x2 + x 1. Его корни равны. Таким образом, уравнение h(x) = x имеет корни Докажем, что не существует даже функции f(x), которая определена для этих четырёх значений x и удовлетворяет указанному соотношению.

Пусть a и b — числа из множества (1). Докажем, что если f(a) = = f(b), то a = b. Действительно, если f(a) = f(b), то g(a) = f(f(a)) = = f(f(b)) = g(b). Поэтому h(a) = h(b). Но h(a) = a и h(b) = b.

Если a = 1 или 2, то g(f(a)) = f(f(f(a))) = f(g(a)) = f(a), поэтому f(a) = 1 или 2.

Если a =, то h(f(a)) = f(h(a)) = f(a), поэтому f(a) — одно из чисел (1). Мы доказали, что f взаимно однозначно отображает множество (1) на себя. Более того, f отображает подмножество, состоящее из чисел 1 и 2, на себя. Поэтому f(a) = a или и f( ) =. Но тогда = f( ) = f(f( )) = g( ). Приходим к противоречию.

34.8. Ясно, что f(2x) = f(x + x) = f(x) + f(x) = 2f(x), f(3x) = = f(2x + x) = f(2x) + f(x) = 2f(x) + f(x) = 3f(x). Аналогично доказывается, что f(nx) = nf(x) для любого натурального n. Далее, f(x) = f(x+ 0) = f(x) + f(0), поэтому f(0) = 0, а значит, f(x) + f(x) = = f(x x) = f(0) = 0. Таким образом, равенство f(nx) = nf(x) выполняется для всех натуральных n.

Для любого рационального числа x = m/n получаем f(nx) = = nf(x), т. е. f(m/n) = f(m)/n = (m/n)f(1). Функция f непрерывна, поэтому f(x) = xf(1) для любого (вещественного) x. Действительно, любое число x является пределом рациональных чисел.

34.9. Ясно, что f(x) = ax f(x/2) = ax ax/2 f(x/4) = ax ax/2 ax/4 f(x/8) = =... = ax(1+1/2+1/4+...+1/2 ) f(x/2k+1 ). Если k, то f(x/2k+1 ) f(0), при k. Поэтому f(x) = a2x f(0). Таким образом, f(x) = Ca2x, где C — произвольная константа.

34.10. Равенство f(x)f(x0 x)=f(x0 ) показывает, что f(x)=0 для всех x. Но тогда f(x) > 0 для всех x, поскольку f(x) = f(x/2)f(x/2).

Индукцией по n легко доказать, что для всех натуральных n. Ясно также, что f(0) = 1, поскольку f(x) = f(x + 0) = f(x)f(0). Кроме того, f(x)f(x) = f(0) = 1. Поэтому равенство (1) выполняется для всех целых n. В частности, f(n) = an, где a = f(1).

Докажем теперь, что равенство f(r) = ar выполняется для любого рационального числа r = m/n. Запишем равенство (1) для x = m/n: f(m) = (f(m/n))n. Учитывая, что f(m) = am, получаем am = (f(m/n))n, т. е. f(m/n) = am/n.

Равенство f(x)=ax доказано для всех рациональных x. Поэтому из непрерывности функции f следует, что f(x) = ax для всех x.

34.11. а) Сделаем замену u = loga x, т. е. x = au, и рассмотрим функцию g(u) = f(x) = f(au ). Функция g тоже непрерывна. Она удовлетворяет соотношению g(u + v) = g(u) + g(v). Действительно, g(u + v) = f(au+v ) = f(au av ) = f(au ) + f(av ) = g(u) + g(v). Поэтому согласно задаче 34.8 g(u) = ug(1) = uf(a) = u. Таким образом, f(x) = g(u) = u = loga x.

б) Легко проверить, что f(xn ) = nf(x0 ) для любого целого n.

Поэтому функция f принимает значения как больше 1, так и меньше 1.

34.12. Ясно, что Покажем индукцией по n, что для любого натурального n выполняется равенство Действительно, из этого равенства следует, что f((n + 1)x) = f(nx + x) = f(nx) + f(x) + f(x)f(nx) = = (1 + f(x))n 1 + f(x) + f(x)(1 + f(x))n f(x) = (1 + f(x))n+1 1.

Пусть f(1) = c. Запишем равенство (2) для x = 1:

Запишем также это равенство для x = m/n:

478 Глава 34. Функциональные уравнения Но f n Здесь всегда нужно брать положительное значение корня, потому что если заменить в равенстве (1) x на x/2, то получим f(x) + 1 = (1 + f(x/2))2 0.

В итоге по соображениям непрерывности получаем, что если Положим в исходном функциональном уравнении x = 0, а потом y = x:

Если f(y) 1, то f(0) = 0. В таком случае для x > 0 получаем откуда f(x) = kx 1.

Итак, мы получили, что либо f(x) 1, либо f(x) 0, либо f(x) = kx 1, где k > 0, k = 1. Несложная проверка показывает, что все эти функции удовлетворяют данному функциональному уравнению.

34.13. Пусть f(0) = a и f(1) = b. Положив в исходном функциональном уравнении x = y = t/2, получим f(t/2) = af(t), поэтому f(1/2) = ab= a(a/b)1/2 = ac1/2, где c= b/a, f(1/4) = af(1/2) = ac1/4, и вообще, f(1/2n ) = ac1/2 (если a = 0, то всё равно получаем f(1/2n ) = 0, поскольку в этом случае можно обойтись без деления на a).

Положим теперь в исходном функциональном уравнении x = т. е.

Ясно также, что если f следует, что f натуральных m. Поэтому по непрерывности f(x) = acx для всех положительных x.