«Алфутова Н. Б. Устинов А. В. А45 Алгебра и теория чисел. Сборник задач для математических школ.— М.: МЦНМО, 2002.— 264 с. ISBN 5-94057-038-0 Настоящее пособие представляет собой сборник задач по математике, ...»

Алгебра и теория чисел для

математических школ

Н. Б. Алфутова, А. В. Устинов

September 3, 2003

УДК 51

ББК 21.1

А45

Алфутова Н. Б. Устинов А. В.

А45 Алгебра и теория чисел. Сборник задач для математических

школ.— М.: МЦНМО, 2002.— 264 с.

ISBN 5-94057-038-0

Настоящее пособие представляет собой сборник задач по математике,

предназначенный прежде всего для учеников старших классов с углубленным изучением математики, интересующихся точными науками. Он также будет полезен преподавателям математики и студентам, изучающим математику в высших учебных заведениях. Значительная часть материала может быть использована для подготовки к письменным и устным вступительным экзаменам в ВУЗы.

Основу сборника составляют задачи, к курсу алгебры, который в 1995— 2000 годах читался в школе-интернате им. А. Н. Колмогорова.

ББК 21. c Алфутова Н. Б., Устинов А. В., 2002.

c МЦНМО, 2002.

ISBN 5-94057-038- Предисловие Настоящее пособие представляет собой сборник задач по математике, предназначенный прежде всего для учеников старших классов, интересующихся точными науками. Он также будет полезен преподавателям математики и студентам, изучающим математику в высших учебных заведениях. Значительная часть материала может быть использована для подготовки к письменным и устным вступительным экзаменам в ВУЗы.

Основу сборника составляют задачи к курсу алгебры, который в 1995 – 2000 годах читался О. А. Чалых, Н. Б. Алфутовой и А. В. Устиновым. В приложении А приведена программа этого курса. Для того, чтобы сделать содержание книги более широким и целостным, авторы включили в нее дополнительный материал, собрав и упорядочив задачи из других источников.

Математические курсы, читаемые в школе-интернате им. А. Н. Колмогорова, традиционно содержат разделы, которые можно назвать смежными. Они находятся на стыке алгебры с комбинаторикой, геометрией, теорией чисел и математическим анализом. Поэтому некоторые задачи из книги имеют к алгебре лишь косвенное отношение. Эти задачи призваны подчеркнуть связь различных разделов математики и проиллюстрировать многообразие методов.

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

При подготовке пособия использовались различные учебники и монографии, сборники олимпиадных и конкурсных задач, большая часть упражнений была почерпнута из многочисленных публикаций журнала «Квант». В результате работы над книгой был создан своеобразный путеводитель, помещенный в приложение Б. В нем по каждой из тем задачника даны ссылки на соответствующие публикации. К сожалению, в настоящий момент не представляется возможным указать авторов всех задач, вошедших в книгу, и перечислить все оригинальные источники. Часть материала встречается сразу в нескольких сборниках. Со многими задачами авторы познакомились еще за время своего обучения в школе-интернате. Некоторые упражнения рождались в разговорах с коллегами по кафедре математики.

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

Авторы приносят глубокую благодарность педагогам и математикам, работавшим в разное время в ФМШ № 18 при МГУ (позднее в школе им. А. Н. Колмогорова), опыт которых отражен в этой книге.

Особенно авторы благодарят В. В. Вавилова, А. А. Егорова, И. Д. Кана, которые взяли на себя труд прочесть предварительные варианты книги, за их многочисленные добавления, исправления и полезные советы.

Отдельное спасибо О. А. Соловьеву за неизменную TEX-ническую поддержку.

Авторы будут благодарны читателям за отзывы, критические замечания, предложения и новые задачи. Их можно отправлять по электронной почте или по адресу: 117630, Москва, ул. акад. Челомея, д. 8 Б, ЦДО «Дистантное обучение».

Н. Б. Алфутова [email protected] А. В. Устинов [email protected] Обозначения В списке указаны страницы, на которых введены эти обозначения.

Обозначение Смысл Стр.

множество натуральных чисел N множество целых чисел Z множество рациональных чисел Q целая часть числа x (наибольшее целое, не превосx] ходящее x) {x} дробная часть числа x: {x} = x [x] факториал: n! = 1 · 2 ·... · n n!

{xn } последовательность x1, x2,..., xn,...

b|a b делит a.

. a кратно b a.b (ak... a0 )q (n) (n) (n) Метод математической индукции 1. Аксиома индукции Аксиома индукции. Если известно, что некоторое утверждение верно для 1, и из предположения, что утверждение верно для некоторого n, вытекает его справедливость для n+1, то это утверждение верно для всех натуральных чисел.

1.1. Деление с остатком. Докажите, что если a и b — целые числа и b = 0, то существует единственная пара чисел q и r таких, что 1.2. Позиционная система счисления. Докажите, что при целом q 2 каждое натуральное число n может быть единственным образом представлено в виде где 0 a0,..., ak < q. (См. также 3.125, 11.68.) Определение. Если ak, ak1,..., a1, a0 — цифры числа n в q-ичной системе счисления, то используется запись n = (ak ak1... a1 a0 )q.

Для записи числа в десятичной системе счисления используется также запись (ak ak1... a1 a0 )10 = ak ak1... a1 a0.

1.3. Пусть {an } = a0, a1,..., an,... — периодическая последовательность, то есть для некоторого натурального T Докажите, что среди всех периодов этой последовательности существует период наименьшей длины t, причем T делится на t без остатка.

1.4. Аксиомы индукции. Докажите, что аксиома индукции равносильна любому из следующих утверждений. (См. также 12.1.) 1) Всякое непустое подмножество натуральных чисел содержит наименьшее число.

2) Всякое конечное непустое подмножество натуральных чисел содержит наибольшее число.

3) Если некоторое множество натуральных чисел содержит 1 и вместе с каждым натуральным числом содержит следующее за ним, то оно содержит все натуральные числа.

4) Если известно, что некоторое утверждение верно для некоторого a, и из предположения, что утверждение верно для всех натуральных чисел k, таких, что a k < n вытекает его справедливость для n, то это утверждение верно для всех натуральных чисел k a.

5) (Обратная индукция.) Если известно, что некоторое утверждение верно для 1 и 2, и из предположения, что утверждение верно для некоторого n > 1, вытекает его справедливость для 2n и n 1, то это утверждение верно для всех натуральных чисел.

любом натуральном n число xn + также является целым. (См. такxn же 7.46.) 1.6. Даны натуральные числа x1,..., xn. Докажите, что число можно представить в виде суммы квадратов двух натуральных чисел.

(См. также 7.14.) 1.7. Числовая последовательность A1, A2,..., An,... определена равенствами 2. Тождества, неравенства и делимость Определение. Через n! (читается «n факториал») обозначается произведение всех натуральных чисел от 1 до n:

Для удобства считается, что 0! = 1.

В задачах 1.8 – 1.14 докажите тождества.

1.15. Факториальная система счисления. Докажите, что каждое натуральное число n может быть единственным образом представлено в виде 1.16. Числа a0, a1,..., an,... определены следующим образом:

Найдите и докажите формулу для этих чисел.

Определение. Пусть a — целое и b — натуральное числа. b называется делителем a, если существует целое число q такое, что a = bq.

В этом случае a называется кратным b, а q — частным от деления a на b.

Соотношение «b делит a» записывается в виде b | a или в виде a. b («a кратно b»). Причем эти записи всегда включают в себя предположение, что b = 0.

Если b не является делителем a, то будем писать b a.

Докажите, что в задачах 1.17 – 1.24, указанные соотношения выполняются для любого натурального n.

1.19. 25n+3 + 5n · 3n+2. 17.

1.25. Докажите, что для всех натуральных n число, записываемое 3n единицами, делится на 3n.

1.26*. Из чисел от 1 до 2n выбрано n+1 число. Докажите, что среди выбранных чисел найдутся два, одно из которых делится на другое.

(См. также 2.34.) 1.27. Решите уравнение В задачах 1.28 – 1.36 докажите справедливость неравенств для натуральных n.

числа.

1.37*. Неравенство между средним арифметическим и средним геометрическим. Докажите неравенство где x1,..., xn — положительные числа.

числа.

1.39. Для каких n выполняются неравенства:

1.40. Вычислите произведение 3. Индукция в геометрии и комбинаторике 1.41. Из квадрата клетчатой бумаги размером 16 16 вырезали одну клетку. Докажите, что полученную фигуру можно разрезать на «уголки» из трех клеток.

1.42. Ханойская башня I. Головоломка «Ханойская башня» представляет собой 8 дисков, нанизанных в порядке уменьшения размеров на один из трех колышков. Задача состоит в том, чтобы переместить всю башню на один из других колышков, перенося каждый раз только один диск и не помещая больший диск на меньший.

Докажите, что эта головоломка имеет решение. Какой способ решения головоломки будет оптимальным (по числу перемещений)? (См.

также 5.71.) 1.43. Ханойская башня II. Занумеруем колышки в задаче о Ханойской башне числами 1, 2, 3. Предположим, что требуется переместить диски с 1-го колышка на 3-й. Сколько понадобится перекладываний, если прямое перемещение диска с 1-го колышка на 3-й запрещено?

(Каждое перекладывание должно производится через 2-й колышек. Как и раньше, больший диск нельзя класть на меньший.) 1.44. Ханойская башня III. Сколько понадобится перекладываний, если в условии задачи 1.42 добавить дополнительное требование:

первый диск нельзя класть на второй колышек?

1.45. Докажите, что квадрат можно разрезать на n квадратов для любого n, начиная с шести.

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

1.47. Золотая цепочка. а) На постоялом дворе остановился путешественник, и хозяин согласился в качестве уплаты за проживание брать кольца золотой цепочки, которую тот носил на руке. Но при этом он поставил условие, чтобы оплата была ежедневной: каждый день должно быть отдано ровно на одно кольцо больше, чем в предыдущий день. Замкнутая в кольцо цепочка содержала 11 колец, а путешественник собирался прожить ровно 11 дней, поэтому он согласился. Какое наименьшее число колец он должен распилить, чтобы иметь возможность платить хозяину?

б) Из скольких колец должна состоять цепочка, чтобы путешественник мог прожить на постоялом дворе наибольшее число дней при условии, что он может распилить только n колец?

1.48. Банк имеет неограниченное количество трех- и пятирублевых купюр. Докажите, что он может выдать ими без сдачи любое число рублей, начиная с восьми. (См. также 3.72.) 1.49*. Гениальные математики. а) Каждому из двух гениальных математиков сообщили по натуральному числу, причем им известно, что эти числа отличаются на единицу. Они поочередно спрашивают друг друга: «Известно ли тебе мое число?» Докажите, что рано или поздно кто-то из них ответит «да». Сколько вопросов они зададут друг другу? (Математики предполагаются правдивыми и бессмертными.) б) Как изменится число заданных вопросов, если с самого начала известно, что данные числа не превосходят 1000?

1.50. На сколько частей делят плоскость n прямых «общего положения», то есть таких, что никакие две не параллельны и никакие три не проходят через одну точку?

1.51. На плоскости проведены n окружностей так, что любые две из них пересекаются в паре точек, и никакие три не проходят через одну точку. На сколько частей делят плоскость эти окружности?

1.52. На сколько частей делят пространство n плоскостей, проходящих через одну точку, если никакие три не имеют общей прямой?

1.53*. На сколько частей делят пространство n плоскостей «общего положения»? И что это за «общее положение»?

1.54. Плоскость поделена на области несколькими прямыми. Докажите, что эти области можно раскрасить в два цвета так, чтобы любые две соседние области были окрашены в разные цвета. (Соседними называются области, имеющие общий участок границы.) 1.55. Сумма углов n-угольника. Докажите, что произвольный n-угольник (не обязательно выпуклый) можно разрезать на треугольники непересекающимися диагоналями. Выведите отсюда, что сумма углов в произвольном n-угольнике равна (n 2).

1.56. Клетки шахматной доски 100 100 раскрашены в 4 цвета так, что в любом квадрате 2 2 все клетки разного цвета. Докажите, что угловые клетки раскрашены в разные цвета.

1.57. Имеется k ящиков. В некоторых из них лежат еще k ящиков.

В некоторых из последних лежат еще ящики (снова k штук) и т. д.

Сколько всего ящиков, если заполненных m?

1.58. Теорема Эйлера. Докажите, что для любого выпуклого многогранника имеет место соотношение где В — число его вершин, Р — число ребер, Г — число граней.

1.59*. Задача Сильвестра. На плоскости взяты несколько точек так, что на каждой прямой, соединяющей любые две из них, лежит по крайней мере еще одна точка. Докажите, что все точки лежат на одной прямой.

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

1.61. Сколько существует (невырожденных) треугольников периметра 100 с целыми длинами сторон?

1. Сложить или умножить?

2.1. а) В Стране Чудес есть три города A, B и C. Из города A в город B ведет 6 дорог, а из города B в город C — 4 дороги. Сколькими cпособами можно проехать от A до C?

б) В Стране Чудес построили еще один город D и несколько новых дорог — две из A в D и две из D в C. Сколькими способами можно теперь добраться из города A в город C?

Правило суммы. Если элемент a можно выбрать m способами, а элемент b (независимо от выбора элемента a) — n способами, то выбор «a или b» можно сделать m + n способами.

Правило произведения. Если элемент a можно выбрать m способами, а элемент b (независимо от выбора элемента a) — n способами, то выбор «a и b» можно сделать m · n способами.

2.2. Cколько существует различных семизначных телефонных номеров (cчитается, что номер начинаться с нуля не может)?

2.3. Номер автомашины состоит из трех букв русского алфавита (30 букв) и трех цифр. Сколько существует различных номеров автомашин?

2.4. В некоторой школе каждый школьник знаком с 32 школьницами, а каждая школьница — с 29 школьниками. Кого в школе больше:

школьников или школьниц и во сколько раз?

2.5. В языке одного древнего племени было 6 гласных и 8 согласных, причем при составлении слов гласные и согласные непременно чередовались. Сколько слов из девяти букв могло быть в этом языке?

2.6. Алфавит племени Мумбо-Юмбо состоит из трех букв. Словом является любая последовательность, состоящая не более чем из четырех букв. Сколько слов в языке племени Мумбо-Юмбо? (См. также 12.9.) 2.7. Сколько существует шестизначных чисел, делящихся на 5?

2.8. Сколько существует шестизначных чисел, в записи которых есть хотя бы одна четная цифра?

2.9. Сколько существует десятизначных чисел, в записи которых имеется хотя бы две одинаковые цифры?

2.10. Каких семизначных чисел больше: тех, в записи которых есть единица, или остальных?

2.11. Пассажир оставил вещи в автоматической камере хранения, а когда пришел получать вещи, выяснилось, что он забыл номер. Он только помнит, что в номере были числа 23 и 37. Чтобы открыть камеру, нужно правильно набрать пятизначный номер. Каково наименьшее количество номеров нужно перебрать, чтобы наверняка открыть камеру?

(Числа 23 и 37 можно увидеть и в числе 237.) 2.12. Сколько существует пятизначных чисел, которые одинаково читаются слева направо и справа налево (например, таких как 54345, 17071)?

2.13. Сколько существует девятизначных чисел, сумма цифр которых четна?

2.14. Сколькими способами можно разложить 7 монет различного достоинства по трем карманам?

2.15. Назовем натуральное число «симпатичным», если в его записи встречаются только нечетные цифры. Сколько существует четырехзначных «симпатичных» чисел?

2.16*. На двух клетках шахматной доски стоят черная и белая фишки. За один ход можно передвинуть любую из них на соседнюю по вертикали или по горизонтали клетку. (две фишки не могут стоять на одной клетке). Могут ли в результате таких ходов встретится все возможные варианты расположения этих двух фишек, причем ровно по одному разу?

2. Принцип Дирихле Принцип Дирихле (принцип ящиков). При любом распределении nk + 1 или более предметов по n ящикам в каком-нибудь ящике окажется не менее чем k + 1 предмет.

2.17. Докажите, что среди москвичей есть два человека с равным числом волос, если известно, что у любого человека на голове менее одного миллиона волос.

2.18. В мешке 70 шаров, отличающихся только цветом: 20 красных, 20 синих, 20 желтых, остальные — черные и белые. Какое наименьшее число шаров надо вынуть из мешка, не видя их, чтобы среди них было не менее 10-ти шаров одного цвета?

2.19. Некоторые точки из данного конечного множества соединены отрезками. Докажите, что найдутся две точки, из которых выходит поровну отрезков.

2.20. Имеется 2k + 1 карточек, занумерованных числами от 1 до 2k + 1. Какое наибольшее число карточек можно выбрать так, чтобы ни один из извлеченных номеров не был равен сумме двух других извлеченных номеров?

2.21. Какое наибольшее число королей можно поставить на шахматной доске так, чтобы никакие два из них не били друг друга?

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

2.23. На складе имеется по 200 сапог 41, 42 и 43 размеров, причем среди этих 600 сапог 300 левых и 300 правых. Докажите, что из них можно составить не менее 100 годных пар обуви.

2.24. Несколько футбольных команд проводят турнир в один круг.

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

2.25*. Дано 51 различных двузначных чисел (однозначные числа считаем двузначными с первой цифрой 0). Докажите, что из них можно выбрать 6 таких чисел, что никакие 2 из них не имеют одинаковых цифр ни в одном разряде.

2.26. Числа от 1 до 101 выписаны в произвольном порядке. Докажите, что из них можно вычеркнуть 90 чисел так, что оставшиеся 11 чисел будут следовать одно за другим в порядке возрастания или убывания.

2.27. Имеется 2000 точек. Какое максимальное число троек можно из них выбрать так, чтобы каждые две тройки имели ровно одну общую точку?

2.28. Даны 1002 различных числа, не превосходящих 2000. Докажите, что из них можно выбрать три таких числа, что сумма двух из них равна третьему. Останется ли это утверждение справедливым, если число 1002 заменить на 1001?

2.29*. Дана прямоугольная таблица, в каждой клетке которой написано вещественное число, причем в каждой строке таблицы числа расположены в порядке возрастания. Докажите, что если расположить числа в каждом столбце таблицы в порядке возрастания, то в строках полученной таблицы числа по-прежнему будут располагаться в порядке возрастания.

2.30. В волейбольном турнире команды играют друг с другом по одному матчу. За победу дается одно очко, за поражение — ноль. Известно, что в один из моментов турнира все команды имели разное количество очков. Сколько очков набрала в конце турнира предпоследняя команда и как она сыграла с победителем?

2.31. Бесконечная клетчатая доска раскрашена в три цвета (каждая клеточка — в один из цветов). Докажите, что найдутся четыре клеточки одного цвета, расположенные в вершинах прямоугольника со сторонами, параллельными стороне одной клеточки.

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

2.33. На плоскости даны 6 точек так, что никакие три из них не лежат на одной прямой. Каждая пара точек соединена отрезком синего или красного цвета. Докажите, что среди данных точек можно выбрать такие три, что все стороны образованного ими треугольника будут окрашены в один цвет. (См. также 5.36.) 2.34. Докажите утверждение задачи 1.26 при помощи принципа Дирихле.

3. Размещения, перестановки и сочетания Определение. Пусть M = {a1,..., an } — множество из n элементов. Наборы вида (ai1,..., aik ) будем называть k-размещениями. Два k-размещения считаются различными, если они отличаются друг от друга входящими в них элементами или порядком элементов.

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

Количества размещений без повторений и с повторениями обозначаются Ak и Ak соответственно.

2.35. Докажите равенства:

2.36. В пассажирском поезде 17 вагонов. Сколькими способами можно распределить по вагонам 17 проводников, если за каждым вагоном закрепляется один проводник?

Определение. Перестановками называются n-размещения без повторений элементов множества M = {a1,..., an }.

Количество перестановок множества из n элементов обозначается Pn.

2.37. Докажите равенство Pn = n!.

2.38. Сколько существует способов расставить 8 ладей на шахматной доске так, чтобы они не били друг друга?

2.39. Семнадцать девушек водят хоровод. Сколькими различными способами они могут встать в круг?

2.40. Сколько существует ожерелий, составленных из 17 различных бусинок?

2.41. Найдите сумму всех 7-значных чисел, которые можно получить всевозможными перестановками цифр 1,..., 7.

2.42. а) Сколькими способами 28 учеников могут выстроиться в очередь в столовую?

б) Как изменится это число, если Петю Иванова и Колю Васина нельзя ставить друг за другом?

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

2.44. Из класса, в котором учатся 28 человек, назначаются на дежурство в столовую 4 человека. Сколькими способами это можно сделать? Сколько существует способов набрать команду дежурных, в которую попадет ученик этого класса Коля Васин?

Определение. Пусть M = {a1,..., an } — множество из n элементов. k-сочетаниями называются наборы (ai1,..., aik ), в которых порядок считается несущественным. То есть два k-сочетания считаются различными, если они отличаются друг от друга входящими в них элементами, но не порядком элементов.

Аналогично размещениям сочетания бывают без повторений и с повторениями.

Количества сочетаний без повторений и с повторениями обозначаются Ck и Ck соответственно.

2.45. Из двух математиков и десяти экономистов надо составить комиссию из восьми человек. Сколькими способами можно составить комиссию, если в нее должен входить хотя бы один математик?

2.46. На плоскости дано n точек. Сколько имеется отрезков с концами в этих точках?

2.47. На плоскости проведено n прямых «общего положения». Найдите количество точек пересечения этих прямых. Сколько треугольников образуют эти прямые?

2.48. На двух параллельных прямых a и b выбраны точки A1, A2,..., Am и B1, B2,..., Bn соответственно. Сколько будет точек пересечения, если провести все отрезки вида Ai Bj (1 i m, 1 j n), при условии, что никакие три из этих отрезков в одной точке не пересекаются?

2.49*. Ключи от сейфа. Международная комиссия состоит из человек. Материалы комиссии хранятся в сейфе. Сколько замков должен иметь сейф, сколько ключей для них нужно изготовить и как их разделить между членами комиссии, чтобы доступ к сейфу был возможен тогда и только тогда, когда соберутся не менее 6 членов комиссии?

Рассмотрите задачу также в том случае, когда комиссия состоит из n человек, а сейф можно открыть при наличии m членов комиссии (m n).

2.50. У Нины 7 разных шоколадных конфет, у Коли 9 разных карамелек. Сколькими способами они могут обменяться друг с другом пятью конфетами?

2.51. Докажите равенства 2.52. Докажите, что биномиальный коэффициент Ck можно опреn делить как количество способов выбрать k-элементное подмножество в множестве из n элементов.

2.53. Бином Ньютона. Докажите справедливость формулы Числа Ck называются биномиальными коэффициентами, поскольку они возникают при возведении в степень бинома x + y.

2.54. Сколько рациональных слагаемых содержится в разложении 2.55*. Докажите, что для любого натурального a найдется такое натуральное n, что все числа n + 1, nn + 1, nn + 1,... делятся на a.

2.56. Сколько диагоналей имеет выпуклый:

а) 10-угольник; б) k-угольник (k > 3)?

2.57. В выпуклом n-угольнике проведены все диагонали. Они разбивают его на выпуклые многоугольники. Возьмем среди них многоугольник с самым большим числом сторон. Сколько сторон он может иметь?

2.58. Анаграммы. Анаграммой называется произвольное слово, полученное из данного слова перестановкой букв. Сколько анаграмм можно составить из слов: а) точка; б) прямая; в) перешеек; г) биссектриса; д) абракадабра; е) комбинаторика?

Некоторые комбинаторные задачи решаются, если условие удается переформулировать в терминах слов и анаграмм. Примером может служить следующая задача.

2.59. Шахматный город. Рассмотрим прямоугольную сетку квадратов размерами m n — шахматный город, состоящий из «кварталов», разделенных n 1 горизонтальными и m 1 вертикальными «улицами». Каково число различных кратчайших путей на этой сетке, ведущих из левого нижнего угла (точка (0; 0)) в правый верхний угол (точку (m; n))? (См. также 2.77.) 2.60. Имеется куб размером 10 10 10, состоящий из маленьких единичных кубиков. В центре O одного из угловых кубиков сидит кузнечик. Он может прыгать в центр кубика, имеющего общую грань с тем, в котором кузнечик находится в данный момент, причем так, чтобы расстояние до точки O увеличивалось. Сколькими способами кузнечик может допрыгать до кубика, противоположного исходному?

2.61. Параллелограмм пересекается двумя рядами прямых, параллельных его сторонам; каждый ряд состоит из m прямых. Сколько параллелограммов можно выделить в образовавшейся сетке?

2.62. Сколькими способами можно разделить на команды по 6 человек для игры в волейбол группу:

а) из 12; б) из 24 спортсменов?

2.63. Имеется множество C, состоящее из n элементов. Сколькими способами можно выбрать в C два подмножества A и B так, чтобы а) множества A и B не пересекались;

б) множество A содержалось бы в множестве B?

2.64. Полиномиальная теорема. Докажите, что в равенстве коэффициенты C(k1,..., km ) могут быть найдены по формуле Числа C(k1,..., km ) называются полиномиальными коэффициентами.

2.65. При игре в преферанс каждому из трех игроков раздают по 10 карт, а две карты кладут в прикуп. Сколько различных раскладов возможно в этой игре? (Считаются возможные раздачи без учета того, что каждые 10 карт достаются конкретному игроку.) (См. также 2.95.) 2.66. Сколько существует 6-значных чисел, у которых каждая последующая цифра меньше предыдущей?

2.67. Имеется m белых и n черных шаров, причем m > n. Сколькими способами можно все шары разложить в ряд так, чтобы никакие два черных шара не лежали рядом? (См. также 3.129, 11.84.) 2.68. Шесть ящиков занумерованы числами от 1 до 6. Сколькими способами можно разложить по этим ящикам 20 одинаковых шаров так, чтобы ни один ящик не оказался пустым?

Сколькими способами можно разложить n одинаковых шаров по m (n > m) пронумерованным ящикам так, чтобы ни один ящик не оказался пустым?

2.69. Шесть ящиков занумерованы числами от 1 до 6. Сколькими способами можно разложить по этим ящикам 20 одинаковых шаров (на этот раз некоторые ящики могут оказаться пустыми)?

2.70. Сколько решений имеет уравнение а) в натуральных; б) в целых неотрицательных числах?

(См. также 11.67.) 2.71. Сколькими способами можно составить букет из 17 цветков, если в продаже имеются гвоздики, розы, гладиолусы, ирисы, тюльпаны и васильки?

Определение. Биномиальные коэффициенты удобно располагать в виде таблицы, которая называется треугольником Паскаля Он обладает самыми разнообразными свойствами (см. задачи 2.76, 2.77).

2.72. Почему равенства 112 = 121 и 113 = 1331 похожи на строчки треугольника Паскаля? Чему равно 114 ?

2.73. Сколькими способами двигаясь по следующей таблице от буквы к букве можно прочитать слово «квадрат»?

2.74. Придумайте какой-нибудь способ достроить треугольник Паскаля вверх.

2.75. При каких значениях n все коэффициенты в разложении бинома Ньютона (a + b)n нечетны?

2.76. Вычислите суммы:

2.77. Докажите тождества:

б) Cm+1 = Cm + Cn ;m+ Попробуйте доказать эти тождества тремя разными способами:

пользуясь тем, что Ck — это количество k-элементных подмножеств в множестве из n элементов; исходя из того, что Ck — это коэффициент при xk у многочлена (1 + x)n ; пользуясь «шахматным городом» из задачи 2.59.

2.78. Свойство шестиугольника. Докажите равенство 2.79. 120 одинаковых шаров плотно уложены в виде правильной треугольной пирамиды. Сколько шаров лежит в основании?

2.80. В разложении (x + y)n по формуле бинома Ньютона второй член оказался равен 240, третий — 720, а четвертый — 1080. Найдите x, y и n.

2.81. Биномиальная система счисления. Покажите, что любое целое неотрицательное число n может быть представлено в виде 2.82. В компании из 10 человек произошло 14 попарных ссор. Докажите, что все равно можно составить компанию из трех друзей.

2.83. Найдите m и n зная, что 2.84. Какое слагаемое в разложении (1 + 3)100 по формуле бинома Ньютона будет наибольшим?

2.85. Сколько четырехзначных чисел можно составить, используя цифры 1, 2, 3, 4 и 5, если:

а) никакая цифра не повторяется более одного раза;

б) повторения цифр допустимы;

в) числа должны быть нечетными и повторений цифр быть не должно?

2.86. Сколько существует различных возможностей рассадить юношей и 5 девушек за круглый стол с 10-ю креслами так, чтобы они чередовались?

2.87*. В выпуклом n-угольнике проведены все диагонали. Известно, что никакие три из них не пересекаются в одной точке. На сколько частей разделится при этом многоугольник? Во скольких точках пересекутся диагонали?

2.88. Гармонический треугольник Лейбница.

Здесь изображен фрагмент таблицы, которая называется треугольником Лейбница. Его свойства «аналогичны в смысле противоположности» свойствам треугольника Паскаля. Числа на границе треугольника обратны последовательным натуральным числам. Каждое число внутри равно сумме двух чисел, стоящих под ним. Найдите формулу, которая связывает числа из треугольников Паскаля и Лейбница.

2.89. Докажите равенства:

2.90. Найдите сумму и обобщите полученный результат.

2.91. Найдите суммы рядов Определение. Вероятностью наступления какого-либо события называется отношение числа благоприятных исходов к числу всех возможных исходов, предполагаемых равновероятными. (См. [8].) 2.92. В ящике имеется 10 белых и 15 черных шаров. Из ящика вынимаются 4 шара. Какова вероятность того, что все вынутые шары будут белыми?

2.93. Пишется наудачу некоторое двузначное число. Какова вероятность того, что сумма цифр этого числа равна 5?

2.94. Имеется три ящика, в каждом из которых лежат шары с номерами от 0 до 9. Из каждого ящика вынимается по одному шару. Какова вероятность того, что а) вынуты три единицы; б) вынуты три равных числа?

2.95. У игрока в преферанс оказалось 4 козыря, а еще 4 находятся на руках у двух его противников. Какова вероятность того, что козыри лягут а) 2 : 2; б) 3 : 1; в) 4 : 0? (См. также 2.65.) 4. Формула включений и исключений 2.96. Зоопарки. Во всех зоопарках, где есть гиппопотамы и носороги, нет жирафов. Во всех зоопарках, где есть носороги и нет жирафов, есть гиппопотамы. Наконец, во всех зоопарках, где есть гиппопотамы и жирафы, есть и носороги. Может ли существовать такой зоопарк, в котором есть гиппопотамы, но нет ни жирафов, ни носорогов?

2.97. Двоечники. В классе имеется a1 учеников, получивших в течение года хотя бы одну двойку, a2 учеников, получивших не менее двух двоек, и т. д., ak учеников, получивших не менее k двоек. Сколько всего двоек в этом классе? (Предполагается, что ни у кого нет более k двоек.) 2.98. Пусть имеется n подмножеств A1,..., An конечного множества E и j (x) — характеристические функции этих множеств, то есть Докажите, что при этом (x) — характеристическая функция множества A = A1... An, связана с функциями 1 (x),..., n (x) формулой 2.99. Формула включений и исключений. Докажите справедливость равенства где через |A| обозначено количество элементов множества A. (См. также 4.138.) 2.100. Из 100 студентов университета английский язык знают студентов, немецкий — 30, французский — 42, английский и немецкий — 8, английский и французский — 10, немецкий и французский — 5, все три языка знают 3 студента. Сколько студентов не знают ни одного из трех языков?

2.101. Каждая сторона в треугольнике ABC разделена на 8 равных отрезков. Сколько существует различных треугольников с вершинами в точках деления (точки A, B, C не могут быть вершинами треугольников), у которых ни одна сторона не параллельна ни одной из сторон треугольника ABC?

2.102. Сколько существует целых чисел от 1 до 16 500, которые в) не делятся ни на 5 ни на 3, ни на 11?

2.103. Сколько существует целых чисел от 1 до 33 000, которые не делятся ни на 3 ни на 5, но делятся на 11?

2.104. Сколько существует целых чисел от 1 до 1 000 000, которые не являются ни полным квадратом, ни полным кубом, ни четвертой степенью?

2.105. Беспорядки. В классе 30 учеников. Сколькими способами они могут пересесть так, чтобы ни один не сел на свое место?

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

2.107. В комнате площадью 6 м2 постелили три ковра произвольной формы площадью 3 м2 каждый. Докажите, что какие-либо два из них перекрываются по площади, не меньшей 1 м2.

2.108. В прямоугольнике площади 5 расположено 9 фигур площади 1 каждая. Докажите, что найдутся две фигуры, площадь общей части которых не меньше 1/9.

2.109*. В прямоугольнике площади 1 расположено 5 фигур площади 1/2 каждая.

а) Докажите, что найдутся два фигуры, площадь общей части которых не меньше 3/20.

б) Докажите, что найдутся две фигуры, площадь общей части которых не меньше 1/5.

в) Докажите, что найдутся три фигур, площадь общей части которых не меньше 1/20.

2.110. Докажите, что в условии задач 2.109 б) и в) числа 1/5 и 1/ нельзя заменить большими величинами.

5. Числа Каталана Во многих комбинаторных задачах решением является последовательность чисел Каталана Определение. Пусть имеется n + 1 переменная x0, x1,..., xn, и мы хотим вычислить их произведение при помощи n умножений. Определим число Cn как количество способов расставить скобки в произведении x0 · x1 ·... · xn так, чтобы порядок умножений был полностью определен. Например, при n = 2 существует два способа: x0 · (x1 · x2 ), (x0 · x1 ) · x2, а при n = 3 уже 5:

2.111. Сколько последовательностей {a1, a2,..., a2n }, состоящих из + 1 и 1, обладают тем свойством, что a1 + a2 +... + a2n = 0, а все их частичные суммы неотрицательны?

2.112. Сколько существует способов разрезать выпуклый (n + 2)угольник диагоналями на треугольники?

2.113. Маршруты ладьи. Рассмотрим шахматные доски со сторонами 2, 3, 4,... Требуется провести ладью из левого нижнего угла в правый верхний. Двигаться можно только вверх и вправо, не заходя при этом на клетки главной диагонали и ниже нее. (Ладья оказывается на главной диагонали только в начальный и в конечный моменты времени.) Сколько существует таких маршрутов?

2.114. Очередь в кассу. Билеты стоят 50 центов, и 2n покупателей стоят в очереди в кассу. Половина из них имеет по одному доллару, остальные — по 50 центов. Кассир начинает продажу билетов, не имея денег. Сколько существует различных порядков в очереди, таких, что кассир всегда может дать сдачу?

2.115. Формула для чисел Каталана. Пусть {a1, a2,..., an } — последовательность целых чисел, сумма которых равна + 1. Докажите, что ровно у одного из ее циклических сдвигов все частичные суммы положительны. Выведите отсюда равенства:

где (4n 2)!!!! = 2 · 6 · 10... (4n 2) — произведение, в котором участвует каждое четвертое число. (См. также 3.105.) 2.116. Рекуррентное соотношение для чисел Каталана. Докажите, что числа Каталана удовлетворяют рекуррентному соотношению (См. также 11.92.) и основная теорема арифметики 1. Простые числа Определение. Натуральное число p называется простым, если p > 1 и p не имеет положительных делителей, отличных от 1 и p.

По соглашению, 1 не является простым числом. Остальные числа, имеющие три и более делителей, называются составными.

3.1. Теорема Евклида. Докажите, что простых чисел бесконечно много.

3.2. Найдите все простые числа, которые отличаются на 17.

3.3. Докажите, что остаток от деления простого числа на 30 — простое число.

3.4. Пусть n > 2. Докажите, что между n и n! есть по крайней мере одно простое число.

3.5. Найдите все такие простые числа p и q, для которых выполняется равенство p2 2q2 = 1.

3.6. Докажите, что если число n! + 1 делится на n + 1, то n + 1 — простое число.

3.7. Докажите, что множество простых чисел вида p = 4k + 3 бесконечно. (См. также 4.127.) 3.8. Докажите, что множество простых чисел вида p = 6k + 5 бесконечно. (См. также 4.128.) 3.9. Докажите, что составное число n всегда имеет делитель 3.10. Когда натуральное число n имеет нечетное количество делителей?

3.11. Разложите на простые множители числа 111, 1111, 11111, 111111, 1111111. (См. также 4.25.) 28 3. Алгоритм Евклида и основная теорема арифметики 3.12. Докажите, что существуют 1000 подряд идущих составных чисел.

3.13. Докажите, что для любого натурального n найдутся n подряд идущих натуральных чисел, среди которых ровно одно простое.

3.14. Существуют ли а) 5; б) 6 простых чисел, образующих арифметическую прогрессию?

3.15. Существуют ли арифметическая прогрессия, состоящая лишь из простых чисел?

3.16. Предположим, что нашлись 15 простых чисел, образующих арифметическую прогрессию с разностью d. Докажите, что d > 30000.

Определение. Два простых числа, отличающиеся на 2 называются простыми числами-близнецами.

3.17. Докажите, что 3, 5 и 7 являются единственной тройкой простых чисел-близнецов.

3.18. Найдите все простые числа, которые равны сумме двух простых чисел и разности двух простых чисел.

3.19. Докажите, что при n > 2 числа 2n 1 и 2n + 1 не могут быть простыми одновременно.

3.20. При каких целых n число n4 + 4 — составное?

3.21. Верно ли, что многочлен P(n) = n2 + n + 41 при всех n принимает только простые значения?

3.22. Пусть {pn } — последовательность простых чисел (p1 = 2, p2 = 3, p3 = 5,... ). Докажите, что pn > 2n при n 5. При каких n будет выполняться неравенство pn > 3n?

3.23. Докажите неравенство pn+1 < p1 p2... pn.

3.24. Верно ли, что все числа вида p1 p2... pn + 1 являются простыми?

3.25. Числа Евклида. Евклидово доказательство бесконечности множества простых чисел наводит на мысль определить рекуррентно числа Евклида:

Все ли числа en являются простыми? (См. также 4.79.) 3.26. Числа Ферма. Докажите, что если число an + 1 простое, то. 2 и n = 2k. (Простые числа вида fk = 22k + 1 называются числами Ферма.

3.27. Докажите, что fn делит 2fn 2.

3.28. Докажите, что числа Ферма fn при n > 1 не представимы в виде суммы двух простых чисел.

3.29. Числа Мерсенна. Докажите, что если число an 1 простое, то a = 2 и n — простое.

Простые числа вида q = 2p 1 называются числами Мерсенна.

3.30. Пусть Pn (x) = an xn +...+a1 x+a0 — многочлен с целыми коэффициентами (n 1, an = 0). Может ли быть так, что при x = 0, 1, 2,...

все числа Pn (x) — простые?

2. Алгоритм Евклида Определение. Наибольшим общим делителем (НОД) целых чисел a1,..., an называется такой положительный общий делитель a1,..., an, который делится на любой другой общий делитель этих чисел. НОД чисел a1,..., an обозначается (a1,..., an ).

Если наибольший общий делитель чисел a1,..., an равен 1, то эти числа называются взаимно простыми.

3.31. Докажите, что если в наборе целых чисел a1,..., an хотя бы одно отлично от 0, то они имеют наибольший общий делитель.

3.32. В прямоугольнике с целыми сторонами m и n, нарисованном на клетчатой бумаге, проведена диагональ. Через какое число узлов она проходит? На сколько частей эта диагональ делится линиями сетки?

3.33. Натуральные числа p и q взаимно просты. Отрезок [0; 1] разбит на p + q одинаковых отрезков. Докажите, что в каждом из этих отрезков, кроме двух крайних лежит ровно одно из p + q 2 чисел 3.34. С 1 сентября четыре школьника начали посещать кинотеатр.

Первый бывал в нем каждый четвертый день, второй — каждый пятый, третий — каждый шестой и четвертый — каждый девятый. Когда второй раз все школьники встретятся в кинотеатре?

3.35. В задаче 1.1 доказана возможность деления с остатком произвольного целого числа a на натуральное число b. Докажите, что из равенства a = bq + r следует соотношение (a, b) = (b, r).

3.36. Алгоритм Евклида. Пусть m0 и m1 — целые числа, m1 > и m1 m0. Докажите, что при некотором k > 1 существуют целые числа 30 3. Алгоритм Евклида и основная теорема арифметики и (m0, m1 ) = mk.

3.37. Докажите, что для любого s от k 1 до 0 существуют числа us, vs такие, что us ms + ms+1 vs = d, где d = (m0, m1 ). В частности, для некоторых u и v выполняется равенство:

(См. также 6.67.) 3.38. Пусть (a, b) = 1 и a | bc. Докажите, что a | c.

3.39. Найдите (1... 1, 1... 1).

3.40. Какое наибольшее значение может принимать наибольший общий делитель чисел a и b, если известно, что a · b = 600?

3.41. Натуральные числа a1, a2,..., a49 удовлетворяют равенству Какое наибольшее значение может принимать их наибольший общий делитель?

3.42. Можно ли с помощью циркуля и линейки разделить угол на 19 равных частей?

3.43. Числа от 1 до 1000 выписаны подряд по кругу. Начиная с первого, вычеркивается каждое 15-е число: 1, 15, 31,..., причем при повторных оборотах, зачеркнутые числа считаются снова. Число оборотов не ограничено. Сколько чисел останутся незачеркнутыми?

3.44. Докажите, что (5a + 3b, 13a + 8b) = (a, b).

3.45. Может ли наибольший общий делитель двух натуральных чисел быть больше их разности?

3.46. Докажите, что для нечетных чисел a, b и c имеет место равенство 3.47. По окружности радиуса 40 катится колесо радиуса 18. В колесо вбит гвоздь, который ударяясь об окружность, оставляет на ней отметки. Сколько всего таких отметок оставит гвоздь на окружности?

Сколько раз прокатится колесо по всей окружности, прежде чем гвоздь попадет в уже отмеченную ранее точку?

3.48. Для некоторых целых x и y число 3x + 2y делится на 23.

Докажите, что число 17x + 19y также делится на 23.

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

3.50. При каких целых n сократимы дроби 3.51. При каких целых n число также будет целым?

3.52. Найдите все натуральные n > 1 для которых n3 3 делится на n 1.

3.53. На какие натуральные числа можно сократить дробь, если известно, что она сократима и что числа m и n взаимно просты.

3.54. Докажите, что при m = n выполняются равенства:

где fk = 22 + 1 — числа Ферма. (См. также 3.39, 3.122, 6.69.) 3.55. Докажите, что число 22 1 имеет по крайней мере n различных простых делителей.

3.56. Докажите, что для простых чисел выполняется неравенство pn+1 22 + 1.

3.57. Докажите, что равенство (a, mn) = 1 равносильно выполнению двух условий (a, m) = 1 и (a, n) = 1.

3.58. Докажите, что если (a, b) = 1, то (2a + b, a(a + b)) = 1.

3.59. Докажите, что если (a, b) = 1, то наибольший общий делитель чисел a + b и a2 + b2 равен 1 или 2.

3.60. Пусть a и b — натуральные числа. Докажите, что среди чисел a, 2a, 3a,..., ba ровно (a, b) чисел делится на b.

32 3. Алгоритм Евклида и основная теорема арифметики 3.61. Пусть (a, b) = 1 и (x0, y0 ) — некоторое целочисленное решение уравнения ax + by = 1. Докажите, что все решения этого уравнения в целых числах получаются по формулам x = x0 + kb, y = y0 ka, где k — произвольное целое число.

3.62. Как описать все решения в целых числах уравнения ax+by = c при произвольных a, b, c?

3.63. Решите в целых числах уравнения (укажите все решения):

3.64. Докажите, что число шагов в алгоритме Евклида может быть сколь угодно большим.

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

3.66. Найдите все взаимно простые a и b, для которых 3.67. Докажите, что если (a1, a2,..., an ) = 1, то уравнение разрешимо в целых числах.

Определение. Пусть a1,..., an — отличные от 0 целые числа. Наименьшим общим кратным (НОК) этих чисел называется наименьшее положительное число, кратное всем этим числам. НОК чисел a1,...

..., an обозначается [a1,..., an ].

3.68. Докажите равенства 3.69. На доске написано n натуральных чисел. За одну операцию вместо двух чисел, не делящих друг друга, можно написать их наибольший общий делитель и их наименьшее общее кратное.

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

б) Финальный результат независимо от порядка действий будет одним и тем же. Например:

3.70. Найдите наименьшее c, при котором а) уравнение 7x + 9y = c имело бы ровно 6 целых положительных решений;

б) уравнение 14x + 11y = c имело бы ровно 5 целых положительных решений.

3.71. В каких пределах должно заключаться c, чтобы уравнение 19x + 14y = c имело бы 6 целых положительных решений?

3.72. Пусть a и b — натуральные взаимно простые числа. Рассмотрим точки плоскости с целыми координатами (x, y), лежащие в полосе b 1. Каждой такой точке припишем целое число N(x, y) = = ax + by.

а) Докажите, что для каждого натурального c существует ровно одна точка (x, y) (0 x b 1), что c = N(x, y).

б) Теорема Сильвестра. Докажите, что наибольшее c, для которого уравнение ax + by = c не имеет решений в целых неотрицательных числах, имеет вид c = ab a b.

3.73*. Пусть числа a и b взаимно просты. Докажите, что для того, чтобы уравнение ax + by = c имело ровно n целых положительных решений, значение c должно находиться в пределах (См. также 1.48.) 3.74*. Отметим на прямой красным цветом все точки вида 81x + + 100y, где x, y — натуральные, и синим цветом — остальные целые точки. Найдите на прямой такую точку, что любые симметричные относительно нее целые точки закрашены в разные цвета. Объясните, почему такая точка существует.

3. Мультипликативные функции Основная теорема арифметики. Всякое натуральное число, большее 1, раскладывается и только одним способом (с точностью до порядка сомножителей) в произведение простых чисел.

3.75. Докажите основную теорему арифметики при помощи утверждения из задачи 3.38.

3.76. Найдите все двузначные числа, квадрат которых равен кубу суммы их цифр.

3.77. На какое количество нулей заканчивается число 100! ?

34 3. Алгоритм Евклида и основная теорема арифметики 3.78. Найдите наименьшее натуральное n, для которого 1999! не делится на 34n.

3.79. Докажите, что произведение чисел от n+1 до 2n делится на 2n, но не делится на 2n+1.

простые, и 1,..., s, 1,..., s 0. Докажите равенства:

а) (a, b) = pmin(1,1 ) ·... · pmin(s,s ) ;

б) [a, b] = pmax(1,1 ) ·... · pmax(s,s ) ;

в) (a, b)[a, b] = ab.

3.81. Докажите равенства:

а) [a, (a, b)] = a; в) abc = [a, b, c](ab, ac, bc);

б) (a, [a, b]) = a; г) abc = (a, b, c)[ab, bc, ac].

3.82. Докажите, что (bc, ac, ab). (a, b, c)2.

3.83. Приведите пример, когда равенство (a, b, c)[a, b, c] = abc не выполнено. Каким неравенством всегда будут связаны числа (a, b, c) [a, b, c] и abc?

3.84. Сколько различных делителей имеют числа 3.85. Для каждого k от 1 до 6 найдите наименьшее натуральное число, которое имеет ровно k различных делителей.

3.86. Пусть (n) — количество положительных делителей натурального числа n = p1 ·... · ps, а (n) — их сумма. Докажите равенства:

3.87. Найдите натуральное число n, зная, что оно имеет два простых делителя и удовлетворяет условиям (n) = 6, (n) = 28.

3.88. Некоторое натуральное число n имеет два простых делителя.

Его квадрат имеет а) 15; б) 81 делителей. Сколько делителей имеет куб этого числа?

3.89. Найдите натуральное число вида n = 2x · 3y · 5z, зная, что половина его имеет на 30 делителей меньше, треть — на 35 и пятая часть — на 42 делителя меньше, чем само число.

Определение. Функция f(n), определенная на множестве натуральных чисел называется мультипликативной, если она удовлетворяет двум условиям:

1) f(1) = 1; 2) f(m · n) = f(m) · f(n) при (m, n) = 1.

Если f(1) = 1 и равенство f(m · n) = f(m) · f(n) выполнено для всех пар натуральных чисел m и n, то функция f(n) называется вполне мультипликативной.

3.90. Докажите мультипликативность функций (n) и (n).

3.91. Докажите неравенство (n) 2 n.

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

3.93. Пусть (m, n) > 1. Что больше (m · n) или (m) · (n)? Исследуйте тот же вопрос для функции (n). (См. также 4.144.) Определение. Число n называется совершенным, если (n) = 2n.

Например, числа 6 и 28 — совершенные:

3.94. Совершенные числа. Докажите, что если 2k 1 = p — некоторое простое число Мерсенна, то n = 2k1 (2k 1) — совершенное число.

3.95*. Теорема Эйлера. Докажите, что если n — четное совершенное число, то оно имеет вид n = 2k1 (2k 1), и p = 2k 1 — простое число Мерсенна.

Проблема существования нечетных совершенных чисел остается среди трудных и нерешенных задач теории чисел.

Определение. Числа m и n называются дружественными, если сумма собственных делителей числа m равна n и, наоборот, сумма собственных делителей числа n равна m. Другими словами, числа m и n являются дружественными, если или 3.96. Дружественные числа. Докажите, что если все три числа m = 2k · p · q и n = 2k · r — дружественные. Постройте примеры дружественных чисел.

3.97. Может ли быть так, что а) (n) > 3n; б)* (n) > 100n?

3.98. Задача Ферма. Найдите наименьшее число вида n = 2 p1 p2, где p1 и p2 — некоторые простые числа, такое, что (n) = 3n.

36 3. Алгоритм Евклида и основная теорема арифметики 3.99. Пусть — действительное положительное число, d — натуральное. Докажите, что количество натуральных чисел, не превосходящих и делящихся на d, равно.

3.100. Докажите, что для действительного положительного и натурального d всегда выполнено равенство.

3.101. Формула Лежандра. Число n! разложено в произведение простых чисел n! = p1... ps. Докажите равенство 3.102. Докажите, что число p входит в разложение n! с показателем, 3.103. Пусть представление числа n в двоичной системе выглядит следующим образом:

Докажите, что n! делится на 2nr, но не делится на 2nr+1.

3.104. Результат предыдущей задачи допускает обобщение. Пусть p — простое число и представление числа n в p-ичной системе имеет вид:

Найдите формулу, выражающую показатель p, с которым это число p входит в каноническое разложение n!, через n, p и коэффициенты ak.

3.105. При помощи формулы Лежандра из задачи 3.101 докажите, 3.107. Существует ли такое целое r, что число nr является целым 4. О том, как размножаются кролики Определение. Последовательность чисел Фибоначчи {F0, F1, F2,... } = {0, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610,... } Эти числа были впервые описаны в «Книге абака» (1202 г.) итальянского математика Леонардо Пизанского (Фибоначчи).

3.108. Задача Леонардо Пизанского. Некто приобрел пару кроликов и поместил их в огороженный со всех сторон загон. Сколько кроликов будет через год, если считать, что каждый месяц пара дает в качестве приплода новую пару кроликов, которые со второго месяца жизни также начинают приносить приплод?

3.109. О том, как прыгают кузнечики. Предположим, что имеется лента, разбитая на клетки и уходящая вправо до бесконечности. На первой клетке этой ленты сидит кузнечик. Из любой клетки кузнечик может перепрыгнуть либо на одну, либо на две клетки вправо. Сколькими способами кузнечик может добраться до n-й от начала ленты клетки? (См. также 3.114.) 3.110. Некоторый алфавит состоит из 6 букв, которые для передачи по телеграфу кодированы так:

При передаче одного слова не сделали промежутков, отделяющих букву от буквы, так что получилась сплошная цепочка из точек и тире, содержащая 12 знаков. Сколькими способами можно прочитать переданное слово?

3.111. Чему равны числа Фибоначчи с отрицательными номерами 3.112. Тождество Кассини. Докажите равенство Будет ли тождество Кассини справедливо для всех целых n? (См.

также 12.13.) 3.113. Докажите следующие свойства чисел Фибоначчи:

3.114. Докажите, что при n 1иm 0 выполняется равенство Попробуйте доказать его двумя способами: при помощи метода математической индукции и при помощи интерпретации чисел Фибоначчи из задачи 3.109. Докажите также, что тождество Кассини является частным случаем этого равенства.

38 3. Алгоритм Евклида и основная теорема арифметики 3.115. Докажите равенства б) Fn+1 Fn+2 Fn Fn+3 = (1)n+1 ;

3.116. Вычислите F4 Fn Fn+1 Fn+3 Fn+4.

3.117. Вычислите сумму 3.118. Делимость чисел Фибоначчи. Докажите справедливость следующих утверждений:

3.119. Докажите, что для любого натурального m существует число Фибоначчи Fn (n 1), кратное m.

3.120. Пусть первое число Фибоначчи, делящееся на m есть Fk.

Докажите, что m | Fn тогда и только тогда, когда k | n.

3.121. Докажите, что два соседних числа Фибоначчи Fn1 и Fn (n 1) всегда взаимно просты.

3.122*. Теорема Люка. Докажите равенство (Fn, Fm ) = F(m,n).

(См. также 3.141.) 3.123. В последовательности чисел Фибоначчи выбрано 8 чисел, идущих подряд. Докажите, что их сумма не является числом Фибоначчи.

3.124. Рассмотрим множество последовательностей длины n, состоящих из 0 и 1, в которых не бывает двух 1 стоящих рядом. Докажите, что количество таких последовательностей равно Fn+2. Найдите взаимно однозначное соответствие между такими последовательностями и маршрутами кузнечика из задачи 3.109.

3.125. Фибоначчиева система счисления. Докажите, что произвольное натуральное число n, не превосходящее Fm, единственным образом можно представить в виде где все числа b2,..., bm равны 0 либо 1, причем среди этих чисел нет Для записи числа в фибоначчиевой системе счисления используется обозначение:

(См. также 12.14, 4.193.) 3.126. Формула Бине. Докажите по индукции формулу Бине:

где = — «золотое сечение» или число Фидия, а = («фи с крышкой») — сопряженное к нему. (См. также 11.43, 11.75.) 3.127. Докажите следующий вариант формулы Бине:

(См. также 4.129.) 3.128. Докажите, что число Фибоначчи Fn совпадает с ближайшим целым числом к, то есть 3.129. Числа Фибоначчи и треугольник Паскаля. Докажите равенство:

Сумма, стоящая в левой части равенства, может быть интерпретирована, как сумма элементов треугольника Паскаля, стоящих в одной диагонали (См. приложение В, II и задачи 2.67, 3.124, 11.44 и 11.45.) 3.130. Вычислите сумму:

(См. также 11.44, 11.45.) 3.131. Сколько существует последовательностей из 1 и 2, таких что сумма чисел в каждой такой последовательности равна n? Например, если n = 4, то таких последовательностей пять:

3.132. Решите в целых числах уравнение Определение. Последовательность чисел Люка {L0, L1, L2,... } = {2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, 521,... } задается равенствами L0 = 2, L1 = 1, Ln+2 = Ln+1 + Ln (n 0).

3.133. Докажите, что числа Люка связаны с числами Фибоначчи соотношениями:

(См. также 9.79, 11.41.) 3.134. В вершинах правильных многоугольников записываются числа 1 и 2. Сколько существует таких многоугольников, что сумма чисел стоящих в вершинах равна n (n 3)? Две расстановки чисел, которые можно совместить поворотом не отождествляются.

3.135. Выразите Ln в замкнутой форме через и. (См. также 11.77.) 3.136. Докажите равенства Найдите общую формулу, для которой данные равенства являются частными случаями.

3.137*. Решите в целых числах уравнения:

3.138. а) Докажите, что в последовательности чисел Фибоначчи при 2 встречается не менее 4 и не более 5 m-значных чисел.

б) Докажите, что число F5t+2 (t 0) содержит в своей десятичной записи не менее t + 1 цифры.

3.139. Рассмотрим алгоритм Евклида из задачи 3.36 состоящий из k шагов. Докажите, что начальные числа m0 и m1 должны удовлетворять неравенствам m1 Fk+1, m0 Fk+2.

3.140. Теорема Ламе. Пусть число m1 в десятичной системе счисления записывается при помощи t цифр. Докажите, что при любом m число шагов k в алгоритме Евклида для чисел m0 и m1 удовлетворяет неравенству k 5t.

3.141. Фибоначчиевы коэффициенты.

Данная таблица аналогична треугольнику Паскаля и состоит из фиk боначчиевых коэффициентов Fn, определяемых равенством а) Докажите, что фибоначчиевы коэффициенты обладают свойk k ством симметрии Fn = Fnk.

б) Найдите формулу, которая выражает коэффициент Fn через Fn и Fn1 (аналогичную равенству б) из задачи 2.77).

в) Объясните, почему все фибоначчиевы коэффициенты являются целыми числами.

3.142*. Обобщенные биномиальные коэффициенты. Пусть A1, A2,... — последовательность ненулевых целых чисел, такая, что Докажите, что все обобщенные биномиальные коэффициенты являются целыми числами. (См. также 8.89.) 5. Цепные дроби Определение. Пусть a0 — целое, a1, a2,..., an — натуральные и an > 1. n-членной цепной (непрерывной) дробью называется выражение (обозначается [a0 ; a1, a2,..., an ]).

Числа a1, a2,..., an называются неполными частными дроби (3.1).

3.145. Как связано разложение рационального числа в цепную дробь с алгоритмом Евклида?

3.146. Геометрическая интерпретация алгоритма Евклида.

Работу алгоритма Евклида (см. раздел 2) можно представить следующим образом. В прямоугольник размерами m0 m1 (m1 m0 ) укладываем a0 квадратов размера m1 m1, в оставшийся прямоугольник размерами m1 m2 (m2 m1 ) укладываем a1 квадратов размера m2 m2, и т. д. до тех пор, пока весь прямоугольник не покроется квадратами. (См. также 3.157.) Выразите общее число квадратов через элементы цепной дроби числа m1 /m2.

3.147. Для каждого натурального n приведите пример прямоугольника, который разрезался бы ровно на n квадратов.

3.148. Цепные дроби и электрические цепи. Для данного рационального числа a/b постройте электрическую цепь из единичных сопротивлений, общее сопротивление которой равнялось бы a/b. Как такую цепь можно получить при помощи разбиения прямоугольника a b на квадраты из задачи 3.146?

3.149. Пусть a0 — целое, a1,..., an — натуральные числа. Определим две последовательности Докажите, что построенные последовательности для k = 0, 1,..., n обладают следующими свойствами:

Определение. Рациональные дроби называются подходящими дробями к непрерывной дроби (3.1).

3.150. Докажите следующие свойства подходящих дробей:

д) 2k < 2l+1 (k, l 0).

..., an ]. Докажите, что уравнение ax by = 1 c неизвестными x и y имеет решением одну из пар (Qn1, Pn1 ) или (Qn1, Pn1 ). Отчего зависит, какая именно из пар является решением?

3.152. Разлагая число a/b в непрерывную дробь, решите в целых числах уравнения ax by = 1, если 3.153. Григорианский календарь. Обыкновенный год содержит 365 дней, високосный — 366. n-й год, номер которого не делится на 100, является високосным тогда и только тогда, когда n кратно 4. n-й год, где n делится на 100, является високосным тогда и только тогда, когда n кратно 400. Так, например, 1996-й и 2000-й годы — високосные, а 1997-й и 1900-й — нет. Эти правила были установлены папой Григорием XIII.

До сих пор мы имели ввиду «гражданский год», число дней которого должно быть целым. Астрономическим же годом называется период времени, за который Земля совершает полный оборот вокруг Солнца.

Считая, что «григорианский год» полностью согласован с астрономическим годом, найдите продолжительность астрономического года. (См.

также 12.7.) Определение. Бесконечной непрерывной дробью называется выражение вида где a0 — целое, a1, a2,..., an,... — натуральные числа.

Величиной бесконечной непрерывной дроби называется предел ее подходящих дробей, то есть такое число, что 3.154. Докажите, что любое иррациональное число допускает представление где a0 — целое, a1, a2,..., an1 — натуральные, n > 1 — иррациональное действительное числа. Отсюда следует, что каждому иррациональному действительному числу можно поставить в соответствие бесконечную цепную дробь.

3.155. Докажите, что для любой бесконечной цепной дроби существует предел ее подходящих дробей — иррациональное число.

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

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

3.156. Предположим, что число задано бесконечной цепной дробью Докажите, что 3.157. Последовательности {ak } и {bk } строятся по следующему закону:

a1 = 1, b1 = 2, an+1 = min(an, bn ), bn+1 = |bn an | (n 1).

а) Докажите, что an = 0 и an стремится к 0 при n.

б) Докажите, что последовательность cn = a2 + a2 +... + a2 имеет предел и найдите этот предел.

3.158. Юлианский календарь. Из астрономии известно, что год имеет 365,2420... = [365; 4, 7, 1, 3,... ] так называемых «календарных суток». В Юлианском стиле каждый четвертый год — високосный, то есть состоит из 366 дней. За сколько лет при таком календаре накапливается ошибка в одни сутки? На сколько дней отстает Юлианский календарь за 1000 лет? И вообще, почему он отстает, если юлианский год длиннее астрономического?

3.159. Персидский календарь. Наиболее точный календарь ввел в Персии в 1079 году персидский астроном, математик и поэт Омар Альхайями. Восстановите этот календарный стиль, рассмотрев третью подходящую дробь [365; 4, 7, 1] к длительности астрономического года.

За сколько лет в этом календаре накапливается ошибка в одни сутки?

Определение. Бесконечная непрерывная дробь вида называется периодической с периодом ak+1,..., ak+T. Набор a0, a1,...

..., ak называется предпериодом.

Бесконечная непрерывная дробь вида [ a0 ; a1,..., aT 1 ] называется чисто периодической.

3.160. Вычислите следующие цепные дроби:

3.161. Разложите в цепные дроби числа:

3.162. Формат A4. Найдите наименьшее натуральное n, для которого существует такое m, что 3.163. Числа из электрической розетки. Найдите наименьшее натуральное n, для которого существует такое m, что (См. [185].) Определение. Число называется квадратичной иррациональностью, если оно является иррациональным корнем некоторого квадратного уравнения с целыми коэффициентами.

46 3. Алгоритм Евклида и основная теорема арифметики Если = b + c d — квадратичная иррациональность, то число = = b c d называется сопряженным к числу.

3.164. Докажите, что значение любой периодической цепной дроби — квадратичная иррациональность.

Верно более сильное утверждение.

Теорема Лагранжа. Число разлагается в периодическую цепную дробь тогда и только тогда, когда оно является квадратичной иррациональностью. (См. [5], [28].) 3.165. Найдите рациональное число, которое отличается от не более чем 0,0001, где 3.166. Докажите равенство:

3.167*. Теорема Лежандра. Докажите, что если то — подходящая дробь к числу.

3.168. Теорема Валена. Докажите, что если pn /qn (n 1) — подходящая дробь к числу, то имеет место по крайней мере одно из неравенств 4.24. Докажите, что любое натуральное число, десятичная запись которого состоит из 3n одинаковых цифр, делится на 37.

4.25. Докажите, что число 11... 1 (1986 единиц) имеет по крайней мере а) 8; б) 32 различных делителя.

4.26. Докажите, что числа 4.27. Докажите следующие соотношения:

а) 241 1. 83; б) 270 + 370. 13; в) 215 1. 20801.

4.28. Докажите, что для любого простого числа p > 2 числитель дроби делится на p.

4.29. Натуральные числа m и n таковы, что m > n, m не делится на n и имеет от деления на n тот же остаток, что и m + n от деления на m n. Найдите отношение m : n.

4.30. Даны целые числа a, b, c такие, что a + b + c. 6. Докажите, что a3 + b3 + c3. 6.

4.31. Докажите, что 1110 1. 100.

4.32. Сколько имеется различных прямоугольных треугольников, длины сторон которых выражены целыми числами, если один из катетов этих треугольников равен 15?

4.33. Решите уравнения:

4.34. Докажите, что число 11999 + 21999 +... + 161999 делится на 17.

4.35. Назовем шестизначное число счастливым, если сумма его первых трех цифр равна сумме последних трех цифр. Докажите, что сумма всех счастливых чисел делится на 13.

4.36. Докажите, что числа от 1 до 2001 включительно нельзя выписать подряд в некотором порядке так, чтобы полученное число было точным кубом.

4.38. Число x таково, что x2 заканчивается на 001 (в десятичной системе счисления). Найдите три последние цифры числа x (укажите все возможные варианты).

4.39. Имеется много одинаковых квадратов. В вершинах каждого из них в произвольном порядке написаны числа 1, 2, 3 и 4. Квадраты сложили в стопку и написали сумму чисел, попавших в каждый из четырех углов стопки. Может ли оказаться так, что а) в каждом углу стопки сумма равна 2004?

б) в каждом углу стопки сумма равна 2005?

4.40. Дан многочлен с целыми коэффициентами. Если в него вместо неизвестной подставить 2 или 3, то получаются числа, делящиеся на 6.

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

4.41. Докажите, что в трехзначном числе, делящемся на 37, всегда можно переставить цифры так, что новое число также будет делится на 37.

Ck. p.

4.43. Докажите утверждение обратное тому, что было в задаче 4.42:

если Ck. n при 1 k n 1, то n — простое число.

pk+1 Cpk1. p. Верно ли обратное утверждение?

4.45. Докажите, что если p — простое число, то при любых целых a и b выполняется соотношение 4.46*. Камни лежат в трех кучках: в одной — 51 камень, в другой — 49 камней, а в третьей — 5 камней. Разрешается объединять любые кучки в одну, а также разделять кучку из четного количества камней на две равные. Можно ли получить 105 кучек по одному камню в каждой?

В следующих задачах понадобится вспомнить принцип Дирихле из раздела 2.

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

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

4.49. На 99 карточках пишутся числа 1, 2,..., 99. Затем карточки тасуются и раскладываются чистыми сторонами вверх. На чистых сторонах карточек снова пишутся числа 1, 2,..., 99. Для каждой карточки числа, стоящие на ней, складываются и 99 полученных сумм перемножаются. Докажите, что в результате получится четное число.

3. Сравнения Определение. Пусть m 1. Два числа a и b называются сравнимыми по модулю m, если их разность делится на m. Записывается это в виде a b (mod m).

4.50. Что означают записи:

4.51. Свойства сравнений. Докажите, что если a b (mod m) и c d (mod m), то Определение. Классом вычетов по данному модулю m называется множество всех целых чисел сравнимых с некоторым данным целым числом a по модулю m. Такой класс обозначается a.

4.52. Докажите, что класс a состоит из всех чисел вида mt + a, где t — произвольное целое число.

4.53. Докажите, что два класса a и b совпадают тогда и только тогда, когда a b (mod m).

Определение. Полной системой вычетов по некоторому модулю называется система чисел, взятых по одному из каждого класса по этому модулю.

4.54. Докажите, что любые m чисел x1,..., xm попарно несравнимых по модулю m, представляют собой полную систему вычетов по модулю m.

4.55. Пусть числа x1, x2,..., xm образуют полную систему вычетов по модулю m. Для каких a и b числа yj = axj + b (j = 1,..., m) также образуют полную систему вычетов по модулю m?

4.56. Из свойств сравнений следует, что с классами вычетов можно делать все операции, которые допустимы для целых чисел: складывать, вычитать, умножать, возводить в степень. Отличие будет лишь в том, что построенная арифметика действует на конечном множестве классов вычетов. Например, для m = 6 получаются такие таблицы сложения и умножения:

Постройте аналогичные таблицы сложения и умножения для модулей 4.57. Когда сравнения a b (mod m) и ac bc (mod m) равносильны?

4.58. Равносильны ли сравнения a b (mod m) и ac bc (mod mc)?

4.59. Имеется 100 камней. Два игрока берут по очереди от 1 до камней. Проигрывает тот, кто берет последний камень. Определите выигрышную стратегию первого игрока. (См. также 5.81.) 4.60. Разочарованный вкладчик фонда «Нефтьалмазинвест» разорвал акцию на 8 кусков. Не удовлетворившись этим, он разорвал один из кусков еще на 8, и т. д. Могло ли у него получиться 2002 куска?

4.61. Иван-царевич имеет два волшебных меча, один из которых может отрубить Змею Горынычу 21 голову, а второй — 4 головы, но тогда у Змея Горыныча вырастает 1999 голов. Может ли Иван отрубить Змею Горынычу все головы, если в самом начале у него было голов? (Примечание: если, например, у Змея Горыныча осталось лишь 3 головы, то рубить их ни тем, ни другим мечом нельзя.) 4.62. В магазине было 6 ящиков яблок, массы которых соответственно 15, 16, 18, 19, 20 и 31 килограммов. Две фирмы приобрели 5 ящиков, причем одна из них взяла по массе яблок в два раза больше, чем другая.

Какой ящик остался в магазине?

4.63. Составьте список всевозможных остатков, которые дают числа n2 при делении на 3, 4, 5,..., 9.

4.64. Докажите, что если все коэффициенты уравнения — целые нечетные числа, то ни один из корней этого уравнения не может быть рациональным.

4.65. Докажите, что квадрат целого числа не может оканчиваться четырьмя одинаковыми цифрами, отличными от 0. Какими тремя цифрами может оканчиваться целое число, квадрат которого оканчивается тремя одинаковыми цифрами, отличными от 0?

4.66. Докажите, что если две последние цифры целого числа нечетны, то это число не может быть квадратом целого числа.

4.67. Найдите остатки от деления числа 22001 на 3, 5, 7,..., 17.

4.68. Шестизначное число делится на 7. Его первую цифру стерли, а затем записали ее позади последней цифры. Докажите, что новое число также делится на 7.

4.69. Найдите все p такие, что числа p, p + 10, p + 14 — простые.

4.70. Известно, что числа p и 8p2 + 1 — простые. Найдите p.

4.71. Известно, что числа p и p2 +2 — простые. Докажите, что число p + 2 также является простым.

4.72. Найдите конечную арифметическую прогрессию с разностью максимальной длины, состоящую из простых чисел.

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

4.74. Может ли число быть целым при натуральных n?

4.75. Пусть a и b — целые числа. Докажите, что а) если a2 + b2. 3, то a2 + b2. 9; б) если a2 + b2. 21, то a2 + b2. 441.

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

4.77. Целые числа a, b и c таковы, что a3 + b3 + c3. 7. Докажите, что abc. 343.

4.78. Найдите остаток от деления на 17 числа 21999 + 1.

4.79. Встретится ли каждое простое число в качестве сомножителя некоторого числа Евклида en ? (См. также 3.25.) 4.80. Пусть в прямоугольном треугольнике длины сторон выражаются целыми числами. Докажите, что длина одного из катетов кратна 3, и длина одной из трех сторон делится на 5.

4.81. Пусть m — произведение первых n простых чисел (n > 1).

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

4.82. При каких целых n число an = 5n2 + 10n + 8 делится на 3?

А при каких на 4?

4.83. При каких целых n выражение n2 6n 2 делится на 4.84. При каких целых n выражение n2 n 4 делится на 4.85. Найдите все такие целые числа x, что x 3 (mod 7), x 44 (mod 72 ), x3 111 (mod 73 ).

4.86. Докажите, что 22225555 + 55552222. 7.

4.87. Докажите справедливость следующих сравнений:

Будут ли справедливы аналогичные сравнения для бльших показао телей?

4.88. Докажите, что число 1k + 2k +... + 12k делится на 13 для 4.89. Докажите, что если 6n + 11m делится на 31, то n + 7m также делится на 31.

4.90. Известно, что ax4 + bx3 + cx2 + dx + e, где a, b, c, d, e — данные целые числа, при всех целых x делится на 7. Докажите, что все числа a, b, c, d, e делится на 7.

4.91. Докажите, что если многочлен с целыми коэффициентами принимает при x = 0 и x = 1 нечетные значения, то уравнение P(x) = не имеет целых корней.

4.92. Докажите, что pp+2 + (p + 2)p 0 (mod 2p + 2), где p > 2 — простое число.

4.93. Решите сравнения:

а) 8x 3 (mod 13); в) 7x 2 (mod 11);

б) 17x 1 (mod 37); г) 80x 17 (mod 169).

Чтобы решить сравнение ax b (mod m), попробуйте сначала решить в целых числах уравнение ax + my = b.

4.94. Найдите все пары чисел вида 1xy2 и x12y, таких, что оба числа делятся на 7.

4.95. В каких случаях разрешимо сравнение ax b (mod m)? Опишите все решения этого сравнения в целых числах.

4.96. Для каких чисел a решением сравнения ax 1 (mod p) будет само число a?

4.97. Теорема Вильсона. Докажите, что для простого p 4.98. Обращение теоремы Вильсона. Докажите, что если n>1и то n — простое число.

4.98. Геометррическое доказательство теоремы Вильсона.

Пусть p > 2 — простое число. Сколькими способами можно провести через вершины правильного p-угольника замкнутую ориентированную, p-звенную ломанную? (Ломанные, которые можно совместить поворотом, считаются одинаковыми.) Найдите формулу и выведите из неё теорему Вильсона.

4.99. Теорема Лейбница. Докажите, что p — простое тогда и только тогда, когда 4.100. Теорема Клемента. Докажите, что числа p и p+2 являются простыми числами-близнецами тогда и только тогда, когда 4.101. Известно, что числа a1,..., an равны ±1 и Докажите, что n. 4.

Пусть F(x1,..., xn ) — многочлен с целыми коэффициентами от переменных x1,..., xn. Очевидно, что каждое решение уравнения в целых числах является и решением сравнения Поэтому, если хотя бы при одном m сравнение (4.2) неразрешимо, то уравнение (4.1) не имеет решений в целых числах.

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

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

4.104. Гармонические числа. Докажите, что числа при n > 1 не будут целыми.

4.105. Решите в натуральных числах уравнение 4.106. Решите в целых числах уравнение 4.107. Докажите что если (m, n) = 1, то сравнение a b (mod mn) равносильно одновременному выполнению сравнений a b (mod m) и a b (mod n).

4. Теоремы Ферма и Эйлера 4.108. Найдите такое n, чтобы число 10n 1 делилось на 4.109. Докажите, что Малая теорема Ферма. Пусть p — простое число и p a. Тогда 4.110. Докажите теорему Ферма, разлагая (1 + 1 +... + 1)p посредством полиномиальной теоремы.

4.111. Пусть p — простое число, p = 2, 5. Докажите, что существует число вида 111... 11, кратное p.

Придумайте два решения этой задачи: одно, использующее теорему Эйлера, и второе — принцип Дирихле.

4.112. Для каких n число n2001 n4 делится на 11?

4.113. Докажите, что для любого натурального числа найдется кратное ему число, десятичная запись которого состоит только из 0 и 1.

4.114. Дано простое p и целое a, не делящееся на p. Пусть k — наименьшее натуральное число, такое что ak 1 (mod p). Докажите, что p 1 делится на k.

4.115. С помощью индукции докажите следующее утверждение, эквивалентное малой теореме Ферма: если p — простое число, то для любого натурального a справедливо сравнение 4.116. Известно, что Докажите, что abcdef. 136.

4.117. Геометрическое доказательство малой теоремы Ферма. Пусть p > 2 — простое число. Сколько существует способов раскрасить вершины правильного p-угольника в a цветов? (Раскраски, которые можно совместить поворотом, считаются одинаковыми.) Получите формулу и выведите из нее малую теорему Ферма.

4.118. Найдите остатки от деления на 103 чисел а) 5102 ; б) 3104.

4.119. Докажите, что число 30239 + 23930 — составное.

4.120. Будет ли простым число 2571092 + 1092?

4.121. Докажите, что если p — простое число, p = 2, 5, то длина периода разложения 1/p в десятичную дробь делит p 1. Приведите пример, когда длина периода совпадает с p 1.

4.122. Пусть p — простое число. Докажите, что любой простой делитель числа 2p 1 имеет вид 2kp + 1.

4.123. Пусть n — натуральное число, не кратное 17. Докажите, что либо n8 + 1, либо n8 1 делится на 17.

4.124. Докажите, что при любом простом p 4.125. Пусть для простого числа p > 2 и целого a, не делящегося на p, выполнено сравнение x2 a (mod p). Докажите, что 4.126. Докажите, что если x2 + 1 делится на нечетное простое p, то p = 4k + 1.

4.127. При помощи задачи 4.126 докажите, что существует бесконечно много простых чисел вида p = 4k + 1. (См. также 3.7.) 4.128. Докажите, что для простого числа p вида p = 4k + 1 числа x = ±(2k)! являются решениями сравнения x2 + 1 0 (mod p).

4.129. Пользуясь результатом задачи 3.127 найдите остатки, которые при простом p дают числа Фибоначчи Fp и Fp+1 при делении на 4.130. Пусть p — простое число и p > 3. Докажите, что если разрешимо сравнение то p 1 (mod 6). Выведите отсюда бесконечность множества простых чисел вида 6n + 1. (См. также 3.7.) 4.131. Пусть p — простое число и p > 5. Докажите, что если разрешимо сравнение то p 1 (mod 5). Выведите отсюда бесконечность множества простых чисел вида 5n + 1.

Определение. Функция Эйлера (n) определяется как количество чисел от 1 до n, взаимно простых с n.

4.132. Найдите a) (17); б) (p); в) (p2 ); г) (p ).

4.133. Чему равна сумма где — некоторое натуральное число? (См. также 4.149.) 4.134. Основным свойством функции Эйлера (n) является ее мультипликативность. Для взаимно простых a и b рассмотрим таблицу В каких столбцах этой таблицы находятся числа взаимно простые с числом b? Сколько в каждом из этих столбцов чисел взаимно простых с a? Докажите мультипликативность функции Эйлера, ответив на эти вопросы.

Определение. Приведенной системой вычетов по некоторому модулю m называется система чисел, взятых по одному из каждого класса, взаимно простого с модулем. (Говорят, что класс a взаимно прост с модулем m, если само число a взаимно просто с m.) 4.135. Сколько классов составляют приведенную систему вычетов по модулю m?

4.136. Пусть числа x1, x2,..., xr образуют приведенную систему вычетов по модулю m. Для каких a и b числа yj = axj + b (j = 1,..., r) также образуют приведенную систему вычетов по модулю m?

4.137. Пусть (m, n) = 1, а числа x и y пробегают приведенные системы вычетов по модулям m и n соответственно. Докажите, что число A = xn+ym пробегает при этом приведенную систему вычетов по модулю mn. Выведите отсюда мультипликативность функции Эйлера.

4.138. Пусть n = p1... ps. Докажите равенство а) пользуясь мультипликативностью функции Эйлера;

б) пользуясь формулой включений и исключений (см. 2.99).

4.139. Решите уравнения а) (x) = 2; б) (x) = 8; в) (x) = 12; г) (x) = 14.

4.140. По какому модулю числа 1 и 5 составляют приведенную систему вычетов?

4.141. Решите уравнения а) (x) = x/2; б) (x) = x/3; в) (x) = x/4.

4.142. Для каких n возможны равенства:

a) (n) = n 1; б) (2n) = 2(n); в) (nk ) = nk1 (n)?

4.143. Решите уравнения а) (5x ) = 100; б) (7x ) = 294; в) (3x · 5y ) = 600.

4.144. Известно, что (m, n) > 1. Что больше (m · n) или (m) (n)? (См. также 3.93.) 4.145. Решите уравнение a = 2(a).

4.146. Докажите, что если n > 2, то число всех правильных несократимых дробей со знаменателем n — четно.

4.147. Найдите сумму всех правильных несократимых дробей со знаменателем n.

4.148. Выпишем в ряд все правильные дроби со знаменателем n и сделаем возможные сокращения. Например, для n = 12 получится следующий ряд чисел:

Сколько получится дробей со знаменателем d, если d — некоторый делитель числа n?

4.149. Тождество Гаусса. Докажите равенство где знак означает, что суммирование идет по всем делителям числа n (См. также 4.133.) 4.150. Вписанные ломаные. Окружность разделена n точками на n равных частей. Сколько можно составить различных замкнутых ломаных из n р а в н ы х звеньев с вершинами в этих точках?

4.151. Докажите равенства:

а) (m) (n) = ((m, n)) ([m, n]);

б) (mn) ((m, n)) = (m) (n) (m, n).

Следующая теорема является обобщением малой теоремы Ферма.

Теорема Эйлера. Пусть m 1 и (a, m) = 1. Тогда имеет место сравнение (См. также 4.197.) 4.152. Существует ли степень тройки, заканчивающаяся на 0001?

4.153. Докажите теорему Эйлера с помощью малой теоремы Ферма б) в общем случае.

4.154. Докажите, что 751 1 делится на 103.

4.155. Пусть p > 2 — простое число. Докажите, что 4.156. При помощи теоремы Эйлера найдите число x, удовлетворяющее сравнению ax + b 0 (mod m), где (a, m) = 1.

4.157. Докажите, что при любом целом a:

4.158. Докажите, что для любого нечетного числа m существует такое натуральное число n, что 2n 1. m.

4.159. Докажите, что при любом нечетном n число 2n! 1 делится на n.

4.160. Числа Кармайкла. Докажите, что для составного числа 561 справедлив аналог малой теоремы Ферма: если (a, 561) = 1, то выполняется сравнение a560 1 (mod 561).

Числа, обладающие этим свойством, называются числами Кармайкла.

4.161. Найдите все такие целые числа a, для которых число a10 + делится на 10.

4.162. Усиление теоремы Эйлера. m = p1 1... ps — разложение натурального числа m на простые множители. Обозначим через (m) наименьшее общее кратное чисел (p1 ),..., (ps ):

Докажите, что для любого целого числа a такого, что (a, m) = 1, будет выполняться сравнение 5. Признаки делимости 4.163. Признаки делимости на 3, 9 и 11. Число N записано в десятичной системе счисления Докажите следующие признаки делимости:

4.164. Может ли число, записываемое при помощи 100 нулей, единиц и 100 двоек, быть полным квадратом?

4.165. Признаки делимости на 2, 4, 8, 5 и 25. Сформулируйте и докажите признаки делимости на числа 2, 4, 8, 5 и 25.

4.166. Найдите все числа вида xy9z, которые делились бы на 132.

4.167. Найдите все числа вида 13xy45z, которые делились бы на 792.

4.168. Цифровой корень числа. Рассмотрим число N, записанное в десятичной системе счисления. Найдем сумму цифр этого числа, потом сложим цифры, которыми записана сумма и т. д. Будем продолжать этот процесс, пока в конце концов не получим однозначное число, которое называют цифровым корнем числа N. Докажите, что цифровой корень сравним с N по модулю 9.

4.169. Делится ли на 9 число 1234... 500? (В записи этого числа подряд выписаны числа от 1 до 500.) 4.170. Докажите, что число 192021... 7980 делится на 1980.

4.171. Докажите, что число abcd делится на 99 тогда и только тогда, когда число ab + cd делится на 99.

4.172. Последовательность {xn } устроена следующим образом: x1 = = 32001, а каждый следующий член равен сумме цифр предыдущего.

Найдите x5.

4.173. Найдите наименьшее число, запись которого состоит лишь из нулей и единиц, делящееся без остатка на 225.

4.174. Какие цифровые корни бывают у полных квадратов и полных кубов?

4.175. Два числа a и b получаются друг из друга перестановкой цифр. Чему равен цифровой корень числа a b?

4.176. Докажите, что если n > 6 — четное совершенное число, то его цифровой корень равен 1.

4.177. На доске написано число 8n. У него вычисляется сумма цифр, у полученного числа вновь вычисляется сумма цифр, и так далее, до тех пор, пока не получится однозначное число. Что это за число, если n = 2001?

4.178. Докажите ошибочность следующих записей:

а) 4237 · 27925 = 118275855; в) 19652 = 3761225;

б) 42971064 : 8264 = 5201;

4.179. Коля Васин выписал пример на умножение, а затем заменил все цифры буквами: одинаковые цифры одинаковыми буквами, а разные — разными. Получилось равенство ab · cd = effe. Не ошибся ли Коля?

4.180. Докажите, что в записи числа 230 есть по крайней мере две одинаковые цифры, не вычисляя его.

4.181. Существует ли число, которое является степенью 2 такое, что перестановкой его цифр можно получить другую степень 2?

4.182. Признак делимости на 19. Существует следующий способ проверить делится ли данное число N на 19:

1) отбрасываем последнюю цифру у числа N;

2) прибавляем к полученному числу произведение отброшенной цифры на 2;

3) с полученным числом проделываем операции 1) и 2) до тех пор, пока не останется число, меньшее или равное 19.

4) если остается 19, то 19 | N, в противном случае 19 N.

Докажите справедливость этого признака делимости.

4.183. Аналогичные признаки делимости существуют и для всех чисел вида 10n ± 1 и их делителей. Например, существует признак делимости на 21, из которого получается и признак делимости на 7.

Как устроен признак делимости на 21?

4.184. При каких x и y число xxyy является квадратом натурального числа?

4.185. Найдите все такие трехзначные числа, которые в 12 раз больше суммы своих цифр.

4.186. Докажите, что если числа N и 5N имеют одинаковую сумму цифр, то N делится на 9.

4.187. Двое пишут а) 30-значное; б) 20-значное число, употребляя только цифры 1, 2, 3, 4, 5. Первую цифру пишет первый, вторую — второй, третью — первый и т. д. Может ли второй добиться того, чтобы полученное число разделилось на 9, если первый стремится ему помешать?

4.188. Рассматриваются всевозможные семизначные числа с цифрами 1, 2, 3, 4, 5, 6, 7, записанными в произвольном порядке. Докажите, что ни одно из них не делится ни на какое другое.

4.189. Признак делимости Паскаля. Пусть запись числа N в десятичной системе счисления имеет вид N = an an1... a1 a0, ri — остаток от деления числа 10i на m (i = 0,..., n). Докажите, что число N делится на m тогда и только тогда, когда число M = an rn + an1 +...

... + a1 r1 + a0 делится на m.