Страница:
<< 1 2 3 4 >> [Всего задач: 19]
|
[Больное войско]
|
|
Сложность: 4-
Классы: 10,11
|
Генерал хочет построить для парада своих солдат в одинаковые квадратные каре (конечно, в каре должно быть более одного человека), но он не знает сколько солдат (от 1 до 37) находится в лазарете. Докажите, что у генерала может быть такое количество солдат, что он, независимо от заполнения лазарета, сумеет выполнить свое намерение. Например войско из 9 человек можно поставить в виде квадрата 3×3, а если один человек болен, то в виде двух квадратов
2×2.
Подсказка
Примените китайскую теорему об остатках с 
где p1, ..., p37 – различные простые числа.
|
[Китайская теорема об остатках]
|
|
Сложность: 4
|
Докажите китайскую теорему об остатках:
Пусть целые числа m1, ..., mn
попарно взаимно просты, m = m1...mn, и a1, ..., an, A –
произвольные целые числа. Тогда существует ровно одно такое целое число x, что
x ≡ a1 (mod m1),
...
x ≡ an (mod mn)
и
A ≤ x < A + m.
|
|
|
Сложность: 4
Классы: 9,10,11
|
Пусть натуральные числа m1, m2, ...,
mn попарно взаимно просты. Докажите, что если числа x1, x2, ..., xn пробегают полные системы вычетов по модулям m1, m2, ..., mn соответственно, то число x = x1m2...mn + m1x2m3...mn + ... + m1m2...mn–1xn пробегает полную систему вычетов по модулю m1m2...mn. Выведите отсюда китайскую теорему об остатках (см. задачу 60825).
|
[Китайская теорема об остатках для многочленов]
|
|
Сложность: 4
Классы: 9,10,11
|
Пусть m1(x), ..., mn(x) – попарно взаимно простые многочлены, a1(x), ..., an(x) – произвольные многочлены.
Докажите, что существует ровно один такой многочлен p(x), что
p(x) ≡ a1(x) (mod m1(x)),
...
p(x) ≡ an(x) (mod mn(x))
и deg p(x) < deg m1(x) + ... + deg mn(x).
Подсказка
Докажите утверждение индукцией по n.
|
|
|
Сложность: 4+
Классы: 9,10,11
|
При каких натуральных n > 1 существуют такие натуральные b1, ..., bn (не все из которых равны), что при всех натуральных k число
(b1 + k)(b2 + k)...(bn + k) является степенью натурального числа? (Показатель степени может зависеть от k, но должен быть больше 1.)
Решение
Все числа в решении считаются натуральными, если не оговорено противное.
Пусть n – составное число, то есть n = rs, где r > 1, s > 1. Тогда достаточно рассмотреть числа b1 = ... = br = 1, br+1 = ... = bn = 2. Очевидно, что при всяком k число (b1 + k)...(bn + k) – r-я степень.
Пусть n – простое число и есть требуемый набор (b1, ..., bn). Без ограничения общности можно считать, что b1, ..., bq – попарно различные числа, а каждое из чисел bq+1, ..., bn равно одному из b1, ..., bq (q > 1, так как не все числа равны). Пусть среди чисел b1, ..., bn имеется si равных bi, где
1 ≤ i < q, s1 + ... + sq = n.
Рассмотрим q различных простых чисел p1, ..., pq, которые больше всех bi. Числа 
попарно взаимно просты и 0 < ri < pi < . По китайской теореме об остатках найдётся такое целое m, что 
при всех i от 1 до q. Пусть (b1 + m)...(bn + m) = uv.
то есть делится на pi и не делится на . При j ≠ i, 1 ≤ j ≤ q, имеем 0 < |bi – bj| < pi, поэтому bj + m на pi не делится.
Таким образом, в каноническом разложении числа (b1 + m)...(bn + m) на простые множители каждое число pi содержится ровно в степени si.
Значит, число v является делителем всех si, а значит, и делителем их суммы n. При этом v < n (так как q > 1), поэтому v = 1.
Ответ
При составных n.
Страница:
<< 1 2 3 4 >> [Всего задач: 19]
Тема:
Все темы
>>
Алгебра и арифметика
>>
Теория чисел. Делимость
>>
Деление с остатком. Арифметика остатков
>>
Китайская теорема об остатках
