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

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

Докажите, что  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>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>тождество Гаусса</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>p</i> вида  4<i>k</i> + 1  числа <i>x</i> = ± (2<i>k</i>)!  являются решениями сравнения  <i>x</i>² + 1 ≡ 0 (mod <i>p</i>).

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

Пусть для простого числа  <i>p</i> > 2  и целого <i>a</i>, не кратного <i>p</i>, выполнено сравнение  <i>x</i>² ≡ <i>a</i> (mod <i>p</i>).  Докажите, что  <i>a</i>^{(<i>p</i>–1)/2} ≡ 1 (mod <i>p</i>).

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

Пусть <i>p</i> – простое число,  <i>p</i> > 2.  Докажите, что любой простой делитель числа  2^<i>p</i> – 1  имеет вид  2<i>kp</i> + 1.

С помощью индукции докажите следующее утверждение, эквивалентное малой теореме Ферма: если <i>p</i> – простое число, то для любого натурального <i>a</i> справедливо сравнение  <i>a^p ≡ a</i> (mod <i>p</i>).

Дано простое <i>p</i> и целое <i>a</i>, не делящееся на <i>p</i>. Пусть <i>k</i> – наименьшее натуральное число, при котором  <i>a^k</i> ≡ 1 (mod <i>p</i>).  Докажите, что  <i>p</i> – 1  делится на <i>k</i>.