Новости    Библиотека    Энциклопедия    Биографии    Карта сайта    Ссылки    О проекте




предыдущая главасодержаниеследующая глава

Решения задач

1. 0 = а × 0 при любом а.

2. а = 1 × а, значит, а 1.

3. Пусть 1 а. Это значит, что 1 = ас при некотором целом с. Отсюда следует, что |а|≤1. А так как а ≠ 0, должно быть а = 1.

4. Достаточно взять любое с > 1 и положить b = ас.

5. В качестве такого b можно взять, например, 2а, Пусть при этом для некоторого с и 2а с и с а. Это значит, что найдутся такие d1 и d2, что 2а = d1c и с = d2a. Отсюда следует, что 2а = d1d2a или, после сокращения на а,

2 = d1d2.

Но при целых d1 и d2 такое равенство возможно лишь в случае, когда одно из этих чисел равно 1, а другое 2. Если d1 = 1, то с = 2а = b; если же d1 = 1, то с = а.

6. Доказательства ничем не отличаются от доказательств в случае обычной делимости.

7. Пусть n - некоторое фиксированное число, большее единицы. Положим а n b, если найдется такое целое с, что а = bc и c ≤ n. Справедливость теорем, аналогичных теоремам 1, 3 и 4, проверяется без труда. Однако если мы возьмем а = nb и b = nc, то а n b и b n с. В этом случае а = n2с, а так как n2 > n, делимость а n с не имеет места. Точно также не имеет места делимость (а + а) n b.

8. а) Пусть имеются два минимальных числа a1 и a2. В силу дихотомичности либо a1 ≥ а2, либо а2 ≥ а1. Если a1 ≥ а2, то из минимальности a1 следует, что a1 = а2. Вели же а2 ≥ a1, то a1 = а2 следует из минимальности а2.

б) Пусть а - некоторое число, a b1 и b2 - два непосредственно предшествующих ему числа. По дихотомичности должно быть либо b1 ≥ b2, либо b2 b1. Пусть, для определенности, b1 ≥ b2. Мы имеем a ≥ b1 ≥ b2, а так как число b2 непосредственно предшествует числу а, должно быть либо b1 = а, либо b1= b2. Но по условию b1 ≠ а; значит, b1 = b2, и требуемая единственность доказана.

в) Непосредственно следующим за а числом называется такое b, что b ≥ а, b ≠ а, и из b ≥ с ≥а следует либо c = b, либо с = а.

Предположим, что некоторое а не имеет непосредственно следующего за ним числа. Это значит, что для любого аn ≥ а и отличного от а найдется такое аn+1 отличное как от аn, так и от а, что аn ≥ аn+1 ≥ а. Возьмем теперь произвольное a1 ≥ а и отличное от а (в силу 2° это сделать можно) и, исходя из него, построим бесконечную последовательность различных чисел

a1 ≥ а2 ≥ ... ≥ an > an+1 ≥ ... ≥ a.

Существование же этой последовательности противоречит 4°. Следовательно, непосредственно следующее число существует. Единственность его устанавливается при помощи дихогомичности подобно тому как это делалось в пп. а) и б).

9. Остается в силе транзитивность (3°), неограниченность множества чисел (5°), свойство 4° и существование непосредственно предшествующего числа (6°). Дихотомичность заменяется трихотомичностыо (либо a > b, либо b > а, либо а = b).

Становится неверным свойство рефлексивности (1°), ибо а > а всегда неверно.

Что же касается, наконец, утверждения 2°, то формально оно остается в силе (хотя, быть может, и выглядит несколько Парадоксально).

В самом деле, говоря строго, это утверждение в нашем случае формулируется так: для любых натуральных чисел а и b из а > b и b > а следует а = b.

Предположим, что это высказывание неверно. Тогда найдутся такие натуральные числа а и b, что одновременно будет и а > b и b > а, и а ≠ b, а этого не может быть. Полученное противоречие доказывает истинность нашего утверждения.

10. Пусть множество упорядочено отношением обладающим свойствами 1 - 7°. Как уже было установлено, оно обладает минимальным элементом. Обозначим этот элемент через а0. Из результатов задачи 8 следует, что каждый элемент обладает непосредственно следующим. Обозначим непосредственно следующий за а0 элемент через a1, непосредственно следующий за a1 - через a2 и т. д. В итоге мы получаем последовательность

а0, a1, a2 (Р.1)

в которой аn+1an при любом n. По рефлексивности и транзитивности отношения отсюда следует, что aiaj тогда и только тогда, когда i ≥ j. Нам остается показать, что последовательность (Р.1) охватывает все рассматриваемые нами объекты. Это достигается довольно тонким рассуждением по индукции.

Предположим, что b0 не принадлежит последовательности (Р.1). Получение этого b0 будем считать первым шагом нашего индуктивного рассуждения. Пусть n его шагов уже проведены, в результате чего нами получен некоторый элемент bn-1.

Если bn-1 = а0, то наш процесс будем считать законченным; если же bn-1 ≠ a0, то элемент bn-1 имеет непосредственно пред-шествующий, который мы и возьмем в качестве bn. В результате получаем последовательность различных элементов


На основании 4° эта последовательность должна иметь последний член. Но по самому принципу построения этой последовательности ее последним членом может быть только а0. Пусть для определенности bn = a0.

Нетрудно проверить, что если некоторое а непосредственно предшествует b, то b непосредственно следует за а. Значит, bn-1 = a1, bn-1 a1, bn-2 = a2, . . .,b0 = an.

Последнее означает, что b0 принадлежит последовательности (Р.1), но это противоречит предположенному. Следовательно, последовательность (Р.1) содержит все рассматриваемые нами объекты.

11. Пусть а - некоторое число. Всякую последовательность различных чисел а0 = a, a1, а2, . .. , аn, для которых


где an минимально в смысле упорядочения , назовем цепью Предшественников а0. Число n называется длиной этой цепи.

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

В самом деле, пусть а - некоторое число, a b1, b2, ..., bk - непосредственно предшествующие ему числа.

Если a1 не предшествует a0 непосредственно, мы можем на основании 9° вставить в цепь (Р.2) некоторое непосредственно предшествующее а число. Поэтому если имеются сколь угодно Длинные цепи предшественников а, должны найтись и такие его сколь угодно длинные цепи предшественников, которые начинаются с чисел, непосредственно предшествующих а. Будем далее рассматривать только такие цепи.

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

Значит, при нашем предположении хотя бы одно из чисел, непосредственно предшествующих а0, имеет сколь угодно длинные цепи предшественников. Обозначим это число через а1 и повторим в применении к нему все только что проведенные рассуждения. Это даст нам некоторое число а2, непосредственно предшествующее а1 и имеющее сколь угодно длинные цепи предшественников. Повторяя этот процесс, мы приходим к последовательности


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

Следовательно, для каждого числа а среди его цепей предшественников можно выбрать самую длинную. Обозначим ее длину через n(а). Если b непосредственно предшествует а, ТО очевидно, n(b) = n(а)-1, а для всех минимальных a n(a) = 0.

Пусть, наконец, А (а)-высказывание, зависящее от а. Обозначим через В(n) высказывание "A(а) верно для всех чисел а, для которых n(а) = n". Тогда, как легко видеть, формулировка принципа индукции в новой форме для утверждений А (а) совпадает с формулировкой этого принципа в старой форме для утверждений В(n).

12. Каковы бы ни были четные числа а и b, существуют такие четные числа q и r, что

a = bq + r (0 ≤ r < 2b).

Такие числа q и r единственны.

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

а = 2bq + r (0 ≤ r < 2b). (Р.3)

При этом числа q и r определяются однозначно. Из четности и 2bq следует четность их разности, т. е. числа r. Нам остается, положив 2q = q', переписать (Р.3) в виде

а = q'b + r (0 ≤ r < 2b)

и заметить, что оба числа q' и r четные и определяются единственным образом.

13. Пусть р - наименьший простой делитель числа а. Отсюда следует, что а = pb. Всякий простой делитель q числа b является вместе с тем и делителем а. Поэтому q ≥ р, значит, и b ≥ р, так что а ≥ р2 и, наконец, р ≤ √а .

14. Пусть р1, р2,..., pk - полный список всех простых чисел, входящих хотя бы в одно из канонических разложений а и b. Положим

a = p1α1p2α2....pkαk
b = p1β1p2β2....pkβk

(Если а не делится на рi, то αi = 0; если b не делится на pi, то βi = 0.) Пусть γi - наибольшее из чисел αi и βi для t = 1, 2, ..., k, а δi - наименьшее из них.

Тогда, на основании теоремы 17, наибольший общий делитель а и b есть p1δ1p2δ2....pkδk а их наименьшее общее кратное - p1γ1p2γ2....pkγk.

15. Как следует из теоремы 17, каждый делитель числа а с каноническим разложением p1α1p2α2....pkαk должен иметь вид p1β1p2β2...pkβk, где β1 принимает α1 + 1 значений: 0, 1, 2, ..., α1, β2 принимает α2 + 1 значений и т. д. Так как любые комбинации этих значений возможны и дают нам все делители а, причем; каждый по одному разу (если бы какой-нибудь делитель повторился несколько раз, то это означало бы наличие у него нескольких канонических разложений), число делителей а равно

1 + 1)(α2 + 1)...(αk + 1). (Р.4)

16. Пусть каноническое разложение а есть p1α1p2α2....pkαk. Очевидно, можно положить p1 = 2, α1 ≥ 2 и р2 = 3, α2 ≥ 1. Далее, согласно (Р.4), мы имеем

1 + 1)(α1 + 1)....(αk +1) = 14.

Отсюда k = 2, α1 + 1 = 7 и α2 + 1 = 2. Таким образом, α = 26×3 = 192.

17. Мы имеем

τ(a2) = τ(p11p22) = (2α1 + 1) (2α2 + 1) = 81,

так что (2α1 + 1) (2α2 + 1) есть разложение числа 81 на два множителя. Так как нумерация простых делителей а зависит от нас, ограничимся рассмотрением следующих возможностей:

1 + 1 = 1, 2α2 + 1 = 81;
1 + 1 = 3, 2α2 + 1 = 27;
1 + 1 = 9, 2α2 + 1 = 9.

В первом из этих случаев α1 = 0, что противоречит предположенной положительности числа α1. Оставшиеся случаи дают там

α1 = 1, α2 = 13;
α1 = 4, α2 = 4.

Значит, либо


либо


18. Пусть p1α1p2α2....pkαk - каноническое разложение числа а. Условие задачи дает нам


или


Заметим, что




Поэтому в (Р.5) слева каждая дробь не меньше единицы и, следовательно, ни одна из дробей не может быть больше, чем 2. Значит, в левой части (Р.5) могут стоять лишь дроби из следующего набора:

21/(1+1), 22/(2+1), 23/(3+1), 31/(1+1)

причем их произведение есть 2. Но это может быть лишь в двух случаях: когда в (Р.5) слева стоит только одна дробь 23/(3+1) или когда там стоят две дроби 22/(2+1), 31/(1+1).Этим двум случаям соответствуют два ответа задачи: 8 и 12.

19. Напишем каноническое разложение числа а:

a = p1α1....pkαk

Тогда

a2 = p11....pkk

и согласно (Р.4) (задача 15)


Легко видеть, что каждая дробь (2αi + 1)/(αi + 1) с ростом αi возрастает (приближаясь к 2), так что наименьшее значение этой дроби будет достигаться при αi = 1 и будет равно 3/2. Это значит, что


Ясно, что при достаточно большом k будет (3/2) > K. Для этого достаточно взять


Например, при K = 100 достаточно взять k > 2/0,18 == 11,1; так как число k должно быть целым, можно взять k = 12.

20. Аналоги теорем 11-14 для четной делимости неверны. В самом деле, числа 30 и 42 четно простые. Их наименьшее четное кратное есть 420, а произведение - 1260.

Далее, 60 = 6×10 четно делится на четно простое число 30; 6 и 30 четно взаимно просты, а 10 четно на 30 не делится.

Наконец, 60 = 6 × 10 = 30×2 - два различных разложения числа 60 на четно простые множители.

21. а) 116 при делении на 8 равноостаточно с 4, а 17 - с 1. Значит, А равноостаточно с 521 = (52)10×5. Но 52 = 25 при делении на 8 равноостаточно с единицей. Следовательно, А при делении на 8 дает в остатке 5.

б) 14 при делении на 17 равноостаточно с -3. Поэтому А равноостаточно с (-3 )256 = 3256 = (33)85×3. Но 33 мы можем заменить на 10: 1085×3 = (102)42×30. Далее, 102 при делении на 17 равноостаточно с числом -2, а 24 с -1. Значит, А равноостаточно с (-2)42×30 = 242×30 = (24)10×4×30 = (-1)10×4×30 = 120. Последнее же число при делении на 17 дает в остатке 1.

22. а) Пусть n1 - остаток от деления n на 6. Тогда n1 может принимать значения 0, 1, 2, 3, 4 и 5, а n31 + 11n1 при делении на 6 равноостаточно с n3 + 11n. Значит, нам следует испытывать делимость на 6 чисел 0, 12, 30, 60, 108 и 180. Но все эти числа на 6 делятся.

Для получения того же результата можно воспользоваться и более частными соображениями. Число n3 + 11n равноостаточно при делении на 6 с числом n3 + 11n - 12n = n3 - n = (n - 1)n(n + 1). Но из трех последовательных целых чисел n - 1, n и n + 1 хотя бы одно - четное (т. е. делится на 2) и ровно одно делится на 3. Значит (согласно следствию теоремы 11), произведение этих трех чисел делится на 6. Кстати, можно заметить, что


б) При n ≥ 2 мы имеем (пользуясь формулой бинома)


и оба слагаемых, очевидно, делятся на 9.

При n = 1 наше выражение равно 41 + 15×1 - 1 = 18.

в) Доказательство ведется по индукции.

При n = О


Пусть теперь делимость


имеет место. Тогда


Первый сомножитель справа делится на 3n+2 по индуктивному предположению. Во втором же сомножителе мы можем заменить десятки на равноостаточные им при делении на 3 единицы; полученное число 3 показывает, что второй сомножитель делится на 3. Следовательно, все произведение делится на 3n+3 = 3(n+1)+2 что и требовалось.

г). При делении на а2- а + 1, очевидно, а2 равноостаточно с а - 1. Значит,


равно-остаточно с


что и требовалось.



23. Пусть ~ - эквивалентное отношение на множестве чисел. Возьмем произвольное число а и рассмотрим все числа, эквивалентные а. Все они ввиду транзитивности отношения ~ эквивалентны между собой. Обозначим через К класс всех этих чисел.

Рассмотрим теперь произвольное число b, не принадлежащее К? Если бы было b ~ с, где с - некоторое число из К, то было бы и b ~ а, чего, однако, не может быть по выбору b. Значит, ни одно из чисел, лежащих вне К, не эквивалентно ни одному из чисел К. Следовательно, К есть класс эквивалентности, содержащий а.

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

24. Очевидно, среди чисел 0, 1, ..., m найдутся два, принадлежащие одному классу. Пусть этими числами будут k и l k ~ l. Таких пар чисел из одного класса может оказаться, вообще говоря, и несколько. Выберем ту из них, для которой величина |k - l| будет наибольшей. Поскольку - l ~ - l, мы, по условию, получаем

k - l ~ l - l = 0.

Далее, мы находим, что и при любом целом n

n(k - l) ~ 0.

Наконец, при любом r

n(k - l) + r ~ r,

т. е. из а ≡ b(mod k - l) следует а ~ b, Таким образом, классы отношения ~ содержат целиком классы вычетов по модулю m.

Для того чтобы классов ~ -эквивалентности было m, необходимо, чтобы каждый класс ~ -эквивалентности содержал не более одного класса вычетов и чтобы k - l = m.

25. а) Обе части сравнения и модуль можно разделить на одно и то же число (разумеется, отличное от нуля).

В самом деле,

ad ≡ bd (mod md)

означает, что


т. e.


откуда a ≡ b (mod m).

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

Действительно, если d и m взаимно просты, то из

ad ≡ bd (mod m),

т. е. из


следует на основании теоремы 12, что (а - b) m, что и требовалось.

26. Предположим, что

1 ≤ k < l ≤ p - 1, ka ≡ la (mod р).

Это значит, что (l - k)a р. Поскольку а не делится на р, должно быть (l - k) р. Но и этого не может быть, так как 0. < l - k < p.

27. Необходимость. Пусть число р простое. Возьмем 0 < q < р. Среди чисел q, 2q, ..., (p - 1)q найдется ровно одно, дающее при делении на р в остатке единицу. Пусть этим числом будет qq:

qq ≡ 1(mod р). (Р.6)

С другой стороны, среди чисел q, 2q, ..., (p - 1)q также может быть лишь одно, дающее при делении на р в остатке единицу. Это, как уже установлено, число qq.

Выясним, в каких случаях q = q. Во всех таких случаях сравнение (Р.6) переписывается так:

q2 = 1(mod р),

или, что то же самое,

q2 - 1 ≡ 0 (mod р).

Это значит, что


Ввиду того, что число р простое, по теореме 13 должно быть либо (q + 1) р, либо (q - 1) р. Так как число q заключено между нулем и р, первый из этих случаев возможен лишь при q = p - 1, а второй - при q = 1. Таким образом, при р = 2 и р = 3 всегда q = q, при р ≥ 5 - лишь в случаях q = 1 и q = p - 1.

Следовательно, при р ≥ 5 все оставшиеся числа 2, ..., р - 2 можно объединить в такие (р - 3)/2 пары, что произведение чисел, составляющих каждую из пар, при делении на р дает в остатке 1. Выпишем сравнения вида (Р.6) для всех таких пар, добавив в этот список сравнение

р - 1 ≡ р - 1 (mod р),

и перемножим все (р - 1)/2 полученных сравнений почленно.

В результате такого умножения мы получим слева произведение всех чисел от 2 до р - 1, а справа р - 1:

2×3 ... (р - 1) ≡ р - 1 (mod р),

или

1×2×3... (р - 1) + 1 ≡ 0(mod p).

Последнее сравнение означает, что


а это и требовалось.

Остается проверить случаи р = 2 и р = 3. Но для них, очевидно, (1 + 1) 2 и (2 + 1) 3.

Достаточность. Если число р не простое, то оно может быть разложено в произведение двух меньших множителей: р = p1р2.

Если р1 ≠ р2, то и p1 и р2 входят сомножителями в произведение 1×2...(р - 1), которые тем самым делятся на р1p2, т.е. на р. Пусть теперь p1 = р2 = q. Тогда р = q2 (т. е. р есть квадрат простого числа). Если q > 2, то p > 2q, и в произведение 1×2...(р - 1) входят множителями q и 2q, так что в этом случае оно делится на q2, т. е. на р. В обоих случаях 1×2...(р - 1) + 1 на р делиться не может. Наконец, если р = 4, то 1×2×3 - 1 = 5, и на 4 не делится.

28. Теорема. Пусть m = р1α1р2α2 ... рkαk - каноническое разложение m. Тогда для того чтобы числа А и В были равноостаточными при делении на m необходимо и достаточно, чтобы они были равноостаточными при делении на р1α1 на р2α2,...., на pkαk.

Доказательство. Необходимость. Равноостаточность А и В при делении на m означает (А - В) m. Тем более (А - В) рiαi (i = 1, ..., k), и числа А и В оказываются равноостаточными при делении на все рiαi.

Достаточность. Пусть числа А и В при делении на а, каждое piαi равноостаточны. Обозначим через ri остаток от деления А и В на рiαi (i = 1, 2, ,. k). Это значит, что


Положим, далее,


и умножим в сравнении (Р.7) обе части и модуль на mi.


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


Ввиду равноостаточности A и В при делении на p1α1, p2α2,...,pkαk мы получаем также


Вычтя почленно сравнение (P.9) из (P.8), мы имеем

(A - В) (m1 + m2 + ... + mk) ≡ 0 (mod m),

т. е. (A - B) (m1 + m2 + ... + mk) m.

Но сумма m1 + m2 + ... + mk взаимно проста с m. В самом деле, если бы она имела с m некоторый общий простой делитель р, то он входил бы в каноническое разложение т, т. е. имел бы вид pi. Но тогда на него делилась бы как вся сумма, так и каждое слагаемое, кроме одного, mi, а этого быть не может.

Теперь мы можем применить теорему 12, которая даст, что (A - В) m, т. е. числа А и В при делении на m равноостаточны.

29. а) Выпишем систематически все равенства, описывающие деления с остатком, которые составляют применение алгорифма Евклида к числам а и b:


Мы имеем rn-1 rn. Вместе с rn-2 = rn-1qn-1 + rn, это дает нам rn-1 r. Продвигаясь аналогичным образом вверх по системе равенств (Р. 10), мы получаем, наконец, что а rn и b rn, Значит, rn есть общий делитель а и b.

Пусть d - любой общий делитель а и b. Вместе с а = bq0 + r1 это дает нам r1 d. Продвигаясь по системе равенств (Р.10) вниз, мы будем последовательно получать, что r2 d, r3 d,..., rn d. Значит, rn делится на любой общий делитель а и b, являясь тем самым наибольшим общим делителем этих чисел.

б) Доказательство ведется по индукции. Полагая А0 = 0, В0 = 1, A1 = 1, В1 = -q0, мы имеем r0 - b = аА0 + bВ0 и r1 = аА1 + bВ1.

Пусть теперь



Но тогда


и нам остается положить



Числа An и Bn окажутся искомыми A и В.

30. Если бис взаимно просты, то по предыдущему можно найти такие целые В и С, что

bВ + cC = 1,

или, после умножения на а,

аbВ + асС = а;

ab с по условию; ас с очевидным образом; значит, и а с.

31. Ограничимся рассмотрением признака равно-остаточности при делении на 8.

Пусть произвольное натуральное А представлено в виде 1000а + b, где 0 ≤ b < 1000 (т. е. b - трехзначное число, которым оканчивается А), и


32. Ограничимся рассмотрением признака равно-остаточности при делении на 18 в двенадцатеричной системе счисления.

Пусть А представлено в виде 144а + b, где 0 ≤ b < 144 (т. е. b - двузначное в двенадцатеричной системе счисления число, которым оканчивается записанное в этой системе число A), и


Проверка того, что процесс построения последовательности A, f(A), f(f(A)), ... действительно является признаком равноостаточности, осуществляется стандартно.

33. Для тех m, у которых каноническое разложение имеет вид 2α×5β.

34. Условия а) и б) выполняются автоматически. Поскольку при делении на 3 числа 10 и 1 равноостаточны, равноостаточными же должны быть и числа A и f(A). Наконец, то, что f(A) < A при А ≥ 3, устанавливается простым подсчетом.

35. а) f(858 773) = 38; f(38) = 11; f(11) = 2.

б) f(A) = 4444.4 = 17 776; f(17 776) = 28; f(28) = 10; f(10) = 1.

36. Признак равноостаточности при делении на 9 аналогичен рассмотренному признаку равноостаточности при делении на 3.

Для получения признака равноостаточности при делении на 11 представим число А в виде


где 0 ≤ ai < 100. Очевидно, такое представление соответствует разбиению числа на двузначные "грани" (справа налево). Пусть


Нам остается указать, что числа А и f(A) действительно равноостаточны при делении на 11 и, кроме того, f(A) < A.

Другой признак равноостаточности при делении на 11 получается на основе представления числа A в виде


и использования того, что 10 при делении на 11 равноостаточно с -1, а 100 - с 1. Поэтому А равноостаточно с числом а0 - а1 + а2 - а3 +... ± аn, и формулировка соответствующего признака равноостаточности не составляет труда.

Наконец, можно, разбивая число А на трехзначные "грани", представить его в виде


(0 ≤ ai < 1000). Тогда А при делении на 37 равноостаточно с суммой а0 + a1 + ... + an, а при делении на 7, 11, 13 - со знакопеременной суммой а0 - a1 + a2 - ... ± an.

37. Для примера рассмотрим признак равноостаточности на 8 в троичной системе счисления. Представим для этого произвольное А в виде


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


и провести стандартные рассуждения.

38. В шестеричной системе счисления: 5 (k = 1), 7 (k = 2), 43 (k = 3);

В семеричной системе счисления: 2, 3, 6 (k = 1),4, 6, 12, 16, 24 (k = 2), 171 (k = 3);

В девятеричной системе счисления: 2, 4, -8 (k = 1),5, 10, 20, 40 (k = 2), 7, 13, 14, 26 и т. д. (k = 3);

5 В тринадцатеричной системе счисления: 2, 3, 4, 6 (k = 1), 7, 14, 21 и т. д. (k = 2).

39. В троичной системе счисления: 2, 4 (k = 1), 8, 12, 24 (k = 2), 13, 26 (k = 3), 41 (k = 4);

В пятеричной системе счисления: 2, 3, 6 (k = 1), 8, 12, 24 (k = 2), 31 (k = 3);

В восьмеричной системе счисления 3, 9 (k = 1),5, 13 (k = 2);

В десятичной системе счисления: 11 (k = 1), 101 (k = 2), 7, 11, 13 (k = 3).

40. Если числа а и b равноостаточны, то (а - b)m. Поэтому в силу теоремы 6 числа а и b делятся или не делятся на m одновременно.

Числа 4 и 5 равноделимы, но не равноостаточны при делении на 3.

41. Пусть из равноделимости на m следует равно остаточность при делении на m. Это значит, что все не делящиеся на m числа имеют при делении на m один и тот же остаток. Значит, этот остаток должен быть равен единице, так что m = 2.

42. Отношение равноделимости на m, очевидно, является рефлексивным (всякое число равноделимо на m с самим собой), симметричным (если а равноделимо с b, то и b равноделимо с а) и транзитивным (если а равноделимо с b, а b равноделимо с с, то и а равноделимо с с).

Следовательно, это и есть отношение эквивалентности. При этом в один класс попадают все числа, делящиеся на b, а в другой - все не делящиеся на m.

43. Нетрудно проверить, что при m > 2 равноделимость сумм не следует из равноделимости слагаемых.

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

В самом деле, если одно из произведений делится на простое р, то по теореме 13 на это р должен делиться хотя бы один из сомножителей этого произведения. Но тогда на р делится равноделимый ему сомножитель другого произведения, а потому и все произведение. Если же одно произведение на р не делится, то и другое на р делиться не может (ибо в противном случае, на основании только что установленного, на р делилось бы и первое произведение).

Наоборот, если число р составное, то произведения равноделимых сомножителей могут уже равно-4 делимыми не быть. Достаточно положить р = р1р2 (p1 ≠ 1, р2 ≠ 1). Тогда числа 1 и p1, а также числа 1 и р2 равноделимы на р, а произведения 1×1 и p1×p2, очевидно, нет.

44. Непосредственное следствие задачи 36.

45. Выполнение условий а) и б) очевидно.

Если, далее, а - 2b ≥ 0, то, очевидно, f(A) < A. Если же а - 2b < 0, то это неравенство может и нарушиться. При этом наибольшее значение модуля |а - 2b| достигается при а = 0 и b = 9 и равно 18. Следовательно, при А ≥ 19 должно быть f(A) < A. Справедливость этого неравенства при меньших значениях обеспечивается определением функции f.

Наконец, 10а + b равноделимо на 7 с 50а + 56 (ибо числа 5 и 7 взаимно простые) и тем самым с 50а + 5b - 7 (7а + b) = а - 2b.

46. Число 15 при делении на 7 дает в остатке 1, а 1 - 2×5 = -9 дает в остатке 5.

47. Условие в) f(A) < A означает а + 4b < 10а + b, т. е. 3b < 9а. Поэтому при а ≥ 4 нужное условие выполняется.

Условие г) очевидно, 10а + b при делении на 13 равноделимо с 40а + 4b, а последнее число равноостаточно с а + 4b.

48. Признак делимости утратит результативность, так как f(39) = 39.

49. Пусть нам нужно построить признак делимости на некоторое m. Постараемся подобрать такое s, взаимно простое с m и по возможности небольшое, что (10s + 1) m (так было в случае m = 7; s оказалось равным 3) или же (10s - 1) m (например, при m = 13, s = 4).

В первом из этих случаев А = 10а + b равноделимо на m с

10as + bs = (10s + 1)a - a + bs,

т. e. с a - bs, а во втором - с

(10s - 1)a + a + bs,

т. e. с a + bs.

В связи со сказанным число 10a + b

при делении на 17 равноделимо с а - 5b,


Завершение точных формулировок этих признаков делимости предоставляется читателю.

50. а) Так как 100 при делении на 49 равноостаточно с 2, всякое число вида


при делении на 49 равноостаточно с


б) 10a + b при делении на 49 равноделимо с a + 5b.

51. Очевидно, при А ≥ 6 должно быть f(A) < A.

52. а) В семеричной системе счисления представление А в виде 7 а + b дает, что при делении на 5 число А равноделимо с a + 3b;

б) В одиннадцатиричной системе счисления представление А в виде 11а + b дает, что при делении на 7 число А равноделимо с а + 2b;

в) В двенадцатиричной системе счисления, представляя А в виде 12а + b, получаем, что при делении на 17 число равноделимо с а - 7b.

53. Условия а) и б) выполняются автоматически. Условия в) и г) соблюдаются потому, что переход от A к F(A) сводится к замене некоторых чисел на их остатки при делении на А (которые меньше самих чисел и равноостаточны с ними).

54. а) r2 = r3 = ... = rn = 0, т. е. rk = 0 (k ≥ 2);

б) r3 = r4 = ... = rn = 0, т. е. rk = 0 (k ≥ 3);

в) r1 = r2 =... = rn = 1, т. е. rk = 1;

г) r1 = r3 = . . . = r2t-1 = -1, r2 = r4 = r2t = 1, т. е. rk = (-1)k;

д) r6t+1 = 3, r6t+2 = 2, r6t+3 = 6, r6t+4 = 4, r6t+5 = 5, r6t = 1.

55. Предоставляется читателю.

56. Возьмем произвольное m и положим

r1 равным остатку от деления t на m,

r2 >> >> >> tr1 на m

и т. д. Тогда число


при делении на m равноостаточно с числом


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

57. Предоставляется читателю.

58. 102 = 7×14 + 2, так что r = 2, и мы имеем

А0 = 1 048 576, А1 = 1×23 + 4×22 + 85×2 + 76 = 270, A2 = 2×2 + 70 = 74, A3 = 4.

59. Если t равноостаточно с r = r1 при делении на m, то


и т. д.

60. Ни 24 - 2, ни 23 - 1 не делятся на 4.

61. Если ар, то ар, и теорема доказана. Если же а не делится на р, то а взаимно просто с р, и мы можем приведенное в условии теоремы сравнение сократить:


Для доказательства последнего сравнения разделим каждое из чисел вида ta (t = 1, 2, ..., р - 1) на р с остатком:

ta = qtp + rt.

Это можно переписать так:


Из результата задачи 26 следует, что среди чисел rt ровно по одному разу встретится каждое из чисел 1, 2, ..., р - 1. Перемножая все сравнения, мы получаем


Нам остается это сравнение сократить на 1×2 ...(р - 1).

62.




63. Будем искать m в виде p1α1p2α2...pkαk. Тогда


Стоящее слева произведение должно делиться на 5. Значит, либо одно из чисел p1, р2,...,pk есть 5 (пусть для определенности р1 = 5), либо на 5 делится одна из разностей p1 - 1, p2 - 1,....,pk - 1 (пусть в этом случае (p1 - 1)5). В первом из этих случаев p1 - 1 = 4, чего не может быть, так как 10 на 4 не делится. Второй случай, поскольку р1 должно быть простым числом и 10(p1 - 1), возможен лишь при p1 = 11. Но тогда α1 = 1, и из теоремы 25 следует, что


т. е. либо m ÷ 11 = 1 либо m ÷ 11 = 2.

В итоге мы имеем m1 = 11, m2 = 22.


Если m нечетное, то α1 = α2 = ... = αk = 1 (ибо правая часть написанного равенства есть степень двойки):

(p1 - 1)(p2 - 1)....(pk - 1) = 8.

Это возможно лишь при k = 2, p1 = 3, р2 = 5, т. е. при m = 15.

Пусть теперь число m - четное. Положим для определенности p1 = 2. Очевидно, по-прежнему α2 = ... = αk = 1, и мы имеем


Очевидно, α ≤ 4. Если а = 1, то случай подобен рассмотренному: написанное неравенство возможно так же лишь при k = 3, р2 = 3, р3 = 5, т. е. при m = 30.

Если α = 2, то k = 2, р3 = 5 и m = 20.

Если а = 3, то k = 2, р2 = 3 и m = 24.

Если, наконец, а = 4, то k = 1 и m = 16.

Итак, решения нашей задачи: m1 = 15, m2 = 30, m3 = 20, m4 = 24, m5 = 16.

64. Предположим, что


Каждое из чисел вида pi - 1 есть либо единица, либо четное число, и потому не может быть семеркой. Будучи на единицу меньше простого числа, оно не может равняться 14. Значит, семеркой является одно из чисел рiαi-1. Но тогда pi - 1 = 6, а 14 на 6 не делится.

65. Пусть m = p1α1p2α2...pkαk. Рассмотрим сначала случай, когда m есть степень простого числа: m = рα. Для того чтобы некоторое число было взаимно простым с m, необходимо и достаточно, чтобы оно не делилось на р. Но среди чисел 0, 1, 2, ..., m - 1 имеется всего m ÷ p делящихся на р чисел. Следовательно, взаимно простых с р чисел в этом списке имеется столько:


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

По только что установленному число остатков от деления на piαi взаимно простых с piαi, равно φ(piαi). Но, как было выяснено в процессе решения задачи 28, из равноостаточности чисел при делении на все piαi следует их равноостаточность при делении на m, и наоборот. Кроме того, для взаимной простоты некоторого числа с m необходимо и достаточно, чтобы оно было взаимно просто с каждым из чисел

Следовательно, каждой комбинации остатков от деления на p1α1,p2α2,...,pkαk взаимно простых с соответствующими делителями, соответствует ровно один остаток от деления на m, взаимно простой с m. Нам остается заметить, что число таких комбинаций остатков равно


66. Мы имеем

a1 = A + q1m1 и а2 = А + q2m2.

Поэтому


Здесь по теореме Эйлера первое слагаемое при делении на m1m2 равноостаточно с A, а второе делится на m1m2. Значит, вся сумма при делении на m1m2 равдростаточна с А.

67. Предоставляется читателю.

68. Предоставляется читателю.

69. Предоставляется читателю.

70. n13 - n = n(n12 - 1). Но


Поэтому либо n p, либо (n12 - 1) р для р = 2, 3, 5, 7,13. Остается сослаться на теорему 16.

71. Предоставляется читателю.

72. Предоставляется читателю.

73. Пусть наибольший общий делитель чисел а и b есть d. Если с не делится на d, то уравнение

ах + by = с

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

74. Пусть А и В таковы, что

аА + bВ= 1.

Положим

xt = сА + bt,
yt = c(1 - aA)/b -at

Тогда

axt + byt = a (сА + bt) + b(с(1 - аA)/b - at) = саА + аbt + с(1 - аА) - аbt = с,

и (xt,yt) действительно является решением нашего уравнения.

75. а) xt = 9 × 55 + 7t = 28 125 + 7t,


Поскольку свободные члены и коэффициенты при t в выражениях для xt и yt, так сказать, "примерно пропорциональны", мы можем надеяться получить представления наших решений в меньших числах.

В самом деле, мы можем написать:

xt = 6 + 7(t + 4017),
yt = - 3 - 5 (t + 4017),

или, полагая

t + 4017 = t',

мы получаем

xt', = 6 + 7t',
yt' s = - 3 - 5t'.

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

б) Воспользуемся тем, что 25 по модулю 13 при-надлежит показателю 2. Мы можем написать:

xt = 8 × 5 + 13 = 200+ 13t,

или, после упрощений,

xt' = 5 + 13t',
yt' = - 9 - 25t'.

76. Условие в) обеспечивается автоматически, а условие г) следует из теоремы 25.

78. Предоставляется читателю.

79. Предоставляется читателю.

80. a) 8φ(21)-1 = 811 = 645×8. При делении на 21 это число равноостаточно с 8. Значит, числа 8а + b и а + 8b равноделимы на 21.

б) 12φ(31)-1 = 1229 = (122)14×12 = 14414×12 при делении на 31 равноостаточно с 1114×12 = 1217×12 = (-3)7×12 = -(33)2×3×12 = -(31 -4)2(31 + 5), что равноостаточно с -16×5 = -80. Последнее число очевидно равноостаточно с 13. Значит, числа 12а + b и а + 13b равноделимы на 31

предыдущая главасодержаниеследующая глава




ИНТЕРЕСНО:

Многомерный математический мир… в вашей голове

В школах Великобритании введут китайские учебники математики

Найдено самое длинное простое число Мерсенна, состоящее из 22 миллионов цифр

Как математик помог биологам совершить важное открытие

Математические модели помогут хирургам

Почему в математике чаще преуспевают юноши

Физики-практики откровенно не любят математику

В индийской рукописи нашли первое в истории упоминание ноля

Вавилонская глиняная табличка оказалась древнейшей «тригонометрической таблицей» в мире

Ученые рассказали о важной роли игр с пальцами в обучении детей математике
Пользовательского поиска

© Злыгостев Алексей Сергеевич, статьи, подборка материалов, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить ссылку на страницу источник:
http://mathemlib.ru/ 'MathemLib.ru: Математическая библиотека'
Рейтинг@Mail.ru