close

Вход

Забыли?

вход по аккаунту

?

Fedorenko1

код для вставкиСкачать
???????????? ??????????? ? ????? ?????????? ?????????
??????????????? ??????????????? ??????????
??????? ????????????????? ???????????
?????-????????????? ??????????????? ???????????
???????????????? ???????????????
C. ?. ?????????
?????????? ??????????
???????? ??????? ?????? ?????
???????????? ????????
?????-?????????
2011
??????????? ????????? ?. ?. ?????????
????????? ?????? ??????? ?????????????? ?????????? ?
???????????? ????? ?????-?????????????? ???????????????? ???????????????? ????????????, ????????
??????????? ???? ?. ?. ????????
???????????? ???????? ???????????? ????? ????? ????? ??????,
??????? ?????? ???? ???????? ?????????, ??????????? ?? ???????????? «?????????????? ????????????», «?????????????? ???????», «??????????? ? ?????????????? ???????».
????????????? ??? ????????? ????????????? 090104, ? ????? ????? ???? ???????????? ??? ??????????????? ?????? ??? ??????????
??????? ?? ???.
???????????? ???????? ??????????? ?????? ?????????? ? ????????????? ? ??????? ???????????-???????????? ??????? ??????????????????? ???????????????? ???????????? ????????????????
???????????????.
???????? ?. ?. ?????????
????????? ? ?????? 05.05.11. ?????? 60Ч84 1/16.
?????? ????????. ???. ???. ?. 0,7. ????? 100 ???. ????? ? 184.
???????????-???????????? ????? ????
190000, ?????-?????????, ?. ??????? ??., 67
© ?????-????????????? ???????????????
??????????? ????????????????
??????????????? (????), 2011
1.
Основные понятия теории делимости
Число a делится на ненулевое число b, если найдется такое целое число c, что выполняется равенство a = b · c.
Обозначения:
1) a ... b a делится на b;
2) b | a b делит a;
3) a кратно (кратное) b, b делитель a.
Определение.
Деление с остатком
Пусть даны два числа a и b, a ? Z , b ? N , где Z множество
целых чисел, а N множество натуральных чисел. Разделим a
на b с остатком a = b · q + r, где r лежит в промежутке 0 ? r < b,
q неполное частное, r остаток. Например, 7 = 2 · 3 + 1.
Теорема 1.1. Для любого целого a и натурального b представление
единственно.
a = b · q + r,
3
0?r<b
Доказательство
1. Существование.
Рассмотрим бесконечное множество чисел {a ? tb}, где a, b
фиксированные числа, t любое число, t ? Z . Из него мы
выберем наименьшее неотрицательное число r = a?q·b. Докажем,
что r лежит в пределах 0 ? r < b.
Пусть это число не принадлежит данному промежутку. Тогда
оно больше или равно b. Построим новое число r? = r ? b=a ? q ·
b ? b=a ? b(q + 1). Отсюда видно, что:
1) r? ? {a ? tb};
2) r? неотрицательное;
3) r? < r.
Следовательно, не r, a r? является наименьшим неотрицательным числом из множества {a ? tb}, тогда предположение r ? b ложно. Существование доказано.
2. Единственность.
Пусть существует другое представление a = bq? + r? при условии, что 0 ? r? < b; a, b фиксированные числа, q ? Z . То
есть мы можем разделить число a на b двумя способами, тогда
bq + r = bq ? + r? . Перенося слагаемые с q в одну сторону, а с r в
другую, получаем b(q ? q?) = r? ? r. Видно, что (r? ? r) ... b. Каждый
из остатков меньше b и
{
.
(r? ? r) .. b .
|r? ? r| < b
Следовательно, r? ? r = 0, а значит r? = r и q = q?. Итак, доказали, что одно число можно разделить на другое единственным
способом.
Теорема доказана.
.
.
.
Теорема 1.2. Если a .. b и b .. c, то a .. c, где b, c ?= 0.
Доказательство
{
a=b·q
.
b=c·t
4
Следовательно, a = c · qt. По определению делимости видно,
что a ... c.
Теорема 1.3. Пусть выполняется равенство a1 + a2 = b1 + b2
и числа a1, a2, b1 ... d, тогда b2 ... d.
Доказательство
a1 = d · t1 , a2 = d ·t2 , b1 = d · t3 . Выразим b2 из условия теоремы
b2 = a1 + a2 ? b1 =d(t1 + t2 ? t3 ). По определению делимости видно,
что b ... d.
2
2.
Наибольший общий делитель
Если число c является делителем чисел a и b, то
число c называется общим делителем чисел a и b.
Наибольший из общих делителей чисел a и b называется наибольшим общим делителем (НОД) чисел a и b.
Обозначение: (a, b) = d, где a и b числа, а d НОД этих
чисел.
Рассмотрим пример для чисел 12 и 9. Выпишем все делители
12 и все делители 9. Для 12: 1, 2, 3, 4, 6 и 12; для 9: 1, 3 и 9; общие
делители 1 и 3. Выберем наибольший из них это 3. Таким
образом, (12, 9) = 3.
Два числа a и b называются взаимно простыми,
если их НОД равен 1.
Пример. Так как (10, 9)=1, то 10 и 9 взаимно простые
числа.
Это определение можно распространить на любое количество
чисел. Если (a, b, c, . . .) = 1, то числа a, b, c, . . . взаимно простые.
Например: (12, 9, 2)=1.
Определение.
Определение.
Определение.
5
(a1 , a2 , ..., an ) попарно взаимно простые числа,
если НОД любой пары равен единице: (ai, aj ) = 1, i ?= j .
Например: 12, 17, 11 не только взаимно простые, но и попарно взаимно простые.
.
Теорема 2.1. Если a .. b, то (a, b) = b.
Доказательство
Число b не может делиться на число больше самого себя. Следовательно, b является НОД a и b.
Теорема 2.2. Пусть имеется представление a = bq + r (r не
обязательно остаток), тогда (a, b) = (b, r).
Доказательство
1. Рассмотрим любой общий делитель a и b c. Если a ... c и b
... c, то по теореме 1.3 r ... c, т.е. c является также общим делителем
b и r. Любой общий делитель a и b является общим делителем b
и r.
2. Любой общий делитель b и r является делителем a. Значит,
общие делители a, b и b, r совпадают. Это верно и для НОД.
Определение.
3.
Алгоритм Евклида
Для любых чисел a и b с помощью алгоритма Евклида можно
найти НОД.
Пусть a, b ? N входные данные алгоритма, а
(a, b) = d ? N выходные.
6
1
2
3
···
i
···
n
n+1
a
b
r1
=
=
=
ri?2
=
bq0
r1 q1
r2 q2
···
ri?1 qi?1
···
rn?1 qn?1
rn qn
+
+
+
r1
r2
r3
+
ri
0 < r1 < b
0 < r2 < r1
0 < r3 < r2
···
0 < ri < ri?1
···
0 < rn < rn?1
=
+ rn
=
+ 0
Шаг 1. Делим a на b с остатком: a = bq0 + r1 , где 0 < r1 < b.
По теореме 2.2 (a, b) = (b, r1).
Шаг 2. Делим b на r1 с остатком: b = r1 q1 +r2 , где 0 < r2 < r1 .
По теореме 2.2 (b, r1) = (r1, r2).
И так до тех пор, пока не разделится нацело. Из цепочки равенств (a, b) = (b, r1) = (r1, r2) = (r2, r3) = ... = (rn?2, rn?1) =
(rn?1 , rn ) = rn следует, что последний ненулевой остаток rn будет НОД d = rn = (a, b). Так как остатки убывают, то алгоритм
завершится за конечное число шагов.
rn?2
rn?1
Теоремы, связанные с алгоритмом Евклида
НОД двух чисел делится на любой общий делитель этих чисел. ( a b ) d
Если (a, b) = d, то c , c = c , где c общий делитель a и b.
Доказательство
В записи алгоритма Евклида a, b и все ri разделим на c. Получим запись алгоритма Евклида с входными данными ac и cb . Из
нее видно, что НОД ac и cb равен dc .
Теорема 3.1.
Если два числа
разделить
на их НОД, то полу(
)
a b
чим взаимно простые числа: d , d = 1.
Доказательство
Вместо c (из теоремы 3.1) подставим d.
Теорема 3.2.
7
{
Если (a,..b) = 1 , то c ... b.
ac . b
Доказательство
Для взаимно простых чисел a и b по теореме 7.1 (см. ниже)
существует представление ax + by = 1. Умножая это равенство на
c, имеем ac · x + byc = c, но ac = bq , bqx + byc = c, b(qx + yc) = c.
Следовательно, c ... b.
Теорема 3.3.
НОД нескольких чисел
(a1 , a2 , . . . , an ) = dn
(a1 , a2 ) = d2
(d2 , a3 ) = d3
...
(dn?1 , an ) = dn
4.
Наименьшее общее кратное
Общее кратное двух чисел a и b это такое
число, которое делится на оба этих числа a и b.
Наименьшее из общих кратных чисел a и b называется наименьшим общим кратным (НОК) чисел a и b.
Пусть M ... a и M ... b, тогда M общее кратное a и b.
Наименьшее общее кратное чисел a и b обозначим как [a, b].
Теорема 4.1. НОК двух чисел равно отношению их произведения к НОД:
Определение.
Определение.
[a, b] =
8
ab
.
(a, b)
Доказательство
Обозначим некоторое общее кратное чисел a и b через M , тогда M ... a и M ... b. Кроме того, d = (a, b), a = a?d, b = b?d, причем
(a? , b? ) = 1.
По определению делимости M = a · k, где k ? Z :
M
a·k
=
? Z,
b
b
ak
a? dk
a? k
= ? = ? ,
b
bd
b
не делится на b?, так как они взаимно простые, следовательно,
.
k .. b? по теореме 3.3:
a?
k = b? · t =
тогда
M =a·k =
bt
,
d
t ? Z,
ab
ab
t=
t ?
d
(a, b)
вид любого общего кратного чисел a и b. При t = 1 M является
НОК чисел a и b.
НОК нескольких чисел
[a1 , a2 , . . . , an ] = Mn
[a1 , a2 ] = M2
[M2 , a3 ] = M3
[M3 , a4 ] = M4
...
[Mn?1 , an ] = Mn
Если
(a, b) = 1
a1 a2 · . . . · an
.
, то [a, b] = ab. При (ai, aj ) = 1, i ?= j , M
9
=
5.
Простые и составные числа
Любое число делится на 1 и на само себя. Назовем эти делители тривиальными.
Число называется простым, если оно не имеет
нетривиальных делителей. Число называется составным, если оно
имеет нетривиальный делитель. Число 1 не является ни простым,
ни составным.
Теорема 5.1. Для любого натурального числа a и простого
числа p выполняется или (a, p) = 1, или a ... p.
Доказательство
У простого числа p имеются два тривиальных делителя. Возможны два варианта: a ... p или a ? ... p. Если a ? ... p, то НОД a и p
является 1. Следовательно, (a, p) = 1.
Теорема 5.2. Наименьший отличный от единицы делитель
целого, большего единицы, есть простое число.
Доказательство
Если a ?= 1, то a = p · q, где p наименьший нетривиальный
делитель. Предположим, что p составное число. Это означает,
что существует такое число s, что p ... s, но тогда a ... s и p не
является наименьшим делителем, что противоречит условию. Т.о.
p простое число.
Теорема 5.3. Наименьший нетривиальный делитель составного числа не превосходит его корня.
Д о к а з а т е ?л ь с т в о
2
a = q · b, q ? b, q ? bq = a, q ? a.
Определение.
Решето Эратосфена
Запишем множество натуральных чисел
10
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, . . .
Единица это особое число. С остальными числами поступаем следующим образом: берем число, объявляем его простым и
вычеркиваем числа, кратные ему.
Например, 2 простое число, вычеркиваем числа, кратные
двойке, следовательно, четных чисел не останется. Аналогично
поступим и с тройкой. Нужно вычеркнуть 6, 9, 12, 15, 18, и т.д.
Все оставшиеся числа являются простыми.
Теорема 5.4. Множество простых чисел бесконечно.
Доказательство
Пусть {2, 3, 5, . . . , P } конечное множество простых чисел и
N = 2 · 3 · 5 · . . . · P + 1. N не делится ни на одно из простых чисел, так как при делении в остатке получается 1. Но наименьший
нетривиальный делитель N по теореме 5.2 является простым числом ?? {2, 3, 5, . . . , P }. Следовательно, простых чисел не конечное
множество, а бесконечное.
6.
Каноническая форма числа
Любое
число, отличное от 1, единственным способом представляется в
виде произведения простых чисел.
Доказательство
1. Существование.
Число n по теореме 5.2 имеет простой делитель p1:
Теорема 6.1 (основная теорема арифметики).
n
.
p1
n1 =
Аналогичные рассуждения справедливы и для числа n1:
n2 =
n1
,
p2
11
где p2 простой делитель n1. И так будем продолжать до тех
пор, пока не получим ni = 1.
2. Единственность.
Пусть число n имеет два разложения на простые числа:
n = p 1 · p 2 · . . . · p l = q1 · q2 · . . . · qs .
Без ограничения общности примем l ? s. Если левая часть равенства делится на p1, то и правая тоже делится на p1. Значит,
некоторое qi = p1. Пусть это q1 = p1. Разделим обе части равенства на p1:
p2 · . . . · pl = q2 · . . . · qs .
Аналогично примем q2 = p2. Будем продолжать эту процедуру,
пока выражение не примет вид
1 = ql+1 · . . . · qs .
Если l < s, то произведение простых чисел не может быть равно
1. Следовательно, предположение о двух различных разложениях числа n неверно. Если s = l, то pi = qi для i ? [1, l] и два
разложения совпадают.
Теорема доказана.
Любое число n ? N можно записать в канонической форме
n = p1 s 1 · . . . · pl s l ,
где pi простые числа, si ? N .
Каноническое представление позволяет выписать все делители
числа и определить НОД и НОК.
Все делители c числа n имеют вид
c = p1 i · p2 i . . . pl i , где ij ? [0, sj ].
1
2
l
12
Нахождение НОД и НОК
Пусть числа a и b представлены в виде
a = p1 s 1 · p2 s 2 · . . . · pl s l ;
b = p1 t1 · p2 t2 · . . . · pl tl .
Это представление отличается от канонического тем, что некоторые si и ti могут быть равны 0.
Тогда НОД a и b
а НОК
(a, b) = p1 min(s1 ,t1 ) · p2 min(s2 ,t2 ) · . . . · pl min(sl ,tl ) ,
[a, b] = p1 max(s1 ,t1 ) · p2 max(s2 ,t2 ) · . . . · pl max(sl ,tl ) .
Отсюда также видно, что (a, b) делится на любой общий делитель a и b.
7.
Линейные диофантовы уравнения
с двумя неизвестными
Линейным диофантовым уравнением с двумя
неизвестными называется уравнение вида
Определение.
ax + by = c,
где коэффициенты a, b, c и неизвестные x, y целые числа, а a и
b не равны нулю одновременно.
Теорема 7.1 (о линейном представлении НОД). Для любой пары чисел (a, b) ((a, b) ?= (0, 0)) существуют такие x, y ? Z ,
что ax + by=(a, b).
13
Доказательство
Рассмотрим множество чисел {ax + by} и из него выберем минимальное положительное число d = ax0 + by0.
Докажем, что d является делителем b.
Пусть d не делитель b, следовательно, b = d · q + r, где
0 < r < d, r = b ? dq = b ? (ax0 + by0 )q = a(?x0 q) + b(1 ? y0 q).
Видно, что:
1) число r ? {ax + by};
2) r положительное;
3) r < d.
Но мы предположили, что d наименьшее положительное
число из этого множества, следовательно, наше предположение,
что r < d, неверно, значит, d делитель b.
Аналогично можно доказать, что a ... d.
Из всего
? этого следует, что d является общим делителем a и b.
? ..
Итак, ? a .. (a, b) ? d ... (a, b), но d общий делитель a и b,
b .. (a, b)
следовательно, d НОД a и b.
Теорема 7.2. Уравнение ax + by = c имеет решение тогда и
только тогда, когда c делится на (a, b).
Доказательство
.
1. Пусть c .. (a, b), тогда поcтеореме 7.1 ax + by = (a, b).
Умножим уравнение на (a, b) :
a·
xc
yc
+b·
= c.
(a, b)
(a, b)
Пара чисел (x0, y0) будет решением исходного уравнения:
{
x0 =
y0 =
xc
(a,b)
yc
(a,b)
.
2. Докажем, что если уравнение имеет решение, то c ... (a, b).
14
...
, следовательно, c тоже должно делиться на (a, b).
? ..
b . (a, b)
?
?
a (a, b)
Теорема 7.3. Любое решение линейного диофантова уравнения ax + by = c может быть записано в виде
{
x = x0 ? k db
,
y = y0 + k ad
k ? Z,
где d = (a, b), а пара (x0, y0) одно из решений этого уравнения.
Доказательство
1. Изучим связь двух решений уравнения (x0, y0) и (x1, y1).
Вычитая ax1 + by1 = c из ax0 + by0 = c, имеем
a(x0 ? x1 ) + b(y0 ? y1 ) = 0.
Разделим
выражение на d, учитывая,
{
?d
a
=
a
что b = b?d , где (a?, b?) = 1.
a? (x0 ? x1 ) = b? (y1 ? y0 ).
(1)
Правая часть (1) делится на a?: b?(y1 ?y0) ... a?, а так как (a?, b?) =
.
.
1, то по теореме 3.3 (y1 ? y0 ) .. a? , Аналогично (x0 ? x1 ) .. b? .
Значит:
?
.
?
(y1 ? y0 ) .. a?
. ,
?
(x0 ? x1 ) .. b?
{
y1 ? y0 = a? k1
,
x0 ? x1 = b? k2
k1 , k2 ? Z.
Подставляя последнюю систему в (1), имеем a?b?k2 = b?a?k1 и
k2 = k1 = k , т.е.
{
y1 ? y0 = a ? k
.
x0 ? x1 = b? k
Выразим из этой системы x1 и y1:
15
{
x1 = x0 ? b? k
y1 = y0 + a? k
и получим связь между двумя решениями системы
{
2. Докажем, что если
{
x1 = x0 ? k db
.
y1 = y0 + k ad
x1 = x0 ? k db
,
y1 = y0 + k ad
k ? Z,
то (x1, y1) будет решением ax + by = c.
Подставим x1 и y1 в исходное уравнение
a
ab
ba
b
ax1 + by1 = a(x0 ? k ) + b(y0 + k ) = ax0 ? k + by0 + k =
d
d
d
d
ax0 + by0 = c
.
Теорема доказана.
Литература
1. Виноградов И. М. Основы теории чисел. М.: Наука, 1965.
2. Бухштаб А. А. Теория чисел. М.: Просвещение, 1966.
16
Документ
Категория
Без категории
Просмотров
0
Размер файла
164 Кб
Теги
fedorenko1
1/--страниц
Пожаловаться на содержимое документа