Олимпиадные задачи из источника «параграф 4. Теоремы Ферма и Эйлера» для 8-9 класса - сложность 2-3 с решениями

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

Найдите все целые числа <i>a</i>, для которых число  <i>a</i>¹⁰ + 1  делится на 10.

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

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

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

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

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

Докажите, что если  <i>n</i> > 2,  то число всех правильных несократимых дробей со знаменателем <i>n</i> чётно.

Пусть τ(<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.

Пусть  <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>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>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>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; некоторое натуральное число?