close

Вход

Забыли?

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

код для вставкиСкачать
ИвГУ, ф-т МиКН, курс 2
"КОМПЬЮТЕРНАЯ АЛГЕБРА"
Тема 2.
Деление с остатком и НОД
в квадратичных кольцах
Лектор: Н. И. Яцкин, 2014
2
Gaussian
Integers
3
CARL FRIEDRICH GAUSS
(1777 - 1855)
4
1803
1828
5
1832
In old age
6
7
Gaussian Integers:
Z[i]={a + b i : a, b  Z}
образуют целостное кольцо (подкольцо в поле С).
(Напомним определение целостного кольца:
из равенства нулю произведения элементов следует,
что хотя бы один из сомножителей равен нулю.)
8
По всякому целостному кольцу конструируется его
поле частных (как "наименьшее из полей", содержащих
данное кольцо). Например, для Z полем частных служит Q.
Полем частных для кольца Z[i] служит поле
рациональных гауссовых чисел:
Q[i]={a + b i : a, b  Q}
9
Кольцо [ ] является евклидовым. Евклидова норма на нем
определяется как квадрат модуля комплексного числа:
2
2
N(a + b i) = a + b .
Евклидова норма – это функция, позволяющая определить
для элементов кольца деление с остатком.
Теорема 1. Для любых двух гауссовых
целых чисел , ∈ [ ] ( ≠ ) найдутся
гауссовы числа , ∈ [ ] такие, что
=
+ и ( ) < ( ).
Благодаря наличию евклидовой нормы, в кольце работает
алгоритм Евклида отыскания НОД.
10
Группа обратимых гауссовых чисел состоит из четырех
"единиц": 1, i, -1, -i (имеющих единичную норму).
(Напомним определение отношения ассоциированности:
два элемента ассоциированы, если они отличаются обратимым
множителем.)
Ненулевые элементы кольца [ ] группируются в четверки
по отношению ассоциированности.
Все это можно наблюдать на следующем (полученном с
помощью Maple) рисунке.
11
Решетка целых чисел Гаусса
Обратимые элементы: ± , ± .
12
Далее следует алгоритмическая часть темы. Необходимо,
прежде всего, научиться (средствами CAS):
- делить с остатком одно гауссово целое число на другое;
- вычислять НОД двух гауссовых чисел.
13
1. Задача.
(1) Познакомиться с командой (функцией) round округления
действительного числа до ближайшего целого числа; полуцелые числа
округляются в сторону прочь от нуля:
> round(2.5),round(-2,5);
3, -3
Убедиться в том, что эта команда работает в поле комплексных
чисел, по отдельности применяется к действительной и мнимой частям:
> round(-2.5+3.4*I);
-3+3I.
Внимание: системным обозначением мнимой единицы i является I.
См. также другие команды округления: floor ("пол", целая часть
числа) и ceil ("потолок").
14
(2) Написать функцию GIQUOREM деления с остатком в кольце
Г=Z[i] целых гауссовых чисел, полагая, что неполное частное двух
целых гауссовых чисел получается с помощью функции round из
обычного частного (являющегося рациональным гауссовым числом).
Подсматривать в код IQUOREM не придется. Здесь у нас задача
проще, поскольку разрешено использование функции округления.
(3) Написать процедуру CNORM вычисляющую норму (квадрат
модуля) комплексного числа. Эта функция может быть использована
в числовых примерах: норма остатка должна быть строго меньше
нормы делителя.
(4) Написать процедуру GIGCDEX, реализующую расширенный
алгоритм Евклида в кольце Г=Z[i].
15
(1) Округление комплексного числа до целого гауссова числа,
действительная и мнимая части которого являются ближайшими
целыми числами к действительной и мнимой частям данного числа.
Числовой пример.
Округлите вручную число:
−
+
.
16
Применим функцию round.
> CROUND(-75/17+I*135/11);
-412 I
17
(2) Сочиняем процедуру, вычисляющую норму (квадрата модуля)
комплексного числа.
> CNORM:=proc(z::complex)
Продолжим!
18
Код.
> CNORM:=proc(z::complex)
RETURN((Re(z))^2+(Im(z))^2);
end proc;
CNORM := proc (z::complex ) RETURN( ( z )^2( z )^2 ) end proc
19
(3) Деление с остатком в кольце целых гауссовых чисел.
> GIQUOREM:=proc(a::complex,b::complex)
local q,r;
Продолжим!
20
Код.
> GIQUOREM:=proc(a::complex,b::complex)
local q,r;
q:=round(a/b);r:=a-b*q;
RETURN(q,r);
end proc;
21
Числовой пример.
Поделите вручную число - 50 + 167 i с остатком
на число 77 – 15 i.Сравните нормы данных чисел,
неполного частного и остатка.
22
Числовой пример.
Применим процедуру GIQUOREM.
> a:=-50+167*I;b:=77-15*I;
q,r:=GIQUOREM(a,b);
a := -50167 I
b := 7715 I
q, r := -12 I, -32 I
23
Проверим неравенство:
( )<
( ).
> map(CNORM,[a,b,r]);
evalb(CNORM(r)<CNORM(b));
[ 30389, 6154, 13 ]
true
24
(4) Расширенный алгоритм Евклида (только префиксом,
GI вместо I, в именах отличается от аналогичной процедуры
в кольце целых чисел).
> GIGCDEX:=proc(a::complex,b::complex)
local r,q,u,v;
25
> GIGCDEX:=proc(a::complex,b::complex)
local r,q,u,v;
r[0],r[1]:=b,a;
# print(evaln(r[0])=r[0],evaln(r[1])=r[1]);
u[0],u[1]:=0,1;
# print(evaln(u[0])=u[0],evaln(u[1])=u[1]);
v[0],v[1]:=1,0;
# print(evaln(v[0])=v[0],evaln(v[1])=v[1]);
while r[1]<>0 do
q:=GIQUOREM(r[0],r[1])[1];
# print(evaln(q)=q);
r[0],r[1]:=r[1],r[0]-r[1]*q;
# print(evaln(r[0])=r[0],evaln(r[1])=r[1]);
u[0],u[1]:=u[1],u[0]-u[1]*q;
# print(evaln(u[0])=u[0],evaln(u[1])=u[1]);
v[0],v[1]:=v[1],v[0]-v[1]*q;
# print(evaln(v[0])=v[0],evaln(v[1])=v[1]);
end do;
RETURN(r[0],[u[0],v[0]],[u[1],v[1]]);
end proc;
26
GIGCDEX := proc (a::complex , b::complex )
local r , q, u, v;
r [ 0 ], r [ 1 ] := b, a;
u[ 0 ], u[ 1 ] := 0, 1;
v[ 0 ], v[ 1 ] := 1, 0;
while r [ 1 ]0 do
q := GIQUOREM( r [ 0 ], r [ 1 ] )[ 1 ] ;
r [ 0 ], r[ 1 ] := r [ 1 ], r [ 0 ]r[ 1 ]q;
u[ 0 ], u[ 1 ] := u[ 1 ], u[ 0 ]u[ 1 ]q;
v[ 0 ], v[ 1 ] := v [ 1 ], v[ 0 ]v[ 1 ]q
end do ;
RETURN( r [ 0 ], [ u[ 0 ], v[ 0 ] ], [ u[ 1 ], v[ 1 ] ] )
end proc
27
Числовой пример 1 (с раскомментированными принтами).
> a,b:=342+2*I,-6+30*I;
d,K,L:=GIGCDEX(a,b);
a, b := 3422 I, -630 I
r0-630 I, r13422 I
u00, u11
v01, v10
q0
r03422 I, r1-630 I
u01, u10
v00, v11
28
q-211 I
r0-630 I, r1-4 I
u00, u11
v01, v1211 I
q-82 I
r0-4 I, r122 I
u01, u182 I
v0211 I, v1-592 I
29
q1I
r022 I, r10
u082 I, u1-96 I
v0-592 I, v1-8586 I
d, K, L := 22 I, [ 82 I, -592 I ], [ -9 6 I, -85 86 I ]
30
Явный вывод u,v,s,t:
> u,v:=K[];s,t:=L[];
u, v := 82 I, -592 I
s, t := -96 I, -8586 I
Проверка:
> evalb(d=a*u+b*v);evalb(0=a*s+b*t);
true
true
> (342+2*I)*(8+2*I)+(-6+30*I)*(-5+92*I);
22 I
31
Числовой пример 2 (для ручного решения).
a = - 5 + 2 i; b = 3 + i; d, u, v, s, t = ?
32
Сверим ответы с GIGCDEX:
> a:=-5+2*I;b:=3+I;d,K,L:=GIGCDEX(a,b);
a := -52 I
b := 3I
r 0 3I, r 1-5 2 I
u00, u11
v01, v10
q0
r 0-5 2 I, r 13I
u01, u10
v 00, v 1 1
33
q-1I
r 03I, r 1-1
u00, u11
v01, v11I
q-3I
r 0-1 , r 10
u01, u13I
v01I, v 152 I
d, K, L := -1, [ 1, 1I ], [ 3I, 52 I ]
34
Имеются стандартные версии рассмотренных выше процедур.
Они содержатся в специализированном пакете GaussInt;
обратите внимание на стиль вызова функций из пакета.
Если с помощью команды with(GaussInt) пакет предварительно
подгрузить, то эти функции можно будет вызывать непосредственно,
по именам, без указания имени пакета.
> with(GaussInt);
[ GIbasis, GIchrem , GIdivisor , GIfacpoly , GIfacset , GIfactor , GIfactors , GIgcd ,
GIgcdex , GIhermite , GIissqr , GIlcm , GImcmbine , GImod , GInearest , GInodiv ,
GInorm , GInormal , GIorder , GIphi , GIprime , GIquadres , GIquo , GIrem , GIroots ,
GIsieve , GIsmith , GIsqrfree , GIsqrt , GIunitnormal ]
35
Обратите внимание также на иной принцип организации
возврата результатов работы процедуры: по умолчанию возвращается
только значение НОД; для коэффициентов же линейного
представления, u и v, только лишь резервируются имена, которые
указываются (в апострофах) в качестве третьего и четвертого
аргументов функции; значения этих коэффициентов
надо запрашивать отдельно.
> d:=GaussInt[GIgcdex](a,b,'u','v');
u;v; evalb(d=a*u+b*v);
d := 22 I
17 I
794 I
true
36
В чем дело?
Почему результаты получились другими?
Поделим второй ответ (полученный с помощью специализированного
пакета) на первый ответ (наш):
> (2+2*I)/(2-2*I);
I
Получилось одно из четырех обратимых гауссовых чисел,
т. е. один из элементов группы (Z[i])*={1, i, -1, -i},
т. е. два наших ответа ассоциированы.
37
Оба ответа - правильные, поскольку НОД определен лишь
с точностью до ассоциированности.
Эту неоднозначность можно при желании устранить,
систематически заменяя результаты работы процедур на
ассоциированные числа из первого квадранта,
т. е. из подмножества { = + ∶ > , ≥ }.
Что касается коэффициентов линейного представления, u и v,
то они определены в гораздо большей степени неоднозначно.
38
Eisenstein
Integers
39
Требуется "опознать" человека.
40
Эйзенштейн. Но не тот,
не математик…
41
Ferdinand Gotthold Max Eisenstein
(1823 – 1852)
42
Eisenstein Integers:
Z[]={a + b  : a, b  Z}
=
=
− + √
Образуют евклидово кольцо с нормой:
N(a + b ) = a – a b + b .
2
2
43
Такая формула для нормы получается если вычислить квадрат
модуля комплексного числа = +
∈ [ ]:
( )=
=
+
(
− + √
− ) +
−
=
=
−
+
+
√
,
т. е. фактически используется та же функция, что и в кольце
гауссовых чисел.
44
Справедлива
Теорема 2. Для любых двух целых
чисел Эйзенштейна , ∈ [ ] ( ≠ )
найдутся числа Эйзенштейна , ∈ [ ]
такие, что =
+ и ( ) < ( ).
Определено деление с остатком и работает алгоритм
Евклида.
45
Группа обратимых элементов кольца [ ] состоит из шести
чисел (имеющих единичную норму):
∗
( [ ]) =
, 6=−
,
2
6
=
,
3
6
= −1,
4
6
=
,
Множество ненулевых элементов [ ] разбивается
отношением ассоциированности на шестерки вида:
∙
.
Наблюдаем все эти явления на Maple-рисунке.
5
6
=−
.
46
Решетка чисел Эйзенштейна
Обратимые элементы: ± , ± , ±
.
47
2. Задача. Повторить всю работу, проделанную в задаче 1,
применительно к кольцу целых чисел Эйзенштейна Z[].
48
Pell
Integers
49
John Pell (1611-1685).
50
Pell Integers:
Для положительного бесквадратного целого числа d
( ≡ или ) определено кольцо целых чисел
Пелля:
Z[√ ]={a + b√ : a, b  Z}
Для некоторых значений d оно является евклидовым.
Например, для d=2, евклидовой нормой в кольце Z[√ ]
является
+ √
=|
.
−
|
51
Замечание. Для
≡ числа Пелля определяются
несколько иначе:
=
где
√
,
и – целые числа одинаковой четности.
Чтобы понять причины такого "разнобоя" в определениях,
надо учесть "правильное" определение целого элемента
в числовом кольце.
(*)
52
Целым элементом называется корень нормализованного
(старший коэффициент = 1) многочлена с целыми (в обычном
смысле) коэффициентами.
Убедимся в том, что (при =
+ и = + ) числа
вида (*) являются корнями приведенного (нормализованного)
квадратного трехчлена с целыми (в обычном смысле)
коэффициентами:
+ √
− √
−
−
=
−
+ ,
где
=
−
- целое число.
=
( +
) −(
+ )
=
+
−
53
В кольцах целых чисел Пелля бесконечно много "единиц"
(обратимых элементов); они являются решениями
уравнений Пелля
−
=±
(подробности см. в литературе и в интернете).
Числа Пелля, в отличие от чисел Гаусса и Эйзенштейна, являются
действительными и представление их совокупности точками на
обычной комплексной плоскости невозможно. Тем не менее, при
изучении последующих тем, мы покажем плоские изображения
для чисел Пелля, но это будет уже не обычная, но, так называемая,
гиперболическая комплексная плоскость.
Подчеркнем, что и евклидова норма
+ √ =| −
|
в данном случае определяется совсем иначе, нежели в первых двух
примерах, хотя Теорема 3 (сформулируйте ее, по аналогии
с теоремами 1 и 2) остается справедливой.
54
3. Задача. Повторить всю работу, проделанную в задаче 1,
применительно к кольцу целых чисел Пелля Z[√ ].
(Если не пользоваться встроенными процедурами
упрощения иррациональных выражений, то потребуется
представлять числа Пелля (целые и рациональные)
списками вида [ , ], с перезаписью на этом языке всех
арифметических действий.)
55
Необходимы следующие процедуры:
(1) PROUND (покомпонентное округление
рационального числа Пелля до целого);
(2) PQUOREM (деление с остатком в кольце Z[√ ]);
(3) PNORM (вычисление нормы в кольце Z[√ ]
или в поле Q[√ ]);
(4) PGCDEX (расширенный алгоритм Евклида в Z[√ ].
56
1/--страниц
Пожаловаться на содержимое документа