А. А. МАЗАНИК

ДЕЛИМОСТЬ ЧИСЕЛ И СРАВНЕНИЯ

7 И 8 КЛАССЫ

ИЗДАТЕЛЬСТВО «НАРОДНАЯ АСВЕТА»

МИНСК 1971

А. А. МАЗАНИК

ДЕЛИМОСТЬ ЧИСЕЛ И СРАВНЕНИЯ

Учебный материал для факультативных занятий

ПОСОБИЕ ДЛЯ УЧАЩИХСЯ 7 И 8 КЛАССОВ

ИЗДАТЕЛЬСТВО «НАРОДНАЯ АСВЕТА»

МИНСК 1971

СОДЕРЖАНИЕ

От автора............... 3

§ 1. Делимость чисел............ 5

§ 2. Признаки делимости........... 9

§ 3. Составные и простые числа......... 14

§ 4. Наибольший общий делитель........ 20

§ 5. Алгоритм Евклида........... 23

§ 6. Наименьшее общее кратное........ 30

§ 7. Сравнения и их свойства......... 34

§ 8. Вычеты. Теорема Ферма.......... 39

§ 9. Уравнения в целых числах......... 43

§ 10. Задачи повышенной трудности........ 47

Ответы и решения..........

Литература ............

Мазаник А. А.

M 13 Делимость чисел и сравнения. Учебный материал для факультативных занятий. Мн., «Народная асвета», 1971.

64 с. 40 000 экз. 9 к.

В книге помещен учебный материал по теме «Дополнительные вопросы арифметики целых чисел» для факультативных занятий в VII и VIII классах.

Пособие рекомендуется учителям математики и учащимся VII и VIII классов.

511(075)

ОТ АВТОРА

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

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

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

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

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

§ 1. ДЕЛИМОСТЬ ЧИСЕЛ

I. Когда в курсе арифметики предлагалось целое число а разделить на другое целое число b, отличное от нуля, то, в зависимости от условий задания, требовалось одно из двух:

а) либо найти такое число q, которое, будучи умножено на b, дает в точности а, т. е. b⋅q = a;

б) либо найти два таких целых числа q и r, чтобы имело место равенство: а = b⋅q + r, причем 0 ⩽ r < b.

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

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

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

Пусть а — любое целое число, b — натуральное (целое положительное) число. Рассмотрим числа, кратные b:

Если эти целые кратные нанести на числовую прямую, то получим отрезки, каждый длины b, отложенные от нуля по обе стороны. Каково бы ни было целое число а, оно либо совпадет с одним из концов таких отрезков, и тогда a = b⋅q, либо попадет внутрь одного из них, и тогда а = b⋅q + r, где 0 < r < b.

Например: а = 8, b = 2, значит, q = 4;

1. а) Найдите q, если: а = 27, b = 9; а = — 38, b = 2. б) Найдите q и r, если: а = 31, b = 5; а = 121, b = 13; а = — 87, b = 5; а = — 121, b = 13.

2. Можно ли утверждать, что если а = b⋅q + m, то m есть остаток от деления а на b? Рассмотрите примеры: 24 = 7⋅3 + 3; 31 = 7⋅3+10; 20 = 7⋅3—1, где b = 7.

Напомним, что рассмотренные выше числа a, b, q и r называются соответственно делимым, делителем, частным и остатком.

Если условимся рассматривать и остаток, равный нулю, то получим:

каково бы ни было целое число а и натуральное число b, всегда найдутся такие целые числа q и r, чтобы, во-первых, имело место равенство а = b⋅q + r и во-вторых, чтобы имело место неравенство 0 < r < b.

Если r = 0, то говорят, что b делит а, или что а делится на b. Предложение: «а делится на b» обозначают так: а⋮ b (читается: а делится на b). Число b называется делителем числа a, a число а называется кратным b.

Если остаток г не равен нулю, то говорят, что «число а не делится на число b», и это предложение обозначают так: а не ⋮ b.

3. Какой наименьший положительный делитель имеет число а?

4. Какой наибольший делитель имеет число а?

5. Докажите, что любое целое число а ≠ 0 не может иметь более | а | положительных различных делителей.

II. Таким образом, мы знаем, что целое число а делится на натуральное число b ≠ 0 тогда и только тогда, когда существует такое третье целое число q, что a = b⋅q. Теперь можно рассмотреть основные теоремы о делимости целых чисел, известные из курса арифметики.

Теорема 1. Если каждое из двух слагаемых делится на одно и то же число, то и их сумма разделится на это число1.

Доказательство. Пусть а⋮b и с ⋮ b, значит, существуют такие целые числа q1 и q2, что а = bq1, с = bq2- Но тогда а + с = bq1 + bq2 = b (q1 + q2). Сумма двух целых чисел q1 + q2 есть число целое. Обозначив его через q = q1 + q2, получим: а + с = bq, значит, сумма а + с делится на b.

1 Для краткости в дальнейшем будем говорить «число» вместо «целое число».

6. Докажите эту же теорему для случая трех слагаемых.

7. Если уменьшаемое и вычитаемое делятся на одно и то же число, то и их разность разделится на это число. Докажите.

8. Докажите следующие утверждения:

Докажем еще одну теорему.

Теорема 2. Если одно из слагаемых не делится, а остальные делятся на одно и то же число, то их сумма не разделится на это число.

Доказательство. Пусть а ⋮ b, но с не ⋮ b. Предположим, что их сумма (а + с) ⋮ b, тогда а + с = bq, откуда с = bq— а. Так как bq⋮b и а ⋮ b (по условию), то и их разность с должна делиться на 6, что противоречит условию. Следовательно, сумма а + с не может делиться на b.

9. Верно ли утверждение: «Если сумма двух слагаемых делится на какое-нибудь число, то и каждое слагаемое делится на это же число»? Приведите примеры, подтверждающие это.

10. Верно ли утверждение: «Если ни одно слагаемое не делится на какое-нибудь число, то и сумма не разделится на это число»? Приведите примеры, подтверждающие ваш ответ.

III. Мы видели, что каково бы ни было целое число а и натуральное число b, всегда можно найти такие целые числа q и r, что а = bq + r, где 0 < r < b.

Докажем, что такие целые числа q (частное) и r (остаток) определяются единственным образом.

Предположим, что существуют такие q1 и r1 и q2 и r2, что a = bq1 + r1 и а = bq2 + r2, причем 0 ⩽ r1 < b и 0 ⩽ r2 < b. Примем, для определенности, что r2 ⩾ r1. Тогда имеем: bq1 + r1 = bq2 + r2, или bq1 — bq2 = r2 — r1, откуда r2 — r1 = b (q1 — q2). Мы видим, что r2 — r1 делится на b, a это возможно только тогда, когда

r2 — r1 = 0, ибо 0 ⩽ r2 — r1 < b. Получим: b (q1 — q2) = 0, но b ≠ 0, значит, q1 — q2 = 0. Следовательно, r2 = r1 и q1 = q2.

Мы доказали, что существует единственная пара целых чисел q иr таких, что а = bq + r, причем 0 < r < b.

Упражнения

11. Докажите, что если остатки от деления двух чисел а и с на число b равны между собой, то разность a — с делится без остатка на b.

12. Докажите обратное утверждение: если разность двух чисел a и с делится на число b, то остатки от деления а и с на b равны между собой.

13. Верны ли утверждения: 1) Если число делится на 4, то оно делится и на 2. 2) Если число делится на 2, то оно делится и на 4.

14. Верны ли утверждения: 1) Если число не делится на 5, то оно не делится на 10. 2) Всякое число, не делящееся на 10, не делится на 5.

15. Докажите следующие утверждения:

1) Сумма двух нечетных чисел есть число четное.

2) Сумма четного и нечетного числа есть число нечетное.

3) Сумма трех последовательных целых чисел делится на 3.

4) Сумма двузначного числа и числа, написанного теми же цифрами, но в обратном порядке, делится на 11.

5) Разность между двузначным числом и числом, на, писанным теми же цифрами, но в обратном порядке, делится на 9.

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

17. Ниже приведены четыре утверждения. Определите, какие из них верны, а какие неверны.

1) Если сумма двух чисел — число четное, то каждое из слагаемых — число четное.

2) Если сумма двух чисел — число четное, то их разность — число четное.

3) Если произведение двух чисел — число нечетное, то каждый из сомножителей — число нечетное.

4) Если сумма двух чисел — число нечетное, то их произведение — число четное.

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

19. Докажите, что если а число целое: то: 1) a2 —а делится на 2; 2) a3 —а делится на 3.

20. Докажите, что разность квадратов: 1) двух последовательных целых чисел есть число нечетное; 2) двух последовательных нечетных чисел делится на 8; 3) двух последовательных четных чисел делится на 4.

§ 2. ПРИЗНАКИ ДЕЛИМОСТИ

I. Из курса арифметики мы знаем признаки делимости чисел на 2, на 5, на 3 и на 9 и можем, не выполняя деления, определить, разделится ли нацело данное число на любое из указанных четырех чисел. Доказанные в предыдущем параграфе теоремы позволяют вполне строго доказать все эти признаки и вывести некоторые новые.

Пусть мы имеем (n + 1)-значное число1, записанное с помощью цифр an, an-1, ... , a1, a0 в десятичной системе счисления:

Требуется найти условия делимости этого числа N на некоторое число р. Обозначим частные и остатки от деления 10k на число р через qk и rk, где k = 1, 2, ... , n.

Подставив полученные выражения для 10k в запись числа N, получим:

1 В этом параграфе рассматриваются только натуральные числа.

Преобразовав это выражение для N, найдем:

Обозначим второе слагаемое буквой М:

Мы видим, что если число M делится на р, то и N будет делиться на р, а если M не делится на р, то и N не делится на р. Этим мы доказали следующую теорему1:

Данное число N делится на число р тогда и только тогда, когда сумма произведений цифр числа N на остатки, полученные от деления соответствующих степеней 10 на число р, делится на это число р.

а) Пусть р = 2. Очевидно, что тогда r1 = 0; r2 = 0; ... ; rn = 0, значит, M = a0; следовательно:

на 2 делятся те и только те числа, последняя цифра которых делится на 2.

б) Таким же образом получаем признак делимости чисел на 5, так как r1 = r2 = ... = rn = 0, значит, M = a0; следовательно:

чтобы число делилось на 5, необходимо и достаточно, чтобы последняя цифра была 0 или 5.

в) Выведем признак делимости чисел на 9. Так как

то очевидно, что r1 = 1; r2 = 1; ... ; rn = 1, значит, М = an+ an-1 + ... + a1 + a0; следовательно:

для того чтобы число делилось на 9, необходимо и достаточно, чтобы сумма его цифр делилась на 9.

г) Подобным образом выводится и признак делимости чисел на 3. Остатки от деления степеней 10 на 3 будут: r1 = 1; r2 = 1; ... ; rn = 1, значит, M = an + an-1 + . .. + a1 + a0; следовательно:

для того чтобы число делилось на 3, необходимо и достаточно, чтобы сумма его цифр делилась на 3.

1 При делении 1 = 100 на р всегда получаем остаток, равный 1.

II. Рассмотрим делимость чисел на 11. Нетрудно убедиться, что остатки от деления степеней 10 на 11 будут 10 или 1, в зависимости от того, будет ли показатель степени 10 нечетным или четным числом.

Но 10 = 11 — 1, поэтому удобно заменить

Поступая аналогичным образом с r3, r5, . .. , число M представим в виде суммы двух слагаемых, одно из которых делится на 11:

следовательно:

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

Например, число 368312 не делится на 11, ибо разность (3 + 8+ 1) — (6+ 3 + 2) = 1 не делится на 11. Если взять число 271436, то у него соответствующая разность сумм цифр (2 + 1 + 3) — (7 + 4 + 6) = — 11 делится на 11, значит, и само число делится на 11.

21. Определите, какие из следующих чисел делятся на 11:

III. Рассмотрим признак делимости чисел на 4. Так как 100 делится на 4, а 10 = 4⋅2 + 2, то r1 = 2; r2 = 0; r3 = 0; ... ; rn = 0. Значит, M = a0 + 2а1; следовательно:

на 4 делятся те и только те числа, у которых сумма цифр единиц и удвоенной цифры десятков делится на 4.

Признак делимости чисел на 4 обычно формулируется в другой, более удобной для применения форме. Любое число N можно представить в виде N = А⋅100 + 10а1 + a0, где A — число, выраженное цифрами числа N без a1 и a0. Здесь М = 10a1 + a0 есть число, выраженное двумя последними цифрами. Так как 100 = 4⋅25, можно утверждать:

на 4 делятся те и только те числа, у которых две последние цифры выражают число, делящееся на 4.

22. Определите, какие из следующих чисел делятся на 4:

23. Учитывая, что 100 делится на 25 и на 50, выведите признаки делимости чисел на 25 и на 50.

IV. Рассмотренные признаки делимости чисел существенно связаны с представлением чисел именно в десятичной системе счисления. Эти признаки, вообще говоря, неприменимы при других системах счисления1.

Например, в пятеричной системе числа, оканчивающиеся нулем, могут делиться на 2, а могут и не делиться на 2.

Если основание системы обозначить буквой d, то любое число N можно записать в виде:

Рассуждая, как и в случае десятичной системы, мы получим теорему:

Данное число N делится на число р тогда и только тогда, когда сумма произведений цифр числа N на остатки, полученные от деления соответствующих степеней основания системы счисления (d° = 1, d, d2 ,... , dn) на число р, делится на это число р.

Пусть d = 4; р = 3.

Все остатки от деления степеней числа 4 на 3 равны 1, значит, М = an + an-1 + ... + a2 + a1 + a0. Следовательно:

в четверичной системе на 3 делятся те и только те числа, сумма цифр которых делится на 3.

Упражнения

24. Учитывая, что 1000 = 8⋅125, выведите признаки делимости чисел на 8 и на 125.

25. Вместо вопросительных знаков поставьте такие цифры, чтобы каждое из данных чисел, изображенных в десятичной системе, делилось:

1 Если вы не знакомы с недесятичными системами счисления, то этот раздел следует опустить вместе с упражнениями № 28—36.

26. Из каждого ряда чисел одно нужно удалить: оно не обладает свойством, которое есть у остальных чисел. Какое это число?

27. Взяли 5 листов бумаги. Некоторые из них разрезали на шесть частей. Некоторые из получившихся листков снова разрезали на шесть частей. После того, как это проделали несколько раз, сосчитали число получившихся кусков. Их оказалось 54. Как показать, что при подсчете произошла ошибка?

28. Сформулируйте признаки делимости:

1) на 10 для чисел, записанных в десятичной системе;

2) на 2 для чисел, записанных в двоичной системе;

3) на 3 для чисел, записанных в троичной системе;

4) на 5 для чисел, записанных в пятеричной системе;

5) на любое данное число, большее единицы, для чисел, записанных в системе счисления, основанием которой является это же число.

29. Сформулируйте признак делимости на 2 для чисел, записанных в системе счисления с четным основанием (2, 4, 6, 8).

30. 1) Если рассматривать числа в восьмеричной системе, то как сформулируется признак делимости на 4? Сравните с признаком делимости на 5 в десятичной системе.

2) Сформулируйте признак делимости на 3 в шестеричной системе.

31. Сформулируйте признак делимости:

1) на 9 для чисел, записанных в десятичной системе;

2) на 2 для чисел, записанных в троичной системе;

3) на 6 для чисел, записанных в семеричной системе;

4) на 7 для чисел, записанных в восьмеричной системе;

5) на любое данное число для чисел, записанных в системе счисления, основание которой на 1 больше данного числа.

32. Сформулируйте признак делимости:

1) на 3 для чисел, записанных в десятичной системе;

2) на 2 для чисел, записанных в пятеричной системе;

3) на 3 для чисел, записанных в семеричной системе.

33. Определите, какие из следующих чисел являются четными (делятся на 2):

34. Определите, какие из следующих чисел делятся на 3:

35. Определите, какие из следующих чисел делятся на 5:

36. Определите, какие из следующих чисел делятся на 7:

§ 3. СОСТАВНЫЕ И ПРОСТЫЕ ЧИСЛА

I. Натуральное число называется простым, если оно имеет два и только два различных натуральных делителя (единицу и само число), и составным, если у него более двух различных натуральных делителя.

Число 1 не принадлежит ни к простым, ни к составным числам. Всякое же натуральное число, большее единицы, является либо простым, либо составным.

Докажем несколько теорем, относящихся к простым числам.

Теорема. Всякое составное число имеет по крайней мере один простой делитель.

Доказательство. Всякое составное число должно иметь делители, большие единицы. Среди этих делителей будет наименьший, обозначим его буквой р. Этот наименьший делитель будет простым числом. Если бы он был составным числом, то имел бы некоторый делитель d, больший единицы и меньший р. Но тогда первоначальное число, делясь на р, делилось бы и на его делитель d, меньший р, чего быть не может, ибо р — наименьший делитель.

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

38. Если р ≠ 1 — наименьший из делителей составного числа N, то p2 ⩽ N. Докажите.

39. Как следствие из предыдущего утверждения докажите, что если число N > 1 не делится ни на одно простое число, квадраты которых не больше, чем N, то N является простым числом.

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

Теорема. Ряд простых чисел

бесконечен (то есть существуют сколь угодно большие простые числа).

Еще в древней Греции знаменитый математик Евклид (III в. до н. э.) доказал эту теорему.

Доказательство. Предположим, что простых чисел конечное число и обозначим наибольшее из них буквой р. Перемножим все эти простые числа и прибавим к полученному произведению еще 1. Получим некоторое число N.

N = 2⋅3⋅5⋅7⋅11⋅ ... ⋅р + 1.

Это число N не может быть простым, ибо оно больше р, а по нашему предположению самое большое простое число — это р. Но оно не может быть и составным. Первое слагаемое 2⋅3⋅5⋅ ... ⋅р делится на любое простое число, ибо по предположению здесь перемножаются все простые числа. Значит, при делении на любое простое число всегда в остатке будет единица, то есть число N не может иметь простых делителей. А по предыдущей теореме всякое составное число имеет простой делитель.

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

41. В 1850 году П. Л. Чебышев доказал, что между любым натуральным числом, большим единицы, и числом,

1 Наибольшее число, о котором в настоящее время известно, что оно простое — 22281 — 1.

вдвое большим его, всегда имеется хотя бы одно простое число1.

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

II. Как определить, является ли данное число простым или составным? Для небольших чисел это сделать несложно, достаточно лишь найти все его делители. Например, числа 2, 3, 5, 7, 11, 13, ... — простые, а числа 4, 6, 8, 9, 10, 12, ... — составные. Но если данное число велико, то такой способ установления вида числа требует много времени.

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

Существенные упрощения получаем при наличии таблицы простых чисел. В учебнике И. Н. Шевченко, Арифметика, V—VI классы приведена таблица всех простых чисел до 1000. В настоящее время составлены таблицы простых чисел, простирающиеся до миллионов.

Рассмотрим наиболее простой способ составления таблицы простых чисел, который называется «решетом Эратосфена» по имени выдающегося греческого астронома и математика, жившего в 276—192 гг. до нашей эры.

Пусть, например, требуется выделить все простые числа из первой сотни. Составим таблицу из ста клеточек, в которые впишем все натуральные числа от 1 до 100 (см. рис.). Вычеркиваем 1, так как единица — число не простое. Следующее число 2 — простое, его сохраняем.

Вычеркиваем все числа, кратные 2, кроме 2, то есть вычеркиваем все числа через одно, начиная с 4.

1 Фактически теорема утверждает, что какое бы ни было натуральное число n > 3, между n и 2n — 2 содержится хотя бы одно простое число.

Вычеркиваем теперь все числа, кратные 3, кроме 3, ибо 3 — число простое.

Первое после 3 незачеркнутое число 5; оно простое, так как не делится ни на одно меньшее его простое число. Отсчитываем от него числа по пять и каждое пятое вычеркиваем.

Подобным образом вычеркиваем и все составные числа, делящиеся на 7.

Так как следующее простое число 11, причем 112 больше 100, следовательно, все оставшиеся невычеркнутыми числа в первой сотне — простые.

42. Используя полученную таблицу, определите, какие из следующих чисел простые, а какие составные:

41; 57; 59; 67; 91; 97.

43. Методом «Эратосфенова решета» составьте таблицу всех простых чисел, меньших 200. Подсчитайте, сколько всего простых чисел среди чисел первой сотни и сколько среди чисел второй сотни.

III. Сформулируем теорему о разложении чисел на простые множители.

Любое число, большее единицы, или простое, или может, быть представлено в виде произведения простых чисел, то есть разложено на простые множители.

Доказательство. Если число N > 1 простое, то утверждение доказано. Если же число N составное, то по доказанной ранее теореме оно имеет простой делитель p1. Тогда N = p1⋅n1, причем 1 < n1 < N, ибо 1 < p1 < N.

Если n1 — число простое, то теорема доказана, если же n1 — число составное, то оно имеет простой делитель p2 и n1 = p2⋅п2, причем 1 < n2 < n1; тогда N = p1⋅p2⋅n2.

Если n2 — число простое, то теорема доказана; если оно составное, мы продолжаем наши рассуждения.

Так как N > n1; n1 > n2; n2 > n3; ... , то наши рассуждения должны рано или поздно закончиться, ибо целых положительных чисел, меньших N, конечное число. Но закончиться данный процесс может только тогда, когда какое-нибудь nk-1 = pk окажется числом простым.

Полученное разложение: N = p1⋅р2⋅р3⋅ ...⋅pk и будет искомым разложением числа N на простые множители. Следовательно, возможность представления числа N в виде произведения простых чисел доказана.

Можно вполне строго доказать и единственность такого разложения (см. задачу № 156).

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

44. Разложите на простые множители следующие числа:

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

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

В общем случае каноническое разложение числа N будет иметь вид:

где p1, p2, ..., pn — различные простые числа, а α1, α2, ... , αп— натуральные числа.

45. Напишите канонические разложения следующих чисел:

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

Известны попытки отыскания формул, которые хотя и не выражают всех простых чисел, но позволяют найти сколь угодно большое простое число. Например, французский математик XVII в. П. Ферма нашел, что формула 2n+ 1 дает простые числа при значениях n, равных

Ферма высказал предположение, что формула 2n + 1 должна давать простые числа при всяком n, равном степени 2. Это предположение долгое время принималось

как верное утверждение. Дальнейшая проверка (а эти числа при возрастании степени 2 увеличиваются очень быстро!) подтвердила, что при n = 24 = 16 число 216 +1 = 65537 является простым.

Впервые это утверждение было опровергнуто знаменитым математиком Л. Эйлером (XVIII в.), членом Петербургской Академии наук, который доказал, что при n = 25 формула 2n + 1 дает число 4294967297, делящееся на 641.

Большой интерес для ученых представляли, да и сейчас еще не утратили своего интереса, вопросы распределения простых чисел в натуральном ряду. Легко заметить, что простые числа с возрастанием натуральных чисел встречаются все реже. Например, в первой сотне натуральных чисел имеется 25 простых чисел, во второй — 21, в третьей—16. В первой тысяче натуральных чисел 168 простых чисел, во второй тысяче—135. Можно доказать (см. задачу № 148), что существуют сколь угодно длинные участки натурального ряда, сплошь состоящие из составных чисел.

С другой стороны, существует много пар следующих друг за другом нечетных чисел, которые оба являются простыми, например пары 3 и 5; 5 и 7; 11 и 13; 17 и 19; 29 и 31; 41 и 43. Такие пары называются парами чисел близнецов.

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

Важнейшие результаты о законах чередования простых чисел в натуральном ряду были получены величайшими математиками Л. Эйлером и П. Л. Чебышевым.

Упражнения

46. 1) Можно ли число 1 назвать простым числом? А составным?

2) Найти закономерность, по которой построена следующая последовательность чисел:

2; 3; 5; 7; 11; 13; 17; 19; ...

1 Пока наибольшей известной парой близнецов являются числа 1 000 000 009 649 и 1 000 000 009 651.

47. 1) Может ли сумма двух простых чисел быть числом простым?

2) Может ли быть простым числом сумма двух простых чисел, больших 2?

48. (Шутка.) Покажите, что при всех целых значениях x числа вида 1х + 2 — простые.

49. Докажите, что если простое число р делится на простое число q, то р = q.

50. Проверьте, какие из следующих чисел простые, а какие — составные:

51. Разложите на простые множители произведение

(Кратко оно записывается так: 10! и читается «10 — факториал»)1.

52. В какой степени простое число 2 входит в каноническое разложение числа 12!?

53. В какой степени простое число 5 входит в каноническое разложение числа 20!?

54. Сколькими нулями оканчивается число 20!?

55. Сколькими нулями оканчивается число 100!?

§ 4. НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ2

В этом параграфе помещен теоретический материал и соответствующие упражнения, рекомендуемые для тех учащихся, которые в арифметике не изучали наибольший общий делитель двух чисел. Решение упражнений № 56 — 63 из данного параграфа подготовит читателя к восприятию довольно сложного теоретического материала следующего параграфа.

56. 1) Сколько различных делителей имеет число 1⋅2⋅3⋅5?

2) Сколько различных делителей имеет число 2⋅3⋅5⋅7?

1 При решении задач № 51 — 55 сами данные числа не вычисляются.

2 В этом параграфе рассматриваются лишь натуральные числа.

3) Сколько различных делителей имеет число 1⋅2⋅3⋅4⋅5?

57. 1) Число 90 разложите на простые множители и найдите все делители этого числа.

2) Найдите все делители числа 140.

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

58. 1) Найдите все общие делители чисел 90 и 140, используя ответ к задаче № 57.

2) В одной школе 90, а в другой 140 физкультурников. На физкультурном параде обе школы должны пройти колоннами с равным числом учащихся в каждом ряду. Какие имеются возможности построения таких колонн?

Наибольшим общим делителем данных чисел называется самый больший из их общих делителей. Можно сказать иначе:

Наибольшим общим делителем данных чисел называется самое большое число, на которое делятся все эти числа.

Например, для чисел 12 и 8 наибольшим общим делителем будет число 4 (проверьте!), что сокращенно обозначают так: НОД (12,8) = 4.

59. Найдите НОД (90, 140), используя решение задачи № 58.

60. 1) Числа 18 и 30 разложите на простые множители, найдите их общие делители и запишите наибольший общий делитель.

2) Найдите НОД (120, 420).

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

Разложим числа 120 и 420 на простые множители:

Простыми общими делителями этих чисел являются простые множители, имеющиеся как в одном, так

и во втором разложении. Составные общие делители можно получить только лишь при перемножении одинаковых простых множителей.

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

Отсюда находим, что НОД (120, 420) = 60.

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

Найдем, например, НОД (120, 540). Запишем их разложения на простые множители:

Сравнивая простые множители в этих разложениях, видим, что общими являются следующие простые множители: 2, 2, 3 и 5. Каждый из них будет общим делителем 120 и 540. Перемножая их по два, по три и даже все четыре, будем получать общие делители, а наибольший получим, если перемножим все четыре общие делители.

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

61. Найдите наибольший общий делитель следующих чисел:

62. Имеется 70 апельсинов, 175 орехов и 210 конфет. Какое наибольшее число одинаковых подарков для детей можно сделать из этого запаса?

Из способа нахождения наибольшего общего делителя разложением на множители видно, что любой общий делитель данных чисел является делителем НОД,

и, наоборот, всякий делитель НОД является общим делителем данных чисел. Поэтому иногда дают несколько иное определение НОД, а именно:

НОД данных чисел называется такой их общий делитель, который делится на все общие делители этих чисел.

63. Найдите все общие делители чисел 48 и 60, предварительно найдя их наибольший общий делитель.

§ 5. АЛГОРИТМ ЕВКЛИДА

I. Возьмем произвольное натуральное число N и разложим его на простые множители. Пусть N = p1⋅p2⋅ ... prk. Очевидно, что каждый из этих множителей будет простым делителем данного числа N.

Перемножая их по два, по три, по четыре и так далее, будем получать составные делители данного числа. Следует учитывать, что каждое число имеет делитель 1.

64. 1) Найдите все делители числа 30, разложив его предварительно на простые множители.

2) То же для числа 81.

Решая последний пример, видим, что если N = 34, то его делителями являются следующие степени числа 3:

Аналогично, если число N = pk, где р— простое число, a k — натуральное число, то каждое число вида рα, где 0 ⩽ α ⩽ k, является делителем числа N.

Пусть N = pkqs, где р и q —простые числа, a k и s — натуральные числа. Нетрудно убедиться, что все числа вида d = pαqβ, где 0 ⩽ α ⩽ k и 0 ⩽ ß ⩽ s, являются делителями числа N. Действительно, так как k — α ⩾ 0 и s — ß ⩾ 0, то число pk-αqs-β является целым числом.

Подобным образом получаем, что если

— каноническое разложение числа N то каждое произведение вида

является делителем числа N.

Позже (см. задачу № 162) будет доказано, что любой делитель числа N = p1α1⋅p2α2⋅ ... ⋅ pnαn можно представить

в виде

Будем применять пока это утверждение без доказательства.

Пусть, например, требуется найти все делители числа

Они имеют вид

Следовательно, делителями числа 120 будут следующие числа:

65. Найдите все делители следующих чисел:

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

II. Возьмем два произвольных натуральных числа N1 и N2. Они имеют общий делитель 1. Возможны и другие общие делители этих чисел.

Наибольшим общим делителем данных чисел называется наибольшее число, на которое делятся эти числа.

Докажем его существование и единственность.

Любое натуральное число N не может иметь делителей, больших этого числа N, значит, все положительные делители числа N заключены между числами 1 и N. Следовательно, число различных делителей числа N конечно.

Но если число делителей у числа N1 конечно, и число делителей у числа N2 конечно, то и число общих делителей этих чисел конечно. Значит, среди этих общих делителей, число которых конечно, есть наибольший и притом один.

Наибольший общий делитель чисел N1 и N2 обозначают так: (N1, N2), а в школьных учебниках употребляется

и такая запись: НОД (N1, N2). Например, НОД (6,8) = 2; НОД (24,12) = 12; НОД (8,9) = 1.

Если два числа не имеют никаких других общих делителей, кроме 1, то такие числа называются взаимно простыми. Например, числа 15 и 22 взаимно простые, ибо НОД (15,22) = 1.

Так как все делители числа N имеют вид

то можно найти вид общих делителей двух данных чисел.

Пусть

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

Например, N1 = 23⋅33⋅7 и N2 = 2⋅35⋅52. В разложение любого общего делителя чисел N1 и N2 могут входить только простые числа 2 и 3, причем 2 в степени не выше первой, а 3 — в степени не выше третьей. Наибольший общий делитель получим, если каждый из общих простых множителей взять в наивысшей возможной для него общей степени. НОД (N1, N2) = 2⋅33 = 54.

67. Найдите наибольшие общие делители следующих пар чисел: (24,84); (120,420); (323,816).

68. 1) Докажите, что каждый делитель НОД данных чисел является общим делителем этих чисел.

2) Докажите, что всякий общий делитель данных чисел является делителем их наибольшего общего делителя.

III. Рассмотренный нами способ нахождения наибольшего общего делителя разложением на множители не всегда является рациональным, простым. Пусть, например, требуется найти НОД (464899, 232921). Вся трудность состоит в том, чтобы разложить эти числа на простые множители. Не так легко и быстро найти, что 464899 = 17⋅23⋅29⋅41 и 232921 = 13⋅19⋅23⋅41. Поэтому рассмотрим еще один способ нахождения наибольшего общего делителя двух чисел: метод последовательного деления.

Этот метод основан на двух утверждениях.

1) Если большее из двух данных чисел делится на меньшее, то наибольшим общим делителем этих двух чисел будет меньшее число.

Например, НОД (48,12) = 12.

Действительно, большее число делится на меньшее и меньшее число делится само на себя, значит, меньшее число есть общий их делитель.

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

69. Найдите наибольший общий делитель чисел: 75 и 25; 252 и 42; 216 и 27.

2) Если большее из двух данных чисел не делится на меньшее, то наибольший общий делитель данных чисел равен наибольшему общему делителю двух других чисел: меньшего из данных чисел и остатка, полученного от, деления большего числа на меньшее.

Например, при делении 72 на 16 получим в остатке 8, значит, НОД (72,16) = НОД (16,8).

Доказательство. Пусть а и b— любые два натуральные числа, причем 1 < b < а. Так как а не ⋮ b, то найдутся такие целые числа q и r, что а = bq + r, где 0 < r < b.

Всякий общий делитель d чисел b и r будет являться и делителем числа а, ибо если b⋮d и r⋮d, то и а ⋮ d, так как а = bq + r.

С другой стороны, возьмем произвольный общий делитель d1 чисел а и b. Тогда r = а — bq также будет делиться на этот делитель d1, значит, делитель d1 является общим для r и b.

Получили, что общие делители чисел а и b и чисел b и r совпадают, но тогда совпадают и их наибольшие общие делители.

Итак, НОД (а, b) = НОД (b, r).

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

Так как остаток меньше делителя, то всегда получаем

новую пару чисел (меньшее число и остаток), меньших, чем исходные числа. Найдем, например, НОД (96,36).

значит, НОД (96,36) = НОД (36,24).

Рассуждая таким же образом, для чисел 36 и 24 получим:

36 = 1⋅24+ 12, значит, НОД(36,24) = НОД(24,12).

Число 24 делится на 12, поэтому НОД(24,12) = 12.

Итак, НОД (96,36) = НОД (36,24) = НОД (24,12) = 12.

Рассмотрим общий случай. Пусть a = bq1 + r1, где 0 ⩽ r1 < b.

Если r1 = 0, значит, a ⋮ b и НОД (а, b) = b. Если же r1 > 0, то по второму утверждению НОД (а, b) = НОД(b, r1).

Делим b на r1, пусть b = r1⋅q2 + r2, где 0 < r2 < r1. Если r2 = 0, то НОД (b, r1) = r1,а значит и НОД (a, b) = r1 Если же r2 > 0, то вновь делим r1 на r2, и так далее.

Этот процесс, каковы бы ни были числа а и b, после определенного числа повторений такого последовательного деления, обязательно закончится, ибо b1 > r1 > r2 > r3 > > ... ⩾ 0, а натуральных чисел, меньших 6, конечное число. Следовательно, должны найтись такие остатки rn-1 и rn, что rn-1 ⋮ rn.

Тогда НОД (а, b) = НОД (b, r1) = НОД (r1, r2) = ... = НОД(rn-1, rn) = rn.

70. 1) Найдите НОД(464899, 232921).

Решение. Покажем, как удобно располагать записи при последовательном делении.

2) Найдите НОД (270, 114).

Решение.

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

Теперь очень хорошо видно, что остатки всякий раз уменьшаются. Это же будет иметь место и для любой другой пары чисел, а поэтому такое последовательное деление всегда после нескольких шагов закончится (хотя бы делением на 1).

Чтобы найти наибольший общий делитель двух чисел, делят большее число на меньшее, меньшее на первый остаток, первый остаток на второй остаток, второй на третий и так далее, до тех пор, пока не получится в остатке нуль. Тогда последний делитель и будет наибольшим общим делителем данных чисел.

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

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

Алгоритмом (или алгорифмом) в средние века называли правило, по которому выполняется то или иное арифметическое действие. Это слово происходит от имени великого узбекского математика Ал-Хорезми, который в IX веке сформулировал подобные правила.

В современной математике алгоритм — это такое предписание о выполнении в определенном порядке некоторой системы операций, позволяющее решать задачи определенного класса.

71. 1) Способом последовательного деления найдите наибольший общий делитель следующих пар чисел: 60 и 45; 56 и 42; 221 и 130; 273 и 170; 391 и 299; 15456 и 14041.

2) Способом последовательного деления найдите наибольший общий делитель чисел: а) 12, 18 и 30; б) 6, 10 и 15; в) 350, 231 и 105; г) 1260, 2310 и 1995.

Указание. Так как общий делитель любых двух чисел является делителем их наибольшего общего делителя, то наибольший общий делитель трех чисел N1, N2 и N3 либо совпадает с d = НОД(N1, N2) (когда N3 делится на d), либо будет делителем d. Следовательно, чтобы найти способом последовательного деления наибольший общий делитель трех или более чисел, находят наибольший общий делитель каких-нибудь двух из них, потом — наибольший общий делитель найденного делителя и какого-нибудь третьего данного числа, затем — наибольший общий делитель последнего делителя и четвертого данного числа и так далее.

Упражнения

72. Найдите двумя способами (разложением на множители и последовательным делением) наибольший общий делитель чисел:

Сравните оба способа.

73. 1) Туристы проехали на велосипедах в первый день 56 км, а во второй — 72 км, причем каждый день были в пути целое число часов. Найдите скорость движе-

ния, если известно, что она выражалась целым числом километров в час, была все время одинакова и наибольшая из возможных.

2) Туристы прошли в первый день 36 км, во второй — 32 км и в третий — 24 км, причем каждый день были в пути целое число часов. Сколько часов они были в пути, если их скорость выражалась целым числом километров в час, была постоянной и наибольшей из возможных?

74. В одном скором поезде 432 пассажирских места, во втором — 576 и в третьем — 480. Сколько вагонов имеет каждый поезд, если известно, что в каждом вагоне одинаковое число пассажирских мест, наибольшее из возможных?

§ 6. НАИМЕНЬШЕЕ ОБЩЕЕ КРАТНОЕ

I. Возьмем два натуральных числа а и b. Всякое число, делящееся на а и делящееся на b, называется общим кратным чисел а и b. Очевидно, что число 0 делится на любые числа а и b. Но мы будем рассматривать лишь положительные общие кратные.

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

Установим его существование и единственность.

Очевидно, что произведение а⋅b является общим кратным чисел а и b. Возможны и меньшие, чем a⋅b натуральные числа, делящиеся как на а, так и на b.

Натуральных чисел, не больших, чем а⋅b, конечное число, значит, можно проверить, которые из них кратны и а и 6, и выбрать среди этих нескольких общих кратных наименьшее. Следовательно, наименьшее общее кратное любых двух натуральных чисел существует и притом одно.

Заметим, что общих кратных а и b бесконечное множество, ибо всякое число вида q⋅(ab) является общим кратным а и 6, каким бы ни было натуральное число q.

Наименьшее общее кратное чисел а и b обозначается [а, b]; в школьной математике обычно употребляется обозначение НОК(а, b). Например, НОК(15, 20) = 60; НОК(8, 9) = 72.

II. Понятие общего кратного двух чисел связано с понятием их общего делителя. Докажем следующие две теоремы.

1) Если d — общий делитель чисел а и b, то произведение а ⋅ b делится на d. Частное является кратным а и b.

Доказательство. Так как a⋮d и b⋮d, то а = d ⋅ q1 и b = d⋅q2. Поэтому а⋅b = (dq1)⋅(dq2) = d(dq1q2). Мы видим, что ab ⋮ d, причем частное ab/d = dq1q2. Оно делится на а и на b, ибо ab/d = (dq1)q2 = aq2 и ab/d = (dq2)q1 = bq1.

Следовательно, каждому общему делителю чисел а и b соответствует общее кратное этих чисел, не большее, чем а⋅b.

2) Если m = HOK(a, b), то ab⋮m, причем частное ab/m является общим делителем а и b.

Доказательство. Пусть ab = mq + r, где 0 ⩽ r < < m. Поскольку ab делится и на а и на 6, и m делится как на а, так и на 6, то r = ab — mq должно делиться и на а и на b, то есть r есть общее кратное чисел а и b. Но m — наименьшее из положительных общих кратных а и b, следовательно, r = 0.

Обозначим частное ab/m через d, тогда ab/m = d, или ab = md. Докажем, что a ⋮ d и b⋮d.

Равенство ab = md можно записать так: m/a = b/d или m/b = a/d. Но m/a и m/b есть числа целые, так как m = НОК(а, b), то и b/d и a/d — числа целые. Значит, b ⋮ d и а ⋮ d, то есть d — есть общий делитель чисел а и b.

75. Докажите, что если D = НОД(а, b), то ab/D = m, где m = НОК(а, r).

Решив эту задачу, мы можем записать равенство:

а⋅b = НОД(а, b)⋅НОК(а, b).

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

рассматривать эти вопросы, а ознакомимся с еще одним способом отыскания наименьшего общего кратного.

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

а⋅b = НОД(а, b)⋅НОК(а, b)

позволяет находить НОК двух чисел без обязательного разложения данных чисел на простые множители:

НОД можно найти, например, алгоритмом Евклида, а тогда легко найти и их наименьшее общее кратное.

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

76. Найти НОК (2261, 1729).

Решение. Методом последовательного деления найдем, что НОД (2261, 1729) = 133.

Находим, что 2261⋅1729 = 3909269, значит, НОК (2261, 1729) = 3909269 : 133 = 29393.

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

Упражнения

77. Докажите, что НОК двух взаимно простых чисел равно их произведению.

78. Найдите двумя способами наименьшее общее кратное чисел: 35 и 10; 36 и 32; 135 и 108; 1260 и 336.

79. Любым способом найдите НОК следующих чисел: 21 и 28; 60 и 105; 4181 и 4847.

80. Найдите наименьшее общее кратное и наибольший общий делитель чисел: 6, 10 и 14. Сравните произведение трех данных чисел с произведением их наибольшего общего делителя и наименьшего общего кратного.

81. Найдите любым способом НОК чисел:

82. 1) Какой наименьшей длины должны быть доски, чтобы их можно было разрезать поперек как на куски длиной по 40 см, так и на куски длиной по 60 см, и чтобы при этом не получалось обрезков?

2) Какую наименьшую квадратную площадь можно вплотную замостить плитами, размеры которых 6 дм × 8 дм?

83. 1) На столе лежат книги, не более 100. Определите, сколько их, если известно, что их можно связывать в пачки по 3 книги, по 4 книги и даже по 5 книг.

2) В три школьных киоска отправили по одинаковому числу тетрадей. Для одной школы отправили тетради по 150 штук в каждой пачке, для второй — по 100 штук, а для третьей школы — по 200 штук в каждой пачке.

Сколько тетрадей отправили каждой школе, если число тетрадей наименьшее, какое может быть упаковано в целое число пачек?

84. Три теплохода заходят в порт после каждого рейса. Первый теплоход совершает рейс в 3 дня, второй — в 4 дня, а третий — в 5 дней. В понедельник они встретились в порту все вместе. Через какое наименьшее число дней встретится второй теплоход с первым; первый теплоход с третьим; второй теплоход с третьим? Через сколько дней встретятся все три теплохода и в какой это будет день недели?

85. В первом туре школьной олимпиады пятиклассникам было предложено решить дома 16 задач. За каждую верно решенную задачу ученику засчитывали 3 балла, а за неверное решение снимали 5 баллов. При подсчете оказалось, что у Миши нет ни одного балла. Сколько задач он решил верно?

86. 1) Найдите наименьшее число, которое при деле-

нии на 8 дает в остатке 7, а при делении на 9 дает в остатке 8.

2) Найдите наименьшее число, которое при делении:

на 8 дает в остатке 7,

» 7 » 6,

» 6 » 5,

» 5 » 4,

» 4 » 3,

» 3 » 2,

» 2 » 1.

§ 7. СРАВНЕНИЯ И ИХ СВОЙСТВА

I. Решение и обоснование многих задач на делимость чисел, в том числе и выводы признаков делимости, становятся яснее и проще, если пользоваться понятием сравнения и соответствующими обозначениями. Отношение сравнения было введено немецким математиком К. Гауссом, но наиболее полное и глубокое изложение теории сравнений было дано П. Л. Чебышевым в его работе «Теория сравнений».

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

Обозначают это так:

(читается: а сравнимо с b по модулю m).

Если же а и b не сравнимы по модулю m, то пишут: а ≢ b (mod m).

Например: 22 ≡ 7(mod 5); 17 ≡ —4 (mod 7); 102 ≡ 1 (mod 11); 27 ≢ 5 (mod 4).

87. Напишите несколько сравнений по модулю 6, 7, 10.

Сравнения встречаются и в повседневной жизни, например, часовая стрелка указывает время по модулю 12; минутная стрелка указывает время по модулю 60; домашний электросчетчик указывает расход электроэнергии по модулю 1000 (квт⋅ч).

II. Мы знаем, что два числа а и b при делении на m имеют равные остатки тогда и только тогда, если раз-

ность a — b делится без остатка на m (см. № 11 и 12), следовательно:

два числа а и b сравнимы по модулю m тогда и только тогда, когда их разность а — b делится на m.

Этот признак позволяет доказывать многие свойства сравнений.

88. Докажите, что а и b сравнимы по модулю m тогда и только тогда, когда a = b+m-k, где k — целое число.

Решение. Если a ≡ b (mod m), то (а — b)⋮m, значит, существует такое целое число что а — b = k⋅m, откуда а = b + km.

Справедливо и обратное. Если а = b+km, то а—b = km, где целое число; значит, (а — b) ⋮ m, следовательно, a ≡ b (mod m).

89. Проверьте, что: 1) Всегда a ≡ a(mod m).

2) Если a ≡ b(mod m), то b ≡ a(mod m).

3) Если a ≡ b (mod m) и b ≡ с (mod m), то a ≡ c(mod m).

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

Теорема. Сравнения по одному и тому же модулю можно почленно складывать, вычитать и умножать.

Доказательство. Пусть известно, что a ≡ b (mod m) и c ≡ d(mod m), тогда a = b + k⋅m и c = d + s⋅m, где k и s — целые числа. Отсюда получаем:

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

Следствия. 1. К обеим частям сравнения можно прибавить или вычесть одно и то же число, и обе части сравнения можно умножить на одно и то же число.

2. Члены сравнения можно переносить из одной части сравнения в другую с противоположными знаками.

3. Если а ≡ b (mod m), то ak ≡ bk (mod m), где k — любое натуральное число.

4. Пусть Р (х) = апхп + an-1xn-1 + ... + a1х + a0 — лю-

бой многочлен с целыми коэффициентами. Если

III. Последнее следствие служит теоретическим основанием для вывода наиболее важных признаков делимости. Пусть некоторое число N в десятичной системе счисления изображается, считая слева направо, цифрами an, an-1 ..., a1, a0, тогда можно записать:

а) Так как 10 = 9+1, то 10 ≡ 1 (mod 9), откуда 10k ≡ 1 (mod 9). Поэтому N ≡ an + an-1 + ... + a1 + a0 (mod 9).

Следовательно, число N делится на 9 тогда и только тогда, когда на 9 делится сумма его цифр.

Аналогично получается признак делимости на 3.

б) Для любого натурального числа k очевидно, что 10k ≡ 0 по модулю 2, по модулю 5 и по модулю 10, значит, по каждому из них N = a0; получаем известные признаки делимости чисел на 2; 5 и 10.

в) Так как 10 = — 1 + 11, то 10 ≡ — 1 (mod 11). По следствию 4 имеем:

Следовательно, число N при делении на 11 дает тот же остаток, что и сумма его цифр, взятая с чередующимися знаками

В частности, число N делится на 11 в том и только в том случае, если знакочередующаяся сумма его цифр делится на 11.

г) Рассмотрим остатки, получающиеся при делении на 7 последовательных степеней числа 10. Легко находим, что по модулю 7 будет 10 ≡ 3; 102 ≡ 2; 103 ≡ — 1; 104 ≡ — 3; 105 ≡ —2; 106 ≡ 1. Далее остатки повторяются. Следовательно, число N делится на 7 тогда и только тогда, если число M = a0+3а1 + 2а2—а3 — 3а4 — 2а5 + a6 +3а7+ ... делится на 7.

90. Определите остатки от деления на 11 следующих чисел:

91. Какие из следующих чисел делятся на 7:

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

1. Найти остаток от деления числа 5 на 6.

Решение. 5 ≡ — 1 (mod 6), тогда 5k ≡ (— 1)k(mod 6).

Но число k = 7 — нечетное, поэтому Значит, искомый остаток равен 5.

2. Доказать, что число

делится на 7.

Решение.

3. Доказать, что число

не делится на 3.

Решение.

Следовательно, A ≡ 1 + 0 + 1 (mod 3), откуда следует, что при делении числа А на 3 получим остаток 2.

V. В заключение рассмотрим один из случаев, когда сравнения ведут себя иначе, чем равенства. Мы знаем, что если ab = ас и а ≠ 0, то b = с. Выясним, всегда ли возможно деление обеих частей сравнения на одно и то же число, т. е. всегда ли можно сравнение ab = ас сокращать на множитель а.

В сравнении 35 ≡ 77 (mod 6) обе части делятся на 7. Выполнив это деление, мы получим верное сравнение: 5 ≡ 11 (mod 6).

В сравнении 45 = 75 (mod 6) обе части делятся на 15; но, выполнив это деление, мы получаем уже неверное сравнение, ибо 3 ≢ 5(mod 6).

Рассмотрим теперь в общем виде, когда для сравнений

имеет место правило сокращения на общий множитель, иными словами, когда из условия ab ≡ ac и a ≢ 0, следует, что b ≡ с.

Пусть ab ≡ ас (mod m), значит, разность ab — ас = а(b — с) делится на m. Если даже а не ⋮ m, то нельзя утверждать, что b — с делится на m. Но если числа а и m взаимно просты (см. № 153), то тогда b — с обязательно должно делиться на m. Следовательно, если ab ≡ ас (mod m) и НОД (а, m) = 1, то b ≡ c(modm).

Таким образом, обе части сравнения всегда можно разделить на одно и то же число, взаимно простое с модулем.

92. Всегда ли возможно деление обеих частей сравнения на одно и то же число в случае простого модуля?

93. Покажите, что имеет место правило сокращения на общий простой множитель, т. е. если по любому модулю m ab ≡ ac и простое число а не делит m, то b ≡ с.

Упражнения

94. При делении на m число а дает остаток r1, а число b — остаток r2. Можно ли утверждать, что число а⋅b дает остаток r1⋅r2 при делении на m? Как изменить формулировку, чтобы получилось верное утверждение?

95. Докажите следующие утверждения:

1) Если a ≡ b (mod m), то всякий общий делитель чисел а и m будет вместе с тем и общим делителем чисел b и m, и наоборот.

2) Если a ≡ b (mod m), то НОД (а, m) = НОД (b, m).

96. Докажите, что число N делится на число m тогда и только тогда, когда сумма произведений цифр числа N на остатки, полученные от деления соответствующих степеней 10 на число m, делится на это число m.

97. Как установить, что число 100 ... 001, в котором число нулей четное, делится на 11?

98. Покажите, что при любом натуральном n число 52n+1⋅2n+2+ 3n+2⋅22n+1 делится на 19.

99. Выведите признак делимости на 13, подобный выведенному в этом параграфе признаку делимости на 7.

100. Найдите остатки от деления числа 3162819 на 11; на 7; на 13.

101. Найдите остатки от деления на 7 следующих чисел:

102. Известно, что если произведение двух чисел равно нулю, то хотя бы один из сомножителей также равен нулю. Можно ли утверждать, что если произведение двух чисел сравнимо с нулем по модулю m, то хотя бы один из сомножителей также сравним с нулем по модулю m?

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

§ 8. ВЫЧЕТЫ. ТЕОРЕМА ФЕРМА

I. Возьмем натуральное число m = 6 и будем (мысленно!) делить на 6 все целые числа. Группируя числа по остаткам, получим шесть различных классов чисел, объединенных нами в столбцы:

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

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

Число таких классов по модулю m равно m, ибо числа одного класса при делении на m дают один и тот же остаток, а остатками могут быть лишь следующие m чисел: 0, 1, 2, ..., .....m — 1.

Выберем произвольным образом по одному числ у (представителю) в каждом из классов. Получим группу из m чисел, никакие два из которых не сравнимы между собой по модулю m, но любое целое число сравнимо по модулю m с одним из чисел этой группы. Такую группу чисел называют полной системой вычетов по модулю m.

Например, по модулю 6 полными системами вычетов являются группы чисел: (0, 1, 2, 3, 4, 5); (—6, 7, 2, —9, 10, 17) и другие. Очевидно, что полных систем вычетов по любому модулю существует бесконечное множество.

104. Напишите по две полные системы вычетов по модулям 3, 7 и 10.

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

Например, требуется установить делимость числа N = 1663⋅320а+ 104⋅220 + 89 на 13. Нет необходимости выполнять указанные действия и получившийся результат делить на 13. Можно выполнять действия не над самими числами, а над их вычетами по модулю 13.

166 можно заменить вычетами 10 или —3; 320 — вычетами 8 или —5; 24 = 16 заменяем вычетом 3 и т. д. Число N при делении на 13 даст тот же остаток, что и число

Если заметить, что 33 = 27 можно заменить вычетом 1, а 52 = 25 — вычетом —1, то легко найти остаток от деления числа N на 13: — 1 ⋅(— 1) + 1 — 2 = 0.

Возможны и иные приложения такой арифметики вычетов. Надо, например, доказать, что число n5 — n при любом целом n делится на 5. Возьмем полную систему вычетов по модулю 5 в виде (—2, — 1, 0, 1, 2). Легко проверить, что при любом значении n из этих пяти вычетов n5 — n равно числу, делящемуся на 5. Следовательно, n5 — n делится на 5 при любом целом n.

105. Докажите, что n7 — n при любом целом n делится на 7.

III. Выясним теперь, когда значения произведения

а⋅х образуют полную систему вычетов по модулю m, если x пробегает полную систему вычетов по модулю m.

Пусть m = 6 и а = 5. Будем придавать х значения 0, 1, 2, 3, 4, 5. Тогда получим, что по модулю 6: 5⋅0 ≡ 0; 5⋅1 ≡ 5; 5⋅2 ≡ 4; 5⋅3 ≡ 3; 5⋅4 ≡ 2; 5⋅5 ≡ 1. Следовательно, значения произведения 5⋅х также образуют полную систему вычетов по модулю 6.

Возьмем а = 4 при том же значении m = 6. Очевидно, что 4⋅0 ≡ 0; 4⋅1 ≡ 4; 4⋅2 ≡ 2; 4⋅3 ≡ 0; 4⋅4 ≡ 4 и 4⋅5 ≡ 2 по модулю 6. В этом случае мы уже не получим полной системы вычетов по модулю 6.

106. Проверьте для модуля m = 4, в каком случае значения произведения ах образуют полную систему вычетов, если X пробегает полную систему вычетов по модулю 4, беря а = 3 и а = 6.

Теорема. Если числа а и m взаимно просты и в выражении ах число х пробегает полную систему вычетов по модулю m, то и полученные значения этого выражения образуют полную систему вычетов по модулю m.

Доказательство. Так как х принимает m значений, то и для ах получим ровно m значений. Чтобы утверждать, что они образуют полную систему вычетов, надо показать, что никакие два из них не сравнимы по модулю m. Предположим, что для некоторых двух чисел x1 и x2, принадлежащих разным классам по модулю m, аx1 ≡ аx2 (mod m). Но а взаимно просто с m, поэтому обе части сравнения можно разделить на а, тогда должно быть x1 = x2 (mod m), чего быть не может. Таким образом, теорема доказана.

IV. При решении упражнений на делимость чисел, содержащих большие показатели степеней, удобно применять так называемую «малую теорему Ферма».

Если р — простое число, не делящее целого числа а, то ар-1 ≡ 1 (mod р).

Доказательство. Рассмотрим числа, кратные а:

Никакие два из них не сравнимы между собой по модулю р, ибо в противном случае их разность nk — ns = ka — sa = a(k — s) делилась бы на р, чего быть не может. Действительно, р — число простое и по условию а не ⋮ р; с другой стороны, и k — s не может делиться на р, ибо

1 ⩽ s < k ⩽ p — 1, значит, 0 < k — s < p. Значит, и произведение a(k — s) не делится на р.

Аналогично устанавливается, что ни одно из выписанных чисел n не делится на р.

Следовательно, числа n1, n2, . . ., np-1 образуют полную систему вычетов по модулю р, отсутствует лишь нуль. Поэтому они сравнимы с числами 1, 2, ..., р—1, взятыми, быть может, в некоторой их перестановке. Тогда

Но число k = 1⋅2⋅3(р— 1) не делится на простое число р, поэтому обе части сравнения можно сократить на число получим:

107. Проверьте, что

Решение. Рассмотрим вычисления при а = 4 для модуля р = 23. По модулю 23 имеем: 42 ≡ — 7; 43 ≡ 42 × 4 ≡ —28 ≡ —5; 44 ≡ 43⋅4 ≡ — 20 ≡ 3; 48 ≡ 44⋅44 = 9; 411 = 48⋅48 = — 45 ≡ 1; 422 = (411)2 ≡ 1.

Из приведенного решения видно, что иногда не только (р—1)-я степень, но и более низкая степень а оказывается сравнимой с единицей. Но можно доказать, что наименьшая степень k такая, что ak ≡ 1 (mod р) обязательно является делителем числа р— 1 (см. № 172).

Следствие. Если р — простое число, то для любого целого числа а имеем ap ≡ a(mod p), иными словами, разность ар — а делится на р.

Действительно, если а делится на р, то утверждение очевидно. Если же а не делится на р, то по теореме Ферма ар-1 = 1 (mod р). Умножив почленно на а, получим требуемое сравнение.

Применим теорему Ферма к решению задачи: «Найти остаток от деления на 5 числа 19671971».

Очевидно, что 1967 ≡ 2 (mod 5), значит, 19671971 ≡ 21971 (mod 5). Но 24 ≡ 1(mod5), поэтому найдем остаток от деления 1971 на 4, получим 21971 = 24⋅492+3 = (24)492 × 23 ≡ 1—23(mod5). Так как 23 = 3(mod5), то искомый остаток равен 3.

Рассмотрим решение еще одной задачи: «Может ли быть точным квадратом число, сумма цифр которого 1970?»

Пусть существует такое число n, что сумма цифр у n2 равна 1970. Так как 1970 = 2 (mod 3), то и n2 = 2 (mod 3). Очевидно, что n не ⋮ 3, но тогда по теореме Ферма должно быть n2 ≡ 1 (mod 3). Одновременно не могут иметь места сравнения n2 ≡ 2 и n2 ≡ 1. Следовательно, число, сумма цифр которого 1970, не может быть точным квадратом.

Примечание. Имеет место более общая теорема Эйлера: если а взаимно просто с m, то а φ(m) ≡ 1(modm), где φ(m) равно числу натуральных чисел, не больших m и взаимно простых с m (см. № 174).

Упражнения

108. Напишите полные системы вычетов по модулю 6, состоящие:

а) из наименьших положительных чисел;

б) из наименьших неотрицательных чисел;

в) из наименьших по абсолютной величине чисел.

109. В арифметике вычетов по некоторому модулю числа 3⋅5; 4⋅4 и 6⋅4 заменили соответственно вычетами 1, 2 и 3. Найдите неизвестный модуль.

110. Если числа а и m взаимно просты и в выражении ах + b число X пробегает полную систему вычетов по модулю m, то и получаемые значения этого выражения образуют полную систему вычетов по модулю m. Докажите.

111. Проверьте, что

112. Проверьте теорему Ферма, взяв р = 5, 7, 11 и придавая а различные значения.

113. Найдите остаток от деления числа 1971 — 19671967 на 7.

§ 9. УРАВНЕНИЯ В ЦЕЛЫХ ЧИСЛАХ

I. Нередко при решении задач составлением уравнений требуется не вообще решить уравнение, а найти целочисленные значения неизвестных, причем коэффициенты в таких уравнениях также целые числа. Решение

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

Решением таких уравнений занимались видные математики древности, такие, как греческий математик Пифагор (VI век до н. э.), александрийский математик Диофант (II—III век н. э.), по имени которого уравнения в целых числах называются диофантовыми уравнениями. Этой труднейшей проблемой теории чисел занимались и такие крупные математики, как П. Ферма, Л. Эйлер и другие. Но и на сегодняшний день нет общих методов решения таких уравнений.

Решение диофантовых уравнений первой степени с двумя неизвестными вида ах+bу = с теснейшим образом связано с решением сравнений с неизвестным. Действительно, это уравнение можно записать в виде двух сравнений: ах ≡ с (mod b) или by ≡ c (mod а). Наоборот, сравнение ax ≡ c(mod b) приводит к уравнению в целых числах ах — с = by.

II. Рассмотрим подробно решение сравнений вида ах ≡ с (mod b), содержащих неизвестное в первой степени. Очевидно, что если число x0 удовлетворяет данному сравнению, то и любое число х, сравнимое с x0 по модулю b, также будет ему удовлетворять. Поэтому обычно решением (или корнем) сравнения называют не отдельное число, а целый класс (по модулю b) чисел, удовлетворяющих данному сравнению.

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

Решениями сравнения ах ≡ с (mod b) являются такие целые числа х, что с — ах делится на b, значит с — ах = by или ах+by = с, где у — целое число. Полученный нами результат о решении сравнений можно применить к уравнениям в целых числах.

Если числа а и b взаимно просты, то уравнение ах + by = с всегда может быть решено в целых числах. Если (x0, y0) есть одно из его решений, то все решения могут быть записаны так:

где k — любое целое число.

114. Решить в целых числах уравнение:

Решение. Заменим это уравнение сравнением — 8у ≡ 13 (mod 5) или 2у ≡ 3 (mod 5). Очевидно, что y0 = 4 удовлетворяет этому сравнению, после чего легко найти x0 = 9, а все решения даются формулами: х = 9 — 8k; у = 4 — 5k, где k — любое целое число. 115. Решите следующие диофантовы уравнения:

Рассмотрим случай, когда а и b имеют наибольший общий делитель d > 1. Пусть а = d⋅a1; b = d⋅b1, причем НОД (a1, b1) = 1.

Если с не делится на d, то уравнение ах+ by = с не может иметь решений, ибо допустив, что при некоторых целых x0 и y0 будет ах0 + bу0 = с, то тогда слагаемые ax0 и bу0 делились бы на d, а их сумма, число с, не делится на d.

Если же с делится на d, то с = dc1, и уравнение ах + by = с можно заменить ему равносильным уравнением a1х + b1у = c1, у которого коэффициенты при неизвестных уже взаимно просты, а такие уравнения мы умеем решать. Следует учесть, что в этом случае все решения даются формулами:

116. Решите следующие уравнения в целых числах а) 3x+6у = 22; б) 14x+ 22у = 26.

III. Иногда по условию задачи требуется найти не любые целые числа, а такие, которые удовлетворяют некоторым дополнительным условиям. Например, требуется найти все целые положительные значения х и у, удовлетворяющие уравнению: 3x+5у = 19.

Решая это уравнение, мы найдем, что х = 3 + 5k, у = 2 — 3k. Но k не может быть любым целым числом, ибо надо, чтобы х > 0 и у > 0, т. е. 3 + 5k > 0 и 2 — 3k > 0, откуда находим, что k > — 3/5 и k < 2/3.

Значит, k может принимать только одно целое значение: k = 0, а тогда x = 3; у = 2. Никаких других целых положительных решений уравнение не имеет.

117. Найдите все целые положительные значения x и y, удовлетворяющие следующим уравнениям: а) 3х + 2y = 5; б) 5х + 7у = 112.

118. Трехзначное число оканчивается цифрой 7. Если переставить эту цифру на первое место, то получится число, в два раза и еще на 21 единицу большее первоначального. Определите это число.

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

IV. Решение некоторых задач сводится к решению в целых числах систем двух уравнений с тремя неизвестными. Такие системы обычно решаются методом последовательного исключения неизвестных: исключая одно из неизвестных, получим одно уравнение с двумя неизвестными. Рассмотрим, в качестве примера, такую задачу:

«Можно ли на 100 копеек купить 100 предметов: карандашей (цветных и простых) и перьев, если известно, что цветной карандаш стоит 5 коп., простой — 3 коп., а перьев продают 3 штуки на одну копейку?»

Решение. Обозначив число цветных карандашей через X, простых карандашей — через у и перьев — через z, легко составить два уравнения:

Следовательно, получили систему двух уравнений с тремя неизвестными:

где x, у и z — целые неотрицательные числа, не большие 100.

Исключив z, получим одно уравнение с двумя неизвестными:

Очевидно, что х должно быть кратно 4, причем 7х = 100 — 4y, поэтому 7х < 100, то есть х ⩽ 14.

Вычислив значения у и z при х = 0; 4; 8; 12, получим четыре различных ответа: (0; 25; 75), (4; 18; 78), (8; 11; 81) и (12; 4; 84).

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

Упражнения

120. Решите следующие сравнения:

а) 5x ≡ 4 (mod 7); б) 6x ≡ 5 (mod 15); в) 6х ≡ 3 (mod 15).

121. Решите следующие уравнения в целых числах: а) 3х — 4у = 29; б) 91x — 65y = 42.

122. Если между цифрами двузначного числа вписать нуль, то полученное трехзначное число будет в 7 раз больше первоначального. Найдите это число.

123. Если к двузначному числу приписать слева и справа по единице, то полученное четырехзначное число будет больше первоначального в 21 раз. Найдите это число.

124. Библиотека на 20 рублей купила 20 книг трех видов: по 3 рубля, по 2 рубля и 50 копеек за книгу. Сколько книг каждого вида купила библиотека?

125. Докажите, что сравнение ах ≡ b (mod р), где р — число простое и а ≠ 0 (mod р), всегда имеет в точности одно решение. Убедитесь, что х ≡ bаp-2 (mod р) является решением.

§ 10. ЗАДАЧИ ПОВЫШЕННОЙ ТРУДНОСТИ

126. Докажите, что если а ⋮ b и b ⋮ а, то а = ±b.

127. Докажите, что: 1) Сумма пяти последовательных целых чисел делится на 5. 2) Произведение пяти последовательных целых чисел делится на 5.

128. Докажите, что a5 — а делится на 5 при любом целом а.

129. 1) Может ли сумма нечетных чисел быть числом четным? 2) Каким числом, четным или нечетным, будет сумма нечетного числа слагаемых, каждое из которых есть число нечетное?

130. Члены футбольной команды пионерского лагеря перед отъездом домой решили обменяться друг с другом фотографиями. Каким числом, четным или нечетным, будет общее число фотографий, которыми обменялись ребята?

Сколько было таких фотографий, если в обмене участвовало 11 человек?

131. 1) 31 августа на школьном дворе встретилось 7 пятиклассников. Некоторые из них обменялись рукопожатиями. Докажите, что хотя бы один из них пожал руку четному числу друзей.

Примечание. Нуль — число четное, поэтому ученик, ни с кем не поздоровавшийся за руку, сделал четное число рукопожатий.

2) В розыгрыше приза «Кожаный мяч» участвовало большое число футбольных детских команд в каждой возрастной группе. Некоторые из них провели четное число матчей, другие — нечетное число матчей. Каким числом, четным или нечетным, будет число команд, которые провели нечетное число матчей?

132. В одной рукописи приведено описание города, расположенного на 8 островах. Острова между собой и с материком были соединены мостами. На материк выходило 5 мостов; на 4 островах берут начало по 4 моста; на 3 островах берут начало по 3 моста и на один остров можно пройти только по одному мосту.

Почему такого расположения мостов быть не может?

133. Если сумма двух чисел оканчивается нулем, то разность квадратов этих чисел делится на 10. Докажите.

134. Можно ли число 1970 представить в виде разности квадратов двух целых чисел?

135. Число, записанное в десятичной системе, оканчивается нулем. Будет ли это число оканчиваться нулем: 1) В пятеричной системе? 2) В троичной системе? 3) Будет ли оно кратно 5, если его записать в восьмеричной системе?

136. Вместо точек поставьте такие цифры, чтобы каждое из чисел: 1011⋅2; 12⋅23; 34⋅21б; 345⋅68 делилось на 2.

137. Какие цифры можно поставить вместо точек, чтобы каждое из чисел: 1⋅23 и 5⋅267 было четным?

138. Вместо точек поставьте такие цифры, чтобы каждое из чисел: 201⋅3; 120⋅03; 4⋅347; 336⋅9 делилось на 3.

139. Вместо точек поставьте такие цифры, чтобы каждое из чисел: 32⋅5; 2⋅405; 1⋅56; 3⋅346 делилось на 5.

140. Вместо точек поставьте такие цифры, чтобы каждое из чисел: 642⋅37; 2313⋅4 делилось и на 2 и на 3.

141. 1) Можно ли из одних «двоек» составить число (2; 22; 222; 2222; . . .), которое делится на 9? на 5?

2) Можно ли в семеричной системе из одних «пятерок» составить число (5; 55; 555; . . .), делящееся на 3?

142. Выведите признаки делимости чисел на 4; 25; 50, считая основанием системы счисления d = 100.

143. Выведите общий признак делимости на 7, 11 и 13, считая основанием системы счисления d = 1000.

144. А — 1970-значное число, делящееся на 9; Б — сумма цифр числа А; В— сумма цифр числа Б.

Найдите сумму цифр числа В.

145. Докажите, что нет таких чисел, которые от перестановки начальной цифры в конец числа увеличивались бы ровно в 5 раз.

146. Найдите такое целое число, которое в 7 раз больше цифры единиц этого числа.

147. Докажите, что число вида n4 + 4 есть составное при любом целом n, большем единицы.

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

149. Докажите, что два соседних целых числа n и n+ 1 всегда являются взаимно простыми.

150. Докажите, что если а — b = 2 и числа а и b не являются взаимно простыми, то НОД (а, b) = 2.

151. Докажите, что каковы бы ни были натуральные числа а и 6, всегда можно подобрать два таких целых числа x и y, что ах+ by = НОД (а, b).

152. Для того чтобы числа а и b были взаимно простыми, необходимо и достаточно, чтобы существовали два таких целых числа х и у, что ах + by = 1. Докажите.

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

154. Верно ли утверждение, что если произведение a-b делится на р, то один из сомножителей делится на р? Приведите примеры, подтверждающие это.

155. Докажите следующие утверждения:

1) Если р простое число, то любое натуральное число а либо делится на р, либо взаимно просто с ним.

2) Если произведение а⋅b делится на простое число р, то по крайней мере один из сомножителей делится на р.

3) Если произведение нескольких чисел делится на простое число р, то по крайней мере один из сомножителей делится на р.

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

157. Применяя задачу № 153, установите, что если число а делится порознь на два числа р и q, которые взаимно просты, то а делится на их произведение pq.

158. Сформулируйте признаки делимости чисел на 6, 12 и 15.

159. Докажите следующие утверждения:

1) Произведение трех последовательных целых чисел делится на 6.

2) Произведение четырех последовательных целых чисел делится на 24.

3) Произведение пяти последовательных целых чисел делится на 120.

160. Установите, что если а целое число, то

1) a3 — а делится на 6.

2) a5 — а делится на 30.

3) а(a2 + 5) делится на 6.

161. Докажите, что всякое общее кратное чисел а и b делится на m = HOK(a, b).

163. Найдите число всех различных делителей числа

164. Дайте строгое обоснование известных вам способов отыскания НОД (а, b) и НОК(а, b) разложением а и b на простые множители.

165. При делении числа на 2 в остатке получается 1, а при делении на 3 — остаток 2. Какой будет остаток, если это число разделить на 6?

166. 1) Найдите наименьшее число, которое при делении на 3 дает в остатке 2, при делении на 5 дает в остатке 3 и при делении на 7 — снова 2.

2) Найдите наименьшее число, которое кратно 7, но при делении на 3, на 4 и на 5 дает в остатке 1.

167. 1) Вместо точек поставьте такие цифры, чтобы числа 8. и 1. 4 делились и на 3 и на 4.

2) Вместо точек поставьте такие цифры, чтобы каждое из чисел: 2.. и 86.. делилось одновременно и на 5, и на 9.

168. 1) Из цифр 0, 2, 3 и 4 составьте четырехзначные числа, которые делились бы на 4, на 5 и на 9 (одновременно).

2) Из цифр 5, 8, 4 и 1 составьте несколько четырехзначных чисел, которые делились бы на 4, на 5 и на 9.

169. Сколько натуральных чисел, не больших 500 и не делящихся ни на 2, ни на 3?

170. Найдите остаток от деления числа 5 на 7.

171. Делятся ли числа на 7?

172. Докажите, что наименьшее натуральное число k, для которого ak ≡ 1(mod р) (где р — простое число, не делящее а), должно быть делителем р—1.

173. Мы знаем, что если одно из чисел данного класса вычетов по модулю m взаимно просто с m, то и все числа этого класса взаимно просты с m (см. № 95). Поэтому можно говорить о классах, взаимно простых с модулем. Группа чисел, содержащая по одному представителю от каждого класса, взаимно простого с модулем, называется приведенной системой вычетов по данному модулю.

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

174. Докажите теорему Эйлера: если числа а и b взаимно просты, то а φ(m) ≡ 1 (mod m), где φ(m) равно числу натуральных чисел, не больших m и взаимно простых с m.

175. Найдите остаток от деления числа 127107 на 15.

176. Решить диофантовы уравнения:

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

178. Даны три разные цифры. Сумма всех трехзначных чисел, какие только можно составить, комбинируя эти три цифры, равна 2886. Если расположить данные цифры по убыванию их значений и из полученного числа вычесть число, составленное из этих же цифр, но взятых в обратном порядке, то разность составит 495. Найдите эти три цифры, если известно, что среди них нет нуля.

179. В учреждении стоят 14 канцелярских столов с одним, двумя, тремя и четырьмя ящиками. Всего в столах 33 ящика. Сколько столов с одним ящиком, если известно, что их столько, сколько с двумя и тремя ящиками вместе?

180. Люда с мамой делали покупки. У них было немного менее 150 рублей, причем только пятерками и рублями. По возвращении домой у них осталось ровно треть первоначальной суммы, при этом пятерок стало столько, сколько раньше было рублей, а рублей столько, сколько раньше было пятерок. Сколько денег они истратили на покупку?

181. В шахматном турнире участвовало два ученика седьмого класса и несколько восьмиклассников. Два семиклассника набрали вместе 8 очков, а каждый восьмиклассник набрал одно и то же число очков. Сколько восьмиклассников участвовало в турнире?

Ответы и решения

1. б) 6 и 1; 9 и 4; —18 и 3; —10 и 9.

4. |а|.

5. Наибольший положительный делитель числа а есть | а |, значит, если а ⋮ b, где b > 0, то b < | а |. Но различных натуральных чисел, не больших |а|, только лишь |а|.

15. 4) Двузначное число, у которого цифра десятков а и цифра единиц 6, содержит 10а + b единиц. Число, записанное теми же цифрами, но в обратном порядке, есть 106 + а. Их сумма (10а + b) + (10b + а) = 11a + 11b = — 11 (а + b).

16. Если N1 = 100а + 10b + с, то обращенное число N2 = 100с + 10b +а. Значит, N1 — N2 = (100a+ 10b + с) — ( 100с + 10b + а) = 99а — 99с = 99 (а — с).

18. 1) Рассматриваем два случая: n = 2k — число четное и n = 2k + 1 — число нечетное.

2) Рассматриваем три возможных случая: число n делится на 3, значит, n = 3k; число n при делении на 3 дает остаток 1, значит, n = 3k+ 1; число n при делении на 3 дает остаток 2, значит, n = 3k + 2.

20. 2) Возьмем два последовательных нечетных числа:

21. 5643; 14014; 5069812; 4 192716.

22. 2348; 483 568.

25. 1) 0 или 5; любую цифру; такую цифру найти нельзя.

2) 1; 2; 7.

3) 0, 3, 6 или 9; 2, 5 или 8; 2, 5 или 8.

26. 1) 401, остальные делятся на 5.

2) 366, остальные делятся на 9.

3) 342, остальные делятся на 4.

27. Всякий раз число кусков увеличивалось на 5, поэтому общее число кусков должно делиться на 5.

28. Те и только те числа, которые оканчиваются цифрой 0.

29. Те и только те числа, которые оканчиваются четной цифрой.

30. 1) Те и только те числа, которые оканчиваются нулем или цифрой 4.

2) Те и только те числа, которые оканчиваются нулем или цифрой 3.

31. Те и только те числа, у которых сумма цифр делится на данное число.

32. Те и только те числа, у которых сумма цифр делится на данное число.

33. 10102; 10018; 213б; 11007; 56 048.

34. 2203; 3124; 2317; 4839. 35 . 3205; 523б.

36. 20107; 46 407; 258; 47308.

38. Пусть наименьший отличный от единицы положительный делитель составного числа N есть р, значит, N = p⋅q, где q ⩾ р. Тогда p2 = р⋅р ⩽ p⋅q = N, то есть p2 ⩽ < N.

39. Если бы число N было составным, то оно имело бы наименьший простой делитель, квадрат которого не больше N.

40. Достаточно проверить для 2, 3, 5 и 7, ибо 112 > 100.

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

47. 1) Да, например: 3 + 2; 11 + 2 и другие числа-близнецы.

2) Нет, ибо сумма таких простых чисел (нечетных!) есть всегда число четное.

49. Простое число р может делиться только на 1 и на р. Но q — число простое, оно не равно 1, значит, q = р.

50. 2⋅3⋅5⋅7⋅11⋅13+ 1 = 30031 = 59⋅509; остальные все числа простые.

51. Разложим сначала на простые множители все составные множители, а затем соберем все простые множители, складывая соответствующие показатели степеней. Получим

52. В десятой степени.

53. В четвертой степени.

54. Четырьмя нулями.

55. 24 нулями.

56. 1) 8; 2) 16; 3) 16.

57. 1) 1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45, 90. 2) 1, 2, 5, 7, 4, 10, 14, 35, 20, 28, 70, 140.

58. 1) 1, 2, 5, 10.

2) По 1, по 2, по 5 или по 10 учащихся в один ряд.

59. 10.

60. 1) 6; 2) 60.

61. 6; 9; 8; 16.

62. 35.

63. 12; 6; 4; 3; 2; 1.

64. 1) 1; 2; 3; 5; 6; 10; 15; 30. 2) 1; 3; 9; 27; 81.

65. à) 1; 2; 4; 8. б) 1; 2; 3; 4; 6; 9; 12; 18; 36. в) 1; 2; 3; 4; 5; 6; 8; 10; 12; 15; 20; 24; 25; 30; 40; 50; 60; 75; 100; 120; 150; 200; 300; 600.

66. а) 4×3 = 12 делителей; б) 4 × 5 = 20 делителей; в) (k+ l)⋅(n+ 1) делителей.

67. 12; 60; 17.

71. 1) 15; 14; 13; 1; 23; 1. 2) 6; 1; 7; 105.

72. 7; 16; 128.

73. 1) 8 км/ч; 2) 23 часа.

74. 9, 12 и 10 вагонов.

75. По доказанному первому утверждению ab/D = M есть общее кратное чисел а и b. По второму утверждению ab/m = d есть общий делитель чисел а и b. Следовательно, ab = MD и ab = md, откуда MD = md.

D = НОД (а, b), значит, D ⩾ d, но тогда М ⩽ m, что возможно лишь в том случае, когда M = m, ибо m — наименьшее общее кратное.

78. 70; 288; 540; 5040.

79. 84; 420; 547 711.

81. 120; 270; 288; 2310.

82. 1) 120 см; 2) 24 дм × 24 дм.

83. 1) 60 книг; 2) 600 тетрадей.

84. Все три встретятся через 60 дней, в пятницу.

85. 10 задач.

86. 1) НОК (8,9) — 1 = 72 — 1 = 71. 2) НОК (8, 7, 6, 5, 4, 3, 2) — 1 = 839.

90. 0; 4; 0; 10.

91. 234 122 и 23543 723.

92. Всегда, кроме деления на число, сравнимое с нулем по данному модулю.

93. Так как а — число простое, то а и m взаимно просты.

94. Может оказаться, что r1-r2 ⩾ m, поэтому можно лишь утверждать, что остаток произведения сравним с произведением остатков по модулю m.

95. Достаточно сравнение а = b (mod m) заменить эквивалентным ему утверждением, что а = b + km.

97. Применить признак делимости на 11.

98. Но по модулю 19 имеем: 20 = 1; 18 = —1 и 50 = 12, поэтому

100. Остатки соответственно равны: 0; 2; 10.

101. По модулю 7 можно записать:

102. Нельзя. Например: 3⋅4 ≡ 0(mod6), но 3 ≢ 0(mod 6) и 4 ≢ 0 (mod 6).

103. Использовать утверждение, что если произведение двух чисел делится на простое число р, то хотя бы один из сомножителей делится на р (см. № 155).

105. Целесообразно взять такую полную систему вычетов: (—3, —2, —1, 0, 1, 2, 3).

106. При а = 3.

108. а) (1, 2, 3, 4, 5, 6); б) (0, 1, 2, 3, 4, 5); в) (-3, —2, —1, 0, 1, 2) или (—2, —1, 0, 1, 2, 3).

109. 7. 113. 1.

115. а) х = — 1 + 4k; у = 2 — 3k; б) х = — 3+8k; у = 3 — 7 k.

116. а) Нет решений; б) х = — 6+11k;; у = 5—7k.

117. а) (1; 1), б) (21; 1), (14; 6), (7; 11).

118. Обозначим цифру сотен через х, а цифру десятков через у. Тогда искомое число будет иметь вид: 100х+10у+7. После перенесения цифры 7 на первое

место получим число 700+ 10x + y. Можем составить уравнение:

700+ 10x+y = 2(100x+ 10y+7)+ 21.

После упрощений получим: 10x + у = 35.

Но x и у — цифры, значит, единственным решением данного уравнения будет х = 3, а у = 5. Искомое число равно 357.

119. 72.

120. а) x = 5 + 7k; б) нет решений; в) х = 3 + 5k.

121. а) х = 11 + 4k; у = 1 + 3k; б) нет решений.

122. Если цифра десятков х, а цифра единиц у, то уравнение имеет вид: (10х + у)⋅7 = 100х+у или 30x — — 6у = 0, откуда у = bх. Так как x и у — цифры, то задача имеет единственное решение х = 1; у = 5. Искомое двузначное число равно 15.

123. 91.

124. 1 книгу за 3 рубля, 5 книг по 2 рубля и 14 книг по 50 копеек за книгу.

125. НОД (а, р) = 1, значит, сравнение имеет единственный класс решений. Подставив значение х в левую часть сравнения, получим: а ⋅ bаp-2 = b⋅аp-1 ≡ b⋅1 (mod р), ибо по теореме Ферма ap-1 ≡ 1 (modp).

126. Если a⋮b и b⋮а, то a = b⋅q1 и b = a⋅q2, тогда a = a(q1q2). Сокращая обе части равенства на а, получим q1q2 = 1, что возможно лишь при условии, что q1 = dz 1 и q2 = 1.

127. а) n + (n + 1) + (n + 2) + (n + 3) + (n + 4) = 5n + 10 = 5 (n+2).

б) Любое целое число n может быть представлено в одном из пяти возможных видов: n = 5k; n = 5k+ 1; n = 5k + 2; n = 5k + 3; n = 5k + 4, где k — целое число. Каково бы ни было n, один из сомножителей произведения n(п + 1) (n + 2) (n + 3) (n + 4) делится на 5, а значит, и все произведение делится на 5.

128. Рассматриваем для а пять возможных случаев, как и в предыдущей задаче, предварительно разложив a5 — а на множители: a5 — а = а(a2—1)(a2+1) = (а — -1)а(а+ 1)(a2 + 1).

129. 1) Может, если слагаемых четное число. 2) Нечетное число.

130. Четным. 11⋅10 = 110.

131. 2) Четным.

132. Число концов у всех мостов должно быть обяза-

тельно четное, а в рукописи имеем 5 +4⋅4 + 3⋅3 +1 = 31 — нечетное число концов.

133. a + b = 10k; a2 — b2 = (а+ b)(а — b) = 10ft (а —b).

134. Предположим, что 1970 = a2— b2, где а и b— целые числа. Значит, 1970 = (а + b)(а — b).

В зависимости от четности а и b возможны 4 случая: 1) а и b — оба четные; 2) а и b — оба нечетные; 3) а — четное, b — нечетное; 4) а — нечетное, b — четное. В первых двух случаях а + b и а — b являются четными числами, поэтому их произведение делится на 4. Следовательно, (а + 6) (а — b) не может равняться числу 1970, не делящемуся на 4. В последующих двух случаях а + b и а — b — нечетные, значит, их произведение число нечетное и не может равняться четному числу 1970.

135. 1) Да. 2) Не обязательно. 3) Да.

136. 0; 1; 0, 2 или 4; любую цифру от 0 до 7.

137. 1; 1, 3 или 5.

138. 0; любую цифру (0, 1 или 2); 1 или 4; 0, 3 или 6.

139. 0; любую цифру от 0 до 4; 4; 0.

140. 3; 0.

141. 1) 222222222 и другие подобные числа делятся на 9; нет, ибо они на 5 делиться не могут.

2) 555; 555555 и другие подобные числа.

144. Самое большое значение для Б будет, если все 1970 цифр числа А равны 9, значит, Б ⩽ 9⋅1970 = 17 730 — пятизначное число. Тогда сумма цифр числа Б меньше, чем 9⋅5 = 45, причем делится на 9. Следовательно, число В может быть 9, 18, 27 или 36. У всех этих чисел сумма цифр равна 9.

145. Исходное и вновь полученное число имеют одинаковое число цифр, ибо мы только переставляем цифру с одного места на другое. Но если при увеличении числа в 5 раз число цифр не изменяется, значит, первая цифра у такого числа равна 1. Число, оканчивающееся на 1, не может делиться на 5.

146. Искомое число обязательно двузначное. Если цифру единиц принять за одну часть, то разность искомого числа и цифры его единиц, оканчивающаяся на нуль, содержит 6 таких частей. Единственное число, оканчивающееся на нуль, которое при делении на 6 дает целое число, меньшее 10, есть число 30. Искомое число 35.

148. Пусть n > 1 — любое натуральное число. Рассмотрим n— 1 последовательных натуральных чисел:

где n! = 1⋅2⋅3⋅4⋅ ... ⋅п. Все эти числа составные, ибо n! + 2 делится на 2, п! + 3 делится на 3 и так далее, наконец, п! + n делится на n. Так как n можно взять сколь угодно большим, то этим и доказано требуемое утверждение.

149. Пусть НОД (n+ 1, n) = d, тогда разность (n + 1) — n = 1 должна делиться на d, что возможно лишь при d = 1.

150. Пусть НОД (a, b) = d, тогда разность а — b = 2 обязательно делится на d, значит, d = 1 или d = 2. Но так как а и b не взаимно простые числа, то d = 2.

151. Применим к числам а и b алгоритм Евклида, полагая а > b. Для определенности будем считать, что процесс последовательного деления закончится на четвертом этапе, то есть

Тогда НОД (а, b) = r3. Из предпоследнего равенства найдем r3 = r1 — r2⋅q3. Подставим сюда значение r2, найденное из второго равенства: r2 = b — r1q2. После упрощений получим: r3 = b (— q3) + r1 (1 + q2q3).

Заменим теперь r1 его выражением из первого равенства: r1 = а — bq1. После упрощений получим:

В обеих скобках имеем целые числа, ибо все частные являются целыми числами. Обозначив 1 + q2q3 = х и —q3 — —q1—q1 < q2qз = y, получим, что r3 = НОД (a, b) = a⋅x + b⋅y.

Очевидно, что таким же рассуждением мы получим требуемое для НОД (а, b) выражение независимо от того, на каком этапе заканчивается процесс деления.

152. Если а и b взаимно простые числа, то НОД (a, b) = 1, и по доказанному в задаче № 151 найдутся такие числа х и у, что а⋅х + b⋅у = 1.

Справедливо и обратное. Пусть при некоторых целых x и у имеет место равенство а⋅х + b⋅у = 1. Тогда любой

общий делитель d чисел а и b будет делителем числа 1, что возможно лишь при d = ±1. Следовательно, числа а и b имеют только один положительный общий делитель d = 1, то есть НОД (a, b) = 1.

153. Так как НОД (а, р) = 1, то найдутся такие целые числа x и у, что а⋅х + р⋅у = 1. Умножив обе части этого равенства на b, получим: (ab)x + р(bу) = b.

По условию (аb) ⋮ р и р ; р, тогда и b = (аb)x + р(by) должно делиться на р.

154. Неверно, например, 3⋅4 делится на 6, но ни один из сомножителей не делится на 6.

155. 1) Пусть НОД (a, p) = d, значит, p⋮d. Но р — число простое, оно может делиться лишь на 1 и на р. Если d = р, то тогда а ⋮ р; если же d = 1, значит, а и р взаимно простые.

2) Если а не делится на р, то, по доказанному выше, НОД (а, р) = 1, но тогда b должно делиться на р (см. № 153).

3) Пусть произведение a1а2а3⋅ . .. ⋅ап делится на простое число р. Рассматривая данное произведение как произведение только двух сомножителей a1 и (a2а3⋅ ... ⋅аn), можем рассуждать так: если a1 не делится на р, то НОД (a1, р) = 1 (см. № 1551), но тогда второй сомножитель (a2а3⋅ ... ⋅ап) должен делиться на р (см. № 153).

Аналогично рассуждая, установим, что если a2 не делится на р, то (a3⋅ ... ⋅ап) должно делиться на р. Продолжая эти рассуждения далее, найдем, что если ни одно из чисел a1, a2, a3, ... , an-1 не делится на р, то an делится на р. Итак, какое-нибудь из данных n чисел обязательно делится на р.

156. Пусть для некоторого числа N мы имеем два разложения: N = p1⋅р2⋅... ⋅pk и N = q1⋅q2⋅. . .⋅qs, где все pi и qn — простые числа. Требуется доказать, что числа q1, q2, ..., qs лишь порядком расположения могут отличаться от чисел p1, p2, ... , pk.

Рассмотрим равенство: p1 ⋅ p2 ⋅ ... ⋅pk = q1⋅q2⋅ ... ⋅qs. Левая часть его делится на p1, значит, и правая часть должна делиться на p1. Но p1 — число простое, поэтому произведение q1⋅q2⋅ . . . ⋅qs делится на p11 только в том случае, когда один из его сомножителей делится на p1 (см. № 1553). Пусть q1 делится на p1, но так как q1 — число простое, значит, q1 = p1 (см. № 49). Разделив обе части равенства на p1, получим: p2⋅р3⋅ . . . ⋅pk = q2⋅q3⋅ . . . ⋅qs.

Аналогично найдем, что q2 = p2; q3 = Р3 и так далее. Получим, что все множители p1, p2, ..., pk входят и в правую часть исходного равенства.

Рассматривая делимость на q, получим, что все множители q1, q2, ... , qs входят в левую часть. Следовательно, левая и правая части могут отличаться только порядком множителей, а не самими множителями.

157. Так как а ⋮ р, то а = p⋅Q; но а ⋮ q, значит, (p⋅Q) ⋮ q. По условию НОД (р, q) = 1, поэтому Q ⋅. q (см. № 153), то есть Q = q⋅c. Тогда a = p⋅q⋅c.

158. Так как 6 = 2⋅3, 12 = 3⋅4 и 15 = 3⋅5 представлены в виде произведений взаимно простых чисел, можно сформулировать следующие признаки делимости:

на 6 делятся те и только те числа, которые делятся и на 2, и на 3;

на 12 делятся те и только те числа, которые делятся и на 3, и на 4;

на 15 делятся те и только те числа, которые делятся и на 3, и на 5.

159. 1) Произведение трех последовательных чисел делится и на 2, и на 3 (см. № 18), значит, оно делится и на 6.

2) Произведение четырех последовательных целых чисел делится на 3 (см. № 18). Среди сомножителей обязательно есть два четных числа: 2k и 2k+ 2. Их произведение делится на 8, ибо 2k⋅(2k+ 2) = 4k(k+ 1), a k(k+1) делится еще на 2 (см. № 18). Значит, все произведение делится на 24, так как НОД (3,8) = 1.

3) Произведение n(n + 1)(n + 2)(n + 3)(n + 4) делится на 3, на 8 и на 5, следовательно, и на 3⋅5⋅8 = 120.

при любом целом а это произведение делится на 2, на 3 и на 5 (см. № 128).

3) Как и при решении задачи № 18, устанавливаем делимость на 2 и на 3.

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

В числителе получили произведение трех последовательных целых чисел, которое делится на 6.

В числителе имеем произведение четырех последовательных целых чисел, которое делится на 24.

161. Пусть M — общее кратное чисел а и b. m = НОК (a, b). Разделим M на m.

Так как M делится и на а и на b, и m делится и на а и на ft, то и г должно делиться и на а и на b, то есть r есть общее кратное чисел а и b. Но наименьшим положительным общим кратным чисел а и b является m, значит, r = 0.

162. Если делитель d = 1, то его можно представить в виде p01⋅р02⋅ ... ⋅p0n. Если d > 1, то он имеет простой делитель р. Так как N ⋮ d и d ⋮ р, то N ⋮ р, значит, один из простых множителей разложения N должен делиться на р, что возможно, если он совпадает с р, иными словами, р есть один из pi, входящих в каноническое разложение числа N.

Если некоторое простое число р входит в разложение числа N в степени α, а в разложение d в степени ß, то ß ⩽ α. Предположим противное, что ß > α. Тогда N = pα⋅q1, причем q1 не делится на р, a d = pßq2.

По условию N ⋮ d, значит, N = d⋅q3 = pβq2q3. Составим равенство: pαq1 = pβq2q3. Сократив на рα, получим q1 = pβ-αq2q3. Правая часть делится на р, а левая не делится. Полученное противоречие и доказывает, что ß не может быть больше α.

165. Остаток равен 5.

166. 1) 3⋅7 + 2 = 23. 2) 60⋅n + 1 = 301.

167. 1) 4; 4. 2) 25 или 70 и 40 или 85.

168. 1) 3420; 4320; 3240; 2340. 2) Нельзя.

169. 167.

170. Так как 56 ≡ 1(mod7), достаточно найти остаток от деления числа 77...7 на 6. Но 7 ≡ 1 (mod 6), поэтому

172. Пусть р — 1 = kq + r, где 0 < r < k, тогда аp-1 = акq+r = (ak)q ⋅ аr. Но ak ≡ 1 (mod р) и аp-1 ≡ 1 (mod р), значит, 1 ≡ 1⋅ar(mod р), чего быть не может, ибо 0 < r < k, а по условию k — наименьшее натуральное число такое, что ak ≡ 1 (mod р).

173. Когда X пробегает все φ(m) значений из приведенной системы вычетов, получим φ(m) произведений ах, и так как а и х взаимно просты с m, то и их произведения взаимно просты с m. Нетрудно показать, что все φ(m) произведений принадлежат разным классам вычетов по модулю m.

174. Возьмем любую приведенную систему вычетов r1, r2, ... , rs, где s = φ(m). Тогда числа аr1, аr2, ... , ar также образуют приведенную систему вычетов по тому же модулю m. Поэтому каждое из чисел ark сравнимо по модулю m с одним из чисел ri, а перемножив все s = φ(m) этих сравнений, получим:

Но все ri взаимно просты с m, тогда и их произведение r1r2⋅ ... ⋅rs взаимно просто с m. Разделив обе части сравнения на это произведение, получим: а φ(m) ≡ 1 (mod m).

175. Сравнение 127107 ≡ 7107 (mod 15) очевидно. Непосредственно определяем, что числа 1, 2, 4, 7, 8, 11, 13, 14 образуют приведенную систему вычетов по модулю 15, значит, < p (15) = 8. По теореме Эйлера 78 ≡ 1 (mod 15), тогда 7107 = 78⋅13+3 = (78)13⋅73 ≡ 73(mod 15). Теперь находим остаток: 73 = 49⋅7 ≡ 4⋅7 = 13(mod 15).

178. Обозначим искомые цифры через х, у и z, причем будем считать, что х < у < z. Из этих трех букв можно составить только шесть различных групп по три буквы: xyz; xzy; yxz; yzx; zxy и zyx. Поэтому комбинируя три цифры, мы получим шесть трехзначных чисел, в общую сумму которых каждая буква входит дважды в качестве цифры сотен, дважды — десятков и дважды — единиц. Следовательно, (200 + 20 + 2) х + 222у + 222z = 2886, откуда x + у + z = 13.

С другой стороны, (100z+ 10у + х) — (100x + 10у + z) = 495; 99z — 99x = 495; z —x = 5.

Если X = 1, тогда z = 6 и у = 6, чего быть не может, ибо все цифры разные. Если х ⩾ 3, тогда z ⩾ 8, а y ⩽ 2 что противоречит условию х < у < z.

Следовательно, х = 2; z = 7 и у = 4.

179. Столов с одним ящиком было 5, с двумя — 3, с тремя — 2 и с четырьмя — 4.

180. Пусть было X пятерок и у рублей, значит, всего было (5x + у) рублей, а после покупок осталось (5у + х) рублей. Из уравнения bх + у = 3(5у + х) находим: 2х = 14у или х = 7у. Следовательно, первоначальная сумма составляла 5⋅7у + у = 36y рублей, что немного меньше 150 рублей только при у = 4. Значит, до покупок у них было 144 рубля, осталось 48 рублей, а на покупки израсходовали 96 рублей.

181. Обозначим число восьмиклассников через n, а число очков, полученных каждым из них, через х. Так как за каждую партию начисляется либо 1 очко одному, либо по 0,5 очка каждому, то число 2х должно быть целым.

Всего участников было n + 2, значит, ими было сыграно (n+2)(n+1)/2 партий и столько же всего было начислено очков. Составляем уравнение:

откуда

Но n и 2х — числа целые, поэтому n должно быть положительным делителем числа 14. Но при n = 1 и n = 2 получим, что 2х < 0, что быть не может. При n = 7 получим X = 4, а при n = 14 будет х = 8. Таким образом, в турнире участвовало или 7, или 14 восьмиклассников,

ЛИТЕРАТУРА

А. И. Маркушевич. Дополнительные вопросы арифметики целых чисел. «Математика в школе», № 4, 1967.

А. Я. Хинчин. Элементы теории чисел. Энциклопедия элементарной математики, т. I.

М. К. Гребенча и С. Е. Ляпин. Арифметика. Учпедгиз, М., 1952.

Н. Н. Воробьев. Признаки делимости. Физматиздат, М., 1963.

В. Серпинский. Что мы знаем и чего не знаем о простых числах. Физматиздат, М., 1963.

Алексей Архипович Мазаник

ДЕЛИМОСТЬ ЧИСЕЛ И СРАВНЕНИЯ

Редактор Б. А. Кимбар. Художественный редактор И. Я. Карпинович. Технический редактор М. Т. Попкова. Корректор Л. С. Калиновская. Сдано в набор 5/VIII 1970 г. Подписано к печати 4/XI 1970 г. Формат 84Х1081/32. Бум. тип. № 3. Физ. печ. л. 2. Усл. печ. л. 3,36. Уч.-изд. л. 3,23. Тираж 40 000 экз. Зак. 1151. Цена 9 коп.

Издательство «Народная асвета» Государственного комитета Совета Министров БССР по печати, Минск, Ленинский проспект, 85.

Типография издательства ЦК КП Белоруссии, Минск, Ленинский проспект, 79