Каталог по темам

Задачи

Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 188]

Задача 32028

Темы:	[	Деление с остатком	]
	[	Разбиения на пары и группы; биекции	]
	[	Арифметика остатков (прочее)	]

Сложность: 3+
Классы: 7,8,9,10

Все натуральные числа поделены на хорошие и плохие. Известно, что если число m хорошее, то и число m + 6 тоже хорошее, а если число n плохое, то и число n + 15 тоже плохое. Может ли среди первых 2000 чисел быть ровно 1000 хороших?

Решение

Предположим, что число – хорошее, а n + 3 – плохое. Тогда с одной стороны, число n + 18 = (n + 3) + 15 должно быть плохим, а с другой стороны, это же число n + 18 = ((n + 6) + 6) + 6 должно быть хорошим.
Если же число n – плохое, а n + 3 – хорошее, то число n + 15 = ((n + 3) + 6) + 6 должно быть одновременно и плохим и хорошим.
Полученное в обоих случаях противоречие доказывает, что числа n и n + 3 всегда принадлежат одному классу. Из этого следует, что любой класс вычетов по модулю 3 является либо целиком хорошим, либо целиком плохим.
Среди первых 2000 чисел каждый такой класс содержит 666 или 667 чисел. Любой класс содержит меньше 1000 чисел, а любые два класса – больше 1000 чисел. Поэтому ровно 1000 хороших чисел быть не может.

Прислать комментарий

Задача 60653

Темы:	[	Деление с остатком	]
	[	Разложение на множители	]
	[	Арифметика остатков (прочее)	]
	[	Малая теорема Ферма	]

Сложность: 3+
Классы: 8,9,10

Докажите, что
а) 2⁴¹ + 1 делится на 83;
б) 2⁷⁰ + 3⁷⁰ делится на 13;
в) 2⁶⁰ – 1 делится на 20801.

Решение

а) 2⁹ = 512 ≡ 14 (mod 83), 2¹⁸ ≡ 196 ≡ 30, 2³⁶ ≡ 900 ≡ 70 ≡ –13, 2⁴¹ ≡ –13·32 ≡ –416 ≡ –1.

б) 2⁷⁰ + 3⁷⁰ = 4³⁵ + 9³⁵ делится на 4 + 9 = 13.

в) 20801 = 11·31·61.
Первый способ. 2⁶⁰ – 1 делится на 2¹⁰ – 1 = (2⁵ – 1)(2⁵ + 1) = 31·33. Это число делится на 31 и на 11. Кроме того, 2⁶ ≡ 3 (mod 61), 2³⁰ ≡ 243 ≡ –1,
2⁶⁰ ≡ 1.
Второй способ. Согласно малой теореме Ферма (см. задачу 60736) 2⁶⁰ – 1 делится на 61, 2³⁰ – 1 делится на 31, 2¹⁰ – 1 делится на 11. Поэтому
2⁶⁰ – 1 делится на все эти числа.

Прислать комментарий

Задача 60685

Тема:

[

Деление с остатком

]

Сложность: 3+
Классы: 7,8,9

Составьте список всевозможных остатков, которые дают числа n² при делении на 3, 4, 5, ..., 9.

Ответ

При делении на 3 и на 4 0 и 1; при делении на 5 и на 8 0, 1 и 4; при делении на 6 0, 1, 3 и 4; при делении на 7 0, 1, 2 и 4; при делении на 9 0, 1, 4 и 7.

Прислать комментарий

Задача 60696

Темы:	[	Деление с остатком	]
Темы:	[	Арифметика остатков (прочее)	]

Сложность: 3+
Классы: 7,8,9

Пусть a и b – целые числа. Докажите, что
а) если a² + b² делится на 3, то a² + b² делится на 9;
б) если a² + b² делится на 21, то a² + b² делится на 441.

Решение

а) a² + b² ≡ 0 (mod 3) ⇔ оба числа a и b делятся на 3 (см. задачу 108744).

б) См. задачу 30380.

Прислать комментарий

Задача 60703

Темы:	[	Деление с остатком	]
Темы:	[	Арифметика остатков (прочее)	]

Сложность: 3+
Классы: 7,8,9

а) При каких целых n число 5n² + 10n + 8 делится на 3?
б) А при каких на 4?

Решение

а) 5n² + 10n + 8 ≡ – n² – 2n – 1 = – (n + 1)² (mod 3).

б) 5n² + 10n + 8 ≡ n² + 2n = n(n + 2) (mod 4).

Ответ

На 3 при n = 2 + 3k; на 4 при n = 2k (k ∈ Z.

Прислать комментарий

Страница: << 4 5 6 7 8 9 10 >> [Всего задач: 188]