АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ ТЕОРИИ ГРУПП И ПОЛУГРУПП 1990 г.

несвободны. ДОКАЗАВЬЛЪСТЬО. Из несвободы данного J 4 сле­ дует несвобода 83- ; несвобода = следует из теоремы I. По­ этому достаточно доказать теорему для случая, когда ( м , 8 ) - i . Г^гсть . . i n = ± А (tft- и / 6 4 ) , ( 5 > где А принимает все возможные значения, не превосходящие 32 и взаимно простые с 64, т .е . нечетные. Для А * I , 7 , 9, 15, 17 23 25, 31 получаем Щ = ± / ( 8 ) , ц — ----- , и- g i у теорема следует из н е с в о б о д ы - g t" t~ T • установленной в теореме I . Для ^ = 3, 5 результат следует из леммы 6 . Сравнение (5 ) равносильно сравнению м г ~ ± A, (h<с с / 6 4 ) , / < ^ < ЗУ , при условии А, = ± А г( т 4 * / 6 4 ) , а также уравнениям 6 4 а ±*v)l i>'L - 1, при условиях A l r = ± l ( tn c - e i6 4 ) , V, = ± У *~(н<сс/6 4 ^ . Составим таблицу соответствующих значений / , ft, , V ъ , 4 ) , причем в каждой строке будем подчеркивать те значения, к которым применима соответствующая лемма или теорема I (по­ следние три строки заполняем только по мере необходимости): А I 3 5 7 9 II 13 15 17 19 21 23 25 27 29 31 Ь 25 7 23 23 7 25 9 V 13 29 5 27 3 19 I I 23 9 25 25 9 23 7 Видим, что только для А = 19 или 27 не работает ни одна из доказанных лемм, для этих случаев проведем отдельное доказа­ тельство, аналогичное доказательству случая (3 .4 ) леммы 3. Здесь V, принимает значение 25 или 23. Условие ( 2 ) имеет вид 6 Чи ± I или 6 Чи ± 2 3 /г> г = i . Перейдем от этих равенств к сравнениям по модулю 24. Так как ( м , б ) - А , то hnl г / (rncJ24)t и получаем сравнение 8 и ± I = 1 ( и-<-еа/ 4 4). Это возможно, только если единица в левой части стоит со зна­ ком плюс, и в этом случае U = 0 ( t u o J i ) t т .е . £/ = 3 ^ . Далее, имеем равенство 64 • 9 - 23 • 25 - I , Следовательно, в обо» значениях леммы 3 имеем соотношения 3t)!l Q 1 ^ v 6 i - i , 3 a t - v t + /, 50