Бардушкин В.В., Кожухов И.Б., Прокофьев А.А., Фадеичева Т.П. Основы теории делимости чисел. Решение уравнений в целых числах
Подождите немного. Документ загружается.
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ИНСТИТУТ
ЭЛЕКТРОННОЙ ТЕХНИКИ
(ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ)
_____________________________________________________________________________
______________________________________________________________
В.В. Бардушкин, И.Б. Кожухов,
А.А. Прокофьев, Т.П. Фадеичева
ОСНОВЫ ТЕОРИИ ДЕЛИМОСТИ ЧИСЕЛ
РЕШЕНИЕ УРАВНЕНИЙ В ЦЕЛЫХ ЧИСЛАХ
Факультативный курс
Рекомендовано региональным советом МГИЭТ(ТУ)
по довузовской подготовке
Москва 2003
УДК 511.8
Рецензенты:
– доктор физико-математических наук, профессор Яковлев В.Б.;
– учитель математики школы № 853 (г. Зеленоград), заслуженный учитель России
Утина Н.И..
Бардушкин В.В., Кожухов И.Б., Прокофьев А.А., Фадеичева Т.П.
Основы теории делимости чисел. Решение уравнений в целых
числах. Факультативный курс. – М.: МГИЭТ(ТУ), 2003. – 224 с.
Рассмотрены вопросы делимости на множестве целых чисел и
методы решения в целых числах некоторых типов уравнений. Все
задачи разбиты по темам, многие из них снабжены указаниями и
решениями.
Для преподавателей математики и учащихся старших классов
лицеев, гимназий и общеобразовательных школ, а также для лиц,
занимающихся математикой самостоятельно.
© Бардушкин В.В., Кожухов И.Б., Прокофьев А.А.,
Фадеичева Т.П. 2003 г.
© Издательство Московского государственного института
электронной техники
(технического университета), 2003 г.
СОДЕРЖАНИЕ
Обозначения 4
Предисловие 5
§ 1. Делимость целых чисел 7
Упражнения 11
§ 2. Простые числа 19
Упражнения 24
§ 3. Сравнения 28
Упражнения 33
§ 4. Наибольший общий делитель 37
Упражнения 44
§ 5. Наименьшее общее кратное 48
Упражнения 51
§ 6. Каноническое разложение натуральных чисел 54
Упражнения 64
§ 7. Диофантовы уравнения 68
Упражнения 81
§ 8. Методы решения нелинейных уравнений 84
Упражнения 99
§ 9. Функция Эйлера 102
Упражнения 108
Приложение 1. О решении
уравнений в рацио-
нальных числах
110
Приложение 2. Варианты контрольных работ 113
Приложение 3. Задачи на целые числа на вступи-
тельных экзаменах в вузы
125
Приложение 4. Краткий исторический очерк 161
Программа факультативного курса
«Основы теории делимости чисел.
Решение уравнений в целых числах»
164
Решения, указания и ответы 166
Литература 221
3
ОБОЗНАЧЕНИЯ
N – множество натуральных чисел;
N
0
– число 0 и множество натуральных чисел;
Q – множество рациональных чисел;
),( bаНОД – наибольший общий делитель целых чисел а и b;
),...,,(
21 п
аааНОД – наибольший общий делитель целых чисел
п
ааа ,...,,
21
;
),( bаНОК – наименьшее общее кратное целых чисел а и b;
),...,,(
21 п
аааНОК – наименьшее общее кратное целых чисел
п
ааа ,...,,
21
;
k
n
С – число сочетаний из п элементов по k;
ab | – целое число b делит целое число а;
ab |
/
– целое число b не делит целое число а;
ba# – целое число а делится на целое число b;
ba #
/
– целое число а не делится на целое число b;
[]
x – целая часть числа х (т.е. ближайшее к х и не превосходящее его
целое число);
)(mod mba ≡ – целое число а сравнимо с целым числом b
по модулю натурального числа
т.
4
ПРЕДИСЛОВИЕ
Уважаемый читатель!
Вашему вниманию предлагается факультативный курс,
затрагивающий традиционно сложные вопросы школьной математики.
Практика преподавания данной тематики показывает, что многие
задачи, связанные с делимостью целых чисел, нестандартны, поэтому
их решение вызывает большие затруднения.
Факультативный курс написан на основе многолетнего опыта
преподавания авторами этого раздела математики в лицее № 1557,
гимназии № 1528, школах №№ 853 и 1151 города Зеленограда. В нем
рассмотрены вопросы делимости на множестве целых чисел и методы
решения в целых числах некоторых типов диофантовых уравнений.
Пособие адресовано в первую очередь преподавателям математики и
учащимся лицеев, гимназий и общеобразовательных школ. Но авторы
надеются, что оно заинтересует и лиц, занимающихся математикой
самостоятельно.
Материал, содержащийся в пособии,
традиционно изучается в
десятых или одиннадцатых классах школ с программой углубленного
курса математики. Однако авторы могли бы рекомендовать учителям
этот материал для внеклассной и кружковой работы в
общеобразовательных школах с нагрузкой по математике не более пяти
часов в неделю. Кроме того, многие задачи можно использовать при
составлении текстов математических олимпиад.
При
написании факультативного курса авторы прекрасно
осознавали трудности, которые возникают перед учителем при
подготовке к занятиям по данной тематике и при разъяснении
материала школьникам. Поэтому составители не ограничились только
теоретическими сведениями и условиями задач с ответами. Все задачи
разбиты по темам, многие снабжены решениями и указаниями.
Пособие состоит из девяти параграфов
и четырех приложений.
Доказательства многих утверждений основаны на методе
математической индукции. Поэтому авторы рекомендуют читателям
заранее ознакомиться с этим методом.
5
В приложении 2 приведены примерные варианты контрольных
работ. Эти (или подобные этим) работы проводились авторами при
изучении данной темы.
В приложении 3 собраны задачи на целые числа, предлагавшиеся в
разные годы на письменных и устных вступительных экзаменах в
различные вузы России.
В конце пособия приведена программа данного факультативного
курса с примерным указанием
часов, отводимых на изучение той или
иной темы.
Необходимо сказать несколько слов об условных значках,
встречающихся в тексте пособия:
– значок
Ö указывает на то, что в теореме доказывается
необходимое условие;
– значок
Õ указывает на то, что в теореме доказывается
достаточное условие;
– значок указывает на завершение доказательства какого-либо
утверждения (леммы, теоремы и т.п.);
– значок * , стоящий после номера упражнения, указывает на то,
что для этой задачи имеется либо решение, либо указание, либо
ответ в соответствующем разделе в конце пособия.
Авторы
приносят искреннюю благодарность рецензентам –
профессору МГИЭТ (ТУ) Виктору Борисовичу Яковлеву и
заслуженному учителю России Утиной Нэлли Ивановне (школа №853
г. Зеленограда) за ценные советы и замечания, способствовавшие
значительному улучшению курса.
В.В. Бардушкин, к.ф.–м.н, доцент, Соросовский учитель
И.Б. Кожухов, д.ф.–м.н, профессор, Соросовский
учитель
А.А. Прокофьев, к.ф.–м.н, доцент, Соросовский учитель
Т.П. Фадеичева, учитель математики школы №853
г. Зеленограда, Соросовский учитель
6
§ 1. Делимость целых чисел
Рассмотрим множество целых чисел Z. Операция деления
выполняется не для всех пар чисел из
Z.
Определение. Число
Z делится на число ∈а
∈
b Z )0(
≠
b , если
существует такое число
Z, что (запись: ). ∈q qba = ba
Замечание. Вместо выражения «
а делится на b» очень часто
используется фраза «число
b делит число а» и при этом применяется
запись
. ab|
Если
а делится на b, то b называется делителем а, само а
называется кратным числа
b. Число q называется частным от деления
а на b.
Число
0 делится на любое . Если 0≠b 0
≠
a , то, очевидно, что
множество всех делителей
а конечно.
Докажем простейшие свойства делимости целых чисел.
Лемма 1. Если и , то . bс| ab| ac |
Доказательство. Так как
и , то bс | ab| cqb
1
=
, bqa
2
=
при
некоторых
Z. Отсюда ∈
21
, qq cqcqqa
=
=
12
, где
12
qqq
=
.
Следовательно,
ac |
Лемма 2. Если , и , то . bam += md | ad | bd |
Доказательство. По определению имеем
dqm
1
=
, dqa
2
=
при
некоторых
Z. Отсюда из равенства ∈
21
, qq bam
+
=
получаем
, т.е. dqqb ⋅−= )(
21
bd |
Замечание. Аналогично доказывается, что если
и d делит числа , то .
nn
aаam +++=
−11
…
11
,,,
−n
aam …
n
ad |
Определение. Общим делителем чисел
∈
n
aаa ,,,
21
… Z называется
число
Z, являющееся делителем каждого из этих чисел. Общий
делитель данных чисел называется их наибольшим общим делителем,
если он делится на всякий общий делитель этих чисел.
∈d
7
Для обозначения наибольшего общего делителя будем
использовать следующее:
),,,(
21 n
аааНОДd …= .
Замечание. На вопросы, связанные с существованием наибольшего
общего делителя, можно получить ответы, изучив § 4 данного пособия.
В этом же параграфе можно получить другие достаточно подробные
сведения о наибольшем общем делителе.
Из определения наибольшего общего делителя вытекает важное
свойство: если
, то множество всех общих
делителей чисел
состоит из всех делителей числа d.
),,,(
21 n
аааНОДd …=
n
aаa ,,,
21
…
Легко видеть, что если
, то
. Очевидно, верно и обратное. Если
, то
),,,(
21 n
аааНОДd …=
)0,,,,(
21 n
аааНОДd …=
)0,,,,(
21 n
аааНОДd …= ),,,(
21 n
аааНОДd …
=
.
Поэтому при нахождении наибольшего делителя нескольких чисел, не
все из которых равны нулю, нули можно не учитывать.
Легко видеть также, что число
0 будет наибольшим общим
делителем чисел
тогда и только тогда, когда
. В этом случае нуль является единственным
наибольшим общим делителем данных чисел.
n
aаa ,,,
21
…
0...
21
====
n
aaa
В дальнейшем изложении будем ограничиваться случаем, когда все
числа отличны от нуля.
Очевидно также, что если
, то число
также является наибольшим общим делителем чисел
. Поэтому в дальнейшем, не ограничивая общности
рассуждений, будем называть наибольшим общим делителем положи-
тельное число в этой паре чисел.
),,,(
21 n
аааНОДd …=
)( d−
n
aаa ,,,
21
…
Если
, то числа
называются взаимно простыми.
1),,,(
21
=
n
аааНОД …
n
aаa ,,,
21
…
Примеры.
; 6)42,18( =НОД 30)360,210,60(
=
НОД ;
1)21,10( =−НОД .
8
Лемма 3. Если Z, ∈cba ,, 1),(
=
baНОД и , то . cab| cb|
Доказательство. Очевидно, что достаточно доказать утверждение для
случая, когда
N. Но сначала докажем более общее ∈cba ,,
утверждение. Если
N , , ∈vuba ,,, vbua = 1),(
=
baНОД , то
, . vа | ub |
Доказательство проведем индукцией по величине суммы
ba
+
.
При имеем , 2=+ ba 1=а 1
=
b , 1),(
=
baНОД .
Утверждение выполняется.
Предположим, что оно справедливо для всех пар
таких, что
, сумма
ba ,
1),( =baНОД kba <
+
, . 2>k
Докажем, что тогда оно имеет место и для таких пар
, что
и сумма . Действительно, из условий
, следует, что
ba ,
1),( =baНОД kba =+
1),( =baНОД 2>+ ba ba
≠
. Ввиду симметрии
равенства
для определенности можно считать, что .
Тогда из
следует, что
vbua = ba >
vbua = buvbbuua
−
=
−
,
. Но )()( uvbuba −⋅=⋅− 1),(
=
−
bbaНОД и сумма
, поэтому по предположению индукции из
равенства
следует, что , или
kabba <=+− )(
)()( uvbuba −⋅=⋅− ub | buu
1
=
.
Подставим это выражение для
и в равенство vbua
=
и сократим обе
его части на
b. Получим, что , следовательно, .
Утверждение доказано.
vau =
1
vа |
Лемма 3 для
∈
cba ,, N следует из доказанного утверждения.
Действительно, если и , то 1),( =baНОД cab| bdac
=
. А по
доказанному выше
cb |
Лемма 4. Если Z взаимно просто с каждым из
Z, то b взаимно просто с их произведением
.
∈b
∈
n
aаa ,,,
21
…
n
aаa ⋅⋅⋅ …
21
Доказательство. Индукция по
п.
При
утверждение очевидно. 1=п
9
Допустим, что
и для утверждение верно. 1>n 1−n
Если
d – общий делитель чисел b и
n
aаa
⋅
⋅
⋅
…
21
, то
и по лемме 3 1),( =
n
adНОД
121
|
−
⋅
⋅
⋅
n
aаad … . По
предположению индукции
1),(
121
=
⋅
⋅
⋅
−n
aаabНОД … . Значит,
1=d
В любом случае (когда
и когда ) можно число а
разделить на число
b с остатком.
ba ba
/
Теорема 1 (о делении с остатком). Если
∈
bа , Z, , то
существуют единственные
0>b
∈
r
q , Z такие, что rqba
+
=
, br
<
≤
0 .
Доказательство.
Существование. Согласно принципу Архимеда (287–
212 г.г. до н.э.) для любого
Z существует такое целое число q, что
. Отсюда . Обозначая
∈а
)1( +⋅<≤ qbabq bbqa <−≤0 rbqa
=
−
,
получим требуемое представление.
Единственность. Предположим, что кроме найденного выше
представления
, имеется другое: rqba += br <≤0
11
rbqa
+
=
,
. Тогда br <≤
1
0
11
)(0 rrqqb −+
−
⋅= , brr <−
1
. Из последнего
равенства следует, что число
b делит разность
1
rr
−
. Но brr <−
1
,
следовательно,
, а тогда и (подставляя
1
rr =
1
qq = 0
1
=
−
rr в
равенство
)
11
)(0 rrqqb −+−⋅=
Замечание. Теорему о делении с остатком можно доказать в более
общей формулировке: если
Z, ∈bа , 0
≠
b , то существуют
единственные
∈
r
q , Z такие, что , rqba += ||0 br
<
≤
.
Примеры. Разделите с остатком а на b, если а = 110, – 53, 156;
b = 12.
Решение.
2912110 +⋅
=
, 1220
<
≤
;
7)5(1253 +−⋅=− , 1270
<
≤
;
01312156 +⋅
=
, 120
<
.
10