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

щие утверждения (теорема 1.3 воспроизводится ниже в упрощенной формули­ ровке). Теорема 1.3. Если (т,п)= 1, mq- пр = 1, 0 < р <т и 0 <q<n, то КЛ* н * г ) = WPAX<’X1Рт-р*-ЛхохЛ Предложение 4.3. Для т,п> 0 пусть Vmll =xt,x 2 Vnjl. Тогда С (*Г' >*? )= КЛХ1 -х2h xr Теорема 4.4. V '\ ,x jl есть циклическая перестановка слова ) Используем эти свойства примитивных элементов Wmn, чтобы получить еще один способ их нахождения. В книге [2] приведена следующая задача (за­ дача 97, стр. 29). Пусть т,п - взаимно простые целые положительные числа. Рассмотрим дроби ~ +~ = и т +~ j (у = 1,...ц - П Если их изобра- т п зить точками на числовой оси, то в каждый из интервалов (l,2)i(2,3),... .(т +п - 2 ,т +п - \ ) попадет ровно одна из указанных дробей. Теорема 1. Если над каждым рассмотренным выше интервалом, содер­ жащим дробь со знаменателем т поставить л,, а со знаменателем п ~ х г, а к полученному слову приписать впереди х,х2, то это слово будет равно Доказательство. Предположим, что между двумя дробями W+- t и т т+п,. Л , т + 1 . — —( j + 1 ) есть дробь------ j. т п Тогда т +п . т+п . т +п ,. ... т п т или —I < у < —(«+ т т 174