1611703151-03589a55eaf19010bb3ad337d2045391 (827005), страница 4
Текст из файла (страница 4)
р» = р2д» .. дь откуда р»... р» = д»... дь Но р»... р» —— п(р, ( и. Поэтому можно применить индуктивное предположение, так что 1= й, и простые числа дь ..., д» отличаются от р», ..., р» только порядком следования. Теорема доказана. Среди сомножителей в разложении и = р1р2 ... р» могут быть равные. Их принято объединять в виде степеней. Разложение в форме п=р" р"2... р"~ при попарно различных рь рь ..., р„ называется каноническим разложением натурального числа и.
Каноническое разложение распространяется на все целые числа, кроме О, в форме п =1 — 1)»»р«,р»» ... р».ь 2 и где а» принимает значения О, 1. Далее, каноническое разложение может быть распространено на дробные рациональные числа, если допустить отрицательные значения для аь ..., и . Чтобы получить каноническое разложение для дробного рационального числа, нужно написать разложения для числителя и знаменателя и выполнить деление одного на другое, употребляя, в случае надобности, отрицательные показатели, Так, — = 2- ~325- 17 ( 1) 2- ~3-збз нз !о ' ь4 Теорема об однозначном разложении целых чисел на простые множители играет исключительно большую роль в теории чисел.
$2. Теория сравнений Пусть т — данное натуральное число. Все целые числа по отношению к числу о2 естественно разбиваются на о2 классов, если отнести к одному классу числа, дающие одни и тот же остаток прн делении иа о». Так, если т = 2, целые числа разбиваются на цялыв числА классы четных и нечетных чисел. Если т = 3, классы в этом смысле составляют числа вида Зй, Зй+ 1, ЗФ+ 2 цри целых й и т. д. Числа, относящиеся к одному классу, называются сравнимыми, и изучение свойств классов носит название теории сравнений. Переходим к точным определениям относящихся сюда понятий.
1. Определение и простейшие свойства. Пусть т — натуральное число. Два целых числа а и Ь называются сравнимыми по модулю т, если их разность а — Ь делится на т. Высказывание «а и Ь сравнимы по модулю т» записывается в виде а= — Ь(шой т). Предложение 1. а = а(шойт); далее, если а = — Ь(гпойт), то Ь а(той т); если а я- =Ь(гной т) и Ь = с(той т), то а = с(шой т). Действительно, а — а = О делится на любое число; если а — Ь делится на т, то и Ь вЂ” а делится на т; если а — Ь и Ь вЂ” с делятся на т, то а — с =(а — Ь)+(Ь вЂ” с) тоже делится на т. Именно эти свойства сравнений позволяют заключить, что каждое целое число попадает в один и только один класс попарно сравнимых между собой целых чисел.
Эти классы называются классами вьшетов по модулю т или просто классами ло модулю т. Предложение 2. Каждое целое число сравнимо ло модулю т с одним и только одним из чисел ряда О, 1, ..., т — 1. Действительно, пусть а — некоторое целое число. Поделим его на т с остатком: а = ту+ г, О < г(т — 1. Ясно, что а ю г(шой т), ибо а — г = тд делится на т. Итак, каждое целое число а сравнимо со своим остатком при делении иа т. Остается показать, что среди чисел О, 1, ..., т — 1 иет сравнимых по модулю т, Но это ясно — если взять два различных целых числа этого ряда и вычесть из большего меньшее, мы получим в качестве разности положительное число, меньшее чем т, и, следовательно, зта разность не делится иа т.
Предложение доказано. В процессе доказательства мы убедились,, что каждый класс по модулю т действительно состоит из чисел, дающих один н тот же остаток при делении на т. Любая совокупность чисел, взятых по одному из каждого класса по модулю т, называется полной системой вычетов по модулю т. Например, числа О, 1, ..., т — 1 образуют полную систему вычетов. Полной же системой вычетов будет 1, 2, ..., т; при нечетном т = 2Ь + 1 полной системой вычетов будет — Ь, ..., — 1, О, 1, ..., Ь,ит.д.
Предложение 3. Если а, = аз(той т) и Ь, =— Ь,(той т), то а1+- Ь1 —= а» ~ Ьг(шой т). Доказательство. Если а, аз(шойт) и Ь| — = Ьз(пюйт), то а1 — а» и Ь, — Ьз делятся на и, а следовательно, и а~ ~.Ь,— — (а»~Ь»)=(а1 — ае)~(Ь| — Ьз) тоже делится на т, т. е. а~ -<- ~Ь вЂ” = аэ -+ Ьг(шой т). Предложение 4.
Если а, = а»(той т) и Ь~ = Ье(гной т), то а,Ь~ = а»ЬА(п1ой т). теоРия сРАВиении Доказательство. а!Ь! — а»Ь» = а,Ь, — а!Ь, + а,Ь,— — а»Ь» = а!(Ь! — Ь»)+(а! — аз)Ь» Если о!— = а» н Ь! — Ь«(той т), то оба слагаемых делятся на т, а с ними и их сумма а!Ь! — а»Ь!. Следовательно, а!Ь! = а»ЬЯ(гпог(т), что и требовалось доказать.
В частности, если а! Рм аз(гподт) и с — любое целое число, то а ! с = — а»с (то!( т), П р е д л о ж е н и е 5. Если са ! — с а! (тоо т) и число с взиимно просто с т, то а! Ям аз(той т). - Действительно, если са! = саз(!под т), то са, — са! = = с(а,— а!) делится на т, с взаимно просто с т и согласно предложению 8 а! — аз делится на т, что н требовалось доказать.
Таким образом, обе части сравнения можно сократить на множитель, взаимно простой с модулем. Без предположения о взаимной простоте это, вообще говоря, делать нельзя. Так, 2 б(щоб 4), но 1 М 3(той 4) . 2. Действия над классами. Пусть т = 6. Представим себе, что числа, сравнимые с нулем, мы записываем черными цифрами, сравнимые с единицей — красными, сравнимые с 2 — желтыми, сравнимые с 3 — фиолетовыми, сравнимые с 4 — зелеными и сравнимые с 5 — синими.
Тогда предложения 3 и 4 можно переформулировать так: цвет суммы двух чисел зависит только от цветов слагаемых, но не от того, как выбраны эти слагаемые внутри своих классов. То же относится к разности и к произведению. Например, складывая «желтое» число с «снним», мы всегда получим «красное». Умножая «синее» на «фиолетовое», мы всегда получим «фиолетовое», и т. д. Сокращенно это можно записать: ж+ с = к; с ф = ф и т.
д. Для шести символов: ч, к, ж, ф, з, с мы можем записать «суммы», «разности» и «произведения», руководствуясь сложением, вычитанием и умножением чисел (все равно каких), взятых из соответствующих классов. То же самое имеет место при любом т. Для того чтобы указать класс, к которому принадлежит сумма, разность или произведение двух чисел, нам достаточно знать классы, к которым эти числа урннадлежат, а как они выбраны внутри классов — на результате не сказывается. Это обстоятельство делает естественными следующие определения. Суммой двух классов по модулю т называется класс по модулю т, к которому принадлежит сумма каких-либо чисел из слагаемых классов. Произведением двух классов по модулю т называется класс по модулю т, к которому принадлежит произведение каких-либо чисел из перемножаемых классов.
В силу предложений 3, 4 этн определения корректны — какие бы числа из двух данных классов мы ни выбрали, их сумма и нх произведение будут принадлежать вполне определенным классам, не зависящим от выбора чисел внутри данных классов. милые числя !гл. ! Пример. Приведем модулю 7 и 8.
Таблица 1 «таблицы умножения» для классов по Таблица 2 6 т 6~ О 1 2 3 4 В 6 7 О 1 2 3 4 5 ль 7 О О 3 4 6 1 2 5 5 2 1 6 з О О 5 6 3 5 1 4 6 3 4 2 2 1 О О О О 1 2 О 2 4 О 3 6 О 4 1 О 5 3 О 6 5 О 1 2 3 4 5 6 7 Б Б О 1 О 2 О З О 4 О 5 О 6 О 7 О О 2 3 4 6 6 1 О 4 2 7 4 2 6 5 О О 4 5 О 2 4 7 О 4 4 1 О 6 4 Э О О 6 7 4 6 2 5 О 4 6 3 4 2 2 1 Символы О, 1, 2, 3, 4, 5, 6 в табл. 1 обозначают классы по модулю 7, которым принадлежат числа О, 1, 2, 3, 4, 5, 6.
Значение символов в табл. 2 — аналогично. Такими обозначениями мы будем пользоваться и впредь †симв а будет обозначать класс по модулю (который предполагается заданным), содержащий число а, Рассмотрение классов по модулю как объектов, над которыми совершаются действия, часто вызывает у начинающих некоторое затруднение.
Иногда оно вызывается тем, что класс это не число, а бесконечное множество чисел, и сама мысль о том, что действие иад классами суть действия сразу над бесконечными множествами чисел, кажется противоестественной. Для преодоления этого психологического барьера следует мыслить вместо класса одно иэ чисел этого класса, но безразлично какое, как бы отказываясь различать их одно от другого, как бы «склеивая» их в один объект. Собственно говоря, зто обычный и привычный в обыденной жизни путь формирования абстрактного понятия. Говоря слово «яблоко», мы отвлекаемся от особенностей конкретных представителей этого класса предметов и подразумеваем некоторое яблоко, все равно какое.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
