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

Докажите, что для любого нечётного натурального числа <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>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> равных частей. Сколько можно составить различных замкнутых ломаных из <i>n равных</i> звеньев с вершинами в этих точках?

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

Докажите, что если  <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.

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

<i>Функция Эйлера</i> φ(<i>n</i>) определяется как количество чисел от 1 до <i>n</i>, взаимно простых с <i>n</i>. Найдите   a) φ(17);   б) φ(<i>p</i>);   в) φ(<i>p</i>²);   г) φ(<i>p</i>^α).

При помощи задачи <a href="https://mirolimp.ru/tasks/160752">160752</a> докажите, что существует бесконечно много простых чисел вида  <i>p</i> = 4<i>k</i> + 1.

Пусть <i>n</i> – натуральное число, не кратное 17. Докажите, что либо  <i>n</i>⁸ + 1,  либо  <i>n</i>⁸ – 1  делится на 17.

Докажите, что если <i>p</i> – простое число,  <i>p</i> ≠ 2, 5,  то длина периода разложения ¹/_<i>p</i> в десятичную дробь делит  <i>p</i> – 1.

Приведите пример, когда длина периода совпадает с  <i>p</i> – 1.

Будет ли простым число  257¹⁰⁹² + 1092?