Deza_Kotova_Sbornik_zadach_po_teorii_chisel

Введение

Данное пособие содержит обширную коллекцию упражнений и задач по всем классическим разделам арифметики и теории чисел.

Пособие написано на основе лекций, читаемых в течение многих лет студентам математического факультета Московского государственного пе­

дагогического университета, и охватывает все вопросы, рассматриваемые

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

темам: теорема о делении с остатком, отношение делимости, простые

и составные числа, НОД и НОК, алгоритм Евклида, взаимно простые

числа, функции LxJ и {х}, мультипликативные функции, число и сумма

делителей, функция Эйлера, функция Мебиуса, отношение сравнимости,

классы вычетов, полная и приведенная системы вычетов, малая теоре­

ма Ферма и теорема Эйлера, линейные сравнения и системы сравнений,

сравнения и системы сравнений по простому модулю, сравнения по сте­

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

Лежандра, показатели и первообразные корни, индексы, цепные дроби,

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

Изложение каждой из вышеперечисленных тем проведено по единой

схеме: основные определения и примеры; свойства рассматриваемых объ­ ектов, часть которых доказана, а остальные приведены без доказательства,

но со ссылками на соответствующую литературу; примеры решения за­

дач; упражнения, аналогичные рассмотренным выше примерам, решаемые

по заданному алгоритму и предназначенные как для работы в аудитории, так и для выполнения домашней работы; задачи для самостоятельно­

го решения, требующие от студентов активного поиска неизвестного им

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

случаи хорошо известных в теории чисел теорем.

Раздел «Задачи ДJIЯ организации промежуrочного и итогового контроля))

содержит цикл заданий для проведения контрольных работ (30 блоков

заданий по 25 однотипных заданий в каждом блоке), задачи лабораторной

работы по теме •Сравнения по составному модулю• (90 заданий различного

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

ющих положений соответствующей теории), задачи лабораторной работы

по теме •Цепные дроби• (25 вариантов по 8 заданий в каждом варианте),

наконец, типовые задания д;1я проверки усвоения обязательного миниму­

ма содержания дисциплины (30 блоков заданий по 18 однотипных заданий в каждом блоке).

Пособие предназначено д;1я проведения семинарских занятий и орга­ низации самостоятельной работы студентов математических факультетов педвузов, для проведения элективных курсов арифметической тематики

и активизации учебно-исследовательской деятельности старшеклассни­

ков, выбравших естественно-математический профиль обучения, для всех

читателей, интересующихся арифметикой и элементарной теорией чисел.

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

было бы невозможно создание этой книги: Бухштаба А.А., Нечаева В. И., Митькина Д. А., Воронина С. М., Киселеву Л. В., Топунова В. Л., Степано­

ву Л.Л., Чирского В.[, Жмулеву А. В., Баулину Ю. Н., Иконникову Т. К.,

Юрченко А. Л., Александрову Н. В., Гладкову Е. Б.

Глава 1

Задачи по курсу теории чисел

Элементарнаятеория чисел имеетдело с натуральными числами 1, 2, 3, ...

(множество натуральных чисел обозначается символом N) и целыми чис­

лами ... , -3, -2, -1, О, 1, 2, 3, ... (множество целых чисел обозначается символом Z).

§ 1. Теорема о делении с остатком

Теорема о делении с остатком (см., например, [28]) утверждает, что для

любого а Е Z и любого Ь Е N существует единственная пара целых чисел q

и r, таких что а = Ьq+r и О ~ r < Ь. Действительно, для заданного целого

числа а и заданного натурального числа Ь рассмотрим рациональное число

q -

q ~ а/Ь < q+1, q Е Z. Тогда Ьq ~а< Ьq+Ь, или, что тоже, О~ а-Ьq < Ь.

Вводя обозначение r = а - Ьq, мы можем утверждать, что для выбранных целых чисел q и r имеет место соотношение а = Ьq+r, причем О ~ r < Ь. Для доказательства единственности указанного представления достаточно

представления а = Ьq + r и а = Ьq1 + r 1 совпадают. Во втором случае мы

получаем, что Ь(q - q1) ;;::: Ь, что дает противоречие с условием r 1- r < Ь.

В третьем случае мы получаем, что Ь(q - q1) ~ -Ь, что дает противоречие

с условием r1 - r > -Ь.

Число q называется целым частным, а число r называется остатком от деления а на Ь. При решении задач обычно используют обозначение

примеры решения задач

1.Найдите целое частное и остатокотделения 19 на 3;-18 на 5; n3 +2n-l на n, где n Е N; 12n5 + 10n4 + 2 на 2n, где n Е N.

Решение. Легко убедиться в том, что: 19 = 3 · 6 + 1, причем 6, 1 Е Z,

и о~ 1 < З; -18 = 5·(-4)+2, причем -4,2 Е Z, и 0~2<5; n3 +2n-1 = n·(n2+1)+(n-1), причем n2+1, n-1 Е Z, и О~ n-1 < n.

Аналогично, l2n5 + 10n2 + 2 = 2n · (6n4 + 5n) + 2, где 6n4 + 5n,

2 Е Z, однако ограничение О ~ 2 < 2n имеет место лишь д/lЯ n ~ 2.

Для n = 1 искомое равенство принимает вид 12n5 + l0n4 + 2 =

2.Целые числа а, Ь и с дают при делении на 5 остатки 1, 2 и 4 соот­ ветственно. Какие остатки при делении на 5 дают числа 2а; -3Ь; 5с;

а+Ь+с; 2а-3Ь+5с; аЬс; а2 ; Ь3 ; с4; 17а2Ь3с4?

Реwение. Из условия задачи следует, что а = 5q + 1, Ь = 5k + 2,

с= 5т +4, где q, k, т Е Z. Тогда 2а = 5 · (2q) + 2, причем 2q, 2 Е Z,

и О ~ 2 < 5. Следовательно, остаток числа 2а при делении на 5 равен 2:

rest(2a, 5) = 2. Далее, -3Ь = 5· (-3k)-6; поскольку -6 = 5· (-2)+4, то -3Ь = 5·(-3k-2)+4, причем -3k-2,4 Е Z, и О~ 4 < 5.

Следовательно, rest(-3Ь, 5) = 4. Поскольку 5с = 5 · с+ О, причем

с, О Е Z, и О ~О < 5, тo"rest(5c, 5) =О. Аналогично, а+ Ь +с=

= 5(q + k + m) + (1+2 + 4), и 1+2 + 4 = 5: 1+2, то есть а+ Ь+с= = 5(q + k + т + 1) + 2, причем q + k + т + l, 2 Е Z, и О ~ 2 < 5.

Таким образом, rest(а+ Ь+с, 5) = 2. Пользуясь полученными ранее со­

отношениями, можноуrверждать, что 2а - 3Ь+ 5с= 5 · (2q - 3k - 2 +с)+

+ (2 + 4 +О), откуда, с учетом равенства 2 + 4 +О = 5 · l + 1, следует

дование произведения чисел а, Ь и с производится по той же схеме:

поскольку 1·2·4 = 5 · 1 + 3, то аЬс = (5q+ 1)(5k + 2)(5m + 4) =

= 5(25qkm + 20qk + 10qm + 8q + 5km + 4k + 2m + 1) + 3, то есть

= а4 +4а3Ь+6а2Ь2+4аЬ3 +Ь4 и замечая, что 44 = 5·51+1, мы можем за­

писать равенство с4 = 5 ·t + 1 для некоторого целого числа t (найдите

его самостоятельно!), откуда следует, что rest(c4, 5) = 1. Наконец,

пользуясь предьщущими результатами и замечая, что 17 = 5 ·З + 2,

Замечание. Анализ решения приведенной выше задачи позволяет уrверждать,

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

чисел а1 , а2, ... , ап (а также натуральной степени ak целого числа а) при

делении на данное натуральное число Ь достаточно оперировать известными

остатками rest(a;, Ь) чисел а;, i = 1, 2, ... , n при делении на Ь. Именно,

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

остатка: rest(a1+ ... + ап, Ь) = rest(rest(a1, Ь) + ... + rest(an, Ь); rest(a1· ... ·

·ап, Ь) = rest(rest(a1, Ь) · ... · rest(an, Ь), Ь); rest(ak, Ь) = rest((rest(a, Ь))k, Ь).

3.Докажите, что любое целое число представимо в виде 5k, или 5k ± 1,

или 5k ± 2, k Е Z, причем данное представление единственно.

Решение. Рассмотрим произвольное целое число z и разделим его

состатком на 5. По теореме о делении с остатком, имеет место

соотношение z = 5q + r, где q, r Е Z, и О ~ r < 5. Другими словами, r Е {О, 1, 2, 3, 4}. Если r =О, то z = 5q +О, то есть, взяв k = q, мы

можем представить z в виде 5k, k Е Z. Если r = 1, то z = 5q + 1, то

есть, взяв k = q, мы можем представить z в виде 5k + 1, k Е Z. Если r = 2, то z = 5q + 2, то есть, взяв k = q, мы можем представить z

Замечание. В ходе рассуждений мы показали, что любое целое число пред­ ставимо в виде 5k, или 5k + 1, или 5k + 2, или 5k + З, или 5k + 4, k Е Z,

причем указанное представление единственно. Этот факт немедленно следует

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

4. Докажите, что квадрат целого числа не может иметь вид 4k +2, k Е Z.

Решение. Рассмотрим произвольное целое число z и поделим его

с остатком на 4: z = 4q + r, О ~ r < 4. Тогда z 2 = (4q + r) 2 =

= 4(4q2 +2qr) +r2 • Если r =О или r = 2, то z 2 имеет вид 4k, k Е Z; если r = 1 или r = 3, то z 2 меет вид 4k + 1, k Е Z. Таким образом,

квадрат целого числа на может имет остаток два при делении на 4,

то есть не может быть представлен в виде 4k + 2, k Е Z. Обычно

приведенные вычисления принято оформлять в виде табл. lа).

Таблица станет еще компактнее (табл. lб)), если воспользоваться иде­

ей предыдущей задачи и представить произвольное целое число z

в виде 4k, или 4k ± 1, или 4k + 2, k Е Z, заменяя rest(z,4) Е

{О, 1, 2, 3} на Rest(z, 4) Е {О, ±1, 2} по закону Rest(z,4) =rest(z,4) при rest(z,4) ~ 2, и Rest(z, 4) = rest(z, 4) - 4 при rest(z, 4) > 2. С>

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

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

q Е Z. Далее, рассмотрим три последовательных целых числа z, z + 1 и z + 2. Легко убедиться в том, что они имеют различные остатки при делении на 3, то есть одно из указанных чисел имеет вид 3k,

при возведении трех указанных чисел в четные степени мы получим

три целых числа, одно из которых имеет вид 31, второе - вид 3q + 1,

а третье - вид 3s + 1, q, l, s Е Z. Сумма полученных целых чисел

имеет вид 3(1+q+в)+2, то есть дает остаток два при делении на 3,

и, следовательно, не может быть четной степенью целого числа. С>

Уnражненuя

Свойства отношения делимости

1. Если аlЬ и alc, то аl(Ь±с), более того, al(mЬ+nc) для любых целых

тип.

2.Если аlЬ и Ьlс, то alc.

3.Если аlЬ и Ьlа, то а = Ь или а = -Ь.

4.Если аlЬ, где а, Ь Е N, то Ь ~а.

Так, если аlЬ и alc, то Ь = ak, и с= al, k, l Е Z. Тогда тЬ = a(mk),

пс= a(nl), и mЬ+nc=a(mk+nl), где mk+nlEZ, то есть al(mЬ+nc).

Доказательства остальных свойств аналогичны. Их можно найти, напри­

мер, в [28).

nрuмеры решенuя задач

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

Решение. Рассмотрим произвольное целое число z и разделим его

2. Докажите, что число а5 + 9а делится на пять при любом целом а.

Решение. Легко убедиться в том, что остаток при делении на 5 пятой

степени целого числа совпадает с остатком при делении на 5 са­

мого числа: rest(05, 5) =О, rest(l 5, 5) = 1, rest(25, 5) = 2, rest(35, 5) = = rest((-2)5, 5) = 3, rest(45 , 5) = rest((-1 )5 , 5) = 4. Поскольку остаток

числа 9 при делении на 5 равен 4, то соответствующие остатки числа

9а равны, соответственно, О, 4, 3, 2 и 1: rest(4·0, 5) =О, rest(4· l, 5) = 4, rest(4 · 3, 5) = 2, rest(4 · 4, 5) = 1. Теперь становится очевидным, что

остаток числа а5 +9а при делении на 5 всегда равен О: rest(O+O, 5) =О, rest(l + 4, 5) =О, rest(2 + 3, 5) =О, rest(3 + 2, 5) =О, rest(4 + 1, 5) =О.

Впрочем, убедиться в этом еще проще, заметив, что число 9 имеет вид 5q - 1, то есть может быть заменено при проведении операций с остатками на число «-1», и, следовательно, вычисления с остат­

ками сводятся к разности двух одинаковых чисел, что, очевидным

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

лять в виде таблицы. В табл. 2 а) мы имеем дело с «классическими» остатками О, 1, 2, 3, 4 при делении на 5, в табл. 2 б) - используем