ОТ АВТОРА

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

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

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

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

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

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

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

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

б) либо найти два таких целых числа q и г, чтобы имело место равенство: а = b-q + г, причем

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

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

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

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

0; ±6; ±2Ь; ±ЗЬ; . .

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

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

а = — 15, b = 3, тогда q = — 5;

а = 27, b = 4, значит, q = б и г = 3;

а = — 32, b = 5, тогда q = — 7 и г = 3.

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

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

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

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

каково бы ни было целое число а и натуральное число Ь, всегда найдутся такие целые числа q и г, чтобы, во-первых, имело место равенство а = b-q 4- г и во-вторых, чтобы имело место неравенство О г ; 6.

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

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

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

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

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

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

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

Доказательство. Пусть а • 6 и с'-b, значит, существуют такие целые числа qi и q₂, что а = bq_r, c = bq₂. Но тогда а 4- с = bq_t 4- bq₂ = b(q_v 4- q₂). Сумма двух целых чисел 4- Яг ^есть число целое. Обозначив его через q = q_t 4- q₂, получим: а 4- с = bq, значит, сумма а 4- с делится на 6.

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

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

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

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

1) Если а • (Ьс), то а \ b и а •с.

2) Если а • Ь, то и — а • Ь.

3) Если а • Ь и b • с, то а • с.

4) Если а • Ь, то и ах • b при любом целом х.

5) Если а • b и с '• Ь, то (ах 4- су) \ b при любых

целых хну.

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

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

Доказательство. Пусть а • Ь, но с не • ft. Предположим, что их сумма (а 4- с) • ft, тогда а 4- с = bq, откуда с = bq — а. Так как bq • ft и а • ft (по условию), то и их разность с должна делиться на ft, что противоречит условию. Следовательно, сумма а 4- с не может делиться на ft.

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

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

III. Мы видели, что каково бы ни было целое число а и натуральное число ft, всегда можно найти такие целые числа q и г, что а = bq 4- г, где 0 г ; ft.

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

Предположим, что существуют такие ft и н и q₂ и г₂, что а = bq! 4- и а = bq₂ 4- г₂, причем 0 ;. r_x ; ft и 0 ; r₂ ; ft. Примем, для определенности, что г₂ Тогда имеем: bq_x 4- i\ = bq₂ 4- г₂, или bq_r — bq₂ = r₂ — r_lt откуда r₂ — ri = b(q! — q₂). Мы видим, что r₂ — г_г делится на ft, а это возможно только тогда, когда

r% — r_x = 0, ибо 0 ; r₂ — r_x ; b. Получим: b (q_x — q₂) = 0, но b=£0, значит, q_x — q₂ = Q. Следовательно, r₂ = r_x и ;7i = ;7₂-

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

Упражнения

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

12. Докажите обратное утверждение: если разность двух чисел а п с делится на число Ь, то остатки от деления а и с на 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 и на И.

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

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

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

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

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

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

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

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

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

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

Пусть мы имеем («+ 1) — значное число¹, записанное с помощью цифр а_п, a_n-i, • , a_lt а₀ в десятичной системе счисления:

N = а_п- 10^я + a_n-i • 10^я-¹ + . + а₂-10² + а_х- 10 + а₀.

Требуется найти условия делимости этого числа N на некоторое число р. Обозначим частные и остатки от деления 10* на число р через q_k и r_k, где fe = 1, 2 п.

Ю =pgi + ri; Ю² = pq₂ + г₂;

10³ = pq₃ + Гз

Wⁿ = pq_n+r_n.

Подставив полученные выражения для 10* в запись числа N, получим: N = a_n(pq_n + r_n) + а_п-\ (pq_n-\ + r_rt-i) +

+ . . . 4" ^а2 (РЯъ + ^rz) 4~ ^ai (PQi + ^г1) 4* ^ав‘

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

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

N = (^апЯп + ^ап-1 Яп-1 + • • • + a₂q_z + а^) р +

+ (^ап^гп + ^ап—1 f п—1 4- . + а.₂г_й 4- ^ai^r 14" ^ао)'

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

М = а_пг_п + а_я_1Г_л_1 4- . + а₂г₂ + + а₀,

тогда N = (a_nq_n 4- . 4- ад)Р 4- М.

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

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

а) Пусть р = 2. Очевидно, что тогда = 0; г₂ = = 0; . ; г_п = 0, значит, М = а₀; следовательно:

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

б) Таким же образом получаем признак делимости чисел на 5, так как г_х = г₂ = . = г_п = 0, значит, М — а₀; следовательно:

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

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

10 =9+ 1,

10² = 99 4- 1,

10³ = 999 4- 1,

10" = 99 .9 4- 1,

то очевидно, что r_t = 1; г₂=1; .; r_n= 1, значит, М = а_п 4- Лл-1 4- • 4- 4~ Qo следовательно:

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

г) Подобным образом выводится и признак делимости чисел на 3. Остатки от деления степеней 10 на 3 будут: ri=l; r₂ = 1; .; r_n = 1, значит, M = a_n+a_n-i +

. 4- Oi 4- До’» следовательно:

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

¹ При делении 1 = 10* на р всегда получаем остаток, равный I,

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

10 = 11- 0+ 10, 10² = И- 94-1, 10³= 1Ь90 4- Ю и т. д.

Но 10= И — 1, поэтому удобно заменить а_г- 10 = (11 — 1) = а_х 11 —а_г.

Поступая аналогичным образом с г₃, г₆, .» число М представим в виде суммы двух слагаемых, одно из которых делится на 11:

М ⁼ (^fli + ^аз 4- 4~ • • •) • 11 4~ l(^flo 4~ ^а2 4- °4 + • • •) (^ai 4- Дз + ^fl5 4- • • •)]

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

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

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

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

5643; 14014; 35674; 5069812; 4192716.

111. Рассмотрим признак делимости чисел на 4. Так как 100 делится на 4, а 10 = 4-2 4-2, то г_х = 2; г₂ = 0; г₃ = 0; . ; г_п = 0. Значит, М = а₀ -f- 2а_х; следовательно:

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

Признак делимости чисел на 4 обычно формулируется в другой, более удобной для применения форме. Любое число N можно представить в виде # = 4-1004- 4- 10 а_х 4-а₀, где Д— число, выраженное цифрами числа N без а_г и а₀. Здесь М = 10а_х4-Яо есть число, выраженное двумя последними цифрами. Так как 100 = 4-25, можно утверждать:

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