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

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

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

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

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

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

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

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

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

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

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

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

С помощью признака делимости Паскаля (см. задачу <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>&...

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

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

Пусть  <i>p</i> > 2  – простое число. Докажите, что  7^<i>p</i> – 5^<i>p</i> – 2  делится на 6<i>p</i>.

Существует ли степень тройки, заканчивающаяся на 0001?

Выпишем в ряд все правильные дроби со знаменателем <i>n</i> и сделаем возможные сокращения. Например, для  <i>n</i> = 12  получится следующий ряд чисел:  ⁰/₁, ¹/₁₂, ¹/₆, ¹/₄, ¹/₃, ⁵/₁₂, ¹/₂, ⁷/₁₂, ²/₃, ³/₄, ⁵/₆, ¹¹/₁₂  Сколь...

Пусть τ(<i>n</i>) – количество положительных делителей натурального числа <i>n</i>. Решите уравнение  <i>a</i> = 2τ(<i>a</i>).

Известно, что  (<i>m, n</i>) > 1.  Что больше φ(<i>mn</i>) или  φ(<i>m</i>)φ(<i>n</i>)?  Определение функции φ(<i>n</i>) см. в задаче <a href="https://mirolimp.ru/tasks/160758">160758</a>.

Решите уравнения   а)  φ(5^<i>x</i>) = 100;   б)  φ(7^<i>x</i>) = 294;   в)  φ(3^<i>x</i>5^<i>y</i>) = 600.

Для каких <i>n</i> возможны равенства:   a)  φ(<i>n</i>) = <i>n</i> – 1;   б)  φ(2<i>n</i>) = 2φ(<i>n</i>);   в)  φ(<i>n^k</i>) = <i>n</i>^<i>k</i>–1φ(<i>n</i>)?

Решите уравнения   а)  φ(<i>x</i>) = ^<i>x</i>/₂;   б)  φ(<i>x</i>) = ^<i>x</i>/₃;    φ(<i>x</i>) = ^<i>x</i>/₄.

По какому модулю числа 1 и 5 составляют приведённую систему вычетов?

Решите уравнения   а)  φ(<i>x</i>) = 2;   б)  φ(<i>x</i>) = 8;   в)  φ(<i>x</i>) = 12;   г)  φ(<i>x</i>) = 14.

Пусть  (<i>m, n</i>) = 1,  а числа <i>x</i> и <i>y</i> пробегают приведённые системы вычетов по модулям <i>m</i> и <i>n</i> соответственно. Докажите, что число  <i>A = xn + ym</i>  пробегает при этом приведённую систему вычетов по модулю <i>mn</i>. Выведите отсюда мультипликативность функции Эйлера (см. задачу <a href="https://mirolimp.ru/tasks/160760">160760</a>).

Сколько классов составляют приведённую систему вычетов по модулю <i>m</i>?

<i>Функция Эйлера</i>  φ(<i>n</i>)  определяется как количество чисел от 1 до <i>n</i>, взаимно простых с <i>n</i>.

Основным свойством функции Эйлера является её <i>мультипликативность</i>.

Для взаимно простых <i>a</i> и <i>b</i> рассмотрим таблицу <div align="center"><img src="/storage/problem-media/60760/problem_60760_img_2.gif"></div>В каких столбцах этой таблицы находятся числа взаимно простые с числом<i>b</i>? Сколько в каждом из этих столбцов чисел взаимно простых с<i>a</i>? Докажите мультипликативность функции Эйлера, ответив на эти вопросы.

Чему равна сумма  φ(1) + φ(<i>p</i>) + φ(<i>p</i>²) + ... + φ(<i>p</i>^α),  где α #8211; некоторое натуральное число?