Олимпиадные задачи из источника «глава 4. Арифметика остатков»

Имеется n целых чисел. Доказать, что среди них найдется несколько, или быть может одно, сумма которых делится на n.

Существует ли степень двойки, из которой перестановкой цифр можно получить другую степень двойки?

Из шахматной доски вырезали две клетки – a1 и h8. Можно ли оставшуюся часть доски покрыть 31 косточкой домино так, чтобы каждая косточка покрывала ровно две клетки доски?

Дано <i>n</i> чисел, <i>x</i>₁, <i>x</i>₂, ..., <i>x_n</i>, при этом  <i>x_k</i> = ±1.  Доказать, что если  <i>x</i>₁<i>x</i>₂ + <i>x</i>₂<i>x</i>₃ + ... + <i>x_nx</i>₁ = 0,  то <i>n</i> делится на 4.

Известно, что  <i>ax</i>⁴ + <i>bx</i>³ + <i>cx</i>² + <i>dx + e</i>,  где <i>a, b, c, d, e</i> – данные целые числа, при любом целом <i>x</i> делится на 7.

Доказать, что все числа <i>a, b, c, d, e</i> делятся на 7.

Имеются семь жетонов с цифрами 1, 2, 3, 4, 5, 6, 7.

Докажите, что ни одно семизначное число, составленное посредством этих жетонов, не делится на другое.

Доказать, что многочлен с целыми коэффициентами  <i>a</i>₀<i>xⁿ</i> + <i>a</i>₁<i>x</i>^<i>n</i>–1 + ... + <i>a</i>_<i>n</i>–1<i>x</i> + <i>a_n</i>,  принимающий при  <i>x</i> = 0  и  <i>x</i> = 1  нечётные значения, не имеет целых корней.

Докажите, что для любого нечётного натурального числа <i>a</i> существует такое натуральное число <i>b</i>, что  2^<i>b</i> – 1  делится на <i>a</i>.

В китайской натурофилософии выделяются пять первоэлементов природы – дерево, огонь, металл, вода и земля, которым соответствуют пять цветов – синий (или зелёный), красный, белый, чёрный и жёлтый. В восточном календаре с древних времен используется 12-летний животный цикл так, что каждому из 12 годов в цикле соответствует одно из животных. Кроме того, каждый год проходит под покровительством одной из стихий и окрашивается в один из цветов:

  годы, оканчивающиеся на 0 и 1 – годы металла (цвет белый);

  годы, оканчивающиеся на 2 и 3 – это годы воды (цвет чёрный);

  годы, оканчивающиеся на 4 и 5 – годы дерева (цвет синий);

  годы, оканчивающиеся на 6 и 7 – годы огня (цвет красный);

  годы, оканчивающиеся на 8 и 9 – годы земли (цвет жёлтый).

В 60-летнем календарном цикле каждое...

Генерал хочет построить для парада своих солдат в одинаковые квадратные каре (конечно, в каре должно быть более одного человека), но он не знает сколько солдат (от 1 до 37) находится в лазарете. Докажите, что у генерала может быть такое количество солдат, что он, независимо от заполнения лазарета, сумеет выполнить свое намерение. Например войско из 9 человек можно поставить в виде квадрата 3×3, а если один человек болен, то в виде двух квадратов 2×2.

а) Трёхзначное число 625 обладает своеобразным свойством самовоспроизводимости, как то:  625² = 390625. БикЮ Сколько четырёхзначных чисел удовлетворяют уравнению  <i>x</i>² ≡ <i>x</i> (mod 10000)?

б) Докажите, что при любом <i>k</i> существует ровно четыре набора из <i>k</i> цифр – 0...0, 0...01 и ещё два, оканчивающиеся пятеркой и шестёркой, – обладающие таким свойством: если натуральное число оканчивается одним из этих наборов цифр, то его квадрат оканчивается тем же набором цифр.

Найдите наименьшее натуральное число, половина которого – квадрат, треть – куб, а пятая часть – пятая степень.

Какие цифры надо поставить вместо звёздочек, чтобы число 454** делилось на 2, 7 и 9?

Предположим, что числа <i>m</i>₁, ..., <i>m_n</i> попарно взаимно просты. Докажите, что любую правильную дробь вида   <img width="76" height="43" align="MIDDLE" border="0" src="/storage/problem-media/60833/problem_60833_img_2.gif">  можно представить в виде алгебраической суммы правильных дробей вида ^<i>n_i</i>/_{<i>m_i</i>}  (<i>i</i> = 1, ..., <i>n</i>).

Докажите, что число <i>x</i> является элементом приведённой системы вычетов тогда и только тогда, когда числа <i>a</i>₁, ..., <i>a_n</i>, определённые сравнениями

<i>x ≡ a</i>₁ (mod <i>m</i>₁),  ..., <i>x ≡ a_n</i> (mod <i>m_n</i>)  принадлежат приведённым системам вычетов по модулям <i>m</i>₁, ..., <i>m_n</i> соответственно. Выведите отсюда мультипликативность функции Эйлера.

Пусть натуральные числа <i>m</i>₁, <i>m</i>₂, ..., <i>m_n</i> попарно взаимно просты. Докажите, что если числа <i>x</i>₁, <i>x</i>₂, ..., <i>x_n</i> пробегают полные системы вычетов по модулям <i>m</i>₁, <i>m</i>₂, ..., <i>m_n</i> соответственно, то число  <i>x = x</i>₁<i>m</i>₂...<i>m_n + m</i>₁<i>x</i>₂<i>m</i&gt...

Найдите такое наименьшее чётное натуральное число <i>a</i>, что  <i>a</i> + 1  делится на 3,  <i>a</i> + 2  – на 5,  <i>a</i> + 3  – на 7,  <i>a</i> + 4  – на 11,  <i>a</i> + 5  – на 13.

Найдите остаток от деления числа 1000! на 10²⁵⁰.

На столе лежат книги, которые надо упаковать. Если их связать в одинаковые пачки по 4, по 5 или по 6 книг, то каждый раз останется одна лишняя книга, а если связать по 7 книг в пачку, то лишних книг не останется. Какое наименьшее количество книг может быть на столе?

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

Укажите все целые числа <i>x</i>, удовлетворяющие системам:

  а)   <i>x</i> ≡ 3 (mod 5),

        <i>x</i> ≡ 7 (mod 17);

  б)   <i>x</i> ≡ 2 (mod 13),

        <i>x</i> ≡ 4 (mod 19).

Докажите <i>китайскую теорему об остатках</i>:

  Пусть целые числа <i>m</i>₁, ..., <i>m_n</i> попарно взаимно просты,  <i>m = m</i>₁...<i>m_n</i>,  и <i>a</i>₁, ..., <i>a_n, A</i> – произвольные целые числа. Тогда существует ровно одно такое целое число <i>x</i>, что

    <i>x ≡ a</i>₁ (mod <i>m</i>₁),

      ...

    <i>x ≡ a_n</i> (mod <i>m_n</i>) и  <i>A ≤ x < A + m</i>.

Пользуясь результатом задачи <a href="https://mirolimp.ru/tasks/160823">160823</a>, укажите в явном виде число <i>x</i>, которое удовлетворяет системе из задачи <a href="https://mirolimp.ru/tasks/160825">160825</a>.

Натуральные числа <i>m</i>₁, ..., <i>m_n</i> попарно взаимно просты. Докажите, что число  <i>x</i> = (<i>m</i>₂...<i>m_n</i>)^{φ(<i>m</i>₁)}  является решением системы

    <i>x</i> ≡ 1 (mod <i>m</i>₁),

    <i>x</i> ≡ 0 (mod <i>m</i>₂),

        ...

    <i>x</i> ≡ 0 (mod <i>m_n</i>).

Натуральные числа <i>m</i>₁, ..., <i>m_n</i> попарно взаимно просты. Докажите, что сравнение  <i>a</i> ≡ <i>b</i> (mod <i>m</i>₁<i>m</i>₂...<i>m_n</i>)  равносильно системе

    <i>a ≡ b</i> (mod <i>m</i>₁),

    <i>a ≡ b</i> (mod <i>m</i>₂),

        ...

    <i>a ≡ b</i> (mod <i>m_n</i>).