1611141236-738b6049e710338c8c4dd43e7bd2b717 (824981), страница 13
Текст из файла (страница 13)
— основание натурального логарифма, н = 3, 141592...; символ здесь озыачает, что стнощеыие т'2тап»е»/п1 стремится к 1 при и -г со. При помощи формулы Сткрлинга, дающей приблиыение с недостатком, проверить, что 100! > (9, 33... )10'зг. Сколько в Егсо циклов длины 100? 2.
Найти порядок перестановки (4) н перестановки и = ( 12345878~ 38821457/ 3. Перестаыовка я вида (3) с гп независимыми циклами оставляет щ' = и — ~ 1ь ь=г символов (или точек) на месте. Число 4(н) = и — (гп+ пгг) называетса декремея- гпом перестановки я. Проверить, что е» = (-1)41»1. у' 9.
Арифметика целых чисел 61 4. Найти знак перестановки .=( 1 2 3 ... и — 1 п1 и и — 1 п — 2 ... 2 1/' 5. Пусть й = (1,2,..., и), й х й — декартов квадрат. Будем называть па.- ру (йу) Е Й х Й ииеерсией ошиосишельио иерестаиоеки а Е я» (или, короче: а-инверсией), есля 1 ( 1, но а(4) > а((). Положим — П 14»овь» Тзк как (а(у) — а(1)) /(У вЂ” 1) — отличное от нуля рациональное число, явлшощееся отрицательным в точности тогда, когда (з,у) будет а-инверсией, и так как с: й -т й — биективное отобрзлсение, то збпа ж ( — 1)", где й — общее число а-инверсий.
Если т = (11) — транспозиция, то ейп т = -1. Как легко видеть, (аЦ) а(1))а = ( ... а(1) ... а(у) ... )( ... а(4) ... а(у) ...) ( ... а(1) ... а(1) ... )' так что а-инверсия (ай) перестает быть инверсией относитеаьно перестановки та, где т ж (а(1) а(1)) — транспозиция. Показать, что найдутся й транспозиций ты..., ть, для которых теть 1...т1а = е — единичнаа перестановка. Стало быть, а = т|...ть 1ть взяла = (-1)" = ет— два равноправных обозначение одного и того же инварианта перестановки; ейп (от з1рииш (лат.)) — знак. Мы получили еще один удобный способ определения знака перестановки. Скажем, относительно перестановки (4) множество инверсий состоит вз пвтк пар (1, 5), (2, 5), (3, 5), (4, 5), (б, 7), так что ебп и ж -1.
Практически дело сводитсв к подсчету в нижней строке перестановки и количества чисел у, больших й но стоящих перед в, для з = 1, 2,..., и — 1. З 9. Арифметика целых чисел Задачей этого параграфа является краткое описание тек простейших свойств делимости целых чисел, на которые удобно по разным поводам ссылаться в дальнейшем. Дополнительные факты будут приведены в гл.
б, где теория делимости переносится на более общие алгебраические системы. 1. Основная теорема арифметики. Целое число в называется делипзслем (или миожитпелем) целого числа о, если и = в1 для некоторого 1 Е Е. В свою очередь и называется произнеси в. Делимость п на в обозначается символом в)тз, а отрицание делимости — символом в,(п. Делимость — транзитивное отношение на Е. Если, далее, 62 Гл.
1, ттстони алгебры т~и и и~тп, то и = ~т, и целые числа и, тп называются ассоциированными. Целое число р, делители которого исчерпываются числами хр, х1 (не собстпвснные делитпели), называется простым. Обычно в качестве простых берутся положительные простые числа > 1. Фундаментальную роль простых чисел вскрывает Основная теорема арифметики. Каждое иоложитпельнос целое число и ~ 1 можетп быть записано в виде произведения простых чисел: и = ртрг...р,.
Эта запись единственна с точностпью до порядка множителей. Собрав вместе одинаковые простые множители и изменив обозначения, получим запись и = р",р",... р'„", ет > О, 1 < т < й. Для любого рационального числа а = и/т 6 Я имеет место аналогичное разложение, но с показателями е;, как положительными, так и отрицательными. Заметим, что множестпво Р = (2,3,5,7,11,13,...) всех простыл чисел бесконечно (теорема Евклида). Действительно, если бы существовало лишь конечное число простых чисел, скажем, ры рэ,..., рт, то по основной теореме число с = ртрг...
рт+ 1 делилось бы по крайней мере на одно из рь Без ограничения общности считаем с = рте'. Тогда рт(с' — 1~...рт) = 1, а это невозможно, поскольку делителями единицы в Е являются лишь х1. П Доказательство основной теоремы откладывается до гл. 5. На первый взгляд, ее вообще не надо доказывать, настолько она кажется очевидной. Между тем, хотя речь идет о мультипликативных свойствах (свойствах делимости) целых чисел, основную теорему невозможно доказать, не используя одновременно операций умножения и сложения в Е. В качестве иллюстрации этого утверждения рассмотрим в 1Ч подмножество Я = (4й+ 1~ й = 0,1,2,...). Оно замкнуто относительно умножения: (4йт + 1) (4йэ + 1) = 4йг + 1. Индукцией по и 6 Я нетрудно установить существование разложения (первая часть основной теоремы) и = от...от, где ст — далее неразложимые элементы иэ б.
Мы назовем их квазииростыми числами. Выпишем несколько таких чисел: 5, 9, 13, 17, 21, 49. Вторая часть основной теоремы для системы Я неверна, поскольку, например, число 441 6 Я имеет два существенно разных разложения в произведение квазипростых чисел: 441 = 9 49 = 21э.
~ У. Арифметика целью чисел 63 (3) 2. НОД и НОК в Е. Любые два целых числа п и т можно записать в виде произведения степеней одних и гех же простых чисел а~ аь аь ~ Р~ Рг 9ь если условиться допускать нулевые показатели (как всегда, считая ро = 1). Введем в рассмотрение два целых числа НОД(п т) — рар» ...р» НОК(п,т) = р,'рг'...р ", (1) где»с = ппп(а;,Д), б; = шах(она),1= 1,2,...,Ь. Так как д~п =ь д = юр, '... рь', 0 < а'; < сгс, то нз (1) вытекают следующие утверждения.
() НОД(п,т)(п, НОД(п,т)(т, и если д~п, д)т, то д(НОД(п,т). й) п~НОК(п,т), т)НОК(п,т), и если п)и, т~и, то НОК(п,т)~и. Свойства 1) и й) оправдывают сокращенные обозначения НОД и НОК наибольшею общего делителя и наименьшего общего кратного целых чисел и, т. При п > О, т > 0 выполнено соотношение НОД(п,т) НОК(п,т) = пт. (2) Целые числа и, т называются взаимно простыми, если НОД(п,т) = 1. В этом случае соотношение (2) принимает вид НОК(п,т) = пт. 3.
Алгоритм деления в Е. При заданных а, Ь б Е, Ь > О, всегда набдртсл о, г й Е такие, что а=Ьд+г, 0<г<Ь (если считать лишь Ь 1~ О, пьо будет выполнено неравенство 0 < г < ~Ь|). В самом деле, множество Я = (а — Ьв ) в ч Е,а — Ьв > 0), очевидно, непусто (например, а — Ь(-аз) > 0). Стало быть, Я со- держит наименьший элемент; обозначим его г = а — Ьо. По усло- вию 1 > О.
Предположив г > Ь, мы получили бы элемент г — Ь = = а — Ь(о + 1) б Я, меньший, чем г. Это противоречие устраняется липп при г < Ь. С) Проведенное несложное рассуждение дает также предписание, т.е. алгоритм (или алгорифм), для нахождения частного Ь н остат- ка г в конечное число шагов. Алгоритм деления в Е используется для иного определения НОД, а следовательно, и НОК, если принять во в нимание соотношение (2). Именно, при заданных целых числах п, т, одновременно не рав- ных нулю, положим л = (пи+ те ~ и, о б Е).
Гя. 1. Истпокн алгебры 64 Выберем в,7 наименьший положительный элемент Ы = пио + топо. Используя алгоритм деления, запишем и = сй)+ г, О ( г ( с(. Ввиду выбора с( включение г = и — дй = и — (пио + тпоо)т) = п(1 — иод) + пз(-поо) 6,7 влечет равенство г = О.
Стаю быть, с()п. Аналогично доказывается, что а)тп. Пусть теперь ст — любой делитель чисел и и пз. Тогда с('!и, 4тп =р 47)пио, т('! тппо ~ а'Ипио + тпоо) =р т(')т(. Итак, д обладает всеми свойствами наибольшего общего делителя, и поэтому Ы = НОД(п, тп). Мы приходим к следующему утверждению. Наибольший общий делитель двух целых чисел и, пз, не равных одновременно нулю, всегда эаписываешся в виде НОД(п, тп) = пи + тпо, и, о Н Е. (4) В частностпи, иелые числа и, тп взаимно просты тогда и тполько тогда, когда (4') пи + пап = 1 при некоторых и, о Н Е. Было проверено, что взаимная простота и, тп влечет соотношение (4'). Обратно: если и, тп таковы, что имеет место (4'), то д)п, д)тп ~ т((пи, т()тпо =ф Щпи + пап) =ь т()1 =ю д = х1.
С) Доказательство соотношений (4) и (4') довольно эффективно. Нужно взять любой положительный элемент из множества,7 (см. (3)), а затем уменьшать его при помощи алгоритма деления до тех пор, пока не получится наименьший элемент, который и будет наибольшим общим делителем. УПРАЖНЕНИЯ 1. Каждое нечетное простое число имеет вид 4й + 1 или 4й — 1.
Используя мультипликативность множества о нз и. 1, доказать бесконечность множества простых чисел вида 4й — 1. 2. Доказать, что существует бесконечно много простых чисел вида 4й+ 1, опираясь на следующее нетривиальное утверждение. Если и, пт б Х, НОД(п, пт) ю 1, и если р — престлое число, делящее пз + птз, то р = 4й + ! . 3. Если натуральное число н делится в точности на т различных простых чисел ры...,р„, то количество чисев, меньших и и взаимно простых с и, рвано р(п) = и (1 — — ) ...
(1 — — ) . Функция тю И -т И называется рункчиеб Збяеро. Проверять справедливость формулы длл значений р(п) прн и ( 2б и при и = р'". 4. Используя биномивльную формулу, индукцией по и доказать, что если р — простое число, то пв — и делится на р при любом и Е Е. Глава 2 МАТРИЦЫ Прямоугольные матрицы, введенные в з 3 гл. 1, встречаются настолько часто, что с течением времени возник самостоятельный раздел математики — шеория машрвн. Ее становление относят к середине прошлого века, но полноту и изящество она приобрела позднее, вместе с развитием линейной алгебры. До сих пор теория матриц остается важным инструментом исследования, хорошо приспособленным и к запросам практики, и к абстрактным конструкциям современной математики. Здесь будут юложены простейшие результаты теории матриц. Матрицы являются естественными спутниками линейных отображений векторных пространств. В курсе линейной алгебры и геометрии [ВА П) этому утверждению будет придан точный смысл.
В настоящей главе понятия пространства, вектора, линейной зависимости, ранга системы и т.п. развиваются в чисто алгебраическом аспекте и ровно настолько, насколько они необходимы для наших непосредственных целей. О 1. Векторные пространства строк и столбцов 1. Мотивировка. В связи с системами линейных уравнений нам приходилось рассматривать строки длины п, в которые вкладывался разный смысл.
Это были строки (ап,аи,...,ася), 1 < 1 < т, матрицы А = (а; ) размера т х и и решения (хам хаю...,хе) лннейной системы с матрицей А. Приведение в з 3 гл. 1 системы или матрицы к ступенчатому виду включало, помимо элементарного преобразования типа (1), два важных акта: умножение строки на число и сложение двух строк. Те же действия можно производить и с решениями однородной линейной системы. Действительно, если (х1,хз,...,х'„) и (х",, х~з,...,х'„') — два решения системы опх~ + аьзхз + .. + аь,х„= О, 1 = 1,2,..., ш, а а, ~3 — два любых вещественных числа, то строка (ах', + )3х1', ахз + ~3хз,..., ах'„+ 13х'„') тоже будет решением нашей системы: ап(ах1+ фх~) + ав(ахз + )3хз) +... + аьз(ах'„+ 13х'„') = = а(ам х|+ аьехе +... + асях„)+ = ф(оп х1 + ам хе +... + асях„') = О.
66 Гл. э". Маотринм С другой стороны, любая строка, что бы она ни выражала, является элементом "универсального" множества Й", т.е. и-й декартовой степени множества К вещественных чисел. Поэтому желательно изучить общий объект, свойства которого автоматически переносились бы на матрицы и на решения однородных систем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
