close

Вход

Забыли?

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

?

Fedorenko2

код для вставкиСкачать
???????????? ??????????? ? ????? ?????????? ?????????
??????????????? ??????????????? ??????????
??????? ????????????????? ???????????
?????-????????????? ??????????????? ???????????
???????????????? ???????????????
C. ?. ?????????
?????????? ??????????
?????????????? ?????
?????? ?????
???????????? ????????
?????-?????????
2011
??????????? ????????? ?. ?. ?????????
????????? ?????? ??????? ?????????????? ?????????? ?
???????????? ????? ?????-?????????????? ???????????????? ???????????????? ????????????, ????????
??????????? ???? ?. ?. ????????
???????????? ???????? ???????????? ????? ????? ????? ??????,
??????? ?????? ???? ???????? ?????????, ??????????? ?? ???????????? «?????????????? ????????????», «?????????????? ???????», «??????????? ? ?????????????? ???????».
????????????? ??? ????????? ????????????? 090104, ? ????? ????? ???? ???????????? ??? ??????????????? ?????? ??? ??????????
??????? ?? ???.
???????????? ???????? ??????????? ?????? ?????????? ? ????????????? ? ??????? ???????????-???????????? ??????? ??????????????????? ???????????????? ???????????? ????????????????
???????????????.
???????? ?. ?. ?????????
????????? ? ?????? 05.05.11. ?????? 60Ч84 1/16.
?????? ????????. ???. ???. ?. 1,0. ????? 100 ???. ????? ? 186.
???????????-???????????? ????? ????
190000, ?????-?????????, ?. ??????? ??., 67
© ?????-????????????? ???????????????
??????????? ????????????????
??????????????? (????), 2011
1.
Расширенный алгоритм Евклида
Найдем решение уравнения ax + by = (a, b), где (a, b) наибольший общий делитель (НОД).
Пусть a, b ? Z , (b ?= 0) входные данные алгоритма, а
(a, b) ? N ; x, y ? Z выходные.
?1
r?1
= a
r?1 = ax?1 + by?1
0 r0 = b
r0
= ax0 + by0
1 r?1 = bq0
+ r1 r1 = ax1 + by1
2 r0 = r1q1
+ r2 r2 = ax2 + by2
3 r1 = r2q2
+ r3 r3 = ax3 + by3
···
i
···
n
n+1
ri?2
=
···
ri?1 qi?1
···
rn?1 qn?1
rn qn
+
ri
ri
=
···
axi
···
axn
+
byi
=
+ rn rn =
+ byn
=
+ 0
?1 Положим r?1 = a и представляем
r?1 как линейную
{
x?1 = 1
комбинацию a и b. Очевидно, что y?1 = 0 .
Положим r0 = b и представляем r0 как линейную
rn?2
rn?1
Шаг
.
Шаг 0.
3
{
комбинацию a и b. Очевидно, что xy00 == 10 .
Делим r?1 на r0 с остатком r?1 = r0q0 + r1 и представляем r1 как линейную комбинацию a и b: r1 = a · 1 + b(?q0).
Для вычисления значений линейных коэффициентов xi и yi
на i-м шаге достаточно иметь линейные коэффициенты на двух
предыдущих шагах.
Преобразования продолжаем до тех пор, пока rn ?= 0.
Выведем рекуррентные формулы для линейных коэффициентов
Шаг 1.
ri = axi + byi = ri?2 ? ri?1 qi?1 = (axi?2 + byi?2 ) ? (axi?1 +
byi?1 )qi?1 = a(xi?2 ? xi?1 qi?1 ) + b(yi?2 ? yi?1 qi?1 )
.
Итак, при начальных условиях
?
x?1 = 1
?
?
?
выполняем
y?1 = 0
?
x =0
?
? 0
y0 = 1
?
? ri = ri?2 ? ri?1 qi?1
?
xi = xi?2 ? xi?1 qi?1 ,
yi = yi?2 ? yi?1 qi?1
пока ri ?= 0.
Как только rn+1 = 0, то последний ненулевой остаток есть
НОД rn = (a, b), а x = xn и y = yn искомые линейные коэффициенты.
2.
Сравнения
Если у двух целых чисел a и b остаток от деления
на число m ? N одинаков, то такие числа называются равноостаточными или сравнимыми по модулю m
Определение.
a ? b (mod m).
4
Два числа будут сравнимы по модулю m тогда
и только тогда, когда (a ? b) ... m.
Доказательство
Пусть a = m·q+r, b = m·p+r. Вычтем из первого выражения
второе: a ? b = m · q + r ? m · p ? r = m(q ? p). Видно, что (a ? b)
... m.
Теорема 2.1.
Свойства сравнений
1. Рефлексивность, симметричность и транзитивность.
a ? a (mod m).
Если a{ ? b (mod m), то b ? a (mod m).
(mod m)
Если ab ?? cb (mod
, то a ? c (mod m).
m)
Доказательство
.
(a ? b) .. m ? a ? b = m · q;
.
(b ? c) .. m ? b ? c = m · p.
Складывая две строки, имеем a ? c = m · (q + p) ? (a ? c) ... m ?
a ? c (mod m).
2. Сравнения можно почленно складывать, вычитать и перемножать.
2.1. Сложение.
{
(mod m)
Если ac ?? db (mod
, то a + c ? b + d (mod m).
m)
Доказательство
a = b + mq;
c = d + mp.
Сложив две строки, получаем a + c = (b + d) + m(q + p). Видно,
что a + c ? b + d (mod m).
5
2.2. Вычитание.
{
(mod m)
Если ac ?? db (mod
, то a ? c ? b ? d (mod m).
m)
Доказательство
a = b + mq;
c = d + mp.
Вычитая из первой строки вторую, имеем a?c = (b?d)+m(q ?p).
Видно, что a ? c ? b ? d (mod m).
2.3. Умножение.
{
(mod m)
Если ac ?? db (mod
, то ac ? bd (mod m).
m)
Доказательство
a = b + mq;
c = d + mp.
Перемножая две строки, получаем ac = (b + mq)(d + mp) = bd +
bmp+dmq +m2 pq = bd+m(bp+dq +mpq). Следовательно, (ac?bd)
... m ? ac ? bd (mod m).
3. В сравнении можно переносить слагаемое из одной части в
другую с заменой знака на противоположный.
Если a + b ? c (mod m), то a ? c ? b (mod m).
Доказательство
a + b ? c (mod m);
b ? b (mod m).
Вычитая вторую строку из первой, имеем a ? c ? b (mod m).
4. Обе части сравнения можно умножить на константу.
Если a ? b (mod m), то ac ? bc (mod m).
6
Доказательство
a ? b (mod m);
c ? c (mod m).
Перемножая эти сравнения, имеем ac ? bc (mod m).
5. Обе части сравнения можно возводить в степень.
Если a ? b (mod m), то an ? bn (mod m).
Доказательство
a ? b (mod m).
Умножив само на себя это сравнение n раз, имеем
, т.е. an ? bn (mod m).
6. Обе части сравнения можно разделить на их общий делитель, если он взаимно прост с модулем.
Если a ? b (mod m), то ac ? cb (mod m),
где c общий делитель a и b, (m, c) = 1.
Доказательство
?
Из a = a c и b = b?c имеем
a · a · a . . . · a ? b · b · b . . . · b (mod m)
a? c ? b? c (mod m);
a? c ? b? c = m · q;
... , но m не может делиться на c, так как (m, c) = 1
(a? ? b? )c = mq c
... :
?q c
a? ? b? = mq ? ,
где q? = qc ;
a? ? b?
(mod m);
a
b
?
c
c
(mod m).
7
ту.
7. Обе части сравнения и модуль можно умножить на констанЕсли a ? b
, то ac ? bc (mod mc).
Доказательство
(mod m)
a ? b = mq;
c(a ? b) = c · m · q;
ac ? bc = (mc)q;
ac ? bc (mod mc).
8. Обе части сравнения и модуль можно разделить на их общий
делитель.
(
)
Если a ? b (mod m), то ac ? cb mod mc ,
где c общий делитель a, b, m.
Доказательство
Так как c общий делитель a, b, m, то a = a?c, b = b?c, m =
m? c.
a? c ? b? c = m? cq;
a? ? b? = m? q;
a? ? b?
b
a
?
c
c
(mod m? );
(
mod
m)
.
c
9. Если сравнение выполняется по модулю m, то оно будет
выполняться по любому делителю этого
модуля.
(
)
Если a ? b (mod m), то a ? b mod mc ,
где c делитель m.
Доказательство
a ? b = m · q.
8
Умножим и разделим левую часть равенства на делитель c:
a?b=c
a?b
a?b
(
m
q;
c
... m ;
c
mod
m)
.
c
10. Если одна часть сравнения и модуль делятся на некоторое
число, то и другая часть сравнения делится на то же число.
Если a ? b (mod m), a ... c и m ... c, то b ... c.
Доказательство
a ? b = m · q.
Так как a ... c и m ... c, то и b ... c.
11. Если выполняется система сравнений
?
a?b
?
?
?
(mod m1 )
a ? b (mod m2 )
,
?
···
?
?
a ? b (mod mk )
то a ? b
(mod M ),
где M = [m1, m2, . . . , mn].
Доказательство
Рассмотрим систему из двух сравнений
{
Пусть
(m?1 , m?2 )
a ? b (mod m1 )
.
a ? b (mod m2 )
,
, где d
. Переписывая систему, имеем
m1 = m?1 d m2 = m?2 d
=1
{
a ? b = m1 q1 = m?1 dq1
;
a ? b = m2 q2 = m?2 dq2
9
, причем
= (m1 , m2 )
m?1 q1 = m?2 q2 ;
...
m?1 q1 m?2 ;
q1 = m?2 q3 ;
a ? b = m?1 dm?2 q3 ;
a ? b (mod m?1 m?2 d);
a ? b (mod M ),
где M = [m1, m2] = m?1m?2d.
Аналогичным образом доказывается система с произвольным
числом сравнений.
3.
Полная система вычетов
Все числа, имеющие одинаковый остаток при делении на некоторое число m, образуют класс чисел по модулю m.
Пусть m = 5, тогда
. . . , ?9, ?4, 1, 6, 11, . . . класс чисел по модулю 5;
. . . , ?8, ?3, 2, 7, 12, . . . класс чисел по модулю 5;
. . . , ?7, ?2, 3, 8, 13, . . . класс чисел по модулю 5;
. . . , ?6, ?1, 4, 9, 14, . . . класс чисел по модулю 5;
. . . , ?10, ?5, 0, 5, 10, . . . класс чисел по модулю 5.
Общий вид класса чисел {mq + r | q ? Z}. Все числа из
класса сравнимы по mod m. Всего имеется m классов чисел по
mod m.
Любое число из класса чисел называется вычетом по модулю m.
Наименьший неотрицательный вычет наименьшее неотрицательное число, находящееся в данном классе
чисел.
Определение.
Пример.
Определение.
Определение.
10
Полной системой вычетов по некоторому модулю
называется система чисел, взятых по одному из каждого класса
по этому модулю.
Например, {6, 12, 3, ?1, ?5} образуют полную систему вычетов по mod 5. Каждое из множеств {0, 1, 2, 3, 4}; {?4, ?3, ?2,
?1, 0}; {?2, ?1, 0, 1, 2} также образует полную систему вычетов
по mod 5.
Любые m чисел, попарно несравнимые по модулю m, образуют полную систему вычетов по модулю m.
Доказательство
Если a ?? b (mod m), то числа a и b принадлежат разным
классам. Если m чисел попарно несравнимы между собой, то все
они принадлежат разным классам. Так как всего имеется ровно
m классов, то в каждый класс попадет по одному числу.
Если (a, m) = 1 и x пробегает полную систему вычетов по модулю m, то ax + b, где b любое целое, тоже
пробегает полную систему вычетов.
Доказательство
Докажем, что все m вычетов вида ax + b лежат в разных классах чисел и, следовательно, пробегают полную систему вычетов.
Пусть имеется два вычета, лежащие в одном классе:
Определение.
Теорема 3.1.
Теорема 3.2.
ax1 + b ? ax2 + b (mod m);
ax1 ? ax2
(mod m).
Тогда, учитывая (a, m) = 1, по свойству сравнений 6:
x1 ? x2
(mod m).
Последнее невозможно, так как x1 и x2 лежат в разных классах.
Следовательно, ax + b пробегает полную систему вычетов.
x ? {6, 7, ?2, ?1, 0} пробегает полную систему вычетов по модулю 5, тогда (3x+2) ? {20, 23, ?4, ?1, 2} тоже пробегает
полную систему вычетов по модулю 5.
Пример.
11
4.
Функция Эйлера
Функцией Эйлера от натурального числа m называется число натуральных чисел, не превышающих m и взаимно простых с ним.
Обозначение: ?(m) функция Эйлера от m ? N .
Рассмотрим следующую таблицу.
Определение.
m
?(m)
{a | (a, m) = 1, a ? m}
1
1 1
2
1 1
3
2 1, 2
4
2 1, 3
5
4 1, 2, 3, 4
6
2 1, 5
7
6 1, 2, 3, 4, 5, 6
8
4 1, 3, 5, 7
9
6 1, 2, 4, 5, 7, 8
10
4 1, 3, 7, 9
11
10 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
12
4 1, 5, 7, 11
Из таблицы видно, что ?(10) = 4. Это означает, что с числом
10 взаимно просты четыре числа, не превышающие его самого, это 1, 3, 7 и 9.
Пусть p простое число, ? ? N , тогда
Теорема 4.1.
?(p? ) = p??1 (p ? 1).
Доказательство
Если число не делится на p, то оно взаимно?просто с p?. Всего
чисел, меньших p? и делящихся на p, ровно pp . Тогда чисел, не
?
делящихся на p, ровно p? ? pp = p? ? p??1 = p??1(p ? 1).
12
Рассмотрим примеры ?(9) = ?(32) = 31(3 ? 1) = 6; ?(8) =
= 22 (2 ? 1) = 4.
Функция f (n), n ? N называется мультипликативной, если
{
?(23 )
Определение.
f (ab) = f (a) · f (b)
.
(a, b) = 1
Пусть f (n) = n?, где ? ? N . Тогда f (ab) = (ab)? =
= f (a) · f (b), т.е. рассмотренная функция мультипликативна.
Функция Эйлера мультипликативна.
Пример.
a? b?
Теорема 4.2.
{
?(ab) = ?(a) · ?(b)
.
(a, b) = 1
Доказательство
Составим таблицу из a Ч b чисел от 1 до ab.
1
b+1
2b + 1
...
(a ? 1)b + 1
2
b+2
2b + 2
...
(a ? 1)b + 2
3
b+3
2b + 3
...
(a ? 1)b + 3
...
...
...
...
...
b
b+b
2b + b
...
ab
Строка таблицы с номером i ? [0, a ? 1] имеет вид
ib + 1 ib + 2 ib + 3
···
ib + b.
Общий вид элемента в строке: ib + r, где r ? [1, b]. Число ib + r
взаимно просто с b тогда и только тогда, когда r взаимно просто
с b: (ib + r, b) = 1 ? (r, b) = 1. Во множестве [1, b] имеется
?(b) чисел, взаимно простых с b. Следовательно, в каждой строке
имеется ровно ?(b) чисел, взаимно простых с b.
Рассмотрим столбец с номером i ? [1, b]
13
b
2b
+
+
i
i
i
+
i
...
.
Общий вид элемента в столбце: jb + i, где j ? [0, a ? 1]. Так как
j пробегает полную систему вычетов по mod a, то по теореме 3.2
множество {jb + i} тоже будет пробегать полную систему вычетов по mod a. То есть в каждом столбце содержится ?(a) чисел,
взаимно простых с a.
Число будет взаимно просто с ab, если оно взаимно просто и с
a и с b. Из рассуждений, приведенных выше, видно, что в таблице
имеется ?(a) · ?(b) чисел, взаимно простых с ab. Но, с другой
стороны, их будет ?(ab) (по определению функции Эйлера). Ч.т.д.
Если m = p1? · p2? · . . . · ps? каноническая
форма числа m, то
(a ? 1)b
1
Теорема 4.3.
s
2
?(m) = p1 ?1 ?1 · p2 ?2 ?1 · . . . · ps ?s ?1 · (p1 ? 1) · (p2 ? 1) · . . . · (ps ? 1).
Доказательство
По теореме 4.2 ?(m) = ?(p1? · p2? · . . . · ps? ) = ?(p1? ) ·
?(p2 ? ) · . . . · ?(ps ? ), а по теореме 4.1 ?(pi ? ) = pi ? ?1 (pi ? 1).
Тогда ?(m) = p1? ?1(p1 ? 1) · p2? ?1(p2 ? 1) · . . . · ps? ?1(ps ? 1).
Рассмотрим пример: ?(12) = ?(22 · 31) = ?(22) · ?(31) = 21(2 ?
1
s
2
s
2
1
i
1
i
s
2
1) · 30 (3 ? 1) = 2 · 2 = 4.
Теорема 4.4.
Для любого m > 1
?(m) = m
где
?
p|m
?(
p|m
1?
1)
,
p
произведение по всем простым делителям числа m.
14
Доказательство
Непосредственной проверкой убеждаемся:
?(m) = m
?(
p|m
(
Ч 1?
(
= p 1 ?1 1 ?
1?
1)
= p1 ?1 · p2 ?2 · . . . · ps ?s Ч
p
(
1 )(
1)
1)
1?
· ... · 1 ?
=
p1
p2
ps
(
(
1)
1)
1)
· p 2 ?2 1 ?
· . . . · p s ?s 1 ?
=
p1
p2
ps
= p1 ?1 ?1 (p1 ? 1) · p2 ?2 ?1 (p2 ? 1) · . . . · ps ?s ?1 (ps ? 1).
5.
Приведенная система вычетов
Вычеты из полной системы вычетов по модулю
m, взаимно простые с m, образуют приведенную систему вычетов
по модулю m.
{0, 1, 2, 3, 4, 5} полная система вычетов по модулю 6. {1, 5} приведенная система вычетов по модулю 6. Числа
{13, ?1} также образуют приведенную систему вычетов.
Числа a1, a2, ... ,a?(m) образуют приведенную
систему вычетов по модулю m тогда и только тогда, когда они все
попарно несравнимы по модулю m и (ai, m) = 1.
Доказательство
Если ai и aj попарно несравнимы, то они лежат в разных классах чисел, а так как таких чисел ровно ?(m), то они образуют
приведенную систему вычетов.
Определение.
Пример.
Теорема 5.1.
15
Если (a, m) = 1 и x пробегает приведенную
систему вычетов по модулю m, то ax тоже пробегает приведенную
систему вычетов.
Доказательство
Чисел ax будет столько же, сколько и чисел x, т.е. ?(m). Из
Теорема 5.2.
{
(a, m) = 1
(x, m) = 1
следует, что (ax, m) = 1. Пусть два вычета лежат в одном классе
axi ? axj (mod m), i ?= j , тогда xi ? xj (mod m). Противоречие.
x ? {1, 5} приведенная система вычетов по модулю 6. Пусть a = 7, тогда ax ? {7, 35} тоже приведенная система
вычетов по модулю 6.
Пример.
Литература
1. Виноградов И. М. Основы теории чисел. М.: Наука, 1965.
2. Бухштаб А. А. Теория чисел. М.: Просвещение, 1966.
3. Акритас А. Основы компьютерной алгебры с приложениями.
М.: Мир, 1994.
16
Документ
Категория
Без категории
Просмотров
1
Размер файла
149 Кб
Теги
fedorenko2
1/--страниц
Пожаловаться на содержимое документа