1. Целые числа
1. Делимость целых чисел. Свойства делимости. Теорема о делении с остатком
Определение. Пусть — целые числа. Говорят, что число
делится на
, если
можно представить в виде
, где
— целое число.
Иначе: — делитель
.
Обозначение: .
Свойства делимости
Пусть — целые числа, число
— простое.
1. Если в равенстве два числа делятся на
, то и третье число делится на
.
2. Если , то
.
3. Если и
, то
.
4. Если , то либо
, либо
.
Пример. Доказать, что если и
, то и
Решение.
откуда
и
Теорема. Всякое целое представляется единственным способом с помощью целого
равенством вида
, где
— целые,
. Число
называется частным,
— остатком от деления
на
.
Пример. Может ли число делиться на , а при делении на
давать в остатке
?
Решение. Числа, делящиеся на , имеют вид
,
, а при делении на
дающие в остатке
, — вид
,
. Рассмотрим все остатки при делении на Н.О.К.
. Делятся на
числа вида
, и ни одно из них при делении на
не дает в остатке
.
2. Сравнения и их свойства
Определение. Пусть и
— целые числа,
— натуральное число. Говорят, что
сравнимо с
по модулю
, если при делении на
они дают одинаковые остатки.
Обозначение: или
.
Пример. .
Теорема. по модулю
тогда и только тогда, когда
.
Свойства сравнений
1) (рефлексивность).
2) (симметричность).
3) (транзитивность).
4) ,
,
.
5) , Н.О.Д.
.
Упражнение. Какие остатки могут давать квадраты целых чисел при делении на ; кубы целых чисел при делении на
, на
?
Пример. Доказать, что если — простое число, то
Решение. По условию, . Тогда так как
остается доказать, что второй множитель делится на .
Поскольку , имеем
Отсюда получаем требуемое.
3. Теоремы Ферма и Эйлера
Теорема (Ферма). Если простое и
не делится на
, то
Теорема (Эйлер). Для любых натуральных взаимно простых и
выполняется
Следствие. Пусть ,
, Н.О.Д.
. Тогда
.
Пример. Найти .
Решение.
Пример. Доказать, что если
Решение.
То же для и
.
— числа попарно взаимно простые.
4. Примеры решения нелинейных уравнений
1. Решить уравнение в натуральных числах
Решение. Разложим левую часть уравнения на множители:
Представим в виде произведения двух натуральных множителей всеми возможными способами:
Приравниваем один из множителей слева одному, другой — другому. Решаем полученные системы. Возможно упрощение: здесь числа и
одинаковой четности.
Ответ. .
Замечание. При поиске целых решений рассматривали бы также разложения и т.д.
2. Решить в целых числах уравнение
Решение. На множители не раскладывается. Выразим :
При целом также
будет целым, если
, что возможно при
.
Ответ.
3. Доказать, что уравнение
Решение. Сравнения по модулю :
, что невозможно, так как квадраты целых чисел при делении на
могут давать остатки либо
, либо
.
5. Теорема Вильсона
Теорема. Число — простое тогда и только тогда, когда выполняется сравнение
Пример (теорема Лейбница). Доказать, что число простое тогда и только тогда, когда
Решение. По теореме Вильсона — простое
Тогда имеем
Задачи.
1. Найдите остаток от деления
а) на
; б)
на
.
2. Найдите
а) последнюю цифру числа ;
б) две последние цифры числа .
3. Докажите (без калькулятора), что следующие числа составные:
а) (всего 2004 единицы);
б) .
в) .
4. Докажите, что в последовательности нет квадратов целых чисел.
5. а) При каких натуральных значениях число
делится на
?
б) Докажите, что число делится на
тогда и только тогда, когда число
делится на
.
6. Решите уравнения в целых числах:
а) ; б)
.
7. Пусть — целое число,
. Делится ли
?
8. На 44 деревьях, расположенных по окружности, сидели 44 веселых чижа (на каждом дереве — по чижу). Время от времени два чижа одновременно перелетают на соседние деревья в разных направлениях (один — по часовой стрелке, а другой — против). Докажите, что чижи не смогут собраться на одном дереве.
9. Докажите, что уравнение
не имеет целых решений.
10. Пусть число — простое,
. Докажите, что
если же — простое,
, докажите, что
11. Натуральное число . Докажите, что сумма всех натуральных делителей числа
(включая
и
) также делится на
.
12. Найдите остаток от деления целой части числа на
.
13. Найдите все решения уравнения
в натуральных числах .
1 Zhumakhan:
Лучше чем учетеля
[Ответить]
Елизавета Александровна Калинина Reply:
Ноябрь 15th, 2015 at 19:32
Спасибо
[Ответить]