Алгебра 3 семестр Лекцииi
.pdfФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОУ ВПО "Новосибирский государственный педагогический университет"
М.П.Тропин
АЛГЕБРА
ТЕОРИЯ ДЕЛИМОСТИ
Курс лекций для студентов 2-го курса
Новосибирск 2010
УДК 512(075.8) |
Печатается по решению |
ББК 22.144и73-2 |
Редакционно-издательского совета НГПУ |
Т742
Р е ц е н з е н т ы :
кандидат физико-математических наук, старший
научный сотрудник ИМ СО РАН
М.В.Нещадим;
кандидат физико-математических наук, доцент
кафедры алгебры НГПУ
Ю.В.Сосновский;
Н а у ч н ы й р е д а к т о р :
кандидат физико-математических наук, зав.кафедрой
алгебры НГПУ
М.П.Тропин
Тропин, М.П.
Т742 Алгебра: теория делимости: курс лекций для студентов 2-го курса/ М.П.Тропин. – Новосибирск: Изд. НГПУ, 2010. – 113 с.
Пособие входит в серию "Учебно-дидактические комплексы кафедры алгебры". В курс лекций вошли такие темы, как "Целые числа", "Группы. Кольца. Элементы общей теории делимости", "Многочлены от одной переменной", "Многочлены от нескольких переменных".
Пособие предназначено для студентов- математиков педагогических вузов.
УДК 512(075.8) ББК 22.144и73-2
©Тропин М.П., 2010
©ГОУ ВПО НГПУ, 2010
2
ТЕМА 1. ЦЕЛЫЕ ЧИСЛА
Целые числа ¢ представляют собой один из основных примеров коммутативного кольца с единицей, которые встречаются в различных областях математики. Ниже будет определено отношение делимости в ¢ и доказаны некоторые его свойства.
§1. Отношение делимости и деление с остатком
ОПРЕДЕЛЕНИЕ. Говорят, что целое число a делится на целое число b , если существует такое q ¢ , что a = bq . Коротко этот факт записывается так:
a Mb .
Число a называется делимым, b – делителем, а q –
частным.
Очевидно, что отношение делимости может быть определено в любом кольце.
ТЕОРЕМА (свойства делимости). Для любых целых чисел a, b, c выполняются следующие свойства:
1)a Ma (рефлексивность);
2)если a Mb, bMc , то a Mc (транзитивность);
3) если a Mc, bMc то (a ± b)Mc ;
4)если a Mc , то abMc ;
5)если a Mb , то ±a M±b (делимость не зависит от сомножителя ±1 );
6)0Ma, a M ±1, aM ±a (тривиальные делимости);
7)если a Mb, a ¹ 0 , то a ³ b .
3
ДОКАЗАТЕЛЬСТВО всех свойств проводится по одной схеме: сначала нужно воспользоваться определением делимости, затем выполнить необходимые преобразования. Докажем некоторые из них.
2) |
aMb |
Þ a = bq |
ü |
Þ a = (cq |
|
)q |
= c (q q |
) Þ aMc . |
|
|
1 |
ý |
2 |
||||||
|
bMc |
Þ b = cq2 þ |
|
1 |
2 |
1 |
|
||
|
|
|
|
|
|
|
a Mc
3) bMc
5) a Mb
Þ a = cq |
ü |
Þ a + b = cq1 + cq2 = |
1 |
ý |
|
Þ b = cq2 |
þ |
|
|
|
= c (q1 + q2 ) Þ a + bMc . |
Þ a = bq1 Þ
a= (-b)(-q1 ), - a = b (-q1) = (-b)q1 Þ
Þa M(-b), (-a )Mb, (-a )M(-b) .
7) Если a Mb, a ¹ 0 , то a = bq , причём q ¹ 0 Þ q ³ 1 . Взяв модуль от обеих частей равенства, получаем
a = bq = b × q ³ b ×1 = b .
СЛЕДСТВИЯ ИЗ СВОЙСТВА 7.
а) Если a Mb, bMa , то a = b или a = -b .
б) Если 1Ma , то a = ±1.
ПРИМЕР. Доказать, что число (5 × 333555 + 3 × 555333 )M37 .
Заметим, что 333M37 , 555M37 , т.к. 333 = 37 × 9 ,
555 = 37 ×15 . После этого, |
пользуясь свойствами делимости, |
получаем следующее. |
|
4) |
4) |
333M37 Þ 333555 M37 Þ 5 × 333555 M37 ,
4
4) 4)
555M37 Þ 555333 M37 Þ 3 × 555333 M37 .
Складывая полученные делимости по свойству 3,
получаем
(5 × 333555 + 3 × 555333 )M37 .
ПРИМЕР. Доказать, что для любого натурального n число
(4n + 15n -1)M9 .
Данное свойство удобнее всего доказать по индукции.
Если n = 1, то 41 +15 ×1 -1 = 18M9 .
Предположим, что для n = k свойство выполняется. Докажем его для n = k +1.
4k +1 +15(k + 1) -1 = 4 × 4k +15k +14 = = 4 × (4k +15k -1) - 4 ×15k + 4 + 15k +14 =
= 4 × (4k +15k -1) - 3 ×15k +18 .
Первое слагаемое делится на 9 по предположению, остальные, т.к. у них легко выделить сомножитель 9. По свойствам 4 и 3 полученное выражение делится на 9.
Рассмотрим деление с остатком.
ТЕОРЕМА (о делении с остатком целых чисел). Для любых целых чисел a и b , b ¹ 0 , существуют, причём единственные целые числа q, r такие, что
ìa = bq + r,
íî0 £ r < b .
5
ОПРЕДЕЛЕНИЕ. Число q называется неполным частным,
а число r остатком от деления a на b .. Разделить число a
на число b с остатком, это значит найти неполное частное q и остаток r .
ДОКАЗАТЕЛЬСТВО ТЕОРЕМЫ. 1) СУЩЕСТВОВАНИЕ. |
|
||||||
1-Й СЛУЧАЙ: |
b > 0 |
Þ |
|
b |
|
= b . Рассмотрим множество |
M |
|
|
||||||
чисел вида bk, k Î ¢ , |
удовлетворяющих условию bk £ a , |
и |
|||||
выберем среди |
них |
наибольшее bk0 . Положим q = k0 , |
|||||
r = a - bq , тогда q, r - целые числа и a = bq + r . |
|
Так как bq £ a , то r = a - bq ³ 0 .
Так как b > 0 , то bq < b (q +1) . Так как bq наибольший элемент в M , то
b (q +1) £ a Þ b (q +1) > a Þ
bq + b >a Þ b > a - bq = r Þ b = b > r .
В результате числа q |
и r удовлетворяют всем условиям |
|||
теоремы. |
|
|
|
|
2-Й СЛУЧАЙ: b < 0 Þ |
|
b |
|
= -b . Рассмотрим число -b > 0 , |
|
|
|||
найдём для пары чисел |
|
|
a, - b частное и остаток по |
предыдущему случаю и преобразуем полученный результат.
ïì a = (-b)q + r, |
|
Þ |
ïìa = b (-q ) + r, |
|||||||||||||
í |
£ r < |
|
-b |
|
= |
|
b |
|
; |
í |
0 £ r < |
|
b |
|
. |
|
ï0 |
|
|
|
|
|
ï |
|
|
||||||||
î |
|
|
|
|
|
|
|
|
|
|
î |
|
|
|
|
|
В результате числа −q и r удовлетворяют всем условиям на частное и остаток при делении a на b .
2) ЕДИНСТВЕННОСТЬ.
Пусть
6
a = bq1 + r1, a = bq2 + r2, 0 £ r1 < b , 0 £ r2 < b ,
тогда
bq1 + r1 = bq2 + r2 Þ bq1 - bq2 = r2 - r1 Þ
Þ b (q1 - q2 ) = r2 - r1 .
Если q1 - q2 ¹ 0 , то r2 - r1 ¹ 0 . Сделаем оценку
абсолютной величины левой и правой части полученного равенства:
b £ b × q1 - q2 = b (q1 - q2 ) = r2 - r1 < b .
Противоречие. Следовательно, этот случай невозможен.
Если q1 - q2 = 0 , то r2 - r1 = 0 и q1 = q2, r2 = r1.
СЛЕДСТВИЕ. a Mb тогда и только тогда, когда остаток от деления числа a на число b равен 0.
ДОКАЗАТЕЛЬСТВО. Если a Mb , то a = bq = bq + 0 . В силу
единственности частного и остатка получаем, что q – это частное, а r = 0 – это остаток.
Если остаток от деления числа a на число b равен 0, то
a = bq + 0 Þ a = bq Þ a Mb .
ПРИМЕР. Разделить числа (-344) и 5n -1 на 5 с остатком.
Число 344 на 5 с остатком можно разделить в уме:
344 = 5 × 68 + 4 .
После этого умножаем на -1 и преобразуем равенство так, чтобы выполнялись все условия деления с остатком.
-344 = - (5 × 68) - 4 = 5 × (-68) - 4 = K
7
Число −4 остатком быть не может, т.к. оно отрицательное. Чтобы исправить это, возьмём частное на единицу меньше.
K = 5 × (-69) + 5 - 4 = 5 × (-69) +1.
Теперь все условия выполняются:
ì-344 = 5 × (-69) + 1,
í 0 £ 1 < 5.
î
Следовательно частное равно -69 , а остаток – 1.
Остаток должен быть положительным, поэтому прежде чем выделять сомножитель 5, добавим и отнимем от данного выражения 5.
5n -1 = 5n - 5 + 5 -1 = 5n - 5 + 4 = 5 × (5n −1 -1) + 4 .
В результате получается, что частное равно (5n −1 -1), а
остаток – 4. Отметим, что в данной и предыдущей задаче мы пользовались единственностью частного и остатка: подобрав
подходящие q |
и r , можно прекращать поиски, т.к. других |
||||||||||||
частного и остатка быть не может. |
|
|
|||||||||||
ЗАМЕЧАНИЕ. Остаток при делении должен удовлетворять |
|||||||||||||
условию |
|
|
|
0 £ r < |
|
b |
|
. |
Таких |
чисел |
конечное |
число: |
|
|
|
||||||||||||
0,1, 2,K, |
|
b |
|
-1. |
Ввиду |
этого |
можно |
применять |
метод |
||||
|
|
||||||||||||
перебора всех возможных остатков. |
|
|
|||||||||||
ПРИМЕР. Доказать, что при делении числа n2 |
на 3 не |
||||||||||||
может получиться остаток 2. |
|
|
|
При делении числа n на 3 могут получиться остатки 0,1 и 2. Рассмотрим эти случаи отдельно, и в каждом из них
найдём остаток от деления числа n2 на 3.
n = 3k, n2 = 9k2 = 3 × 3k2 + 0 , остаток равен 0;
8
n = 3k + 1, n2 = 9k2 + 6k +1 = 3 × (3k2 + 2k ) + 1,
остаток равен 1;
n = 3k + 2, n2 = 9k2 +12k + 4 = 3 × (3k2 + 4k +1) + 1,
остаток равен 1.
Ни в одном из случаев остаток 2 не получился.
ПРИМЕР. Доказать, что число 20052006 + 1 не может быть квадратом натурального числа.
Так как 2005 = 3 × 668 +1, то по биному Ньютона можно получить, что
20052006 = (3 × 668 + 1)2006 = 3 × (K) + 1.
Число 20052006 + 1 при делении на 3 будет давать остаток 2, и по предыдущей задаче не может быть квадратом натурального числа.
§2. Наибольший общий делитель и его свойства
ОПРЕДЕЛЕНИЕ. Число m называется общим делителем чисел a и b , если a Mm, bMm .
Число m называется наибольшим общим делителем
чисел a и b , если оно является их общим делителем и делится на любой другой их общий делитель, т.е. если
1)a Mm, bMm ,
2)"k ((a Mk, bMk ) Þ mMk ) .
ЗАМЕЧАНИЕ. Так как наибольший общий делитель делится на любой другой общий делитель, то он (согласно свойству 7) будет действительно наибольшим по абсолютной
9
величине. Таких чисел по крайней мере два: m и −m , т.к. по свойству 5 делимость не зависит от знака. Кроме того их не может быть больше двух, т.к. если m1 и m2 два наибольших
общих делителя, то по определению они делятся друг на друга и, следовательно,
m1 = m2 .
Условимся положительный наибольший общий делитель обозначать
НОД(a, b) .
ЗАМЕЧАНИЕ. НОД(0, 0) не существует, т.к. общим
делителем пары 0,0 является любое целое число. Ниже будет доказано, что во всех остальных случаях НОД существует.
|
|
|
ЛЕММА |
1. |
Если |
числа |
a |
и |
b |
не |
равны |
|
нулю |
||||||
одновременно и a Mb , то НОД(a, b) |
существует и равен |
|
b |
|
. |
||||||||||||||
|
|
||||||||||||||||||
|
|
|
ДОКАЗАТЕЛЬСТВО. |
Заметим, |
что |
если |
bMk , то и |
|
a Mk . |
||||||||||
Поэтому общие делители чисел a |
и b |
– это в точности все |
|||||||||||||||||
делители b . |
Число |
|
b |
|
|
делится на все делители b , поэтому |
|||||||||||||
|
|
||||||||||||||||||
|
b |
|
= НОД(a, b) . |
|
|
|
|
|
a = bq + r , |
то НОД(a, b) |
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
ЛЕММА 2. |
Если |
существует |
||||||||||||||
тогда и только тогда, когда существует НОД(b, r ) и |
|
|
|
|
НОД(a, b) = НОД(b, r ) .
ДОКАЗАТЕЛЬСТВО. Заметим, что множество общих делителей пары a, b и пары b, r совпадают. Действительно,
если aMk, bMk , то r = a − bq Mk . Если bMk, r Mk , то a = (bq + r )Mk .
В результате оба НОД либо не существуют, либо существуют и равны.
10