Основы теории чисел

Основы теории чисел

Конспект лекций

Натуральные числа

- множество натуральных чисел, используемых для счета или перечисления.

Система аксиом Пеано

1. Единица - натуральное число, которое не следует ни за каким числом.

2. Для любого натурального числа существует единственное число которое непосредственно следует за .

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

4. Если некоторое множество содержит и вместе с каждым натуральным числом содержит непосредственно следующее за ним число то (аксиома индукции).

Операции на множестве

Сложение

Умножение

Свойства операций:

Ассоциативность: Доказательство.

Пусть

Тогда Пусть Докажем, что Действительно,

Коммутативность: Доказательство.

Пусть Тогда Пусть Докажем, что Действительно,

Пусть теперь Тогда Пусть Докажем, что Действительно, Следовательно, по аксиоме 4, т. е.

Дистрибутивность: Доказательство.

Пусть

Тогда

Пусть Докажем, что Действительно, Следовательно, по аксиоме 4,

Сравнение в

Определение: такое, что

Утв.1 Для любых двух натуральных чисел имеет место одно из трех соотношений:

Утв.2 Если то:

Утв.3 Если то

Утв.4 Для любых натуральных чисел Если то

Утв.5 Для любых натуральных чисел существует натуральное число такое, что

Вычитание:

Свойства вычитания: Если то

Если то

Некоторые особенности натуральных чисел:

1. Ни для какого натурального числа не существует натурального числа такого, что

2. Любое непустое подмножество натуральных чисел содержит наименьший элемент.

3. Если ограниченное сверху подмножество натуральных чисел, то в существует наибольший элемент.

НЕ нашли? Не то? Что вы ищете?

Принцип математической индукции

Если некоторое утверждение справедливо для некоторых начальных и из условия, что справедливо для следует (удается доказать), что справедливо для то это утверждение справедливо для любого

Пример 1. Докажите следующие утверждения методом математической индукции:

1) Справедливо тожество

2) Справедливо тожество

3) Справедливо тожество

4) Выражение делится на

5) В любой момент времени число людей на земле, сделавших нечетное число рукопожатий, число четное;

6) Любое целое число рублей можно без сдать без сдачи только монетами по и рублей;

7) Если произведение положительных чисел то

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

9) При любом справедливо неравенство

Делимость натуральных чисел

Деление: делится на такое, что

Свойства операций:

1. Если делятся на то делится на

2. Если и делятся на то делится на

3. Если и делятся на то делится на

4. Если делится на то делится на

5. Если делятся на а не делятся на то то не делится на

6. Если или делятся на то делится на

7. Если делится на то делится на и делится на

Теорема о делении с остатком Для любых натуральных чисел существуют и единственные положительные числа такие, что причем

Доказательство. Пусть Рассмотрим следующий алгоритм:

.

.

и т. д.

Если то сделаем еще одно вычитание

Если то сделаем еще одно вычитание

Продолжаем процесс вычитания до тех пор, пока остаток не будет меньше числа

Существует число такое, что

Сложим все строки данного алгоритма и получим требуемое выражение, где

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

Предположим, что существует два представления

и Вычтем одно выражение из другого причем Последнее равенство в целых числах возможно только в случае так как при □

Приведенный в теореме 1 алгоритм отражает хорошо известную всем операцию деления натуральных чисел "столбиком".

Следствие 1. Всякое натуральное число можно представить в виде: или или

Следствие 2. Если подряд стоящих натуральных чисел, то одно из них делится на

Следствие 3. Если два последовательных четных числа, то одно из них делится на

Определение. Натуральное число называется простым, если оно не имеет делителей, кроме единицы и самого себя.

Следствие 4. Всякое простое число имеет вид или

Действительно, всякое число можно представить в виде однако все числа этого ряда, кроме точно являются составными. □

Следствие 5. Если простое число, то делится на

Действительно, три подряд стоящих натуральных числа, причем, четные, а нечетное простое. Следовательно, одно из четных чисел и делится на 4, а одно – еще и на □

Пример 2. Справедливы следующие утверждения:

1.Квадрат нечетного числа при делении на 8 дает остаток

2. Ни при каком натуральном n число n2 +1 не делится на 3.

Доказательство1. Всякое нечетное число можно представить в виде или Возведем каждое из этих чисел в квадрат и получим требуемое утверждение.

Доказательство 2. Всякое натуральное число можно представить в виде Тогда выражение будет равно одному из выражений которые не делятся на

Пример 3. Решите в целых числах уравнение

Решение. Если решение то делится на и из уравнения следует, что делится на Следовательно при решений нет. Тогда и Переберем все числа от до Ответ:

Признаки делимости на

Определение. Десятичным представлением натурального числа называется представление числа в виде

где

Сокращенная запись

Утв.6 Пусть десятичное представление числа числа Тогда:

1. Число делится на когда цифра - четная;

2. Число делится на когда двузначное число делится на

3. Число делится на когда либо

4. Число делится на когда

5. Число делится на когда двузначное число - делится на

6. Число делится на когда сумма цифр числа делится на

7. Число делится на когда сумма цифр числа делится на

8. Число делится на когда сумма цифр числа с чередующимися знаками делится на

Доказательство. Доказательство признаков 1)-5) легко получается из десятичной записи числа Докажем 6) и 7). Действительно,

Отсюда следует, что если делится (или то сумма цифр числа тоже делится на

Докажем 11). Пусть делится на Представим число в виде

Так как все слагаемые суммы делятся на то сумма тоже делится на □

Определение. Число сравнимо с числом по модулю Сокращенная запись

В терминах сравнений признаки делимости можно записать следующим образом:

Признак делимости на и

Утв.7 Пусть десятичное представление числа числа Число делится на когда разность между числом без трех последних знаков и числом, составленным из трех последних знаков, делится на

Доказательство. Представим в виде Так как число делится на и то делится на и □

Пример 4. Пусть Тогда делится на и, следовательно, число делится на Пусть Тогда делится на Тогда число делится на

Простые числа

Решето Эратосфена

(Простой алгоритм получения всех простые чисел)

Алгоритм. Выписываем все числа от 1 до 100 и вычеркиваем сначала все четные. Затем, из оставшихся вычеркиваем делящиеся на 3, 5, 7 и т. д. В результате останутся только простые числа.

Теорема Евклида. Число простых чисел бесконечно.

Доказательство "от противного". Пусть число простых чисел конечно - Рассмотрим число Вопрос: число - простое или составное?

Если - составное число, то оно делится на некоторое простое число и, следовательно, единица делится на это простое число. Противоречие.

Если - простое число, то оно больше любого простого числа а все простые числа мы выписали и пронумеровали. Опять противоречие. □

Утв.8 Если число является составным, то оно имеет простой делитель такой, что

Доказательство. Если - наименьший простой делитель составного числа то

Следствие. Чтобы определить является ли число простым, надо определить имеет ли оно простые делители

Пример5. Пусть Чтобы проверить, является ли число простым, надо проверить, делится ли на простые числа Ответ: число простое.

Пример 6. Разложите на простые сомножители числа и

Решение. Применим признаки делимости. Легко заметить, что делится на Число не подходит ни под один из признаков делимости, поэтому не делится на Для поисков дальнейшего разложения проверим все простые числа от до Делим число на простые числа получим, что

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

Утв. 9 Если то число составное.

Доказательство.. Таким образом, если у числа есть хотя бы один нечетный множитель, то число составное. □

Генераторы простых чисел

Гипотеза: Все числа вида простые.

При - это простые числа для вручную и с помощью компьютера доказано, что все числа составные.

Например, (Эйлер)

Гипотеза: Все числа вида простые.

При это так, а делится на 17.

Гипотеза: Все числа вида простые.

При это так, а

Гипотеза: Все числа вида простые. При это так, а

Только Гольдбах и Эйлер поставила точку в этих изысканиях: ими доказано, что никакой многочлен с целыми коэффициентами не может принимать только простые значения.

С другой стороны, теорема Лежандра: Если простые числа, то среди арифметической прогрессии содержится бесконечно много простых чисел.

Теорема. (Метод Ферма выделения множителей) Целое нечетное число не является простым существуют натуральные числа и такие, что Доказательство.

□

Пример7. Разложить на простые сомножители числа

Или

Пример 8. Разложить на множители число Это число делится на 3 Далее, по методу выделения множителей,

Пример 9. При каких целых число простое?

Заметим, что Так как простое, то либо либо Ответ:

Утв. 10 Натуральное число имеет нечетное число делителей когда оно является полным квадратом?

Доказательство. Если делитель числа то имеет две различные пары делителей и а при обе пары будут равны.

Пример 10. Числа имеют ровно по 99 делителей. Может ли число иметь ровно 100 делителей?

Ответ: нет. Действительно по предыдущему свойству и - полные квадраты, а их произведение – нет.

Пример 11. Числа простые. Найти Ответ:

Пример 12. Числа простые. Найти Ответ:

Для решения примеров 9-10 надо рассмотреть представление числа через остатки от деления на

НОД

Определение. Число называется наибольшим общим делителем чисел и если оно делит и и является наибольшим из таких чисел.

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

Определение. Числа и называются взаимно простыми, если

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

Пусть целые числа,

Разделим на с остатком, а затем на каждом шаге будем делить частное на остаток:

и т. д.

Существует такое, что т. е. на каком-то шаге разделится на без остатка.

Утв. 11 Последний ненулевой остаток в алгоритме Евклида является наибольшим общим делителем чисел и т. е.

Доказательство. Пусть наибольший общий делитель Докажем, что:

1) является общим делителем и

2) делит

Отсюда будет следовать, что (Почему?)

1) Будем подниматься по алгоритму снизу вверх. Из последней строчки следует, что делит из предпоследней, что - делит и т. д. Из алгоритма видно, что делит все остатки. Тогда из первых двух строк следует, что делит и

2) Будем опускаться по алгоритму сверху вниз. Если то из первой строки следует, что делит Из второй строки следует, что делит и т. д. Получается, что делит все остатки в алгоритме Евклида, а значит делит □

Следствие1 . Существую числа и такие, что

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

Алгоритм нахождения чисел показан на примерах 11-14.

Следствие 2. Числа и взаимно простые существуют числа и такие, что

Действительно, если то из следствия 1 следует, что существую числа и такие, что

Обратно: если существую числа и такие, что то делит и, следовательно, равен

Следствие 3.

Например:

Пример13. Найти и выражение через и

Пример14. Найти и выражение через и

Пример15. Найти и выражение через и

Пример16. Найти и выражение через и

Диофантовы уравнения

Определение. Уравнение вида с целыми коэффициентами относительно переменных называются диофантовыми уравнениями.

Теорема Уравнение с целыми коэффициентами имеет целые решения когда делит

Доказательство. Если уравнение имеет целые решения, то и, следовательно, чисел делит

Укажем конструктивный алгоритм нахождения решений. Найдем Разделим обе части уравнения на и получим уравнение причем Тогда существую числа и такие, что Домножим обе части уравнения на и получим Легко заметить, что являются решениями исходного уравнения □

Следствие. Если пара решение исходного уравнения, то любая пара при является решением исходного уравнения.

Доказательство осуществляется непосредственной подстановкой значений и в уравнение

Пример 17. Решить уравнение

Решение. Из алгоритма Евклида находим числа и такие, что т. е. Умножим обе части равенства на и получим равенство т. е. Общее решение будет иметь вид

Пример 18. Доказать, что следующие уравнения не имеют решений:

Действительно, коэффициенты этих уравнений не удовлетворяют условию теоремы.

Пример 19. Решить уравнение

Решение. Разделим обе части уравнения на и получим новое уравнение причем Из алгоритма Евклида находим числа и такие, что т. е. Умножим обе части равенства на и получим равенство т. е. Общее решение будет иметь вид

Пример 20. Решить в натуральных числах уравнение

Решение. Пусть Следовательно, уравнение имеет вид Ответ: Решений нет.

Основная теорема арифметики

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

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

Лемма 1. Всякое натуральное число либо равно, либо простое, либо - произведение простых.

Доказательство по индукции. Для лемма верна. Предположим, что лемма верна для любого и докажем, что она верна для

Возможны два варианта:

1) простое и лемма верна,

2) составное причем из предположения индукции, что и либо простые, либо произведения простых. □

Лемма 2. Если простое число делит произведение то делит либо делит

Доказательство. Пусть не делит Тогда существуют числа и такие, что Умножим обе части равенства на и получим Отсюда следует, что делится на □

Лемма 3. Если простое число делит произведение чисел то делит одно из чисел

Доказательство индукцией по числу сомножителей.

При лемма верна. Пусть делит произведение сомножителей Докажем, что делит произведение Пусть Тогда делит произведение и, следовательно, делит либо - Если делит то все доказано, а если делит то по предположению делит одно из чисел □

Лемма 4. Если простое число делит произведение простых чисел то равно одному из чисел

Доказательство. По лемме 3, если делит произведение чисел то делит одно из чисел Но если делит одно из простых чисел то □

Доказательство теоремы следует из лемм 1-4.

Докажем единственность индукцией по числу сомножителей. Пусть два разложения одного числа. Если или то единственность следует из лемм 3-4. Предположим, что единственность выполняется для Если делит произведение то одно из чисел Сократим обе части равенства на и получим равенство, в котором □

Следствие 1. Пусть Тогда равен произведению всех общих простых сомножителей с наименьшими степенями.

Следствие 2. Пусть Тогда равно произведению всех различных простых сомножителей с наибольшими степенями.

Следствие 3.

Пример 21. Пусть

Тогда

Утв.12 Если произведение двух взаимно простых сомножителей является квадратом, то каждый сомножитель является квадратом.

Доказательство. Пусть Так как и взаимно простые, то в их разложении участвуют различные простые сомножители. Тогда в произведении которое является квадратом, все простые сомножители различные и имеют четные показатели. □

Утв.13 Пусть Тогда сумма всех делителей числа равна

Действительно, общий делитель числа имеет вид а сумма делителей равна

Далее по формуле суммы членов геометрической прогрессии получаем исходное выражение. □

Например,

Утв.14 Пусть Тогда число различных делителей числа равно

Действительно, число равно числу сомножителей в формуле □

Пример 22. (Демо 2010)

1) Найти все числа, которые делятся на 42 и имеют ровно 42 различных делителя.

2) Найти все числа, которые делятся на 10 и имеют ровно 15 различных делителей.

Решение.

1) Так как то исходное число делится на и по Утв.13

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

Ответ:

2) Так как то исходное число делится на и по Утв.13

Следовательно, может иметь только два различных простых сомножителя и степени которых равны или Ответ:

Пример 23.(Окружная олимпиада 2006) Найти все натуральные числа удовлетворяющие условию

Решение 1. Если то число имеет столько нулей, сколько их у числа а число имеет по крайней мере на один нуль больше Следовательно,

Выпишем все возможные значения факториалов:

Решение 2. Докажем, что

Действительно, если значное число, то Ответ:

Пример 24. Найти все пары натуральных чисел, наименьшее общее кратное которых равно а наибольший общий делитель равен

Решение. Пусть исходные числа. Так как простое число, а то по следствиям основной теоремы арифметики только число входит в разложение обоих чисел, а для чисел и возможны варианты:

Ответ:

Пример 25. Решите в целых числах уравнение

Решение. Из уравнения следует, что делится на т. е. Подставим это значение в уравнение, получим и сократим на 2: Откуда следует, что делится на 2, т. е. Тогда уравнение имеет вид Так как не делится на то делится на , т. е. и Отсюда Ответ:

Пример 24. Решите в целых числах уравнение

Решение. Из уравнения следует, что справа стоит нечетное число, следовательно, либо В противном случае оба числа и будут четными. Пусть Тогда Отсюда следует, что иначе будет делится на Следовательно, Рассмотрим все эти случаи: Ответ: решений нет.