Дискретно-непрерывная математика (стр. 27 )

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

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

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

или

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

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

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

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

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

28. Теорема. Пусть — каноническое разложение т. Тогда для того чтобы числа А и В были равноостаточными при делении на т, необходимо и достаточно, чтобы они были равноостаточными при делении на на

Доказательство. Необходимость. Равноостаточность А и В при делении на m означает (А—В)т. Тем более и числа А и В оказываются равно­остаточными при делении на все

Достаточность. Пусть числа А и В при делении на каждое равноостаточны. Обозначим через ri остаток от деления А и В на Это значит, что

(7)

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

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

(8)

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

Ввиду равноостаточности А и В при деления на мы получаем также

(9)

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

т. е.

Ho сумма т1+ т2-+... +тk взаимно проста с т. В самом деле, если бы она имела с т некоторый общий простой дели­тель р, то он входил бы в каноническое разложение т, т. е. имел бы вид рi. Но тогда на него делилась бы как вся сумма, так и каждое слагаемое, кроме одного, mi, а этого быть не может.

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

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

(10)

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

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

б) Доказательство ведется по индукции. Полагая A0=0, В0= 1, A1 = 1, B1 = —q0, мы имеем

Пусть теперь

Но тогда

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

Числа Ап и Вп окажутся искомыми А и В.

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

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

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

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

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

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

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

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

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

34. Условия а) и б) выполняются автоматически. Поскольку при делении на 3 числа 10 и 1 равноостаточны, равноостаточными же должны быть и числа А и 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 представим число A в виде

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

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