Алгебра. Ч. 4. Задачник-практикум

ББК 22.144
Ш73

Р е ц е н з е н т ы: д-р физ.-мат. наук М. И. Башмаков (ИИПО СЗО РАО),
д-р физ.-мат. наук Н. Л. Гордеев (РГПУ им. А. И. Герцена)

Рекомендовано к печати
Учебно-методической комиссией математико-механического факультета
Санкт-Петербургского государственного университета

Ш73

Шмидт Р. А.

Алгебра. Ч. 4. Задачник-практикум. — СПб.: Изд-во
С.-Петерб. ун-та, 2016. — 184 с.
ISBN 978-5-288-05401-3
ISBN 978-5-288-05650-5 (ч. 4)

Предлагаемое учебное пособие в первую очередь адресовано студентам, изучающим бакалаврский курс алгебры. В нём приведены решения более или менее стандартных задач теории чисел, алгебры многочленов, систем линейных уравнений, теории определителей и матриц. Примеры снабжены подробными комментариями и методическими указаниями, облегчающими обучающимся освоение методов поиска
решений и способов вычислений. Основанный на многолетнем опыте
автора и следующий классическим традициям преподавания алгебры
в Санкт-Петербургском государственном университете стиль изложения сочетает простоту, полноту и скрупулёзность описания хода решений. Доступное для изучающих базовый курс математики пособие
будет несомненно полезным и для студентов, сделавших выбор профессионального занятия математикой.

ББК 22.144

У ч е б н о е и з д а н и е

Роберт Анатольевич Шмидт

АЛГЕБРА

Часть 4

Задачник-практикум

Подписано в печать с оригинал-макета автора 18.02.2016.
Формат 60 × 84 1/16. Бумага офсетная. Печать офсетная.
Усл. печ. л. 10,7. Тираж 350 экз. (1-й завод). Заказ №31

Издательство СПбГУ. 199004, С.-Петербург, В. О., 6-я линия, 11

Тел./факс (812) 328-44-22
E-mail: publishing@spbu.ru
publishing.spbu.ru

Типография Издательства СПбГУ. 199061, С.-Петербург, Средний пр., 41

ISBN 978-5-288-05401-3
ISBN 978-5-288-05650-5 (ч. 4)
c⃝
Санкт-Петербургский
государственный университет, 2016

Предисловие 

Эта книга содержит способы и методы решения более или менее 
стандартных задач алгебры (в пределах ее начального курса), а также обсуждение условий их применения и предназначена в основном для студентов-математиков, но может быть использована и студентами других 
специальностей, а также теми, кто хочет повысить уровень своих знаний 
по алгебре. Иногда эти методы алгорифмичны, но столь же часто читателю даются лишь указания на то, какие факты могут быть полезны при 
решении задачи (несколько грубо разделяя эти ситуации, можно сказать, 
что в первом случае мы имеем дело с примером – думать не надо, действуй по алгорифму, а во втором – с задачей, где надо думать, что и как 
использовать для ее решения). 
Некоторый, можно сказать, предшественник этой книги – это вышедший в 1986 году в издательстве ЛГУ "Задачник-практикум по аналитической геометрии и высшей алгебре". Т.к., по-видимому, это издание 
уже стало библиографической редкостью (а также для удобства читателя), его алгебраический раздел (довольно скудный, ибо это издание предназначалось в основном для студентов нематематических специальностей) с некоторыми изменениями включен в настоящую книгу (на всякий 
случай, вместе с материалом, утратившим к настоящему времени свою 
актуальность). В предположении о знакомстве читателя с основами соответствующей теории здесь не приводятся аккуратные формулировки определений и фактов, однако иногда даются некоторые напоминания и 
разъяснения. Автор надеется, что используемые здесь более или менее 
стандартные обозначения будут понятны читателю. 
Для удобства поиска нужных вещей здесь принята сквозная нумерация параграфов (при наличии разбиения на главы). 
Заметим, что в формулировках многих задач присутствует слово 
"найти". Трактовка этого слова чаще всего оказывается интуитивно ясной, вообще же оно значит, что мы должны представить искомый объект 
в наиболее удобном (в каком-либо смысле) виде (насколько это возможно); иногда эта трактовка будет уточняться. Также заметим, что решающему задачу часто приходится естественным образом дополнять ее формулировку: например, если в задаче фигурирует целое число 123, то естественно предполагать, что это – его десятичная запись (если явно не указано иное), если требуется решить уравнение x3 – 3x – 2 = 0, то естественно искать решения в множестве чисел (вещественных или комплексных, 
или, м.б., рациональных – это уже зависит от контекста). 
Автор глубоко благодарен профессору Е.В.Дыбковой, чьи замечания и советы много способствовали улучшению изложения. 

I.  Целые числа и кольца вычетов 

1.  Наибольший общий делитель 
Напомним, что наибольший общий делитель (н.о.д.) семейства 
a = (ai) в любом коммутативном кольце (НОД(a)) – это общий делитель 
всех членов этого семейства, делящийся на все их общие делители, и что 
он определен однозначно с точностью до ассоциированности, т.е. в кольце 
 целых чисел – с точностью до знака; значит, исключая тривиальный случай, когда все члены семейства суть нули (н.о.д. такого семейства 
есть 0), его всегда можно выбрать натуральным.  
Далее мы будем говорить только о н.о.д. пары целых чисел (нахождение н.о.д. любого конечного семейства легко сводится к этому случаю, соответствующие примеры приведены только в упражнениях); ясно, 
что эти числа можно считать натуральными. 
В кольце 
 справедлива основная теорема арифметики, т.е. каждое целое число, кроме 0 и ±1, однозначно раскладывается на простые 
множители. Поэтому, если в одном из чисел пары легко видны какие-то 
его простые делители (в частности, если задано его разложение на простые множители), можно увидеть, которые из них входят в н.о.д., просто 
проверяя делимость на них второго числа этой пары. 
ЗАМЕЧАНИЕ. Ответы к разбираемым далее примерам легко находятся с 
помощью компьютера. Однако соответствующие навыки "ручных" вычислений оказываются весьма полезными в самых разных ситуациях ♦ 

1.1. Найти НОД(33000, 1237874). 
Решение. Очевидно, 33000 = 23⋅3⋅53⋅11. Ясно, что второе число делится на 2 и не делится на 4 (74∂/4) и на 5. Далее, признаки делимости 
на 3 и на 11 показывают, что это число не делится на 3 (1 + 2∂3, 3∂3, 
7 + 8∂3, 7 + 4∂/3) и делится на 11 (1 + 3 + 8 + 4 – 2 – 7 – 7 = 0∂11). Значит, 
НОД(33000, 1237874) = 2⋅11 = 22. 
Если таким образом не удается (или затруднительно) найти н.о.д., 
то общий метод поиска решения заключается в замене данной пары другой, в каком-либо смысле более простой. Один из вариантов такой замены появляется, если мы можем указать какой-то общий делитель данной 
пары (очевидно, НОД(ac,bc) = c⋅НОД(a,b)) или делитель одного из чисел, 
взаимно простой со вторым числом (если b,c взаимно просты, то 
НОД(ac,b) = НОД(a,b)). Например, 

НОД(13475, 15415) = 5⋅НОД(2695, 3083) = 5⋅НОД(539, 3083) 
(последняя пара проще исходной в том смысле, что содержит меньшие 
числа). 

Если нахождение таких делителей затруднено, то почти единственный вариант упрощения данной пары основывается на следующем 
факте: 
∀a,b,c∈  НОД(a,b) = НОД(a + bc,b) , 
т.е. добавляя к одному из чисел данной пары любое кратное другого ее 
числа, мы не меняем ее н.о.д. 
 Смысл такого упрощения может быть разным. Во-первых, таким 
образом мы можем получить число с легко угадываемым делителем и далее действовать так, как указано выше. 

1.2. Найти НОД(1562483, 2483). 
Решение. Вычитая из первого числа второе и затем выбрасывая 
множители 2 и 5, не входящие во второе число, получаем: 
НОД(1562483, 2483) = НОД(1560000, 2483) = НОД(39, 2483). 
Т.к. 39 = 3⋅13 и, очевидно, 2483∂/3, непосредственным делением проверяем, делится ли 2483 на 13, и видим, что 2483∂13. Итак, 
НОД(1562483, 2483) = 13. 

1.3. Найти НОД(513 + 2, 526 + 3). 
Решение. Вычитая из второго числа первое, умноженное на 513 – 2, 
и затем вычитая из первого новое второе, получаем: 

НОД(513 + 2, 526 + 3) = НОД(513 + 2, 7) = НОД(513 – 5, 7) .  

Далее, 513 – 5 = 5⋅(512 – 1) = 5⋅(56 – 1)(56 + 1), и 56 – 1 = (53 – 1)(53 + 1); 
и, т.к. 53 + 1 = 126∂7, 
НОД(513 + 2, 526 + 3) = 7 
(проверять множители 53 – 1 и 56 + 1 уже не нужно, хотя и ясно, 
что они не делятся на 7: 53 – 1 = 4⋅24, а 56 + 1 = (56 – 1) + 2∂/7 ). 

1.4. Найти НОД(a2 + 3a + 7, 2a + 3), a∈  . 
Решение. Здесь естественное упрощение – удаление a2 из первого 
числа данной пары. Этого нельзя сделать сразу (при нечетном a нужный для этого коэффициент не будет целым), однако, т.к. 2a + 3 не 
делится на 2, умножение первого числа на 2 не изменит н.о.д., после 
чего удаление a2 станет возможным. Таким же образом далее удаляется и первая степень a. Итак, 

НОД(a2 + 3a + 7, 2a + 3) = НОД(2a2 + 6a + 14, 2a + 3) =  
= НОД(3a + 14, 2a + 3) = НОД(6a + 28, 2a + 3) = НОД(19, 2a + 3) =  

= {
19, если 2
3 19
1, если 2
3/19
a
a
+
+
.  

ЗАМЕЧАНИЕ. После прочтения §3 будет видно, как можно более изящно 
выразить условия, указанные в ответе ♦ 

Если (в частности) числа заданы десятичной (или другой позиционной) записью, то лежащий, так сказать, на виду вариант упрощения – 
уменьшение одного из них с использованием указанного свойства. Максимальный эффект достигается здесь заменой одного из чисел (большего) 
остатком при делении его на другое число: если a = bq + r (|r|<b), то 
НОД(a,b) = НОД(a – bq,b) = НОД(r,b) (остаток здесь можно выбрать как 
положительным, так и отрицательным; естественно выбирать из них 
меньший по абсолютной величине). С новой парой чисел можно поступить так же, т.е. разделить с остатком b на r (или на –r, если r<0), и 
т.д. Поскольку остатки уменьшаются по абсолютной величине, какой-то 
из очередных остатков будет равен 0; ясно, что последний из ненулевых 
остатков и есть искомый н.о.д. 
Этот процесс нахождения н.о.д. называется алгорифмом Евклида. 
Ясно, что провести его эффективно можно, если мы можем эффективно 
делить с остатком. Хорошо известен алгорифм такого деления для случая, когда числа заданы позиционной (в частности, десятичной) записью 
(т.н. "деление уголком"). Т.о., в этом случае нахождение н.о.д. может 
встретить разве лишь чисто вычислительные трудности. 
Заметим, что после каждого шага алгорифма Евклида (как и после 
каждого шага каждого из делений с остатком) мы получаем пару чисел с 
тем же н.о.д., что и исходная пара, и, значит, можем использовать приемы, указанные ранее (и затем, если надо, продолжать алгорифм). 

1.5. Найти НОД(71449,62107). 
Решение. 

77449 62107
62107 1
9342
  

62107 9342
65394 7
3287
−
  

9342 3287
9861 3
519
−
  

3287 519
3114 6
173
  

519 173
519 3
0
 

Итак, НОД(71449,62107) = 173. 
Если бы мы заметили, что первый остаток делится на 6, то смогли 
бы слегка упростить процесс: 9342 = 6⋅1557, и далее, 

62107 1557
4671 39
15397
14013
1384

  

1557 1384
1384 1
173
  

1384 173
1384 8
0
 ,  или даже так: 

62107 1557
6228 40
173
−
  

1557 173
1557 9
0
 

1.6. Найти НОД(8351277,212267). 
Решение. Начинаем алгорифм Евклида: 

8351277 212267
636801 3
1983267
     – деление не закончено, но легко видеть, что 

здесь выгоднее не продолжать его, а вычесть из последнего остатка 
делитель: 1983267 – 212267 = 1771000, затем сократить это число на 
1000 (это не изменит н.о.д., т.к. 212267 не делится на 2 и на 5) и продолжить алгорифм Евклида: 

212267 1771
1771
12
3516
3542
253
−

  

1771 253
1771 7
0
 . 

Итак, НОД(8351277,212267) = 253 . 
Позже будут рассмотрены и другие методы нахождения н.о.д. 
Упражнения. 
1. Найти н.о.д. следующих пар чисел: 
1) (32⋅53⋅11,47352525) 
2) (99000,588786) 
3) (1383333,271111) 
4) (3a2 + a – 1,5a + 3) 
5) (111426 – 1,11713 – 4) 
6) (107257,88013) 
7) (156505,214135) 
8) (6081703,22703) 
2. Найти н.о.д. следующих троек чисел: 
1) (103926,103896,106955) 
2) (28907,42881,54389) 

2.  Линейные диофантовы уравнения 
Диофантовы уравнения – это алгебраические уравнения с целыми 
коэффициентами, для которых ищутся целочисленные решения. Самое 
простое из таких уравнений – линейное уравнение с двумя неизвестными (случай одного неизвестного тривиален). Один из методов решения 
такого уравнения основан на том, что в кольце  н.о.д. любого семейства 
линейно представи' м через это семейство: если d = НОД((ai)), то ∃(ui): 
d = ∑uiai. В частности, если d = НОД(a,b), то d = ua + vb, где u,v∈  . 
Пусть ax + by = c – диофантово уравнение, и d = НОД(a,b). Очевидное необходимое условие существования его решения – c∂d. Обратно, если это условие выполнено, т.е. c = dc' (c'∈ ), то при d = ua + vb 
пара x0 = uc', y0 = vc' есть, очевидно, решение этого уравнения. Т.о., условие c∂d необходимо и достаточно для разрешимости этого уравнения. 
Выясним теперь, как найти все решения этого уравнения. Если c∂d 
и x0,y0 и x1,y1 – его решения, то ax0 + by0 = c = ax1 + by1, и, после сокращения на d, a'x0 + b'y0 = a'x1 + b'y1, откуда a'(x1 – x0) = b'(y0 – y1)∂b'. Т.к. a',b' 

взаимно просты, по одному из свойств взаимной простоты в 
 x1 – x0∂b', 
т.е. x1 – x0 = b't при некотором t∈ , и x1 = x0 + b't, откуда y1 = y0 – a't. Обратно, если x0,y0 – какое-либо решение нашего уравнения, то, как легко 
видеть, при любом t∈  пара x1 = x0 + b't, y1 = y0 – a't также есть решение. 
Т.о., если x0,y0 – какое-то (любое) решение нашего уравнения, то его 
общее решение (т.е. все множество его решений) задается следующим 
образом: 

{

0

0

x
x
b t
y
y
a t
′
=
+

=
− ′  , t∈  . 

Итак, для нахождения общего решения такого уравнения достаточно найти какое-либо одно из его решений, для чего достаточно найти 
линейное представление н.о.д. его коэффициентов (другие методы будут 
рассмотрены позже). Это можно сделать, в частности, через алгорифм 
Евклида – если можно провести его эффективно (например, если коэффициенты уравнения заданы позиционной записью). Технические нюансы такого процесса продемонстрированы в следующем примере. 

2.1. Решить в целых числах: 26461x + 5969y = 141. 
Решение. Для нахождения линейного представления н.о.д. через алгорифм Евклида удобно после каждого шага алгорифма делать краткую запись этого деления, обозначая буквами делимое, делитель и 
остаток и явно выписывая только неполное частное (польза таких записей станет ясна чуть позже). Проводим этот процесс, обозначив 
коэффициенты уравнения a и b соответственно: 

1

26461 5969
23876 4
2585 r
=
 
a = 4b + r1 

2

5969 2585
5170 2
799
r
=
 
b = 2r1 + r2 

3

2585 799
2397 3
188 r
=
 
r1 = 3r2 + r3 

4

799 188
752 4
47
r
=
 
r2 = 4r3 + r4  

188 47
188 4
0
 
(краткая запись последнего деления не нужна). 

Итак, НОД(a,b) = 47. Проверяя делимость свободного члена на 47, 
видим, что 141 = 47⋅3, т.о., решение существует. 

Теперь из кратких записей делений (проходя их снизу вверх) получаем: 
 
НОД(a,b) = 47 = r4 = r2 – 4r3 = r2 – 4(r1 – 3r2) = –4r1 + 13r2 =        
 
 
= –4r1 + 13(b – 2r1) = 13b – 30r1 = 13b – 30(a – 4b) =      
 
 
= –30a + 133b. 
Следовательно, одно из решений: x0 = –30⋅3 = –90, y0 = 133⋅3 = 399. 
Деля a и b на их н.о.д., получаем: 26461 = 47⋅563, 5969 = 47⋅127. 
Итак, общее решение нашего уравнения таково: 

{
90 127
399 563

x
t
y
t
=−
+
=
−
 , t∈  . 

Сделаем теперь два замечания. 
Во-первых, для лучшего понимания читателем этого процесса цепочка равенств при получении линейного представления н.о.д. излишне 
подробна. Ясно, что некоторые ее члены выписывать необязательно, а 
именно, разумно записать ее так: 

НОД(a,b) = 47 = r4 = r2 – 4(r1 – 3r2) = –4r1 + 13(b – 2r1) = 13b – 30(a – 4b) =
 
 
= –30a + 133b. 
Во-вторых, заметим, что здесь уже нельзя манипулировать с остатками, 
т.к. нам нужны некоторые точные равенства, а не только делимости (но 
остатки можно брать отрицательными, отражая это в краткой записи). 
В реальных условиях диофантово уравнение появляется как часть 
какой-то другой задачи, и тогда, как правило, требуется отыскать его решение (или решения), удовлетворяющее какому-то еще условию (или условиям). Если такое вообще возможно, то это можно сделать за счет выбора подходящего значения параметра, ранее – в записи общего решения – обозначенного t . В разных случаях это, естественно, делается поразному, но если, как часто бывает, нужно найти наименьшее натуральное решение (или решение, наименьшее по абсолютной величине), то таким будет остаток (положительный или отрицательный) при делении 
найденного начального решения на коэффициент при этом параметре. 
2.2. Найти наименьшее натуральное число, дающее при делении на 
2827 и на 3751 остатки 132 и 275 соответственно. 
Решение. Если m – искомое число, то m =2827x+132 =3751y+ 275, 
откуда 2827x – 3751y = 143. Решим это уравнение, заметив, что нам 
достаточно найти только одно из неизвестных, и обозначив a = 2827, 
b = 3751. 

3751 2827
2827 1
924
 
b = a + r1 

2827 924
2772 3
55
 
a = 3r1 + r2 

924 55
55 17
374
385
11
−

 
r1 = 17r2 – r3 

Т.к 55∂11, НОД(a,b) = r3 = 11. 143 = 11⋅13, т.ч. продолжаем: 

r3 = –r1 + 17(a – 3r1) = 17a – 52(b – a) = 69a – … ; 3751 = 11⋅341, значит, 

 
x = 69⋅13 + 341t = 897 + 341t. 
Чтобы получить нужное m, надо взять наименьшее положительное 
значение x, для чего разделим с остатком 897 на 341: 

897 341
682 2
215
 (т.о., при t = –2 получаем x = 215).  

Итак, m = 2827⋅215 + 132 = 607937. 
Следующий пример, конечно, надуман, но хотя бы очень приблизительно представляет возможную конкретную ситуацию. 

2.3. Некий механизм устроен так, что при нажатии одной из клавиш (назовем ее первой) его вал поворачивается на 13 оборотов по часовой 
стрелке, а при нажатии другой (второй) – на 21 оборот против часовой стрелки. Каково наименьшее число нажатий клавиш, нужное 
для поворота вала на 10 оборотов по часовой стрелке? 
Решение. Если x и y – нужные числа нажатий первой и второй 
клавиш соответственно, то 13x – 21y = 10. Т.к. 13 и 21, очевидно, 
взаимно просты, то это уравнение имеет решение (правда, пока неясно, имеется ли подходящее нам решение – очевидно, должно быть 
x,y r0). Обозначим a = 13 и b = –21. Хотя НОД(a,b) и известен, алгорифм Евклида проводить все равно надо. 

2113
26 2
5
−
 –b = 2a – r1   

13 5
10 2
3
 a = 2r1 + r2   

5 3
6 2
1
−
 
r1 = 2r2 – 1 , и 

1 = –r1 + 2(a – 2r1) = 2a – 5(2a + b) = –8a – 5b,