Алгебра в программе Mathematica

             

Пример 3



Пример 3



, является числом того же вида, причем количество цифр я-1 в нем равно d= НОД(n, m). Выясним, как наибольший общий делитель чисел аn -1 и аm -1 представляется в виде их линейной комбинации.

Вот нужные нам определения.

ааа[а_,n_]:=аАп-1; d:= GCD[n, m]

Теперь можно написать и программу. Нужно только не забыть о том, что представление r и s лучше всего получить в системе счисления с основанием я. Для этого вполне подойдет функция IntegerDigits. Она, правда, теряет знак числа, так что его придется печатать отдельно.
Do[ Dot Dot {{g,(r,s}}= ExtendedGCD[aaa[a,n],aaa[a,m]], Print["###", n, ":",m,":",d,":",a,":"], If[g<0,Print["-"]], Print[IntegerDigits[g,a], ":"], If[r<0,Print!"-"]], Print[IntegerDigits[r,a], ":"], If [s<0,Print["-"]], Print[IntegerDigits[s,a]]} , {a,2,n+m+2}],{m,n-l}],{n,10}]
Заметьте, что в программе вставлена печать fit для удобства форматирования результатов.

Скажу сразу, что более скучной таблицы я, наверное, никогда не видел! И все из-за удивительного постоянства г и s! Представление r и s выглядит одинаково в системах счисления с разными основаниями, и потому их представления просто повторяются во многих строках! Это значит, что представление наибольшего общего делителя действительно основано на полиномиальных тождествах вида d(x) = r(x)a(x)+s(x)b(x), причем полиномы r(х) и s(x) легко восстанавливаются по числам r и s! Конечно, я избавлю вас от демонстрации всего этого и просто приведу некоторые наиболее характерные строки таблицы. Разумеется, большинство строк an опустил, и таблица содержит пропуски. Они обозначены строками с многоточиями. Чтобы развеять сомнения, достаточно взглянуть вот на это.

Линейное представление наибольшего общего делителя чисел аn - 1 и аm -1:

НОД= r-(an-l) + s-(am-l)


n
m
d= НОД (n, m)
Основание системы счисления а
Цифры НОД в системе счисления с основанием а
Цифры r в системе счисления с основанием а
Цифры s в системе счисления с основанием а

2
1
1
2
(1)
{0}
{1}

2
1
1
3
{2}
{0}
(1)

2
1
1
4
{3}
{0}
{1}

2
1
1
5
Н)
{0}
(1)

3
1
1
2
{1}
{0}
{1}

3
1
1
3
{2}
{0}
{1}

3
1
1
4
{3}
{0}
{1}

3
1
1
5
{4}
{0}
(1)

3
1
1
6
(5)
{0}
{1}

3
2
1
2
(1)
{1}
-{1,0}

3
г
1
3
(2}
{1}
-{1,0}

3
2
1
4
(3)
{1}
-{1,0}

3
2
1
5
(4}
{1}
-{1,0}

3.
2
1
6
(5)
{1}
-{1,0}

3
2
1
7
(6)
{1}
-{1,0}

4
1
1
2
(1}
{0}
{1}

4
1
1
3
{2}
{0}
{1}

4
1
1
4
(3)
{0}
{1}

4
1
1
5
(4)
{0}
{1}

4
1
1
6
{5}
(0)
{1}

4
1
1
7
{6}
{0}
{1}

4
2
2
2
{1,1}
{0}
{1}

4
2
2
3
(2,2)
{0}
{1}

4
2
2
4
(3,3)
{0}
{1}

4
2
2
5 '
{4,4}
{0}
{1}

4
2
2
6
{5,5}
{0}
{1}

4
2
2
7
{6,6}
{0}
{1}

4
2
2
8
(7,7}
{0}
{1}

4
3
1
2
{1}
{1}
-{1,0.}

4
3
1
3
{2}
{1}
-{1,0}

4
3
1
4
{3}
{1}
-{1,0}

4
3
1
5
{4}
{1}
-{1,0}

4
3
1
6
{5}
{1}
-{1,0}

4
3
1
7
{6}
{1}
-{1,0}

4
3
1
8
{7}
{1}
-{1,0}

4
3
1
9
(81
(1)
-{1,0}
&nbsp &nbsp &nbsp .. &nbsp ... &nbsp ... ...&nbsp &nbsp ...

5
2
1
2
{1}
{1}
-{1,0,1,0}

5
2
1
3
(2)
{1}
-{1,0,1,0}

5
2
1
4
(3}
{1}
-{1,0,1,0}

5
2
1
5
(4)
{1}
-{1,0,1,0}

5
2
1
6
{5}
{1}
-{1,0,1,0}

5
2
1
7
{6}
{1}
-{1,0,1,0}

5
2
1
8
{7}
{1}
-{1,0,1,0}

5
2
1
9
(8)
{1}
-{1,0,1,0}

5
3
1
2
(1)
-{1,0}
{1,0,0,1}

5
3
1
3
{2}
-{1,0}
{1,0,0,1}

5
3
1
4
(3}
-{1,0}
{1,0,0,1}

5
3
1
5
{4}
-{1,0}
{1,0,0,1}

5
3
1
6
{5}
-{1,0}
{1,0,0,1}

5
3
1
7
{6}
-{1,0}
{1,0,0,1}

5
3
1
8
{7}
-{1,0}
{1,0,0,1}

5
3
1
9
(8)
-{1,0}
{1,0,0,1}

5
3
1
10
{9}
-{1,0}
{1,0,0,1}

5
4
1
2
{1}
{1}
-{1,0}

5
4
1
3
{2}
{1}
-{1,0}

5
4
1
4
(3)
{1}
-{1,0}

5
4
1
5
{4}
{1}
-{1,0}

5
4
1
6
(5}
{1}
-{1,0}

5
4
1
7
{6)
{1}
-{1,0}

5
4
1
8
{1}
{1}
-{1,0}

5
4
1
9
{8}
{1}
-{1,0}

5
4
1
10
{9}
{1}
-{1,0}

5
4
1
11
{10}
{1}
-{1,0}

...
 &nbsp &nbsp ... &nbsp ...
...
 &nbsp ... &nbsp ...

7
2
1
2
{1}
11}
-{1,0,1,0,1,0}

7
2
1
3
(2)
{1}
-{1,0,1,0,1,0}

7
2
1
4
{3}
{1}
-{1,0,1,0,1,0}

7
2
1
5
{4}
{1}
-{1,0,1,0,1,0}

7
2
1
6
{5}
{1}
-{1,0,1,0,1,0}

7
2
1
7
{6}
{1}
-{1,0,1,0,1,0}

7
2
1
8
(7)
(1)
-{1,0,1,0,1,0}

7
2
1
9
{8)
{1}
-{1,0,1,0, 1,0}

7
2
1
10
{9}
{1}
-{1,0,1,0,1,0}

7
2
1
11
{10}
{1}
-{1,0,1,0,1,0}

7
3
1
2
{1}
{1}
-{1,0,0,1,0}

7
3
1
3
{2}
(1)
-{1,0,0,1,0}

7
3
1
4
{3}
{1}
-{1,0,0,1,0}

7
3
1
5
{4}
{1}
-{1,0,0,1,0}

7
3
1 i
6
{5}
{1}
-{1,0,0,1,0}

7
3
1
7
{5}
{1}

-{1,0,0, 1,0}

7
3

1
8
{8}
{1}
-{1,0,0,1,0}

7
3
1
9
{8}
{1}
-{1,0,0,1,0}

7
3
1
10
{9}
(1)
-{1,0,0,1,0}

7
3
1
11
{10}
{1}
-{1,0,0,1,0}

7
3
1
12
{11}
{1}
-{1,0,0,1,0}

7
4
1
2
{1}
-{1,0}
{1,0,0,0,1}

7
4
1
3
{2}
-{1,0}
{1,0,0,0,1}

7
4
1
4
{3}
-{1,0}
{1,0,0,0,1}

7
4
1
5
{4}
-{1,0}
{1,0,0,0,1}

7
4
1
6
{5}
-{1,0}
{1,0,0,0,1}

7
4
1
7
{6}
-{1,0}
{1,0,0,0,1}

7
4
1
8
{7}
-{1,0}
{1,0,0,0,1}

7
4
1
9
{8}
-{1,0}
{1,0,0,0,1}

7
4
1
10
{9}
-{1,0}
{1,0,0,0,1}

7
4
1
11
{10}
-{1,0}
{1,0,0,0,1}

7
4
1
12
{11}
-{1,0}
{1,0,0,0,1}

7
4
1
13
{12}
-{1,0}
{1,0,0,0,1}

7
5
1
2
{1}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
3
{2}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
4
{3}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
5
{4}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
6
{5}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
7
{6}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
8
{1}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
9
{8}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
10
{9}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
11
{10}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
12
(11)
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
13
{12}
-{1,0,1,0}
{1,0,1,0,0,1}

7
5
1
14
{13}
-{1,0,1,0}
{1,0,1,0,0,1}
&nbsp &nbsp &nbsp ... &nbsp ... &nbsp ...
...
 &nbsp ...

8
3
1
2
{1}
-{1,0}
{1,0,0,1,0,0,1}

8
3
1
3
{2}
-{1,0}
{1,0,0,1,0,0,1}

8
3
1
4
{3}
-{1,0}
{1,0,0,1,0,0,1}

8
3
1
5
{4}
-{1,0-}
{1,0,0,1,0,0,1}

8
3
1
6
{5}
-{1,0}
{1,0,0,1,0,0,1}

8
3
1
7
{6}
-{1,0}
{1,0,0,1,0,0,1}

8
3
1
8
{7}
-{1,0}
{1,0,0,1,0,0,1}

8
3
1
9
{8}
-{1,0}
{1,0,0,1,0,0,1}

8
3
1
10
{9}
-{1,0}
{1,0,0,1,0,0,1}

8
3
1
11
{10}
-{1,0}
{1,0,0,1,0,0,1}

8
3
1
12
{11}
-{1,0}
{1,0,0,1,0,0,1}

8
3
1
13
{12}
-{1,0}
{1,0,0,1,0,0,1}
&nbsp
...
 &nbsp ... &nbsp ... &nbsp ... &nbsp ... &nbsp ...

8
5
1
2
{1}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
3
(2).
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
4
{3}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
5
{4}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
6
(5}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
7
{6}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
8
{7}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
9
{8}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
10
{9}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
11
{10}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
12
(И)
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
13
{12}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
14
{13}
{1,0,0,1}
-{1,0,0,1,0,1,0}

8
5
1
15
{14}
{1,0,0,1}
-(1,0,0,1,0,1,0)
&nbsp
...
 &nbsp ... &nbsp ... &nbsp ...
...
 &nbsp ...

10
6
2
2
(1,1)
-{1,0,0}
{1,0,0,0,0,0,1}

10
6
2
3
{2,2}
-{1,0,0}
{1,0,0,0,0,0,1}

10
6
2
4
{3,3}
-{1,0,0}
{1,0,0,0,0,0,1}

10
6
2
5
{4,4}
-{1,0,0}
{1,0,0,0,0,0,1}

10
6
2
6
{5,5}
-{1,0,0}
{1,0,0,0,0,0,1}

10
6
2
7
{6,6}
-{1,0,0}
{1,0,0,0,0,0,1}

id
6
2
8
(7,7)
-(1,0,0)
(1,0,0,0,0,0,1)

10
6
2
9
(8,8}
-(1,0,0)
(1,0,0,0,0,0,1)

10
6
2
10
(9,9)
-(1,0,0)
(1,0,0,0,0,0,1)

10
6
2
11
(10,10}
-(1,0,0)
(1,0,0,0,0,0,1)

10
6
2
12
(11,11}
-(1,0,0)
(1,0,0,0,0,0,1)

10
6
2
13
(12,12}
-(1,0,0)
(1,0,0,0,0,0,1)

10
6
2
14
(13,13}
-(1,0,0)
(1,0,0,0,0,0,1)

10
6
2
15
(14,14}
-(1,0,0)
(1,0,0,0,0,0,1)

10
6
2
16
(15,15}
-(1,0,0)
(1,0,0,0,0,0,1)

10

6
2
17
(16,16)
-(1,0,0)
(1,0,0,0,0,0,1)

10
6
2
18
(17,17)
-(1,0,0)
(1,0,0,0,0,0,1)

10
7
1
2
(1)
-(1,0,0,1,0)
(1,0,0,1,0,0,0,1)

10
1
1
3
(2}
-(1,0,0,1,0)
(1,0,0,1,0,0,0,1)

10
1
1
4
(3}
-(1,0,0,1,0)
(1,0,0,1,0,0,0,1)

10
1
1
5
(4}
-(1,0,0,1,0)
(1,0,0,1,0,0,0,1)

10
1
1
6
(5}
-(1,0,0,1,0)
{1,00, 1,0, 0,0,1}

10
1
1
7
(6}
-(1,0,0,1,0)
{1,0,10,1,0,0,0,1}

10
1
1
8
(7)
-(1,0,0,1,0)
{1,0,:0, 1,0, 0,0,1}

10
7
1
9
(8}
-(1,0,0,1,0)
{1,0,0,1,0,0,0,1}

10
7
1
10
(9)
-{1,0,0,1,0}
(1,0,0,1,0,0,0,1)

10
7
1
11
(10}
-(1,0,0,1,0}
(1,0,0,1,0,0,0,1)

10
7
1
12
(11)
-(1,0,0,1,0)
(1,0,0,1,0,0,0,1)

10
7
1
13
(12)
-(1,0,0,1,0}
(1,0,0,1,0,0,0,1)

10
7
1
14
(13)
-(1,0,0,1,0}
(1,0,0,1,0,0,0,1)

10
7
1
15
(14)
-(1, 0,0,1,0}
(1,0,0,1,0,0,0,1)

10
7
1
16
(15)
-{1, 0,0,1,0}
(1,0,0,1,0,0,-0,1)

10
7
1
17
(16)
-(1,0,0,1,0)
{1,0,0,1,0,0,0,1}

10
7
1
18
(17}
-(1,0,0,1,0)
(1,0,0,1,0,0,0,1}

10
7
1
19
(18}
-(1,0,0,1,0)
(1,0,0,1,0,0,0,1}
&nbsp &nbsp
...
 &nbsp ... &nbsp ... &nbsp ...
...


Честно говоря, возникает желание избавиться от этого назойливого повторения. Как это сделать? Для этого придется переделать программу. Но чтобы программа не была слишком длинной, лучше переписать ее. Прежде всего, к уже имеющимся определениям

ааа[а_,n_]:=аАп-1; d:= GCD[n, m]

добавим еше два для печати.
prnt : = {Print["###",n, ":",m,":",d,":",a,":"], If[g<0,Print["-"]], Print[IntegerDigits[g,a],":"], If[r<0,Print["-"]], Print[IntegerDigits[r,a],":"], If [s<0-. Print ["-"] ] , Print[ IntegerDigits [s, a] ] }; prnt1:={Print["%%%",n,":",m,":",d,":"], If[r<0, Print["-"]], Print[FromDigits!IntegerDigits[r,a],10],":"], If[s<0,Print!"-"]]; Print[FromDigits[IntegerDigits[s,a],10]]);
Основным определением здесь является prntl. Именно это определение используется для первого вывода на печать значений n, m, d = НОД(n, m), а также двоичных представлений rus. Чтобы облегчить распознавание определения, которое выполняет печать, в основном определении (prntl) ведущими символами являются ###, а во вспомогательном (prnt) — %%%. Используя вспомогательное определение prnt, предыдущую программу можно переписать так.
Do[ Do[ Do[{{g,{r,s)}=ExtendedGCD[aaa[a,n],aaa[a,m]], prnt}, {a,2,n+m+2}], {m,n-l}], {n,10}]
Вспомогательное определение prnt будет использоваться для первого вывода на печать только тех представлений г и s, которые отличаются от первого. Поэтому в этом определении предусмотрен вывод дополнительной информации: представления g и основания системы счисления а.

Теперь программу можно модифицировать с учетом нового определения функции печати. Возникает соблазн написать программу так.
Do[ Do[{ Do[{{g,{r,s}}=ExtendedGCD[aaa[a,n],aaa[a,m]], If[a==2,{{g0,{r0,s0}}={g,(r,s)}, prntl}], If[{g0,{r0,s0}}!={g,{r,s}},prnt]},{a,2,n+m+2}]},{m,n-l}],{n,10}]
Но это совсем не то, что мы хотели! Ведь условие {g0, {r0, s0}} ! = {g, {r, s}} будет выполнено при а! =2. Все дело в том, что значения ms зависят от основания системы счисления а\ Не зависит от основания системы счисления а лишь их представление в системе счисления с основанием а. Поэтому проверять нужно именно неизменность представления в системе счисления с основанием а. Кроме того, проверка g0! =n лишняя. Поэтому лучше добавить еще одно определение.
newrs:= { Signfr0], Signts0], IntegerDigits[r0,2], IntegerDigits[s0,2] } != { Sign[r], Sign[s], IntegerDigits[r, a], IntegerDigits[s, a] }
Теперь можно записать программу.
Do[ Do [{ Do[{{g,{r,s}}=ExtendedGCD[aaa[a,n],aaa[a,m]], If[a==2,{ {r0,s0}={r,s}, prntl}], If[newrs,prnt]}, {a,2,n+m+2H }, {m,n-l} ]; {n,20}]
Теперь выполним программу. Сколько раз сработала вспомогательная печать? Ни разу! Это значит, что по всем найденным значениям г и s можно восстановить многочлены г(х) и s(x) и написать тождество d(x) = r(x)a(x)+s(x)b(x)\ Полученные результаты стоят того, чтобы собрать их в таблицу (табл. Б.33).

Полученная таблица заслуживает более внимательного рассмотрения. Рассмотрим, например, одну строку таблицы.


20
17
1
1001001001001001
-1001001001001001010 |


Так как d(x) = xd -I = лс-1, эта строка означает, что х-1 = d(x) = r(x)a(x)+s(x)b(x), где а(х)= JC20-1, 'b(х) = хn-1, r(х) = 1+x3+x6+х9+x12+x15, s(x) =-(х+х3+ х6+x9+х12+ х15+х18). Иными словами, она означает, что х-1 = d(x) =r(х) (х20 -1) +s(x) (хn -1) для указанных только что полиномов г(х) и s(x).

Впрочем, вместо r(x) и s(x) можно подставить их выражения, и тогда получится следующее тождество:

x-1 = (1+х3+x6+x9+x12+x15) (х20-1) -(х+х3 + х6+х9 + х12+х15 +х18) (х17-1).

Таким образом, мы видим, что каждая строка полученной таблицы фактически основана на полиномиальном тождестве и фактически является кратким его кодом!

Давайте теперь сравним полученные значения для г и s в равенстве НОД(a, b) = ra+sb для а = хn-1 -1, b= хm+1 -1 (х целое) с теми, которые были получены ранее для такого же равенства для чисел а и b, десятичная запись которых состоит из т единиц и n единиц. (Нужную таблицу мы подготовили заранее.) Не случайно ли значения г и s совпадают? Нет, не случайно. Дело в том, что если справедливо равенство НОД(а,- b) = ra+sb для а = хn-1 -1, b = xm+1 -1 (х целое, отличное от 1), то справедливо и равенство 









Содержание  Назад  Вперед