Задача 1: Вычислите a) ; б) ; в) .

Задача 2: Докажите, что если p – простое число, то .

Задача 3: Сколько чисел, меньших 300, делятся а) на 2 и 3; б) на 2, 3 и 5?

Задача 4: а) Пусть a чисел удовлетворяют какому-то свойству 1, b чисел удовлетворяют свойству 2, и c чисел удовлетворяют обоим свойствам сразу. Тогда количество чисел, удовлетворяющих хотя бы одному из этих свойств, равно a + b – c.

б) Пусть a₁ чисел удовлетворяют первому свойству, a₂ чисел удовлетворяют второму свойству, a₃ чисел удовлетворяют третьему свойству, a₁₂ удовлетворяют свойствам 1 и 2, a₁₃ удовлетворяют свойствам 1 и 3, a₂₃ удовлетворяют свойствам 2 и 3, и a₁₂₃ удовлетворяют всем трем свойствам. Тогда количество чисел, удовлетворяющих хотя бы одному из этих свойств, равно a₁a₂ + a₃ – a₁₂ – a₁₃ – a₂₃ + a₁₂₃.

Задача 5: (Формула включения и исключения) Сформулируйте и докажите аналогичное утверждение для нахождения количества чисел, удовлетворяющих хотя бы одному из n свойств, если для каждого набора этих свойств известно количество чисел, удовлетворяющих одновременно всем свойствам из этого набора.

Задача 6: а) Пусть n = pq, где p, q – различные простые числа. Докажите, что ;

б) Пусть n = pqr, где p, q, r – различные простые числа. Докажите, что .

в) Упростите выражение для в пунктах а) и б).

Задача 7: Докажите, что в условиях предыдущей задачи а) ; б). Верно ли это, если p, q, r – не простые, а попарно взаимно простые числа?

Задача 8: Найдите наименьшее натуральное число, дающее при делении на 2, 3, 5, 7 соответственно остатки 1, 2, 4, 6.

Задача 9: Пусть даны n попарно взаимно простых чисел m₁, m₂, …, m_n; n чисел r₁, r₂, …, r_n таких, что 0 ≤ r_i ≤ m_i – 1 при всех i = 1,2, … ,n и m = m₁m₂ … m_n.

1. Если 0 ≤ N₁ ≤ m – 1, 0 ≤ N₂ ≤ m – 1, и для всех i = 1,2, … ,n, то N₁ = N₂.

2. Количество различных наборов чисел r₁, r₂, …, r_n таких, что 0 ≤ r_i ≤ m_i – 1, равно m.

3. (Китайская теорема об остатках) Существует единственное число N такое, что 0 ≤ N ≤ m – 1 и для всех i = 1,2, … ,n.

4. N взаимно просто с m Тогда и только тогда, когда N взаимно просто с m_i для всех i = 1,2, … ,n.

5. Докажите, что .

Задача 10: Если , то .

Задача 11: Генерал построил солдат в колонну по 4, но при этом солдат Иванов остался лишним. Тогда генерал построил солдат в колонну по 5. И снова Иванов остался лишним. Когда же и в колонне по 6 Иванов оказался лишним, генерал посулил ему наряд вне очереди, после чего в колонне по 7 Иванов нашел себе место и никого лишнего не осталось. Сколько солдат могло быть у генерала?

Задача 12: Для любых попарно взаимно простых чисел m₁, m₂, …, m_n и остатков r₁, r₂, …, r_n по модулям m₁, m₂, …, m_n найдутся n последовательных чисел a, a + 1, …, a + n – 1 таких, что a ≡ r₁ (mod %)%m₁, a + 1 ≡ r₂ (mod m₂₎, …, a + n – 1 ≡ r_n (mod %)%m_n.

Задача 13: Пятнадцать простых чисел образуют арифметическую прогрессию с разностью d. Докажите, что d > 30000.

Задача 14: Докажите, что среди а) любых десяти; б) любых шестнадцати последовательных натуральных чисел найдется число, взаимно простое с остальными.

Задача 15: Существует ли в сутках момент, когда расположенные на общей оси часовая, минутная и секундная стрелки правильно идущих часов образуют попарно углы в 120?