А теперь перейдем к рассмотрению основных свойств сравнений, которые будут использоваться в доказательствах, основанных на фактах из теории чисел. Предполагается, что в приведенныс ниже формулах все переменные являются целыми числами. Целые числа х и у называются взаимно простыми, если у них нет общих множителей, т. е. если их наибольший общий делитель равен 1. Для обозначения этого понятия будем использовать следующую запись: х 1. у. На самом деле понятие взаимной простоты целых чисел всем хорошо знакомо; когда мы говорим, что дробь "несократима", это означает, что числитель и знаменатель - взаимно простые числа.

Свойство А. Если а = Ьпх = у, то а±х = Ь±уи ах = by (по-модулю т).

Свойство В. Если ах = Ьуиа = Ьи если а ± т, то х = у (по модулю т).

Свойство С. а = b (по модулю т) тогда и только тогда, когда an = bn (по модулю тп) при п 0.

Свойство D. Если г ± s, то а = b (по модулю rs) тогда и только тогда, когда а = 6 (по модулю г) и а = 6 (по модулю s).

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

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

Следующая важная теорема является следствием свойств А и В.

Теорема F (Теорема Ферма, 1640). Еслир-простое число, тоаР = а (по модулю р) для всех целых а. .. , .

Доказательство. Если а кратно р, tb, очевидно, = О = а (по модулю р). Поэтому достаточно рассмотреть случай, когда amodp ф 0. Так как р - простое число, то а Lp. Рассмотрим следующие числа:

О mod р, а mod р, 2а mod р, (р- 1)а mod р. (6)

Все эти р чисел различны, так как если бы ах mod р = ay mod р, то по определению (5) ах = ау (по модулю р); следовательно, согласно свойству В х = у (по модулю р).

Таким образом, последовательность (6) представляет собой р различных неотрицательных чисел, меньших, чем р; причем первое число - нуль, а все остальные - упорядоченные определенным образом целые числа 1, 2, ..., р - 1. Следовательно, согласно свойству А

(а)(2а) ... {(р- 1)а) = 1 • 2 ... (р - 1) (по модулю р). (7Л

Умножая обе части этого сравнения на а, получим

аР(1 • 2 ... (р - 1)) = а(1 • 2 ... (р - 1)) (по модулюр). (8)

Это доказывает теорему, поскольку каждый из множителей 1, 2, р-1 взаимно прост с р, поэтому на основании свойства В его можно сократить.

УПРАЖНЕНИЯ

1. [00] Чему равны [1.1J, L-11J, [-111- [0.99999J и Llg35j?

► 2. [01] Чему равно [[xJ]?

3. [М10] Пусть п - целое, а х - действительное число. Докажите, что:

a) [xJ < п тогда и только тогда, когда х < п;

b) п < [xJ тогда и только тогда, когда п < х;

c) [х] < п тогда и только тогда, когда х < п:

d) п < fx] тогда и только тогда, когда п < х;

e) [xJ = п тогда и только тогда, когда х - 1<п<х, а также тогда и только тогда, когда п < X <п + 1;

f) fx] = п тогда и только тогда, когда х<п<х + 1,а также тогда и только тогда, когда п - 1 < X < п.

[Эти формулы являются самыми важными инструментами доказательства утверждений, касающихся [xJ и fx].]

► 4. [М10] Используя предыдущее упражнение, докажите, что [-xJ = -fx].

5. [16] Пусть X - положительное действительное число. Найдите простую формулу округления X до ближайшего целого числа . Искомое правило округления должно давать [xJ в случае, если х mod 1 < , и fx], если х mod 1 > . Вы должны получить единую формулу, включающую в себя оба случая. Рассмотрите, как ваща формула будет выпо.лнять округление для отрицательного х.

► 6. [20] Какие из следующих равенств верны для всех положительных действительных чисел х: (а) [\\ = ]; (Ь) \,Дх]] = (с) = f]?

7. [Ml 5] Покажите, что [xJ + [j/J < [х +j/J и что это соотнощение становится равенством тогда и только тогда, когда х mod 1 -f- j/ mod 1 < 1. Выполняется ли аналогичная формула для функции "потолок"?

8. [00] Чему равно 100 mod 3, 100 mod 7, -100 mod 7, -100 mod О?

9. [05] Чему равно 5 mod -3, 18 mod -3, -2 mod -3?

► 10. [10] Чему равно 1.1 mod 1, 0.11 mod .1, 0.11 mod -.1?

11. [00] Что означ£1ет выражение "х = у (по мод)лю 0)" согласно принятому нами определению?

12. [00] Какие целые числа взаимно просты с 1?

13. [МОО] Будем считать, что наибольщий общий делитель чисел О и п равен \п\. Какие целые числа взаимно просты с О?

► 14. [12] Если X mod 3 = 2 и х mod 5 = 3, чему равно х mod 15?

15. [10] Докажите, что z{xmody) = (zx) mod{zy). [Правило С немедленно следует из этого распределительного закона.]

16. [М10] Пусть у > 0. Покажите, что если (х - z)/у -целое число и О < г < у, то z - X mod у.

17. [Ml 5] Выведите свойство А непосредственно из определения сравнимости и докажите первую половину свойства D: если а = b (по модулю rs), то а = 6 (по модулю г) и а = 6 (по модулю s). (Здесь г и s - произвольные целые числа.)

18. [Ml5] С помощью свойства В докажите вторую половину свойства D: если а = Ь (по модулю г) и а = 6 (по модулю s), то а = 6 (по модулю f>4) при условии, что г ±s.

* 19. [М10] (Закон существования обратного элемента.) Если п ± т, то существует такое целое п, что пп = 1 (по модулю т). Докажите это спомощью обобщенного алгоритма Евклида (алгоритм 1.2.1Е).

20. [Ml 5] Докажите свойство В с помощью свойства А и закона существования обратного элемента.

21. [М22] (Основная теорема Щифметики.) С помощью свойства В и упр. 1.2.1-5 докажите, что любое целое число п > 1 можно единственным образом (если не учитывать порядок сомножителей) представить в виде произведения простых чисел. Другими словами, покажите, что существует ровно один способ записи п = pip2 где каждое pj - гфостое число и pi < рг < • < р*-

► 22. [М10] Приведите пример того, что свойство В не всегда выполняется в случае, если а и m не являются взаимно простыми.

23. [М10] Приведите пример того, что свойство D не всегда выполняется, если г и s не являются взаимно простыми.

► 24. [М20] Допускают ли свойства А, В, С и D такое обобщение, чтобы они выполнялись, не только для целых, но и для произвольных действительных чисел?

25. [М02] На основании теоремы F покажите, что а" mod р = [а не кратно р] для любого простого числа р.

26. [М15] Пусть р - нечетное простое число, а-произвольное целое и Ь = а". Покажите, что 6 modp равно либо О, либо 1, либо р- 1. [Указание. Рассмотрите (Ы-1)(Ь - 1).]

27. [М15] Пусть п - положительное целое число и пусть (р(п) - количество значений из множества {0,1,...,п - 1}, взаимно простых с п. Таким образом, (/5(1) = 1, (/5(2) = 1, 1(3) = 2, ip(4) = 2 и т. д. Покажите, что если р - простое число, то tp(p) = р - 1, и вычислите р(р), где е - патожительное целое число.

► 28. [М25] Покажите, что метод, который использовался для доказательства теоремы F, можно применить для докавательства следзющего ее обобщения, называемого теоремой Эйлера: если а J. т, то а = 1 (по модулю т) для любого положительного целого т. (В частности, число п из упр. 19 можно взять равным п"*" mod т.)

29. [М22] Функхщя /(га) от положительного целочисленного аргумента га называется мультипликативной (multiplicative), если f(rs) = f(r)f(s) для любых взаимно простых г и s. Покажите, что каждая из перечисленных ниже функщ1й является мультипликативной: (а) /(га) = п, где с - произвольная постоянная; (Ь) /(га) = [га не делится на для любого целого к > 1]; (с) /(га) = с*, где к - количество различных простых чисел, которые делят га; (d) произведение любых двух мультипликативных функций.

30. [МЗО] Докажите, что функция p(n) из упр. 27 является мультипликативной. Используя этот факт, вычислите ((1000000) и предложите простой метод вычисления «(га), когда га разложено на простые множители.

31. [М22] Докажите, что если функция f(n) мультипликативна, то д(п) = J2d\n f) также мультипликативна.

32. [М18] Докажите, что для любой функции f(x, у) выполняется тождество

d\n c\d с\п d\{n/c)

33. [MIS] Для целых чисел m и га вычислите:

(а) [i(ra-l-m)J+ [(ra-m + l)J; (b) [(га + m)] + [(га - m + 1)] (Обратите внимание на частный случай т = 0.)

34. [М21] Какие необходимые и достаточные условия нужно наложить на действительное число 6 > 1, чтобы равенство [log;, xJ = [logtLJJ выполнялось для всех действительных X > 1?