Исследование на тему "ПРИМЕНЕНИЕ МАЛОЙ ТЕОРЕМЫ ФЕРМА И ТЕОРЕМЫ ЭЙЛЕРА К РЕШЕНИЮ ЗАДАЧ НА ОСТАТКИ СТЕПЕНЕЙ"

XIX ГОРОДСКАЯ НАУЧНАЯ КОНФЕРЕНЦИЯ

МОЛОДЫХ ИССЛЕДОВАТЕЛЕЙ «ШАГ В БУДУЩЕЕ»

Направление: МАТЕМАТИКА

ПРИМЕНЕНИЕ МАЛОЙ ТЕОРЕМЫ ФЕРМА И ТЕОРЕМЫ ЭЙЛЕРА К РЕШЕНИЮ ЗАДАЧ НА ОСТАТКИ СТЕПЕНЕЙ

Автор: ЗАРАНКОВИЧ АНТОН,

МБОУ СОШ № 46 с УИОП, Сургут, 9 класс

Руководитель: КУЗНЕЦОВА ЕЛЕНА БОРИСОВНА,

учитель математики высшей категории МБОУ СОШ № 46 с УИОП

Сургут, 2017 год

АННОТАЦИЯ

Теоремы Эйлера и Ферма являются основой всей теории сравнений и находят широкое применение как в теоретических исследованиях, так и в арифметических приложениях. Предлагаемый вниманию читателя практический проект посвящен применению малой теоремы Ферма и теоремы Эйлера к решению задач на остатки степеней.

В работе представлен новый вид задач теории чисел на сравнимость по модулю и деление с остатком, что позволит познакомиться с доступным способом решения и откроет возможность решать олимпиадные задачи теории чисел.

ОГЛАВЛЕНИЕ

1. Введение……………………………………………….............................................................3

2. Основная часть……………………………………….……..................…........................……5

   2.1. Малая теорема Ферма и теорема Эйлера.......................................................................... 5

   2.2. Применение малой теоремы Ферма и теоремы Эйлера к решению задач на остатки ...........степеней...............................................................................................................................6

3. Заключение………………………………………….......................……...................……….11

4. Список литературы………………………………………….......................….......................12

1.     ВВЕДЕНИЕ

Предлагаемый вниманию читателя практический проект посвящен применению малой теоремы Ферма и теоремы Эйлера к решению задач на остатки степеней. Я обратил внимание на название этих именных теорем и понял, что не знаю о них практически ничего. Что не удивительно, так как   эти серьезные теоремы из теории чисел не входят в школьный курс математики. При этом хочу их изучить и научиться использовать данные теоремы для решения задач повышенного уровня сложности.

Объект исследования: Сравнимость по модулю в теории чисел.

Предмет исследования: Применение малой теоремы Ферма и теоремы Эйлера к решению задач на остатки степеней.

Проблема: отсутствие знаний по теме «Применение малой теоремы Ферма и теоремы Эйлера к решению задач на остатки степеней».

Причины:

• в школьной программе не рассматриваются малая теорема Ферма и теорема Эйлера;

• недостаточно задач на сравнимость по модулю.

Основной целью работы является изучение сравнимости по модулю в теории чисел и применение малой теоремы Ферма и теоремы Эйлера к решению задач на остатки степеней.

Исходя из цели, необходимо решить такие задачи как:

1.Изучить данную тему, используя математическую литературу, Интернет и другие источники;

2. Рассмотреть доказательство малой теоремы Ферма и теоремы Эйлера;

3. Подобрать различные задания на применение этих теорем и решить их;

4. Представить необходимый материал в докладе и презентации.

Методы решения проблемы:

·                    Анализ и разностороннее изучение математического материала;

·                    Метод обобщения;

·                    Аналогия;

·                    Числовой эксперимент.

Новизна проекта.

Данная тема открыла мне новый вид задач, позволила познакомиться с доступным способом решения задач на сравнимость по модулю с применением малой теоремы Ферма и теоремы Эйлера, открыла возможность решать олимпиадные задачи теории чисел.

2. ОСНОВНАЯ ЧАСТЬ

    2.1. Малая теорема Ферма и теорема Эйлера.

Пьер Ферма сформулировал утверждение теоремы к 1640 году. "Меня озарило ярким светом", - писал Ферма, впервые сообщая о своем открытии в письме. Интересно, что данная фраза была написана по-итальянски, хотя в письме все было написано на французском языке. Письмо от 18 октября 1640-го года Пьера Ферма к французскому математику Бернару Френиклю содержало следующее положение:

"Каждое простое число измеряет одну из степеней любой прогрессии минус 1, для которой показатель степени является делителем данного простого числа минус 1; и после того, как была найдена первая степень, удовлетворяющая этому свойству, все числа, имеющие показатели степени, кратные показателю первой, удовлетворяют тому же свойству".

Малую теорему Ферма удобно записывать в терминах теории сравнений, введенной К. Гауссом в знаменитых «Арифметических исследованиях»: Говорят, что два числа, а и b сравнимы по модулю t, и пишут: а ≡ b (mоd t),

если разность (а – b) делится на t.

Малая теорема Ферма (чаще ее просто называют теоремой Ферма) на языке сравнений формулируется так: «Если р простое число и а не делится на р, то а^{р –1} ≡1 (mod p)».

Доказательство. Поскольку а не делится на р, то а = kр + r₁, 0 <r₁ < р  и   а ≡ r₁ (mod р), отсюда 2а ≡2r₁ ≡ r₂ (mоd р).

Далее найдем 3а = r₃(mоd р) ..., (р - 1) а ≡ r_p -1 (mod р). Перемножив все сравнения, получим 1 * 2 *...* (р - 1) а_р - 1 ≡ r₁ … r_p - 1 (mod р). Так как все сомножители r₁ … r_p - 1 различные и заключены в пределах от 1 до р - 1, то их произведение равно (р - 1)! В левой части также стоит (р - 1)! Это число взаимно простое с р, поэтому обе части сравнения можно поделить на (р -1)! Теорема доказана.

В следующем столетии Эйлер обобщил эту теорему на случай произвольного модуля.

Теорема Эйлера: «Если а и m взаимно просты, то a^φ(m) ≡ 1(mod m).

Здесь φ(m) - функция, названная, по предложению Гаусса, функцией Эйлера. При m> 1 она равна количеству натуральных чисел, меньших m и взаимно простых с ним; при m = 1 ее полагают равной единице. Например, 

φ (6) = 2, так как взаимно простыми с числом 6 являются лишь два числа 1 и 5. Для вычисления значений φ(m) Эйлер вывел формулу:

, где р₁, р₂, ..., р_к - различные простые делители числа m.

Основное предназначение теорем Эйлера и Ферма - понижать показатель степени при ее вычислении по какому-нибудь модулю.

Итак, малая теорема Ферма утверждает, что для любого простого р и любого целого а имеет место сравнение а^Р ≡ a (mod p). Часто используется и такая формулировка: если р - простое число, и а - целое число, взаимно простое с р, то а^Р-1 ≡ l (mod p). Теорема Эйлера утверждает, что для любого натурального числа n и любого целого, а, взаимно простого с n, имеет место сравнение a^φ(n) ≡ I (mod n), где φ(n) - функция Эйлера.

2.2. Применение малой теоремы Ферма и теоремы Эйлера к решению задач на остатки степеней.

Теоремы Эйлера и Ферма являются основой всей теории сравнений и находят широкое применение как в теоретических исследованиях, так и в арифметических приложениях. Рассмотрим решение задач.

№1. Для начала определим закономерности и найдем последнюю цифру числа , n⋲N

a n	1	2	3	4	5	6	7	8	9	10
1	1	2	3	4	5	6	7	8	9	0
2	1	4	9	6	5	6	9	4	1	0
3	1	8	7	4	5	6	3	2	9	0
4	1	6	1	6	5	6	1	6	1	0
5	1	2	3	4	5	6	7	8	9	0
6	1	4	9	6	5	6	9	4	1	0
7	1	8	7	4	5	6	3	2	9	0
8	1	6	1	6	5	6	1	6	1	0
		4	4	2			4	4	2

Вывод:

• при возведении a = 1, 5, 6, 10 в любую степень последняя цифра не меняется;
• при возведении a = 2, 3, 7, 8 – при изменении показателя степени

последняя цифра повторяется с периодичностью 4;

• при возведении a = 4, 9 – при изменении показателя степени

последняя цифра повторяется с периодичностью 2.

№2. Используя результаты предыдущей задачи, найдем последнюю цифру числа:

777⁷⁷⁸ – последняя цифра основания 7, смотрим столбец «7» (последняя цифра периодически повторяется, длина периода 4), показатель степени 778 при делении на 4 (длина периода) дает остаток 2, то есть 778 = 4⋅194 + 2⇒ последняя цифра числа 777⁷⁷⁸ находится в строке «2», то есть 9.

Ответ: 777⁷⁷⁸ ≡ 9(mod 10)

№ 3. Записать и проверить малую теорему Ферма для p=3 и a=4.

Решение. По малой теореме Ферма a ^p-1-1 делится на p. Подставляя заданные значения a и p, получим:

4 ^3-1-1 делится на 3

Действительно, 4² -1=16-1=15, что в свою очередь кратно 3. Из этого следует, что для данных значений теорема верна.

№ 4.  Найти остаток от деления 3¹⁰²  на 101.

Решение: Число 101 является простым числом. Согласно малой теореме Ферма имеет место следующее сравнение:

3¹⁰⁰  ≡1 (mod 101)

Домножим правую и левую часть этого сравнения на 9, получим:

9*3¹⁰⁰  ≡ с 9*1 (mod 101)

3² *3¹⁰⁰ ≡9 (mod 101)

3¹⁰² ≡9 (mod 101)

Ответ: r (3¹⁰²)₁₀₁ = 9

№ 5. Найти остаток от деления 5¹⁴ на 7.

Решение: по теореме Эйлера φ (7) = 7(1 - 1/7) = 6, 5⁶ ≡ 1 (mod 7), 14= 6⋅2+2 ⇒ 5¹⁴ = 5^6⋅2+2 = (5⁶)²⋅5² ≡ 25 (mod 7), 25 = 7 ⋅ 3 + 4 ⇒ 25≡4 (mod 7)

Ответ: r (5¹⁴)₇ = 4

№ 6. Найти остаток от деления 24¹⁶ на 7.

Решение: 24 = 7⋅3 + 3⇒ 24≡ 3(mod 7)

по теореме Эйлера φ (7) = 7(1 - 1/7) = 6, 3⁶ ≡ 1 (mod 7), 16= 6⋅2+4 ⇒ 3¹⁶ = 3^6⋅2+4 = (3⁶)²⋅3⁴ ≡ 81 (mod 7), 81 = 7 ⋅ 11 + 4 ⇒ 81≡4 (mod 7)

Ответ: r (24¹⁶)₇ = 4

№ 7. Найти остаток от деления 5¹⁰⁰ на 11.

Решение: по теореме Эйлера φ (11) = 11(1 - 1/11) = 10, 5¹⁰ ≡ 1 (mod 11),

100 = 10⋅ 10 + 0 ⇒ 5¹⁰⁰ = (5¹⁰)¹⁰ ≡ 1 (mod 11)

Ответ: r (5¹⁰⁰)₁₁ = 1

№ 8. Найти остаток от деления 17³³² на 10.

Решение: 17 = 10⋅1 + 7⇒ 17≡ 7(mod 10)

по теореме Эйлера φ (10) = 10(1 - 1/2) (1 – 1/5) = 4, 7⁴ ≡ 1 (mod 10), 332= 83⋅ 4 + 0 ⇒ 17³³² = (7⁴)⁸³≡ 1 (mod 10)

Ответ: r (17³³²)₁₀ = 1

№ 9. Найти остаток от деления 23²⁷⁷  на 9.

Решение: 23 = 9 ⋅2 + 5⇒ 23≡ 5(mod 9)

по теореме Эйлера φ (9) = 9 (1 - 1/3) = 6, 5⁶ ≡ 1 (mod 9), 277 = 6 ⋅ 49 + 1 ⇒ 5²⁷⁷ = (5⁶)⁴⁹ ⋅ 5 ≡ 5 (mod 9)

Ответ: r (23²⁷⁷)₉ = 5

№10. Вычислить последние две цифры числа 1988¹⁹⁸⁸.

Решение: При делении этого числа на 100 образуется остаток из последних двух цифр числа, т. е. 1988¹⁹⁸⁸≡x (mod 100), где . Так как , то .  поэтому теорему Эйлера Применить пока что нельзя. Положим , имеем , откуда . Применяем теорему Эйлера: , , , . Тогда получаем . Так как , то , . Следовательно, , т.е. последние две цифры числа  являются 9 и 6.

№ 11. Найдите однозначное число n, девятая степень которого оканчивается цифрой 7.

Решение: Так как девятая степень числа n оканчивается цифрой 7, то остаток от деления n⁹ на 10 должен быть равен 7 => возможно сравнение:

n⁹ ≡ 7 (mod 10)

Так как (7, 10) =1, то (n, 10)=1. Используя теорему Эйлера, получим n^φ(10)≡1(mod 10). n⁴≡1(mod 10) или n⁸≡1(mod 10). Тогда сравнение примет вид: n≡7(mod 10) => n=7, т.к. по условию n - однозначное число.

№ 12. p - простое число. Сколько существует способов раскрасить вершины правильного p-угольника в a цветов? (Раскраски, которые можно совместить поворотом, считаются одинаковыми)

Решение: Забудем временно про совмещение раскрасок поворотами. Тогда p вершин можно раскрасить a^p способами. Среди этих раскрасок есть a одноцветных. Каждая из оставшихся совмещается с p раскрасками (считая исходную). Поэтому различных не одноцветных раскрасок в p раз меньше:

.

Ответ:  способов.

3. ЗАКЛЮЧЕНИЕ

Работа над проектом была познавательной:

− в процессе работы я узнал именные теоремы Ферма и Эйлера;

− научился пользоваться научной литературой по теории чисел;

− теперь я знаю, какие действия нужно выполнять при решении задач на сравнимость чисел по модулю и на остатки степеней.

В работе представлены решения десяти задач на остатки степеней. Задачи подобраны из разных источников: сборников задач и интернет-сайтов.

4. Список литературы:

1. Алфутова Н. Б., Устинов А. В - Алгебра и теория чисел - МЦНМО - 2002 год - 264 с.

2. Деза Е. И., Котова Л. В. Сборник задач по теории чисел (112 задач с подробными решениями): Учебное пособие. - М.: Книжный дом «ЛИБРОКОМ», 2012. - 224 с.

3. Совертков П.И. Сургутские олимпиады по математике: Учебное пособие. – Сургут: МОУ ДО «ЦРО», 2008. - 148 с.

Интернет-ресурсы:

1.https://ru.wikipedia.org/

2. http://ru.solverbook.com/spravochnik/teoremy/teorema-ferma/