Олимпиадные задачи из источника «параграф 4. Теоремы Ферма и Эйлера» для 7-9 класса - сложность 3-4 с решениями
параграф 4. Теоремы Ферма и Эйлера
НазадДокажите, что при любом нечётном <i>n</i> число 2<sup><i>n</i>!</sup> – 1 делится на <i>n</i>.
Докажите, что 7<sup>51</sup> – 1 делится на 103.
<b>Теорема Эйлера</b>. Пусть <i>m</i> ≥ 1 и (<i>a, m</i>) = 1. Тогда <i>a</i><sup>φ(<i>m</i>)</sup> ≡ 1 (mod <i>m</i>).
Докажите теорему Эйлера с помощью малой теоремы Ферма
а) в случае, когда <i>m = p<sup>n</sup></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 – <sup>1</sup>/<sub><i>p</i><sub>1</sub></sub>)...(1 – <sup>1</sup>/<sub><i>p<sub>s</sub></i></sub>).
а) пользуясь мультипликативностью функции Эйлера;
б) пользуясь формулой включения-исключения.
Определение функции Эйлера φ(<i>n</i>) см. в задаче <a href="https://mirolimp.ru/tasks/160758">160758</a>.
Пусть числа <i>x</i><sub>1</sub>, <i>x</i><sub>2</sub>, ..., <i>x<sub>r</sub></i> образуют приведённую систему вычетов по модулю <i>m</i>.
Для каких <i>a</i> и <i>b</i> числа <i>y<sub>j</sub> = ax<sub>j</sub> + b</i> (<i>j</i> = 1, ..., <i>r</i>) также образуют приведённую систему вычетов по модулю <i>m</i>?
Пусть <i>p</i> – простое число и <i>p</i> > 5. Докажите, что если разрешимо сравнение <i>x</i><sup>4</sup> + <i>x</i><sup>3</sup> + <i>x</i><sup>2</sup> + <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<sub>p</sub></i> и <i>F</i><sub><i>p</i>+1</sub> при делении на <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>.
С помощью индукции докажите следующее утверждение, эквивалентное малой теореме Ферма: если <i>p</i> – простое число, то для любого натурального <i>a</i> справедливо сравнение <i>a<sup>p</sup> ≡ a</i> (mod <i>p</i>).
Дано простое <i>p</i> и целое <i>a</i>, не делящееся на <i>p</i>. Пусть <i>k</i> – наименьшее натуральное число, при котором <i>a<sup>k</sup></i> ≡ 1 (mod <i>p</i>). Докажите, что <i>p</i> – 1 делится на <i>k</i>.