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

В китайской натурофилософии выделяются пять первоэлементов природы – дерево, огонь, металл, вода и земля, которым соответствуют пять цветов – синий (или зелёный), красный, белый, чёрный и жёлтый. В восточном календаре с древних времен используется 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>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).

Пользуясь результатом задачи <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>).

Найдите остатки от деления:  а) 19¹⁰ на 6;   б) 19¹⁴ на 70;   в) 17⁹ на 48;   г) 14^14¹⁴ на 100.

При каких целых <i>n</i> число  <i>n</i>² + 3<i>n</i> + 1  делится на 55?

Докажите, что если необходимый и достаточный признак делимости, выражающийся через свойства цифр числа, не зависит от порядка цифр, то это признак делимости на 3 или на 9.

Найдите наименьшее основание системы счисления, в которой одновременно имеют место следующие признаки делимости:

  1) число делится на 5 тогда и только тогда, когда сумма его цифр делится на 5;

  2) число делится на 7 тогда и только тогда, когда число, составленное из двух его последних цифр, делится на 7.

а) Опишите все системы счисления, в которых число делится на 2 тогда и только тогда, когда сумма его цифр делится на 2.б) Решите задачу, заменив модуль 2 произвольным натуральным числом  <i>m</i> > 1.

С помощью признака делимости Паскаля (см. задачу <a href="https://mirolimp.ru/tasks/160815">160815</a>) установите признаки делимости на числа 3, 9, 6, 8, 12, 15, 11, 7, 27, 37.

Пусть запись числа <i>N</i> в десятичной системе счисления имеет вид   <span style="text-decoration: overline;"><i>a_na</i>_<i>n</i>–1...<i>a</i>₁<i>a</i>₀</span> ,   <i>r_i</i> – остаток от деления числа 10^<i>i</i> на <i>m</i>  (<i>i</i> = 0, ..., <i>n</i>).

Докажите, что число <i>N</i> делится на <i>m</i> тогда и только тогда, когда число  <i>M = a_nr_n + a</i>_<i>n</i>–1<i>r</i><sub>&...

Докажите, что если  <i>n</i> > 6  – чётное совершенное число, то его цифровой корень (см. задачу <a href="https://mirolimp.ru/tasks/160794">160794</a>) равен 1.

<img align="absMIDDLE" src="/storage/problem-media/60788/problem_60788_img_2.gif">  – разложение натурального числа <i>m</i> на простые множители. Обозначим  <img align="absMIDDLE" src="/storage/problem-media/60788/problem_60788_img_3.gif">

Докажите, что  <i>a</i>^λ(<i>m</i>) ≡ 1 (mod <i>m</i>)  для любого целого числа <i>a</i>, взаимно простого с <i>m</i>.

Докажите, что для составного числа 561 справедлив аналог малой теоремы Ферма: если  (<i>a</i>, 561) = 1,  то  <i>a</i>⁵⁶⁰ ≡ 1 (mod 561).

Докажите, что при любом нечётном <i>n</i> число  2^<i>n</i>! – 1  делится на <i>n</i>.

Докажите, что при любом целом <i>a</i>

  a)  <i>a</i>⁵ – <i>a</i>  делится на 30;

  б)  <i>a</i>¹⁷ – <i>a</i>  делится на 510;

  в)  <i>a</i>¹¹ – <i>a</i>  делится на 66;

  г)  <i>a</i>⁷³ – <i>a</i>  делится на 2·3·5·7·13·19·37·73.

При помощи теоремы Эйлера найдите число <i>x</i>, удовлетворяющее сравнению  <i>ax + b</i> ≡ 0 (mod <i>m</i>),  где  (<i>a, m</i>) = 1.