30. Предположим, г ± s. Идея доказательства такова: показать, что ip{rs) чисел, взаимно простых с rs, - это в точнбсти (p(r)(p{s) различных чисел (sx, + ryj) mod (rs), где Xl,..., x(r) иг/1,..., Vfs) - 4HCjia, взаимно простые с г и s соответственно.

Так как (р является мультипликативной функцией, то <( 10®) = <(2®)<(5®) = (2® - 2*)(5® - 5*) = 400000. А в общем случае, когда га = Pi... р", имеем

p{n){pV-pV-)...{pI--р-) = п П (1-1/р).

р\п. р-простое

(Другой вариант доказательства приводится в упр. 1.3.3-27.)

31. Воспользуйтесь тем фактом, что делители rs можно единственнь/м образом записать в виде cd, где с делит г, г, d делит s. Аналогично, если /(га) > О, можно показать, что функция maxd\n f{d) мультипликативна (см. упр. 1.2.3-35).

33. Либо п + т, либо га - m -ь 1 четно, поэтому одна из величин в квадратных скобках является целой. Таким образом, нестрогое неравенство из упр. 7 обращается в равенство и на этом основании получаем: (а) га; (Ь) га -I-1.

34. b должно быть целым числом > 2. (Положим х = Ь.) Достаточность доказывается, как в упр. 6. Это же условие является необходимым и достаточным для того, чтобы [logj х] = riogbHl.

Примечание. Р. Дж. Мак-Элис (R. J. МсЕИесе) указал обобщение этого результата. Пусть / - непрерывная, строго возрастающая функция, определенная на интервале А. Предположим, что если х принадлежит А, то и значения функций [xJ и \х] принадлежат А. Тогда утверждения "[/(x)J = [/(L:])] для всех х из А" и "Г/(х)1 = Г/([а;1)] для всех X из А" равносильны и выполняются тогда и только тогда, когда для всех х из А удовлетворяется следующее условие: "если значением функции /(х) является целое число, то X тоже целое число". Очевидно, что данное условие является необходимым, так как если значением /(х) является целое число, равное [/([xJ)J или [/([х])], то х должно равняться [xJ или [х]. И обратно, если, например, [/(L:])] < L/()Jj силу непрерывности функции /(х) существует такое у, [xJ < у < х, для которого значение /(г/) является целым, но у не может быть целым числом.

35. ±2 - 1 = £±12

1 га-1 1х\ + т га-1 п п га п ~

[xj + т п

х + т . < -. А теперь

га га

воспользуйтесь упр. 3. Применив упр. 4, можно получить аналогичный результат для функции "потолок". Оба тождества являются частными случаями теоремы Мак-Элиса из упр. 34.

36. Предположим сначала, что га = 2t. Тогда

= t = .

следовательно, с помощью результатов упр. 33 получаем

-А fc 1 у-/ fc га + 1-fc 1 2f+ 1

И, если га = 2t -ь 1, имеем + [ra/2J =t+t - - 1/4. Аналогично для второй суммы получаем [n(n-ь 2)/4".

37. Е -~- = -- Обозначим через {у} величину у modi. Чтобы полу-

0<к<п

чить требуемую сумму, мч должны вычесть из предыдущего равенства

Величине 5 состоит из d экземпляров одной и той же суммы, так как если t = n/d, то имеем

f mfc + X1 fm(fc + t) + x j

Положим и = m/d; тогда

i:{=}=E{i+f}.

o<k<t 0<k<t

Поскольку t ± u, последняя сумма равна

{x mod d\ (x mod d 1) fx mod d t - 11

и наконец, так как (х modd)/ra < 1/t, то, опустив скобки в этой сумме, получим

Применяя упр. 4, получим тождество

rmfc + x1 (m + l)(n-l) d-lp

Если суммирование распространить на область О < А; < га, формула станет симметричной относительно m и га. (Эту симметрию можно объяснить, нарисовав график функции, стоящей под знаком суммы, как функции от fc, а затем отразив его относительно прямой j/ = x.)

38. Обе стороны равенства увеличиваются на fj/", когда х увеличивается на 1, поэтому можно предположить, что О < х < 1. При х = О обе части обращаются в нуль. Когда х возрастает, при каждом переходе значения 1 - к/у при у > fc > О обе части увеличиваются на 1. [Crelle 136 (1909), 42; случай у = п был рассмотрен Ш. Эрмитом (С. Hermite), Acta Math. 5 (1884), 315.]

39. Докажем п. (f). Рассмотрим более общее тождество- no<Kn2sm7r(x+fc/ra) = 2sin7rrax. Поскольку 2sine = (е* -е"*)/г = (1 -е~*)е*~", данноетождество является следствием следующих двух формул:

J (1 е-2-(-+-=/")) = 1 - и П

0<i<n 0<к<п

g7r(l:-(l/2)+(fc/n)) ж(пх-1/2)

Вторая формула верна, так как функция х - репликативна, а первая верна, так как в разложении многочлена на множители г" - а" = (г - a){z - ша)... (г - w""a), где Си = е""", можно положить г - 1.

40. (Замечание Н. Г. де Брейна (N. G. de Bruijn).) Если / репликативна, то f{nx + 1)- f{nx) = f{x + 1) - fix) для всех w > 0. Поэтому, если / непрерывна, то f{x + 1) - fix) = с для всех X и, следовательно, д{х) = f{x) - с[х\ репликативна и периодична. Далее,

/"e2"-ff(x)dx = i f ">9{y)dy; Jo " Jo

и разложение в ряд Фурье показывает, что д{х) = {х - )а при О < х < 1. Отсюда следует, что f{x) = (х - )а. Если говорить в общем, это означает, что любая репли-кативная локально интегрируемая по Риману функция почти всюду равна (х - )а + bmax([xj,0) + cmin([xj,0). Дополнительную информацию по данной теме можно найти в работах L. J. Mordell, J. London M&th. Soc. 33 (1958), 371-375; M. F. Yoder, Mquationes Matbematicae 13 (1975), 251-261.

41. Нам нужно, чтобы a„ = при 5fc(fc - 1) < га < 5fc(fc -I- 1). Так как га - целое число, данное неравенство эквивалентно следующему.

2 +8 2 8

т. е. fc - 5 < \/2п < fc -Н 5. Поэтому Оп = [\/2п 1 J, т. е. ближайшему к \/2п целому числу. Можно привести и другие правильные ответы: \\/2п - 5], [(\/8га + 1 - 1)/2], L(v/Sr=-l-l)/2j ИТ д.

42. (а) См. упр. 1.2.7-10. (Ь) Заданная сумма равна ra[logj raj - 5, где

fc= Е {Ь-\) = {Ь"+-Ь)/{Ь-\)-\\og,n\.

1<«<1о8ьп

гп т

< 3 <

(г-И)га

1<*:<п к+1 есть степень b

43. [л/Н] (га - i(2L0iJ + 5){[V\ - 1)).

44. Для отрицательных п эта сумма равна га -Н 1.

45. lmj/n\ = г тогда и только тогда, когда заданная сумма равна

0<г<т

Требуемый результат получаем путем преобразования последней суммы и группирования членов при [гга/т]. Вторую формулу немедленно получаем в результате подстановки:

следовательно.

4в. Ео<,<«п filmj/ni) = Ео<г<атГгга/т1(/(г - 1) - /(г)) + \an]f{\am] - 1). 47. (а) Числа 2, 4, р- 1 - это четные вычеты (по модулю р); поскольку 2fcg = p[2fcg/pj + (2fcg) modp, число ( l)l2*«/pJ((2fcg)modp)- четный вычет или четный вычет минус р, причем очевидно, что каждый четный вычет встречается только один раз. Поэтому {-l)qP-2 4 ... (р - 1) = 2 4 .. (р - 1). (Ь) Пусть q = 2. Если р = 4га -I-1, то (J = га; если р = 4га + 3, то сг = га -I-1. Поэтому () = (1,-1,-1,1), если р mod 8 = (1, 3, 5, 7) соответственно, (с) Для к < р/А имеем

[(р - 1 - 2fc)g/pJ = q - \{2к + l)g/pl = g - 1 - L(2fc + l)g/pj = L(2fc + l)g/pj (no модулю 2). Поэтому мы можем заменить последние члены [(р- l)g/pj, L(P~3)g/pJ,... на \ q/p\, [Зд/р]

и т д. (d) Eo<*<p/2Lfcg/pJ + Ео<г<,/2Гр/д1 = ЫШя -1) = (р+ i)(g -1)/4. кроме

того, Ео<г<в/2ГР/91 = Eo<r<9/2LP/9j + (з " 1)/2- Идея этого доказательства восходит