Исходными данными для программ алгоритмов 8.2 и 8.3 является верхняя граница 2N+ 1 диапазона [3, 2N+ 1] поиска простых чисел. Значение 2N+ 1 этой границы устанавливается явным образом в программе посредством присваивания соответствующего значения переменной n. Нижняя граница диапазона всегда принимается равной 3 - первое нечетное простое число.

Результаты расчетов по программам алгоритмов 8.2 и 8.3 сохраняются в выходном файле Primary.out со следующей структурой:

3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89. Количество простых нечетных чисел в диапазоне [3,91j равно 23.

В первой строке приводятся все вычисленные простые нечетные числа из диапазона [3,27Y+ 1], граншгы которого распечатываются во второй строке результирующего файла. Во второй же строке указывается и общее количество найденных простых чисел.

8.4. Сравнения, свойства сравнений

Пусть т - целое положительное число, которое назовем модулем. Будем говорить, что целые числа а и ъ сравнимы по модулю т, если а - ъ = t т для некоторого целого t, т.е. равны остатки от деления я и b на т. Сравнение чисел а и ъ по модулю т будем записывать а-ь (modт).

Например, 77 = 5(mod 8), 102 = 0(mod 3).

Свойства сравнений

1. а = a (mod т) - свойство рефлексивности.

2. asb (mod m)b = a (mod m) - свойство симметричности.

3. a-b (mod m), b = с (mod m)=>a=c (mod m)- свойство транзитивности.

4. a = b (mod m) => (a, m) = (b, m).

5. a = b (mod m), с = d(mod m)a + csb + af (mod m).

6. a-b (mod m), c-d (mod m) => ac = bd (mod m).

7. a= axd, b = bvd, (d, m) = \, a=b (mod m) => ax = bx (mod m).

8. a - b (mod m), mx\m (отделит m)a = b (mod m,).

9. a-b (mod m), d\a, d\b, d\m => ax = bv (mod m{).

8.5. Полная система вычетов

Свойства 1-3 сравнений показывают, что операция сравнения

целых чисел по модулю является отношением эквивалентности. Множество всех целых чисел Z разбивается на классы эквивалентности (рис. 8.1), которые называются вычетами по модулю т. Числа s с2Тдежатв одном классе {к,}, т.е. s е {к,} тогда и только тогда, когда s (mod т) имеют одинаковые остатки от деления на т. Числа одного и того же класса имеют с модулем т один и тот же наибольший общий делитель, т.к. из г, se Щ следует, что (г, т) = (s, т) (см. п.8.4). Особенно важны классы, для которых этот делитель равен единице, т.е. классы, содержащие числа, взаимно простые с модулем.

Определение. Множество классов вычетов {0}, {1},..., {т - 1} по модулю т называется полной системой вычетов (п.с.в.). Полную систему вычетов можно получить следующим образом. Пусть Z- аддитивная (операция сложения) группа целых чисел, mZ- подгруппа всех чисел, кратных т. Тогда факторгруппа Z/mZ-аддитивная группа вычетов по модулю т (полная система вычетов).

8.6. Приведенная система вычетов

Определение. Пусть т - целое положительное число. Множество классов из полной системы вычетов {0}, {1},..., {т - 1} взаимно простых с т называется приведенной системой вычетов, которую будем обозначать как МК или MJm) Приведенную систему вычетов, следовательно, можно составить из чисел п.св., взаимно простых с модулем. Обыкновенно выделяют из системы наименьших неотрицательных вычетов: О, 1, 2,..., т-1.

Рис. ал

Полная система вычетов

Утверждение 8.6.1. Мп является группой с операцией умножения.

Доказательство. Проверим все свойства (аксиомы) группы.

1. Замкнутость. Пусть произвольные а, b е М„. Покажем, что аЪ е Мп. По условию а = 1 (mod т) и b = 1 (mod т), тогда ab = 1 (mod т).

2. Ассоциативность операции умножения чисел выполняется.

3. Единичный элемент - 1.

4. Существование обратного элемента.

Возьмем произвольный элемент а е Мп. Покажем совпадение множеств = Мк. Ясно, что аМп с Мк, так как для выполняется свойство замкнутости. Для доказательства = М., теперь достаточно показать, что все элементы множества аМ, различны. Предположим, что существуют Мп для

которых abx - ab2 = О (mod т). Отсюда a{bv - b2) = 0 (mod т). Атак как (а, т) = 1 - взаимно простые, то bj - b2s 0 (mod т) или h-L = b2 (mod т), что противоречит принадлежности их разным классам.

Таким образом, все элементы множества аМп различны, значит, 3Ь е Мп, что а b = 1 (mod т) . Элемент b является обратным к а, и по доказательству он единственный такой элемент (существование обратного элемента а доказано).

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

8.7. Функция Эйлера

Определение. Функция Эйлера ср (/я) определяется для всех целых положительных т и равна количеству чисел ряда

1, 2,..., т- 1,

взаимно простых с т, где число 1 полагается взаимно простым с любым из чисел и ср(1) = 1.

Примеры. ф( 1) = 1, <р(2; = 1, Ф(3 = 2, 9(4 = 2, Ф(! = 4, ср(6 = 2.

Замечание. Отметим, что порядок группы Мп(ю)приведенной системы вычетов по модулю т равен \МТ\т) = ф(/я).

Свойства функции Эйлера

Свойство 1. Если (тит2) = 1, то ф(/и, /и2) = Ф(/я1)ф(/и2).

Доказательство 1. Пусть С{тхт2) - циклическая группа порядка \С(тхт2)\ = тхт2, число образующих ее равно ф(/И1/и2) (см. утверждение 7.3.4). Так как (т{т2) = 1, то допустимо разложение (см. п. 7.4) группы С{тхт2) в прямое произведение своих циклических подгрупп С(тлп2) = С{тх) x С(т2/ и, следовательно, число образующих группы Цт) равно ц{тх)ц{т2).

Доказательство 2. Достаточно показать, что

Щщтф\ = ]Л/Я(т,) Штг)\.

1. Заметим, что из (т{т2, - 1 следует существование целых а и Ь, для которых выполняется ат2 Ьт{ 1 (алгоритм Евклида см. п.8.1). Приведем значения целых а и b к значениям а е {1, 2,..., т{}иЬ с {1, 2,...,т2},для которыхат2 + bmj = l(mod/и,/и2). Пусть с е {1, 2,..., пцпь}, тогда верно сд/и2 + с^тi = c(mon2)> где значения са и cb приведены к значениям а е {1, 2,..., тх} и Z> е {1, 2,..., /л2}. Таким образом, произвольное число с е {1, 2,..., /И]Яг2} можно записать в виде а/л2 + Ьтх = с (mod тхт2), где а е {1, 2,.,., пц} иЬ е {1, 2,..., т2). Данное представление является однозначным, так как число возможных пар (а, Ь) равно и такое же количество представляемых чисел с е Ц, 2,..., тхт2}- Далее рассмотрим все представления + Ьтх для всех а е {1, 2,..., т{) и b € {1, 2,..., /и2}.

2 Пусть а е Щти b е Af (/n2), т.е. (а, тх) 1 и (A, m2) 1 и /п2) = 1. Покажем, что (ат2 + Ътъ тут2) = 1. Выражение (ат: + bniy, тлп2] = 1 эквивалентно 6/И], /Л]) = 1 и (а/и- +

+ Ьтх, т2) = 1. В первом случае - (а/и2 +bmit т{) =(ат2, т{) = = (а, тх) = 1 и во втором - (а/и2 +Ыщ,т2) = (Л/И|, ь) =(Ь,т2) = 1. Таких пар (а, Ь), а значит и чисел я/н2 + 6/иj взаимно простых с щт2, равно 9(>Mj) ф(/и2) Покажем, что других чисел взаимно простых с среди + нет.

3. Остались не рассмотренными числа am2 + Ьпц, где а или для них + 1, т.е. такие числа не являются взаимно простыми с тхт2.

4. Из пунктов 1), 2), 3) следует, что ф(/7?1/ 2) = ф(/?ыф(/?г>).

i=l i=l V Pi J (=1

С 1 *

Свойство 2. фО ) = ра -ра 1 =а. 1-- ,

v Р)

где/? - простое число и a > 0.

Доказательство. Числа вида к ЛгдеАг={1, 2,...,/>а~1}-этовсе числа не взаимно простые сра среди 1, 2,.,.,р , а значит остальные являются взаимно простыми с/Л Отсюда у(ра) = Р -ра~ .

Свойство 3. Пусть разложение числа т на простые сомножители имеет вид т = р'! р22---Рк, гае р1 - простые числа, тогда

Свойство 4. ]>/pW) = л, где . - различные делители числа и.

Доказательство 1. Пусть л =pi1p :..р (kk - разложение числа

на простые сомножители. Правило обобщенного произведения (см. позволяет записать:

=ПЁф^/1 >=П Х>№-

Сумма

= + о + -р) + -ра ) =/.

Отсюда искомая сумма

2>/)=ft Z ф(Ю=Ша= .

d\n =ldV° 1=1

Доказательство 2. Пусть С(л) - циклическая группа порядка С(л) = я. Для всякого делителя d числа л существует единственная подгруппа C(d с С(я) порядка = d. Образующие группы C(cf. составляют множество = {х е С(я) \х = d). Из утверждения 7.3.4 следует, что число образующих группы C(d) равно ф(йГ = \Sd\. Так как Sd n Sd = 0 для rf * d, го =С(л) или

теорема 8. 7.1 эйлера. хф(т) = 1 (mod т), где т > 0 и (ж, т) =1. Доказательство. Приведенная система вычетов Мп по модулю

т является группой, порядок которой \Мп\ = Ф(/я). Пусть х - произвольное такое, что (х, т) = \ жх = г (mod т), где г е Afn. Из свойств сравнений следует, что наибольший общий делитель (г, т) = 1. Теорема 7.3.1 Лагранжа утверждает, что порядок элемента группы кратен порядку этой группы. Пусть & - порядок элемента г, т.е. г = 1 (mod т). Отсюда Ф(т) = А; с/, где d - положительное целое. Тогда г*т) = /rf = 1 (mod т). Из х = г (mod ти> следует, что х*(,и) = /*(т) (mod т), а значит, их {т) а 1 (mod /и).

Теорема $. 7.2 Ферма. x(modp), где р - простое число; х - произвольное целое положительное число.

Доказательство. Пусть х 0 (mod тогда и 0 (mod Пусть теперьх = г (modp), где re {1, 2,...,р - 1} и, значит, (г, р) 1. Из теоремы Эйлера следует, что хф(/,) 1 (mod р). где Ф(р) =р -1. Отсюда х^1 = 1 (mod р) жхР = 1 (modр).

Теоремаё. 7.3 Вильсона. (р - l)\ +1 = 0 (mod гдер - простое число.

Доказательство. Пусть Мк = {1,2,...,р - 1} - приведенная система вычетов по модулю р. Мп является группой. Для любого х 6 1.1, 2,...,р- 1} существует единственный обратный элемент 3/е {1,2,...,/?- 1} такой, чтох у* 1 (modp).

Заметим, что х х = 1 (modp)выпoлняeтcятoлькoдлядвyxэлe-ментов: х = 1 и х =р - 1. Действительно х2 - 1 = (х- 1)(х 1) -= 0 (mod р) равносильно х - 1 ш 0 (mod р) или х + 1 = 0 (mod р). От-сюдах = 1 илих =р - 1, Таким образом, обратными элементами к себе являются только х=1 и х = р - 1.

Для любого из оставшихся элементов группы х е {2, 3, ...,р - 2} существует единственный обратный у е {2, 3,...,р - 2} такой, что ху = 1 (mod р)жхФу. Тогда верно 2 3 ... (р -1) з 1 (mod р). Умножив последнее сравнение на 1 (р-1),получим 1 2 (р- 1)= = (р-1)!= -\(modp) или (р- 1)! + 1 = 0 (modp).

Задача, Пустьр - простое и hit h2,..., hn - целые числа. Доказать, что (Aj +п2+--.+ппУ =hf +hP+...+hp(modp).

Решение. Согласно теореме Ферма (8.7.2), hf sfy (modp),

i = \,n. Свойства операции сравнения (см. п.8.4) позволяют записать данные л сравнений hf =h,(mod/ в виде их суммы:

h[ + h{ +...+hf, + +... + hn (modp). С другой стороны, верно и

(я, + + ... + h,f= h{ + + + (modp), что непосредственно вытекает из теоремы Ферма.

8.8. Функция Мёбиуса. Формула обращения Мёбиуса

Определение. Функция Мёбиусац(л) определяется для всех целых положительных я и равна

1, если л = 1,

ф)=\о, если п=р*1р%2...р1*иЭа, >1,

где =/>!*/? 2.. .рак - разложение на простяге сомножители, р, - простые числа, - кратность в разложении.

Пример. ц(1) = 1, ц(2) = -1, ц(3) = -1, ц(4) = 0, ц(5) - -1, ц(6) = 1, м(7) = -1, и(8) = 0, ц(9) = 0, ц(10) = 1, u(ll) = -l, ц(12) =0, и(13) = -1, ц(14) = 1, u(15) = 1, ц(16) =0, ц(17) = -1, ц(18) = 0, д(19) = -1, ц(20) = 0, ц(21) = 1 , ц(22) = 1, ц(23) = -1.

Лемма 8.8.1. УУДО = W, eC >1

d\n если? 4,

где суммирование идет по всем делителям d числа п. Доказательство. Если л = 1, то £pl#) = и(1) =1. Пусть теперь

п -pJ{ 1 р ±\ - разложение на простяге сомножители. Тог-

да = p.(d) =£Crk (-l)r = (l-1) =0. Все делители d, для

d\l d\nit{d)*0 r=0

которых \i(d) Ф- 0, имеют вид р,/> .../>; г и ]х(р^р,г Pjr) = (-l)r.

Количество таких делителей р, ft ...J?, , выбираемых из рьръ..., рь равно числу сочетаний С[.

8.8. Функция Мёбиуса. Формула обращения Мёбиуса 239

Теорема 8.8.1. Формула обращения Мёбиуса: если/(л) = У^,%и1[ то g(n) = yi(d)f(j),

где/(л), g(A% функции, определенные для жительных п.

всех целых поло-

Доказательство. Выполним подстановку А$) в сумме

/\>п'!? [/())- Vfifrf) У^* Заметим, что здесь число неявно

d\n d\n 5\ф j

рассматривается в виде произведения п = d 5 где делители , и 5 принимают все допустимые значения независимо друг от друга и порядок суммирования не влияет на значение суммы, т.е.

n(of) g($) = g(8 ~Yj\\(d) , где p(d)= еСЛИ -&\п . \(> ) d\(f) I1 если * -л

6\ф

это вследствие леммы 8.8.1. Тогда

%$т, ?zv(d) =ф) 5><</>

5\ .. </\г> I ..лг!

Задача. Установить связь функций Эйлера <р(л) и Мёбиусаф). Решение. л - свойство 4 функции Эйлера (см. п.8.7).

К данной сумме применим формулу обращения Мёбиуса:

и, наконец,

Например, для п = 6 имеем ср(6) = 2, все делители d<z {1, 2, 3, 6}, д(1) = 1, ц(2) = -1, (д(3) = -1, ц(6) = 1 и, наконец, выражение ~ Hir в этом случае примет вид

1+ 2 + 3 +

Пусть п =Р*1Р2г -Pi

к ( 11 Так как ф(д)=я-Д1 1-- -

п.8.7), тол-П| 1-- =л-Е /=iv л у а/и

разложение на простые множители. - свойство 3 функции Эйлера (см.

или

/-IV Л У 0/й

Задачи и упражнения

Комбинаторные схемы

1. Доказать комбинаторными рассуждениями (т.е. используя только определение числа сочетаний) тождества:

а) Сп - t- i +-<-n i ;

2. Доказать тождества:

а) ЕС*

б) tk< =n2 l;

в) ХАгг.С*=ф+1)2 -2;

г) ±СЦ(т-1у-к=т 1

д) V(-4fCff =0.

*=о

3. Доказать тождество V X Z Z 2j 2j n+m-

л-2=1 2=I 0=1

4. Доказать, что У = - . я > 1.

5. Доказать, что следующие числа(2л)! (3 )! ( 2)! (2л)!

2 2 3 я и!(я 1)! являются целыми.

6. Доказать формулу бинома Ньютона (а + Ъ) =

7. Найти число подмножеств множества М= {а1,а2,..., ап}.

8. Доказать, что YjCf = XC 2*+1 = 2 -1.

А п

9. Доказать, что £ Ст ci, = Q+m и Z <Рп ) = (теорема сложе-

но А=0

ния).

10. Доказать равенство У У Qс; 4 -3 .

11.Доказать равенство У C,J = -----1.

12. Доказать равенство £(-1) С* X .

13. Найти сумму 2] л2 -1 +--)-С*.

14. Доказать тождество - где суммирование рас-

Щ :ri2:...rik:

пространяется на все упорядоченные разбиения л на k слагаемых:

л = [ + п2 + ... + пк, п 0 - целые числа.

15. Из города А в город ведут семь дорог, а из города В в город С - три дороги. Сколько возможных маршрутов ведут из А в Сче-рез город В?

16. Сколькими способами число 1Г можно представить в виде трех сомножителей (представления, отличающиеся порядком сомножителей, считаются различными; 11° - сомножитель)?

17. Сколькими способами можно указать на шахматной доске 2л х 2л два квадрата - белый и черный?

18. Сколькими способами можно указать на шахматной доске 2п х 2л белый и черный квадраты, не лежащие на одной горизонтали и вертикали?

19. Какое количество матриц можно составить из л строк и т столбцов с элементами из множества {0,1}?

20. Сколькими способами можно составить трехцветный флаг, если имеется материал 5 различных цветов? Та же задача, если

одна из полос должна быть красной.

21. Надо послать 6 срочных писем. Сколькими способами это можно сделать, если любое письмо можно передать с любым из 3 курьеров?

22. У одного студента 7 книг, у другого 9 различных книг. Сколькими способами они могут обменять одну книгу одного на одну

книгу другого?