Конспект занятия "Введение в теорию чисел"

Курс подготовки к олимпиадам. Введение в теорию чисел

Занятие 1

Тема: Введение в теорию чисел

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

Конспект урока

Начнем с задачи:

Найти последнюю цифру числа

Очевидно, что решение «в лоб», т.е. возведение числа 7 в 2025-ую степень, слишком громоздко, и на такое решение просто не хватит времени. Чтобы решать такие задачи, математики придумали особый язык – теорию чисел. На этом уроке мы начнем с основ.

Определение 1.

Ц елое число а делится на целое число , если существует такое целое число k, что выполняется равенство .

Обозначение: .

Пример:

, т.к. существует целое число 4 такое, что

Важно знать свойства делимости:

Определение 2.

Делителем числа а называется число, на которое число а делится без остатка.

Пример:

12 – делитель числа 36, т.к.

Определение 3.

П усть a и b — целые числа, Если существует целое число k, такое что , то говорят, что число a кратно числу b.

Пример:

36 – кратное числу 12, т.к. существует целое число 3, такое, что выполняется равенство

При решении олимпиадных задач полезно помнить признаки делимости:

Более подробно о признаках делимости на 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 20, 25, 30, 50, 90 вы можете узнать из видеоурока: https://www.youtube.com/watch?v=tbsIyT_Ibjc

Определение 4.

Н атуральное число называется простым, если оно имеет ровно два делителя: число 1 и само себя.

Пример:
2, 3, 5, 7, 11, 13, 17…

Существует таблица простых чисел (простые числа хотя бы в первых двух-трех строках полезно запомнить):

(далее на сайте)

З амечание 1. Число 2 – единственное четное простое число.

Определение 5.

Н атуральное число называется составным, если оно имеет более двух делителей.

Пример:

4 (делители 1, 2, 4),

6 (делители 1, 2, 3, 6),

12 (делители 1, 2, 3, 4, 6, 12)…

Замечание 2. Число 1 не является ни простым, ни составным.

З амечание 3. Каждое составное число можно разложить на произведение простых чисел.

Пример:

Определение 6.

Н ОД (наибольший общий делитель) — это самое большое число, на которое два и более данных чисел делятся без остатка.

Пример: найдем НОД (12,18)

Делители числа 12: 1, 2, 3,4, 6,12;

Делители числа 18: 1, 2 , 3, 6, 9, 18.

Наибольший общий делитель: 6.

НОД для чисел 18 и 12 равен 6, так как это самое большое число, на которое делятся числа 18 и 12 без остатка.

Для отыскание наибольшего общего делителя используется алгоритм Евклида.

Алгоритм Евклида

Идея: наибольший общий делитель (НОД) двух чисел — это то же самое, что НОД меньшего числа и остатка от деления большего числа на меньшее.

Пошагово:

1. Берём два числа, скажем, и , где

2. Делим большее число на меньшее и смотрим, какой остаток получился.

3. Если остаток равен 0, то . Всё готово.

4. Если остаток не 0, то теперь ищем НОД для пары и остатка .

5. Повторяем процесс, пока остаток не станет 0.

6. Последнее число, на которое делилось без остатка — это и есть НОД.

Пример. Найти НОД чисел 48 и 18:

1. Делим 48 на 18. Получаем остаток 12.

   • Теперь ищем НОД чисел 18 и 12.

2. Делим 18 на 12. Остаток 6.

   • Теперь ищем НОД чисел 12 и 6.

3. Делим 12 на 6. Остаток 0.

   • Остаток 0 → последний делитель (6) — это НОД.

П очему так работает?

Каждый раз, когда мы делим большее число на меньшее, мы «сокращаем» задачу, но общий делитель не теряется. В итоге остаётся самое большое число, которое делит оба числа.

Определение 7.

Н ОК (наименьшее общее кратное) — это наименьшее число, которое делится без остатка на каждое из заданных чисел.

Пример. Найдем НОК(12, 18)

Кратные 12: 12,24,36,48…

Кратные 18: 18,36,54…

Наименьшее общее кратное — 36.

НОК для чисел 12 и 18 равно 36, поскольку 36 — это наименьшее число, которое делятся и 12, и 15.

Как связаны между собой наименьшее общее кратное и наибольший общий делитель двух чисел?

Связь НОД и НОК

Есть формула:

Все, о чем мы вели речь до сих пор, изучается в курсе математики 6 класса. Рассмотрим еще несколько теорем, которые могут быть полезны.

Согласно замечанию 3 любое составное число можно разложить на произведение простых множителей. Интересным является следующий факт:

Т еорема (малая теорема Ферма).

Любое число, которое не делится на простое p, при возведении в степень p−1 даёт остаток 1 при делении на p.

Пример:

Число 343 не делится на простое число 3. Возведем число 343 в степень (3-1). Получим: . Разделим теперь число 117649 на число 3:

117649 3

9 39216

27

27

6

6

4

3

19

18

1(остаток)

Остаток от деления степени (3-1) числа 343 на число 3 равен 1.

Эта теорема может быть использована, например, при проверке того, является ли данное число составным (рассмотрим задачу на одном из следующих занятий).

Еще одна полезная теорема:

Теорема (о делении с остатком).

Д ля любого целого числа a и любого натурального числа b существует единственная пара чисел q и r, таких что

где

a — делимое,

b — делитель,

q — частное,

r — остаток.

Пример:

1) 23 : 5

где

2) 100 : 7

где 2

3) 126 : 6

где 0

Замечание 4. При делении натурального числа на число n можно получить остатки:

0, 1, 2, …,

Пример:

При делении на 5 возможны остатки: 0, 1, 2, 3, 4 (всего пять)

З амечание 5. Теорема о делении с остатком работает и для отрицательных чисел: для любого целого 𝑎 и :

То есть остаток всегда неотрицательный и меньше 𝑛, даже если делимое отрицательное.

Пример:

Остаток

Замечание 6. Предложение «При делении числа 17 на число 12 получим остаток 5» можно записать на математическом языке:

Нужно иметь в виду, что в математическом сообществе эта запись имеет строгое определение:

Определение 8.

П усть число m натуральное число, больше единицы. Целые числа a и b называют сравнимыми по модулю m, если при делении на m они дают одинаковые остатки:

Тогда запись следует читать и понимать так: числа 17 и 5 сравнимы по модулю 12 (т.е. дают равные остатки при делении на 12):

и

Свойства сравнений:

Если , , то выполняются равенства:

Теперь можно решить задачу урока. Напомним ее условие:

Найти последнюю цифру числа

Решение.

I способ

Последняя цифра числа — это остаток при делении на 10. Значит, нам нужно найти

Начинаем считать степени числа 7 по модулю 10:

Замечаем цикл: 7, 9, 3, 1, 7, 9, 3, 1, 7…

Длина цикла – 4.

Найдем остаток от деления числа 2025 на 4:

Остаток равен 1. Значит, соответствует первой позиции в цикле.

Т.е.

Тогда 7 – последняя цифра числа.

Заметим, что возводить число 7 в четвертую или пятую степень – довольно трудоемкая операция, которая требует времени. Можно рассмотреть еще один способ.

II способ

Чтобы найти последнюю цифру числа, достаточно найти остаток от деления этого числа на 10. Приступим:

Т.е. при делении числа 7 на 10 получаем остаток, равный 7: .

И при делении числа -3 на 10 получим остаток 7:

Тогда по свойству 4:

Посчитаем остатки:

Цикл тот же: 7, 9, 3, 1 (или при отрицательных представителях: −3, 9, 3, 1 с длиной 4. Тогда разделим 2025 на 4: , т.е. степень эквивалента первому элементу цикла:

Тогда последняя цифра – это цифра 7.

Ответ: 7

Задачи для самостоятельного решения

1. Олимпиада «Покори Воробьевы горы!», 2020 г.

Найти последнюю цифру числа

1. Олимпиада Эйлера, РЭ, 2022 г.

Сумма остатков от деления трех последовательных чисел на 2022 – простое число. Докажите, что одно из чисел делится на 2022.

1. Олимпиада «Надежда энергетики», 2020 г.

Какой цифрой оканчивается значение суммы

Легась Е.В., учитель математики МОУ ТОТЛ