Олимпиадные задачи из источника «параграф 4. Теоремы Ферма и Эйлера»

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

<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>.

Найдите все целые числа <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>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.

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

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

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

Докажите равенства:

  а)  φ(<i>m</i>) φ(<i>n</i>) = φ((<i>m, n</i>)) φ([<i>m, n</i>]);

  б)  φ(<i>mn</i>) φ((<i>m, n</i>)) = φ(<i>m</i>) φ(<i>n</i>) (<i>m, n</i>).

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

Окружность разделена <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>.