Решения к главе 3

1. а Из

замечая, что имеем

Следовательно, Р кратно 3 тогда и только тогда, когда сумма цифру его изображающих, кратна 3; оно кратно 9 тогда и только тогда, когда указанная сумма кратна 9.

Замечая, что имеем

Следовательно, кратно 11 тогда и только тогда, когда разность между суммою цифр, стоящих на нечетных (считая справа) местах, и суммою цифр, стоящих на четных местах, кратна 11.

b. Из

ввиду имеем

Поэтому Р кратно 101 тогда и только тогда, когда кратно 101.

с. Из

ввиду имеем

Поэтому Р кратно 37 тогда и только тогда, когда кратно 37.

Ввиду имеем

Поэтому Р кратно одному из чисел 7, 11, 13 тогда и только тогда, когда кратно этому же числу.

2, а) Когда пробегает полную систему вычетов по модулю , то также пробегает полную систему; наименьший неотрицательный вычет числа пробегает значения Поэтому

) Применяя результат вопроса 18, b, гл. II, находим

3.а. Пусть — наименьший неотрицательный вычет числа по модулю . Имеем

При теорема очевидна. Поэтому рассмотрим лишь случай Полагая

имеем в остальных случаях. Поэтому

b. Имеем

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

c. Находим

Применим теорему вопроса а, полагая А. Тогда получим

указанный результат.

4. Разложим в непрерывную дробь. Пусть наибольший из знаменателей подходящих дробей, не превосходящий , имеем (вопрос 4, b, гл. I)

При этом из где С - постоянное, которого не превосходят все для наибольшего целого с условием следует Применяя теорему вопроса находим

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

где применяем обозначение Пусть Если то подобно предыдущему найдем

и т. д., пока не придем к некоторому Тогда получим

Числа удовлетворяют условиям

Поэтому (вопрос 3, b гл. I) и, следовательно, формула, указанная в вопросе, верна.

5, а. Сумму, стоящую слева, обозначим буквою S. Пусть При теорема очевидна. Поэтому предполагаем Взяв найдем числа с условиями

Взяв аналогичным путем найдем числа взяв найдем числа и т. д., пока не придем к с условием Применяя теорему вопроса 3, с, найдем

Длина интервала, для которого, не превосходит Следовательно, с одной и той же дробью — связано чисел Пусть и а — наименьшее и наибольшее значения а, отвечающие данному .

Имеем

Следовательно, с данным m связано

чисел Суммируя последнее выражение по всем получим

b. Имеем

откуда, полагая находим

Но при имеем а при имеем . Поэтому откуда и получим указанную формулу.

6, а. Применим формулу вопроса 1, с, гл. II. Полагая интервале имеем

Поэтому (вопрос 8, а, гл. II, вопрос 5, а)

b. Имеем (вопросы И, d и 1, d, гл. II)

Достаточно рассмотреть лишь случай Интервал где разобьем на интервалов вида где Полагая в интервале имеем

Поэтому (вопрос 6, а)

Далее (вопрос 8, b, гл. II)

Поэтому

c. Напишем ряды дробей

с знаменателями, не превосходящими N. Дробь — с условием встретится в рядах. Поэтому сумма всех членов, содержащихся во всех рядах, равна

С другой стороны, сумма членов ряда

Поэтому та же сумм всех членов, содержащихся во всех рядах, будет

Следовательно, неравенство (1) верно при

Далее, допустив справедливость неравенства (1) при каком-либо докажем, что оно останется верным и после замены на Напишем новые ряды дробей

со знаменателями, не превосходящими N. Здесь сумма всех членов, содержащихся во всех рядах, равна

С другой стороны, сумма членов ряда

Поэтому та же самая сумма, содержащаяся во всех рядах, будет

И мы убедимся, что неравенство (1) останется верным и после замены на

В случае неравенство (2) является следствием неравенства вопроса b. Далее, допустив справедливость неравенства (2) для какого-либо докажем, что оно останется верным и после замены t на Напишем ряды

включающие только значения с условием Здесь сумм» всех членов, содержащихся во всех рядах, равна

С другой стороны, сумма членов ряда будет

Поэтому (теорема вопроса с) сумма всех членов, содержащихся во всех рядах, будет

И мы убедимся, что неравенство (2) останется верным и после/замены I на

7, Пусть система неправильная и - наибольшее число t условием, что входит в нечетное число чисел системы. Одно из последних чисел мы заменим меньшим, содержащим лишь степени 2, входящие в нечетное число чисел оставшейся системы.

Пусть система — правильная. Число, меньшее одного из чисел Т этой системы, отличается от по крайней мере, одним знаком в системе исчисления с основанием 2.

8, а. Добавив к каждому из чисел, представляемых указанным способом, число получим числа, которые можно получить, заставляя в той же сумме пробегать значения 0, 1,2, т. е. получим все числа

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

9, а. Указанным способом получим чисел, не сравнимых по модулю так как из

следовало бы (всякое отличное от кратно )

b. Указанным способом получим чисел ввиду теоремы вопроса а, не сравнимых по модулю и ввиду Мкхк, взаимно простых с

Согласно теореме вопроса а число где пробегают полные сичггемы вычетов по модулям пробегает полную систему вычетов по модулю . Это число взаимно просто с тогда и только тогда, когда Поэтому

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

Поэтому Отсюда и из мультипликативности известное выражение для следует непосредственно.

10, а. Первое утверждение следует из

второе утверждение следует из

b, Дроби совпадают с дробями

т. e. с дробями в Второе утверждение доказывается аналогичным способом.

11, а. При а, кратном , имеем

При а, не делящемся на , имеем

b. При нецелом а левая часть равна

c. Согласно теореме вопроса b левая часть не превосходит где

Но при нечетном

а при четном

При ввиду границу можно уменьшить на

Последнее выражение при при

12, а. Пусть каноническое разложение числа .

Полагая при обозначениях вопроса 10, а имеем

Но при находим

При полагая находим

b. Пусть - целое, Имеем Сумма слагаемых левой части этого равенства с условием согласно теореме вопроса а равна

Находим

где, полагая имеем

Последнее равно 0 при и равно 1 при Отсюда и получаем теорему вопроса а.

d. Равенства следуют из вопроса 10, b.

e. Имеем

где пробегают приведенные системы вычетов по модулям Отсюда (вопрос d) первое равенство вопроса следует непосредственно.

Аналогичным путем докажем и второе равенство.

13, а. Имеем

b. Раскрывая произведение, отвечающее данному , имеем

Отсюда, суммируя по всем и получим известное выражение для

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

15, а. Имеем

и т. д.

b. Полагая из теоремы вопроса а получим теорему Ферма.

c. Пусть При некоторых целых имеем

Пусть - каноническое разложение числа m. Имеем