Упражнения

Разминочные упражнения

1 Каково наименьшее целое положительное число, имеющее ровно к делителей при 1 к 6?

2 Докажите, что и воспользуйтесь этим тождеством, чтобы выразить через при Указание: воспользуйтесь правилами (4.12), (4.14) и (4.15).

3 Пусть — количество простых чисел, не превосходящих х. Докажите или опровергните, что

4 Что бы случилось, если бы построение Штерна—Броко начиналось с пяти дробей дробей

5 Укажите простые формулы для если суть -матрицы из (4.33).

6 Что означает запись

7 Десять человек, перенумерованных числами от 1 до 10, выстроены в круг, как в задаче Иосифа, и каждый человек подвергается казни. (Величина может быть значительно больше 10.) Докажите, что первыми тремя обреченными на уничтожение людьми не могут быть 10-й, 1-й человек (именно в таком порядке) при любом к.

8 Система счисления в остатках рассмотренная в тексте, обладает тем забавным свойством, что числу 13 соответствует в ней пара чисел (1,3), которая выглядит почти так же. Объясните, как установить все случаи подобного совпадения, не вычисляя все пятнадцать пар остатков. Другими словами, найдите все решения сравнений

Указание: воспользуйтесь теми фактами, что

9 Покажите, что — нечетное составное число. Указание: чему равно

10 Вычислите

11 Найдите функцию обладающую тем свойством, что

(Это аналогично функции Мёбиуса: см. (456)

12 Упростите формулу

13 Целое положительное число называется свободным от квадратов, если оно не делится на при любом Установите необходимое и достаточное условие того, что число свободно от квадратов:

а через представление (4.11) числа в виде показателей простых;

b через функцию

Обязательные упражнения

14 Докажите или опровергните следующие правила: а

15 Встречается ли каждое простое число в качестве сомножителя некоторого числа Евклида

16 Чему равна сумма величин, обратных первым числам Евклида?

17 Пусть - „число Ферма" Докажите, что если

18 Покажите, что если — простое число, то является степенью двойки.

19 Докажите следующие тождества при целом положительном

Внимание: вопрос несколько усложнен, но ответ нисколько не сложен.

20 При каждом целом положительном числе найдется простое число , такое, что (В сущности, это „постулат Бертрана“, справедливость которого в 1845 г. проверил Жозеф Бертран для доказал П. Чебышёв для всех Воспользуйтесь постулатом Бертрана для доказательства того, что существует постоянная такая, что все числа

простые.

21 Пусть простое число. Найдите постоянную К, такую, что

22 Число — простое. Докажите, что в системе счисления с любым основанием число может быть простым только тогда, когда число единиц — само простое число.

23 Установите рекуррентность для — линеечной функции из того места в тексте, где обсуждалась величина Покажите, что существует определенная связь между и тем диском, который перекладывался на шаге (1 к при перемещении ханойской башни из дисков за перекладываний.

24 Выразите величину через функцию — сумму цифр представления числа в системе счисления с основанием , обобщая тем самым формулу (4.24).

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

26 Рассмотрим последовательность всех неотрицательных несократимых дробей таких, что Например,

Верно ли, что всякий раз, когда дробь непосредственно предшествует дроби

27 Укажите простое правило сравнения рациональных чисел, основанное на их представлениях посредством символов в системе счисления Штерна—Броко.

28 Представление Штерна—Броко числа имеет вид

воспользуйтесь этим для нахождения всех простейших рациональных приближений к знаменатели которых меньше 50. Относится ли к ним

29 В тексте охарактеризовано соответствие между двоичными вещественными числами из [0, 1) и вещественными числами Штерна—Броко из Если числу х соответствует число а и то какое число соответствует числу

30 Докажите следующее утверждение (китайскую теорему об остатках): пусть целые числа с при пусть — целые числа. Тогда существует ровно одно целое число а, такое, что

31 Десятичное число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3. Докажите это широко известное правило и обобщите его.

32 Докажите теорему Эйлера (4.50), обобщив доказательство теоремы Ферма (4.47).

33 Покажите, что если — мультипликативные функции, то такой же будет и функция

34 Докажите, что (4.56) является частным случаем (4.61).

Домашние задания

35 Пусть — функция, которая удовлетворяет соотношению

если тип — целые неотрицательные числа и Таким образом, в соотношении (4.5); величина — это обращение относительно Установите рекуррентность, которая определяет величину

36 Рассмотрим множество целые Число называется обратимым (или единицей), если так как оно имеет некоторое обратное число (т. е. ). К примеру, — обратимое число, так же как и число Пары взаимно сокращаемых обратимых чисел могут быть вставлены в любое разложение на множители, поэтому оставим их в покое. Необратимые числа множества называются „простыми", если они не могут быть записаны в виде произведения двух необратимых. Покажите, что 2, 3 и являются „простыми" числами множества Указание: если то Кроме того, квадрат любого целого числа по модулю 10 равен 0, 1,4, 5, 6, или 9.

37 Докажите формулу (4.17). Указание: покажите, что и рассмотрите числа

38 Докажите, что если то

(Здесь все переменные — целые числа.) Указание: воспользуйтесь алгоритмом Евклида.

39 Пусть наименьшее целое положительное число для которого существует возрастающая последовательность целых чисел

такая, что полный квадрат. (Если само число — полный квадрат, то можно положить ) К примеру, ибо наилучшей из таких последовательностей является Имеем:

Докажите, что для любых

40 Если представление числа в системе счисления с основанием имеет вид си то докажите, что

(Левая часть есть просто с полностью удаленными множителями . В случае это сводится к теореме Вильсона.)

41 а Покажите, что если то не существует целого числа такого, что делит Указание: воспользуйтесь теоремой Ферма, . С другой стороны, покажите, что если то такое целое число существует. Указание: запишите в виде и вспомните теорему Вильсона.

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

43 На уровне к дерева Штерна—Броко имеется узлов, соответствующих последовательности матриц Покажите, что эту последовательность можно получить, начав с матрицы и затем последовательно умножая на матрицу

при где — линеечная функция.

44 Докажите, что бейсболист, коэффициент бэттера у которого равен .316, должен был отбить мяч по меньшей мере 19 раз. (Если у него было удачных ударов за раз, когда он выходил на биту, то

45 Число 9376 обладает своеобразным свойством самовоспроизводимости, как то:

Сколько четырехзначных чисел х удовлетворяют уравнению ? Сколько -значных чисел х удовлетворяют уравнению

46 а Докажите, что если то Покажите, что если Указание: рассмотрите наименьший простой множитель в разложении

47 Покажите, что если и если для любого простого числа р, такого, что то число — простое. Указание: покажите, что если это условие выполняется, то при все числа различны.

48 Обобщите теорему Вильсона (4.49), установив величину выражения при

49 Пусть — количество пар целых чисел, таких, что

а Выразите через Ф-функцию. Докажите, что

50 Пусть — некоторое целое положительное число и

Говорят, что си является корнем из единицы степени так как На самом деле, каждое из комплексных чисел является корнем степени из единицы, поскольку следовательно, — один из сомножителей многочлена при Поскольку эти сомножители различны, то полное разложение многочлена над полем комплексных чисел должно быть таким:

а Пусть (Этот многочлен степени называется круговым многочленом порядка .) Докажите, что

Ь Докажите, что

Контрольные работы

51 Докажите теорему Ферма (4.48), разлагая посредством мультиномиальной теоремы.

52 Пусть целые положительные числа, такие, что х не имеет делителей (исключая 1), и пусть — некоторое простое число. Докажите, что по меньшей мере чисел кратны .

53 Укажите все целые положительные числа такие, что

54 Вычислите вручную величину

55 Пусть — произведение первых факториалов, -кажите, что при любом целом положительном отношение является целым числом.

56 Покажите, что величина

является степенью 2.

57 Пусть — множество всех целых чисел к, таких, что

К примеру, Докажите, что

Указание: вначале докажите, что сумма

Затем рассмотрите разность

58 Пусть . Укажите необходимое и достаточное условие того, что является степенью 2.

Конкурсные задачи

59 Докажите, что если — целые положительные числа и то Указание: докажите по индукции следующий более сильный результат: где — целые положительные числа и а — рациональное число то (Доказательство этого нетривиально.)

60 Докажите, что существует постоянная Р, такая, что формула (4.18) доставляет только простые числа. Можно воспользоваться следующим (в высшей степени нетривиальным) фактом: при любом достаточно большомр между имеется простое число, если

61 Докажите, что если — последовательные элементы последовательности то

(Эта рекуррентность позволяет вычислить все элементы по порядку, начиная с

62 Какое двоичное число соответствует числу исходя из соответствия „двоичная система система Штерна-Броко“? (Выразите ваш ответ в виде бесконечной суммы, вычислять ее в замкнутой форме не нужно.)

63 Покажите, используя только методы из этой главы, что если последняя теорема Ферма — утверждение (4.46) — неверна, то наименьшее которое ее опровергает, является простым числом. (Можно считать, что утверждение (4.46) справедливо, когда Кроме того, если — наименьший контрпример, покажите, что существует целое число такое, что

Таким образом, число с должно быть поистине гигантским. Указание: положите и заметьте, что

64 Последовательность Пирса порядка — это разделенная знаками или бесконечная строка дробей, состоящая из всех неотрицательных дробей (включая несокращенные дроби). Она определяется рекурсивно, начиная с последовательности

При последовательность образуется путем вставки двух символов непосредственно перед символом последовательности при всех Вставляемые символы суть

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

(Одинаковые элементы выстраиваются в довольно своеобразном порядке). Докажите, что знаки определенные по указанному правилу, корректно описывают отношения между соседними дробями в последовательности Пирса.

Исследовательские проблемы

65 Все ли числа Евклида являются числами, свободными от квадратов?

66 Все ли числа Мерсенна являются числами, свободными от квадратов?

67 Докажите или опровергните, что для любой последовательности целых чисел

68 Существует ли постоянная такая, что число является простым при любом

69 Пусть обозначает простое число. Докажите или опровергните, что

70 Будет ли для бесконечно многих

71 Докажите или опровергните: если к то найдется такое, что Существует ли бесконечно много таких

72 Докажите или опровергните: при любом целом числе а существует бесконечно много таких, что .

73 Если бы членов последовательности Фарея

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

74 Приблизительно сколько различных величин содержится в множестве при