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

Дано <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.

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

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

Предположим, что числа <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²⁵⁰.

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

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

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

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

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

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

Двое пишут  а) 30-значное;  б) 20-значное число, употребляя только цифры 1, 2, 3, 4, 5. Первую цифру пишет первый, вторую – второй, третью – первый и т. д. Может ли второй добиться того, чтобы полученное число разделилось на 9, если первый стремится ему помешать?

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

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

Докажите, что  7⁵¹ – 1  делится на 103.

<b>Теорема Эйлера</b>. Пусть  <i>m</i> ≥ 1  и  (<i>a, m</i>) = 1.  Тогда  <i>a</i>^φ(<i>m</i>) ≡ 1 (mod <i>m</i>).

Докажите теорему Эйлера с помощью малой теоремы Ферма

  а) в случае, когда  <i>m = pⁿ</i>;

  б) в общем случае.

Докажите <i>тождество Гаусса</i>  <img width="27" height="56" align="MIDDLE" border="0" src="/storage/problem-media/60775/problem_60775_img_2.gif">φ(<i>d</i> ) = <i>n</i>. Определение функции φ(<i>n</i>) см. в задаче <a href="https://mirolimp.ru/tasks/160758">160758</a>.

Найдите сумму всех правильных несократимых дробей со знаменателем <i>n</i>.

Пусть  <img align="absMIDDLE" src="/storage/problem-media/60764/problem_60764_img_2.gif">  Докажите равенство   φ(<i>n</i>) = <i>n</i>(1 – ¹/_<i>p</i>₁)...(1 – ¹/_{<i>p_s</i>}).

  а) пользуясь мультипликативностью функции Эйлера;

  б) пользуясь формулой включения-исключения.

Определение функции Эйлера φ(<i>n</i>) см. в задаче <a href="https://mirolimp.ru/tasks/160758">160758</a>.

Пусть числа <i>x</i>₁, <i>x</i>₂, ..., <i>x_r</i> образуют приведённую систему вычетов по модулю <i>m</i>.

Для каких <i>a</i> и <i>b</i> числа  <i>y_j = ax_j + b</i>  (<i>j</i> = 1, ..., <i>r</i>)  также образуют приведённую систему вычетов по модулю <i>m</i>?

Пусть <i>p</i> – простое число и  <i>p</i> > 5.  Докажите, что если разрешимо сравнение  <i>x</i>⁴ + <i>x</i>³ + <i>x</i>² + <i>x</i> + 1 ≡ 0 (mod <i>p</i>),  то   <i>p</i> ≡ 1 (mod 5).

Выведите отсюда бесконечность множества простых чисел вида  5<i>n</i> + 1.

Пусть <i>p</i> – простое число и  <i>p</i> > 3.

  а) Докажите, что если разрешимо сравнение  <i>x</i>² + <i>x</i> + 1 ≡ 0 (mod <i>p</i>),  то  <i>p</i> ≡ 1 (mod 6).

  б) Выведите отсюда бесконечность множества простых чисел вида  6<i>k</i> + 1.

Пользуясь результатом задачи <a href="https://mirolimp.ru/tasks/160579">160579</a>, найдите остатки, которые при простом <i>p</i> дают числа <i>F_p</i> и <i>F</i>_<i>p</i>+1 при делении на <i>p</i>.

Докажите, что если  <i>x</i>² + 1  (<i>x</i> – целое) делится на нечётное простое <i>p</i>, то  <i>p</i> = 4<i>k</i> + 1.

Докажите, что при любом простом  <i>p</i>   <img align="middle" src="/storage/problem-media/60750/problem_60750_img_2.gif">   делится на <i>p</i>.