1611703151-03589a55eaf19010bb3ad337d2045391 (827005), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Нам привычно, говоря «яблоко», ие вызывать в воображении множество всех имеющихся на земле в данный момент яблок. Так же надо относиться к понятию «класс по модулю гл». Отметим некоторые очевидные свойства действий над классами по модулю. 1 (а+ Б)+ с = а+(Б+ с) (ассоциативность сложения). Действительно, (а+ Б)+ с есть класс, содержащий (а+ Ь)+ с, а а+(Б+с) есть класс, содержащий а+(Ь+с). Но (а+Ь)+ + с = а+(Ь+ с), откуда и следует требуемое. 2. а + Б = Б+ а (коммутативность сложения). Фв ТЕОРИЯ СРАВНЕНИИ 3, Класс О играет роль нули при сложении: а+О=а при любом а. 4.

Класс — а играет роль класса, противоположного классу а, именно, а+( — а) =О. 5. а(б+ с) = бб+ ас; 5. (Б+ с) а = Ба + са (дистрибутивность). 6. а(бс) = (аб) с (ассоциативность умножения). 7. об = ба (коммутатнвность умножения). Свойства 3 и 4 очевидны. Свойства 2, 5, 6, 7 доказываются точно так же, как свойство 1, посредством перехода от классов к любым числам пз этих классов, для которых соответствующие свойства действий имеют место.

8. Класс ! играет роль единицы при умножении классов, именно, а. 1 =а при любом а. 3. Приведенная система вычетов и примитивные классы. Предложение 6. Пусть а'=н.о.д.(а, т) и а~ — а(тобт). Тогда н. о. д. ( а ь т) = д. Доказательство. Имеем а~ — — а+то при некотором ч)ен ~, так что д есть общий делитель для а, и т, и потому д "д,, где А = н.о.д.(аь т).

С другой стороны, а = а, — тд, откуда следует, что д~ является общим делителем для а и т, так что д1 ( д. Отсюда заключаем, что А = д. В частности, если одно из чисел класса по модулю т взаимно просто с т, то и все числа этого класса взаимно просты с т. Классы, состоящие из чисел, взаимно простых с модулем, называются прилгитивными классами. Для любого модуля примитивныс классы существуют; такими будут, в частности, классы 1 и т — 1. Предложен не 7.

Для того чтобы сравнение ах = — 1(гпоб т) имело решение, необходимо и достаточно, чтобы а было взаимно просто с т. Доказательство. Необходимость. Пусть существует целое число хь такое, что ахь = — 1(шод т). Число 1 взаимно просто с т, значит (предложение 6), число ах, взаимно просто с т, откуда а взаимно просто с п1, что и требовалось доказать. Д о с т а т о ч н о с т ь.

Пусть а взаимно просто с т. Тогда, согласно предложению 5 6 1, существуют целые числа и и о такие, что аи+ тс =!. Ясно, что аи = 1(шод т), так что и есть решение сравнения ах = 1(шодси), Предложение 7 можно в терминах кчассов сформулировать так: для того чтобы класс а имел обратный а-', т. е. такой, что аа-' =.

1, необходимо и достаточно, чтобы класс а был примитивным, Ясно, что если хь — решение сравнения ах — 1(шод т), то всв сравнимые с хь числа тоже доставляют решения, так что решение «приводит за собой» весь класс, его содержащий. В этом смысле 20 палые шгслк ггл. г решений бесконечно много. Однако класс решений существует только один. Действительно, если ах» = — 1(шод гп) и ах, = =1(гпод т), то ах« — = ахс(шод т), и в силу взаимной простоты а и т, хсг = — хг(шодт). В терминах классов: обратный класс а-' к примитивному классу а существует галька один.

Число примитивных классов по модулю т обозначается ср(т). Так определенная функция называется с(гункс(ией Эйлера. Ясно, что ср(1) = 1. Для т ) 1 ср(т) равно, очевидно, числу взаимно простых с гп чисел ряда О, 1, ..., т — !. Так, ср(2) = 1, ср(З) = 2, сг(4) = 2, ср(5)=4, ср(6) = 2, с)г(7)=6, р(8)=4 и т, д, Если модуль есть простое число р, то все классы, кроме нулевого, примитпвны, так что р(р) = р — 1.

П р е д л о ж е н н е 8. Сравнение ах = — Ь(гпод т), если а взаилно просто с т, и.ивет единственный класс решений. Доказательство. Пусть а' — решение сравнения ах —= = — 1(спой т). Ясно, что а'Ь есть решение сравнения ах= — Ь(гпод т), ибо а(а'Ь) = аа' Ь = 1 Ь(гпод т). Если х,— какое-либо решение сравнения ах = — Ь(пюс1 т), т е. их» — = Ь(пгос1 т), то и'их» =— = а Ь(гпод т), откуда хв —= а'Ь(шос1 т), пбо а'а == 1(гподт). В терминах классов предгсогкение 8 означает, что возможно деление на примитивный класс: уравнение ах = б имеет единственное решение х = а-'б. Если модуль т есть простое число, то все классы, кроме нулевого, примитивны, так что в этом случае возможно деление на любой ктасо, кроме нулевого. Имеет место следчюшая теорема, носящая имя Эйлера.

Теорема Эйлера. Если а и т взаигино просты, то а«с" г = — 1(пюс! и). Д о к а з а т е л ь с т в о. Пусть аг, ам ..., а, — числа, взятые по одному из каждо~о примитивно~о класса, так что й = ср(т). Пусть а взаимно просто с т. Тогда числа ааь аа,, ..., аа, тоже взаимно просты с т, т. е. принадлежат примитивным классам.

Все они попарно несравнимы между собой. Действительно, если аа; = = — аа,(гпод т), то в силу предложения 5 ас = — а;(гпод т), что возможно только если а, и а; равны. Итак, числа аап аа,, ..., аа« лежат в разных классах и, так как их число равно числу классов, среди них имеется по одному из всех классов («1О человек в 10 комнатах, ни в одной нет двоих, следовательно, все комнаты заняты»). Поэтому числа ааь ааэ, ..., аа» сравнимы с аг, ан ... ..., ам расположенными, быть может, в другом порядке. Запишем это: аа, — = ас, аа2 = сгсе (гпод т) НЕКОТОРЫЕ ОБШПЕ ПОНЯТИЯ АЛГЕБРЫ Вдесь Г„(м ..., Г» — те же числа 1, 2...,, й, но в другом порядке. Перемножив эти сравнения, получим а"а,а, ...

а» = — а„а,, ... а,»(П1об т). Ио апа;, ... а,л — — а,а,, аА, так как сомножители различаются только порядком. Итак, а»а,аз ... а» = — а,а2 ...а (гпобгп). Число а,а, ... а, взаимно просто с т, и на него можно сократить Обе части последнего сравнения. Поэтому а» = — 1(глоб т), и остается вспомнить, что я = Гр(т). В терминах классов теорема Эйлера выглядит так: если ив примитивный класс по модулю т, то ат > = 1 Важным частным случаем теоремы Эйлера является теорема Ф ер м а: если р — простое число и и не делится на р, то ая — ' = ии 1(шод р).

Она непосредственно следует из теоремы Эйлера, ибо ~р(р) = р — 1. Теорему Ферма часто записывают в равносильной Арорме ая = — а(шод р). В этой записи предположение о том, что а не делится на р, становится излишним. Теорема Эйлера дает возможность в явном виде записывать зсласс, обратный к данному примитивному классу. Именно, а-' = '= а'И"'~-'. ф 3. Некоторые общие понятия алгебры 1.

Группы. В теории сравнений мы встретились с новым явлением, имеющим большую принципиальную важность. Мы обнарузкили математические объекты, именно, классы по модулю, не являющиеся числами, но над которыми мы имеем возможность совершать алгебраические действия. Свойства этих действий напоминают свойства действий над числамн. Подобного рода системы объектов возникают в математике в разнообразных ситуа'циях, и это делает естественной и необходимой формалпза~ шо Возникающих на этом пути более общих понятий.

Полргруппой называется множество, в котором определено действие, сопоставляющее каждой упорядоченной паре элементов третий — результат действия. Действие предполагается ассоциативным Полугруппами являются: множество целых неотрицательных чисел относительно действия сложения, то же множество отвоеительно действия умножения (это совсем другая полугруппа), множество классов по модулю относительно умножения. Во всех этих примерах действие коммутативно.

Полугруппа называется группой, если в ией существует нейтральный элемент е такой, что при всех а пз группы а» е = е» а = а (через» обозначен знак действия), н для каждого ~Лемента а существует обратный а-' такой, что а» а-' = а-' » а = с. 22 ЦЕЛЫЕ ЧИСЛА >гл. > Примерами групп могут служить: группа всех целых чисел относительно сложения, группа положительных рациональных чисел относительно умножения, группа классов по модулю относительно сложения, группа примитивных классов по модулю относительно умножения. Все эти группы коммутативны. В качестве примера некоммутативной группы рассмотрим множество непрерывных строго возрастаюших функций на [О, 1), со значениями ф(0) = О, р(1) = 1, т.

е. функций, осугцествляющих взаимно однозначные отображения промежутка 10, 1) на себя, по отношению к действию суперпозиции, т. е. подстановки функции в функцию, так что (ф»>(>) (х) = ф(ф(х)). Нейтральным элементом здесь является функция ф(х)= х, осушествляющая отображение каждой точки промежутка на себя. Обратным элементом является обратная функция, ассоциативность очевидна.

Рассмотрим функях. цин ф1 — — х, и ф, = ейп — '. Обе онн принадлежат рассматривае- 2 пх»» мому множеству. Далее, (ф, *ф,)(х) =(з1п —,, ), а (ф,*ф,)(х) = их' = з1п —. Это разные функции, так чтоданная группа некоммута- 2 тивна. Коммутатнвные группы называются также абелгвыми. Действие в группе обозначается обычно как умножение (мультипликативная зались), иногда как сложение (аддитивная запись). Адцитивная запись применяется только для абелевых групп. Нейтральный элемент при мультнплнкативной записи обозначается 1, при аддитивной записи О. Соответственно, обратный к а элемент в мультипликативной записи обозначается а-', в аддитивной— через — а (и называется противоположным элементом).

Характеристики

Список файлов лекций