birmaga.ru
добавить свой файл

1

Занятие 19. Остатки и уравнения в целых числах

Теория. Остатки по модулю ведут себя так же как числа: их можно складывать, вычитать, умножать и возводить в степень. В частности, можно использовать остатки со знаком минус. Например, 9992007=(–1)2007=–1=999 (mod 1000). В частности, a2=(–a)2=(m–a)2 (mod m), поэтому остатков квадратов почти вдвое меньше m. Это уменьшает перебор.

Упр 1. Докажите, что а) 3099+61100 31.
b) 4399+2399 66

Задача 2. Докажите, что а) an+bn (a+b) если n – нечетно.
b) 1n+2n +… +(n1)n n если n – нечетно.

Задача 3. а) Найдите три натуральных числа, не представимых в виде суммы трех точных кубов.
b) Докажите, что таких чисел бесконечно много.

Теория. Если алгебраическое уравнение имеет решение в целых числах, то оно имеет решение в остатках по любому модулю. И наоборот: если уравнение НЕ имеет решений в остатках по какому-то модулю, то и в целых числах оно решения не имеет.
Упр 4. Докажите, что
а) Уравнение n2+1=0 (mod 3) не имеет решений.
b) Уравнение n2+1=3m не имеет решений в целых числах.

Задача 5. Докажите, что следующие уравнения не имеют решений в целых числах:

a) x2+y2=4z–1 b) 15x2–7y2=9 c) x2+y2+z2=8t–1


Теория. Если произведение нескольких выражений равно числу, то уравнение сводится к представлению числа в произведение соответствующего числа сомножителей и решению системы для каждого такого представления. Например, уравнение в целых числах (x+y)y=2 сводится к решению 4-х систем:



Раскладывать выражение на множители обычно приходится самим.

Задача 6. Решите следующие уравнения в целых числах:
a) x2y2=28 b) xy=x+y+3 c) x2y2= x+y+2

Задача 7. Комбинируя работу с остатками и разложение на множители, найдите все решения уравнения 3m+7=2n a) в натуральных числах b) в целых числах.

Задача 8. Решите уравнение 32m+1= n2 в целых числах.

Задача 9. 100 гирек веса 1, 2, …, 100 г разложили на две чаши весов так, что есть равновесие. Докажите, что можно убрать по две гирьки с каждой чаши так, что равновесие не нарушится.

Задача для долгоиграющего матбоя.


M22. Докажите, что (n–1)!+1n  n – простое.

Маткружок http://shap.homedns.org/sks/ryska/ 28 апреля 2007 г , Ведет Александр Шаповалов sasja@shap.homedns.org