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

Описанный процесс является общим признаком равноостаточности в том смысле, что по любому т он выдает некоторый конкретный признак равноос­таточности. Это вытекает из алгоритмичности пред­ставления числа т в форме, указываемой в теоре­ме 18, а сама эта алгоритмичность следует из алго­ритмичности построения канонического разложения чисел (см. п. 9 п. 4.7).

Нам остается сформулировать в явном виде ука­занный признак равноостаточности при делении на m1, пользуясь возможностью определить показатель k на основании теоремы Эйлера.

5. Применяя доказанные теоремы, построим не­сколько общих признаков делимости и равноостаточ­ности.

Фиксируем натуральное т и представим число А в виде

где

т. е. все ai (i — 0, 1, ..., k) являются φ(т)-значнымй числами.

Функция

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

Теорема 27. Если числа а и т взаимно просты, а числа k1 и k2 равноостаточны при делении на φ(т), то числа и равноостаточны при делении на т.

Доказательство.

Пусть

Тогда

На основании теоремы Эйлера и теоремы 20 число равноостаточно при делении на т с числом аr. Аналогично устанавливается равноостаточность при этом делении чисел и аr. Значит, и числа и при делении на т равноостаточны.

6. Построенный общий признак равноостаточности не является во многих случаях, так сказать, «до­статочно экономным», так как число φ(т) может, вообще говоря, оказаться довольно большим.

Поэтому, с одной стороны, при пользовании этим при­знаком приходится складывать большие числа, а с другой стороны, φ(т)-значные числа при этом прихо­дится делить на т непосредственно (или же пользо­ваться каким-нибудь другим признаком делимости и равноостаточности). Желательно поэтому попы­таться взять вместо φ(т) другой, меньший показа­тель. В ряде случаев это удается сделать. Например, при т = 37 вместо φ(т)=36 можно взять показа­тель 3, ибо 1000 при делении на 37 дает в остатке единицу; при т= 11 вместо φ(т)= 10 можно взять показатель 2 и т. д.

Определение. Наименьшее число δ, для кото­рого аδ при делении на т с остатком дает в остатке 1, называется показателем, которому принадлежит число а при делении на m с остатком.

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

Очевидно, каковы бы ни были взаимно простые числа а и т, показатель δ, которому принадлежит а при делении на т, не превосходит φ(т). Этот пока­затель и можно взять вместо φ(т) в формулировке общего признака равноостаточности из п. 5.

7. Показатель, которому принадлежит число а при делении на т, может, вообще говоря, быть и равным φ(т). Например, последовательностью остатков от деления степеней числа 2 на 11 будет

2, 4, 8, 5, 10, 9, 7, 3, 6, 1,

так что при делении на 11 число 2 принадлежит показаЗначит, для применения признака равноостаточности из п. 5 в этом случае приходится брать k = 10 = φ(11).

Однако во многих случаях удается обходиться показателем Пусть, например, т есть степень простого числа: т= рα и р≠2. Тогда и теорема Эйлера приобретает вид: для (а, р) = 1 должно быть Так как число

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

Так как р≠2 оба сомножителя одновременно на р делиться не могут. Значит, на рα делится либо либо

В первом случае мы оказываемся в условиях теоремы 23 с

а во втором — в условиях теоремы 22 с тем же k =

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

Теорема 28. Если числа а и b взаимно просты, то уравнение

ах + bу=с (3)

всегда разрешимо в целых числах, и целыми его ре­шениями будут все пары чисел (xt,yt), где

(t — любое целое число).

Доказательство.

Найдем сначала хотя бы одно решение (х',у') этого уравнения. Очевидно, что для этого достаточно найти такое число х', что (ах' — с) b. По теореме Эйлера Значит, и в каче­стве х' можно взять число

Пусть теперь (х", у") — какое-то другое решение уравнения ах+by= с. Покажем, что числа х' и х" равноостаточны при делении на b. В самом деле, пусть

Вычитая почленно второе равенство из первого, по­лучаем

откуда а(х' — х") b. Так как а и b по условию взаимно просты, по теореме 12 (х'-х") b, и нам остается сослаться на теорему 19.

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

Но (axt — с) b, так что, полагая

мы получаем, что все пары чисел xt и yt являются решениями нашего уравнения.

9. Теорема 29. Пусть m взаимно просто с 10 и k равноостаточно с при делении на т. Тогда числа

10а + b и a + kb

равноделимы на т.

Доказательство. Ввиду взаимной простоты т и 10, числа 10а + b и по теореме 15 равноделимы на т. Но

так что по теореме Эйлера и теореме 20 число 10а + b равноделимо на т с числом а + kb.

Опираясь на эту теорему, можно построить сле­дующий общий признак делимости. Обозначим че­рез k остаток от деления l0φ(т)-1 на т с остатком, представим произвольное число А в виде

и положим

Если k велико (близко к т), то вместо него в формулировке соответствующего признака целесо­образно брать k — т.

Микромодуль 15

Индивидуальные тестовые задания

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

3. Если 1 а, то а = 1.

4. Каково бы ни было а ≠ 0, существует такое отличное от а число b, что b а.

5. Каково бы ни было число а, существует такое число b, что из bс и с а следует либо с = b, либо с = а.

6. Доказать теоремы, аналогичные теоремам 2, 3, 4 и 5 для четной делимости.

7. Построить такую теорию делимости, в которой теоремы 1, 3 и 4 были бы верными, а теоремы 2 и 6 — нет.