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} |
  |   |   .. |   ... |   ... | ...  |   ... |
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} |
... |
  |   ... |   ... |
... |
  ... |   ... |
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} |
  |   |   ... |   ... |   ... |
... |
  ... |
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} |
  |
... |
  ... |   ... |   ... |   ... |   ... |
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) |
  |
... |
  ... |   ... |   ... |
... |
  ... |
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} |
  |   |
... |
  ... |   ... |   ... |
... |
Честно говоря, возникает желание избавиться от этого назойливого повторения. Как это сделать? Для этого придется переделать программу. Но чтобы программа не была слишком длинной, лучше переписать ее. Прежде всего, к уже имеющимся определениям
ааа[а_,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), то справедливо и равенство