Книги по разным темам Pages:     | 1 |   ...   | 7 | 8 | 9 | 10 | 11 |   ...   | 16 |

(е) если нечетное число представимо в виде суммы двух квадратов, (б) если a b (mod m) и c d (mod m), то ac bd (mod m);

то оно имеет вид 4k + 1 (k ).

(в) если P [x] и a b (mod m), то P(a) P(b) (mod m); Задача. (а) Найдите последнюю цифру числа 1414.

(г) если p Ч простое, то (a + b)p ap + bp (mod p) (p, a, b );

(б) Возведя некоторое натуральное число n в 13-ю степень получивыполняется ли это при составных p ли число 21 982 145 917 308 330 487 013 369. Чему равно n (д) (Малая теорема Ферма) ap a (mod p) для любого простого Задача. Придумайте и докажите признаки делимости на p.

(а) и ; (б) ; (в) ; (г).

Задача. Докажите, что Задача.

(а) a b (mod m) a и b имеют одинаковые остатки от деления (а) Докажите, что уравнение x12 - 57x7 + 91 = 0 не имеет целочисна m;

енных решений.

(б) максимальное число попарно не сравнимых по модулю m целых (б) Пусть P(x) [x], и оба числа P(0) и P(1) нечетны. Докажите, чисел равно m;

что тогда уравнение P(x) = 0 не имеет целочисленных решений.

(в) максимальное число попарно не сравнимых по модулю w гаус Признаком делимости на n мы здесь называем такую последовательность целых совых чисел равно N(w);

.

..

чисел ki (|ki| n/2), что anan-1Еa0. n (ankn + an-1kn-1 + Е + a0k0) n. Например, для..

(г) среди любых целых чисел найдутся два числа, разность котопризнака делимости на 3 все ki равны 1. Конечно, есть много разных других признаков рых делится на, несколько чисел, сумма которых делится на ; делимости.

(в) Докажите, что уравнение 7x2 + 2 = y3 не имеет целочисленных решений;

Геом-. Целочисленные решетки (г) Докажите, что уравнение x5 + y5 + z5 + t5 = 5 не имеет целочис( апреля г.) ленных решений.

Определение. Пусть a K (K Ч кольцо). Тогда a называется де- Задача. (а) Докажите, что нельзя нарисовать правильный трелителем нуля, если a = 0 и найдется такое b K, b = 0, что a b = 0. угольник с вершинами в узлах клетчатой бумаги.

Например, в и нет делителей нуля. (б) При каких n существует правильный n-угольник с вершинами в узлах клетчатой бумаги Задача. Докажите, что делителей нуля нет и в (а) [x], [x];

(б) [[x]]; в) [i]. Определение. Целочисленной решеткой называется множество (в) При каких m в m есть делители нуля точек плоскости с целыми координатами. Будем обозначать такую ре(г) Верна ли теорема о степени произведения многочленов в 6[x] шетку через L.

def Научимся решать простейшие сравнения вида ax b (mod m), т. е. линейОпределим сумму точек: (a, b) + (c, d) = (a + c, b + d). Аналогично ные уравнения в m, или, что то же самое, находить целочисленные решения определяется умножение точки на целое число.

уравнения ax - my = b.

инейным преобразованием целочисленной решетки называется Задача. Пусть d = НОД(a, m). Докажите, что такое отображение A: L L, что A(P + Q) = A(P) + A(Q) для любых (а) сравнение ax b (mod m) имеет решения тогда и только тогда, P, Q L.

.

.

когда b d;

.

Задача. Докажите следующие свойства линейных преобразова.

.

(б) если b d, то сравнение имеет ровно d решений в m; причем.

ний.

def если x0 Ч одно из них, то все другие решения Ч это (а) A(0) = 0 (где 0 = (0, 0) Ч начало координат), A(-P) = -A(P).

(б) A(n P) = n A(P), n.

x0 + m, x0 + 2m, Е, x0 + (d - 1)m, (в) Всякое линейное преобразование A однозначно задается точкагде m = m/d.

ми A(1, 0) и A(0, 1).

(в) Придумайте алгоритм для нахождения хотя бы одного реше(г) Всякое линейное преобразование задается формулой ния x0.

A(x, y) = (ax + by, cx + dy), где a, b, c, d.

(г) Найдите все решения в уравнения 29x - 13y = 2.

(д) Проведите полное исследование уравнения (д) Такое преобразование инъективно тогда и только тогда, когда ad - bc = 0.

a1 x1 + a2x2 + Е + an xn b (mod m).

(е) Такое преобразование сюръективно тогда и только тогда, когда ad - bc = 1.

Задача. (а) Дан параллелограмм POQR с вершинами в L. Докажите, что его площадь равна |ad - bc|, где P = (a, b), Q = (c, d). (O Ч начало координат.) (б) Пусть отрезок с концами в узлах решетки не содержит других ее вершин. Докажите, что он является стороной некоторого параллелограмма площади 1 c вершинами в узлах решетки.

(в) На клетчатой бумаге нарисован параллелограмм с вершинами в узлах сетки так, что внутри него и на сторонах нет других узлов сетки.

Докажите, что площадь параллелограмма равна.

Задача (формула Пика). Докажите, что площадь S многоугольm ника с вершинами в узлах сетки равна S = n + - 1, где n Ч число узлов сетки внутри многоугольника, m Ч число узлов сетки на контуре ная вершина сетки, в которой нет дерева Ч центр сада. Радиус каждого многоугольника. дерева равен 1 миллиметру. Докажите, что вид из центра сада полностью заслонен.

Определение. Взаимно однозначные линейные преобразования L называются линейными автоморфизмами. Множество тех линейных ав- Определение. Пусть m Ч свободное от квадратов натуральное томорфизмов целочисленной решетки, для которых ad - bc = 1, обозна- число. Обозначим через [ m] множество пар (a, b) целых чисел (или чается через Sl2( ). множество точек на координатной плоскости с целыми координатами), которые умножаются по правилу: (a, b) (c, d) = (ac + mbd, ad + bc).

Задача. Проверьте, что: (а) A, B Sl2( ) A B Sl2( );

(a, b) естественно обозначить через a + b m.

(б) A Sl2( ) A-1 Sl2( ).

Нормой в [ m] называется величина N(a + b m) = a2 - mb2.

Эти две задачи показывают, что Sl2( ) является группой.

Задача. Пусть z, w [ m]. Докажите, что (в) Сформулируйте и докажите: линейные автоморфизмы L сохра(а) N(zw) = N(z)N(w);

няют площади фигур.

(б) N(z) = 0 z = 0; N(z) = 1 z обратимо;

(г) Сохраняют ли они ориентацию (в) если Задача. (а) Стороны прямоугольника равны m и n и проходят по линиям сетки. Сколько клеток пересечет диагональ a1 a2 (mod N), b1 b2 (mod N), (б) Даны две точки на L: (a1, b1) и (a2, b2). Когда одну из них можно.

.

то (a1 + b1 m) (a2 + b2 m), где N = N(a2 + b2 m).

.

перевести в другую линейным автоморфизмом Задача. (а) Нарисуйте на плоскости множество Mc точек, задаБудем рассматривать такие параллелограммы с вершинами в узлах ваемое уравнением x2 - my2 = c.

сетки, что одна из их вершин есть точка (0, 0).

(б) Докажите, что Mc Ч гипербола.

(в) Докажите, что любой такой параллелограмм (в) Стороны параллелограмма параллельны прямым x = m y, его площади 1 можно перевести с помощью преобравершины лежат на Mc M. Найдите его площадь.

-c зования из Sl2( ) в любой другой такой параллелоЗадача (уравнение Пелля). Докажите, что:

грамм площади.

(а) для некоторого c неравенство |x2 - my2| < c имеет бесконечно (г) Докажите, что если площадь параллелограммного решений;

ма равна, то его можно перевести в один из двух Рис.

Hint. Впишите в Mc M параллелограмм как в (в) и примените лемму параллелограммов, изображенных на рис., а пере- -c Минковского.

вести их друг в друга нельзя.

(б) для некоторого c существует бесконечно много чисел с нормой c;

Задача. Расклассифицируйте с точностью до Sl2( )-эквивалент (в) уравнение N(z) = 1 в [ m ] имеет решения, отличные от 1;

ности параллелограммы площади (а) ; (б).

(г) существует такое z0 = a0 + b0 m [ m ], что все элементы с Задача. На клетчатую бумагу посажена клякса площади S. Докаn нормой 1 имеют вид z0, n.

жите, что При условиях a0, b0 > 0 число z0 называют основным решением урав(а) если S < 1, то можно параллельно перенести кляксу так, чтобы нения x2 - my2 = 1.

она не закрывала узлов сетки;

Решите уравнения: (д) x2 - 5y2 = 1, (е) x2 - 41 y2 = 1.

(б) если S целое, то можно перенести кляксу так, чтобы она закрывала не менее S узлов сетки, а можно Ч что не более S узлов;

(в) (лемма Минковского) если клякса выпукла и симметрична относительно начала координат, а S > 4, то клякса закрывает еще хотя бы один узел сетки (кроме начала координат).

Задача. В круглом саду радиуса 1 километр деревья рассажены в вершинах квадратной сетки со стороной квадратов 1 метр. Единствен- То есть m не делится ни на одно число вида d2 при d > 1.

(б) длина периода разложения 1/p в периодическую дробь делит p - 1 (p = 5);

Ар-. Арифметика остатков (в) любой простой делитель числа 2p - 1 имеет вид 2kp + 1.

( марта г.) Задача. Существует ли натуральная степень тройки, оканчивающаяся на 0001 Задача. Пусть a p (p Ч простое). Отметим p - 1 точку на плоскости, и расставим на них элементы p (кроме нуля). Соединим стрел- Задача * (числа Карлмайкла). Докажите, что для составного чиской точку x с точкой a x. Мы получим диаграмму умножения на a. ла 561 справедливо утверждение малой теоремы Ферма:

(а) Нарисуйте такую диаграмму для p = 13, a = 5; p = 7, a = 3.

НОД(a, 561) = 1 a560 1 (mod 561).

Докажите, что:

Числа, для которых верно утверждение малой теоремы Ферма, на(б) в каждую вершину диаграммы ведет ровно одна стрелка;

зываются числами Карлмайкла.

(в) диаграмма умножения представляет собой объединение непересекающихся циклов;

Задача *. Пусть p > 2 Ч простое.

(г) все циклы имеют одинаковую длину;

(а) Разложите многочлен xp-1 - 1 на множители в p.

(д) найдется такой элемент a p, что диаграмма умножения на a.

.

(б) Докажите, что если (p - 1) d, то сравнение xd 1 (mod p) име.

состоит ровно из одного цикла.

ет ровно d решений в p.

(е) Какие из предыдущих пунктов будут верны для диаграммы умно(в) Докажите, что в p найдется такой элемент a, что ordp(a) = p - 1.

жения на a в Zm при произвольном m (Заметим также, что мультипликативная группа любого конечного поЗадача. (а) При каких m все ненулевые элементы m обратимы ля циклична.) (б) Опишите множество Ч обратимых элементов из m при проm Определение. Корень ( ) n-й степени из называется перизвольном m.

вообразным, если k = 1 ни при каком k, 1 k < n.

(в) Сформулируйте и докажите свойства диаграмм умножения для Задача. (а) Докажите, что всякий корень n-й степени из есть. Нарисуйте диаграмму умножения для m = 30, a = 7.

m натуральная степень первообразного корня.

(г) Докажите, что числитель дроби 1 + 1/2 + 1/3 + Е + 1/(p - 1) (б) Найдите все первообразные корни из степени,,, и.

делится на p (p Ч простое).

(в) Докажите, что число первообразных корней n-й степени из Задача (следствия из свойств диаграмм). Пусть a Ч целое чисравно (n).

о. Докажите, что.

Задача *. Найдите сумму k-х степеней всех корней n-й степени.

(а) если p Ч простое, то a p n : an 1 (mod p);

.

из.

Определение. Минимальное натуральное n для которого Задача (квадратные уравнения).

an 1 (mod p), (а) Сколько квадратов в 4, 5, 6 называется порядком a в p и обозначается через ordp(a). ч Пусть p Ч простое.

.

.

(б) an 1 (mod p) n ordp(a) (n ).

.

(б) Докажите, что уравнение x2 = a имеет не более двух решений (в) (теорема Эйлера) НОД(a, m) = 1 a(m) 1 (mod m), где в p; при каких a решение единственно (m) Ч количество чисел от 1 до |m|, взаимно простых с m. (Как вы, (в) Сколько квадратов в p наверное, уже догадались, (m) называется функцией Эйлера.) (г) Докажите, что уравнение x2 + ax + b = 0 разрешимо в p тогда Задача (следствия теорем ФермаЧЭйлера). Пусть p > 2 Ч прои только тогда, когда a2 - 4b Ч полный квадрат в p. Напишите форстое. Докажите, что мулу для нахождения корней.

(а) существует число вида 111Е11, кратное p (p = 5);

Задача. Пусть p > 2 Ч простое. Докажите теоремы:

Кольцо, в котором все ненулевые элементы обратимы, называется полем. (а) (Вильсона) (p - 1)! -1 (mod p) p Ч простое;

(б) (Лейбница) (p - 2)! 1 (mod p) p Ч простое;

(в) (Клемента) числа p и p + 2 являются простыми-близнецами Десятый класс тогда и только тогда, когда 4((p - 1)! + 1) + p 0 (mod p2 + 2p).

До сих пор неизвестно, бесконечно ли много существует простых-близнецов: (3, 5), (5, 7), (11, 13), (17, 19), (29, 31), (41, 43)Е Ар-. Избранные задачи по теории чисел Задача (квадратичные вычеты). Пусть p > 2 Ч простое. Дока( сентября г.) жите, что в p Задача. Найдите все пары таких взаимно простых чисел a и b, что (а) произведение двух квадратов Ч квадрат;

a + b (б) произведение квадрата и неквадрата Ч неквадрат;

=.

a2 - ab + b(в) произведение двух неквадратов Ч квадрат;

Задача. Дано множество из n натуральных чисел. За одну опера(г) при a = 0 (a p) элемент ap-1/2 равен либо 1, либо -1;

цию можно любые два числа из этого множества заменить на их НОД p - (д) каждое из уравнений xp-1/2 = 1 и xp-1/2 = -1 имеет по реи НОК.

(а) Докажите, что можно провести только конечное число операций.

шений;

(б) Докажите, что окончательный результат не зависит от порядка (е) a = 0 является квадратом тогда и только тогда, когда ap-1/2 = 1.

действий.

(ж) При каких простых p число 2 является квадратом в p Задача. Решите уравнения в целых числах:

1 1 (а) 3m + 7 = 2n; (б) 3 2m + 1 = n2; (в) + + = 1.

a b c Задача. Какую наименьшую сумму цифр может иметь число вида 3n2 + n + 1 при натуральном n Задача. На столе лежат книги, которые надо упаковать. Если их связать в одинаковые пачки по, по или по книг, то каждый раз останется одна лишняя книга, а если связать по книг в пачку, то лишних книг не останется. Какое наименьшее количество книг может быть на столе Задача (китайская теорема об остатках). Натуральные числа m1, Е, mn попарно взаимно просты, m = m1 Е mn.

(а) Докажите, что сравнение x b (mod m) эквивалентно системе x b (mod m1),................

x b (mod mn).

(б) Докажите, что система x b1 (mod m1),.................

x bn (mod mn).

Это теперь твое новое имя! Ч сказал Заяц. Ч Я всю ночь думал: как бы тебя назвать И наконец придумал: МЕДВЕЖОНОККОТОРЫЙДРУЖИТСЗАЙЦЕМ! имеет, и притом единственное, решение в m при любых b1, Е, bn.

Фактически мы доказали, что m m m Е m. где 1, Е, (n) Ч все первообразные корни из 1 степени n.

= 1 2 n (в) Придумайте явную формулу для решения предыдущей системы (а) Вычислите n(x) для первых 12 значений n.

при b1 = 1, b2 = b3 = Е = bn = 0. (б) Докажите, что многочлен n(x) имеет целые коэффициенты. Каков его свободный член Задача (больное войско). Генерал хочет построить для парада (в) Докажите равенство xn - 1 = d(x).

своих солдат в одинаковые квадратные каре. Но некоторые из солдат d|n (от 1 до 37) находятся в лазарете, и генерал не знает, сколько именно.

(г) Выведите из этого равенства формулу для n(x).

Докажите, что у генерала может быть такое количество солдат, что он, (д) Докажите, что многочлены n(x) неприводимы над.

Pages:     | 1 |   ...   | 7 | 8 | 9 | 10 | 11 |   ...   | 16 |    Книги по разным темам