О ПОСТРОЕНИИ ПАРЫ ВЗАИМНО ПРОСТЫХ ЧИСЕЛ

Л.Р. Родкина, доцент кафедры электроники ИИИБС ВГУЭС
А.Ф. Родкин, к.ф.-м.н., доцент АИ ДВФУ

Владивостокский государственный университет экономики и сервиса, Владивосток

"Задача решения систем линейных алгебраических уравнений  возникает очень часто и привлекает внимание многих исследователей ... Имеется множество методов ... и на эту тему можно написать целую книгу."
Р.В. Хемминг [1].
  Задача о построении пары взаимно простых чисел возникает в связи с оценкой эффективности целочисленного метода Гаусса. Целочисленный метод Гаусса (ЦМГ) был предложен авторами в работе [3], в основном,  как представлялось, для разработки тренажерно-обучающих (компьютерных) программ по линейной алгебре.
Цель заключалась в том, чтобы работа с такой вычислительной программой в точности соответствовала работе с такими же вычислениями в аудитории (на доске, в тетради). Но первой операцией в стандартном методе Гаусса является деление всех коэффициентов при неизвестных в первом уравнении  на коэффициент a11 при первой неизвестной x1 [1], приводящее к появлению дробных элементов, чего мы избегаем на занятиях в аудитории. В алгебраической формулировке это означает, что если (расширенная) матрица системы линейных уравнений (СЛУ) 
AX = B						(1)
целочисленная, то все вычисления надо проводить в целых числах, а решение  записывать в виде отношения двух целых чисел, т.е.  рациональным числом.
Обозначенную нами задачу можно сформулировать следующим образом.
Пусть СЛУ (1) - целочисленная. В стандартном методе Гаусса решение системы (1) ищется в поле рациональных чисел Q. Поле рациональных чисел Q является абелевой (коммутативной) группой по сложению (+) и абелевой группой (исключая 0) по умножению (). Но для того, чтобы в процессе решения не было дробных чисел надо отказаться от операции деления - по второй операции умножения множество К (исключая 0) должно быть полугруппой с единицей, т.е. кольцом [2]. Сам же элемент 1 в кольце К может быть получен с помощью первой операции сложения (и обратной - вычитания) и второй - умножения.  Итак, для целочисленной системы линейных уравнений (1) в стандартном методе Гаусса решение ищется в поле рациональных чисел Q. В целочисленном методе Гаусса решение (преобразования) системы (1) проводится в кольце целых чисел (без операции деления), окончательный результат записывается рациональным числом (в виде отношения двух целых чисел) [3].
Эти соображения были воплощены в разработке алгоритма вычислений определителей целочисленных матриц по методу Гаусса [4] и реализованы в виде компьютерных программ. В работе [5] приведены функции на языке Clipper, реализующие алгоритм вычисления определителей целочисленных матриц по ЦМГ [4]. На этом же языке был разработан комплекс программ “Matrix” для решения основных задач линейной алгебры – решения систем линейных уравнений, вычисления определителей и обратных матриц по целочисленному методу Гаусса.
В результате работы и экспериментов с этими программами появилось понимание того, что такой подход к решению  СЛУ может быть использован не только в демонстрационно-тренажерных целях, но и для практических применений - практических вычислений по методу Гаусса, приводящих к отысканию  решений СЛУ любых (больших) размерностей и без известных в этой задаче проблем [6].
 К каким осложнениям приводит отказ от деления в стандартном методе Гаусса и замене его в ЦМГ многократными сложениями (вычитаниями) и умножениями для получения единицы?  В стандартном методе Гаусса единица получается очень просто - в одну (наиболее вычислительно-объемную) операцию деления. В целочисленном методе Гаусса единица может быть получена  в результате многократных сложений (вычитаний) и умножений. Но эта операция деления, делающая алгоритм метода Гаусса тривиально простым, приводит к появлению приближенных коэффициентов, накоплению ошибок и, следовательно, к проблеме  их контроля [1]. 
Основной структурной единицей в ЦМГ является lk-итерация преобразования k-й строки с помощью разрешающего элемента ali l-й строки, введенная в [3].
Под lk - итерацией с разрешающим элементом ali (ali<aki) понимается элементарное преобразование (ЭП) элементов k-й строки, соответствующее делению  элемента aki  по модулю ali (для простоты считаем ali и aki положительными и ali<aki):
a'ki  = aki  - [aki /ali]* ali ,              				        (2)
где [aki /ali] – наибольшее целое число, не превосходящее aki /ali.
В результате применения одной итерации в рассматриваемом столбце получается элемент a'ki, по модулю меньший разрешающего элемента ali. Повторяем lk -итерацию к этой паре строк с разрешающим элементом a'ki. Результатом  проведения двух или более итераций в данной  паре строк будет появление нуля на месте одного из преобразуемых элементов i-го столбца (в (2)  a'ki = 0, если ali = 1 или ali является делителем aki). Если получится 0, то в этой строке неизвестная xi  - исключена (локальная цель достигнута) и дальше процесс продолжается с наименьшим в этом столбце разрешающим элементом a'ki.  Если же  a'ki = 1 (или a'li = 1), то, переставляя строки так, чтобы диагональным  элементом  стала полученная единица a'ii = 1, придем к начальным условиям стандартного метода Гаусса.
Таким образом, вопрос о возможности использования ЦМГ в целях решения практических задач – решения систем линейных уравнений больших размерностей -связан с выяснением следующего обстоятельства: на сколько (или во сколько) затратнее операция вычисления единицы с помощью многократных сложений и умножений в кольце целых чисел К по сравнению с вычислением ее с помощью  единственной операции деления в поле рациональных чисел Q?
Рассмотрим детальнее процесс lk -итераций.
Пусть преобразования по ЦМГ доведены до i-го столбца, т.е. во всех предыдущих столбцах ниже главной диагонали все элементы – нулевые, все неизвестные с первой до i-1 – исключены. Следующий шаг -  с помощью диагонального элемента  aii  преобразовать все элементы, лежащие ниже, в нулевые.
1). Если aii  = 1, то, вычитая из  k-й строки  i-ю, умноженную на aki, получим в k-й строке 0 (аналогично (в цикле) и во всех строках, лежащих ниже i-й):
a'ki  = aki  - aii aki  = aki  - 1* aki = 0.
2). Если aii   1, то единица ищется среди элементов, лежащих ниже.  Если aki =1, то, переставляя i-ю и k-ю строки,   получим условие 1).
3). Общий случай - среди элементов, начиная с диагонального, единиц нет. Алгоритм ЦМГ состоит в следующем. Из всех этих элементов выбирается минимальный по величине и (после перестановки строк, если требуется) этот элемент устанавливается диагональным. Так как, после этого aii  - наименьший по величине, то к любой строке k ниже i-й можно применять lk -итерации (точнее ik –итерации и первой среди них будет k = i+1 строка). В результате первой ik –итерации, соответствующей делению  элемента aki  по модулю aii  (0 < aii <aki)), получим:
a'ki  = aki  - [aki /aii]* aii ,
где a'ki – остаток от деления:   0  a'ki    aii – 1.
Переставляя i-ю и k-ю строки,  придем к условию: диагональный элемент a'ii  - наименьший по величине и продолжаем итерации в этих строках. Так как, после каждого шага остаток a'ki  становится по величине меньше диагонального (разрешающего) элемента aii, то после конечного числа шагов получим остаток a'ki = 0. Предпоследний (не равный нулю) остаток  a'ki = d при d  1 является наибольшим общим делителем элементов aii  и  aki и остаток  a'ki = 1, если aii  и  aki – взаимно простые числа.  Если  a'ki  1, то ik –итерации применяются к следующей  k = i+2 строке  с разрешающим элементом a'ii = d, но этот элемент меньше исходного aii и, следовательно, число следующих итераций может быть значительно меньше. Если  же a'ki  = 1 (после перестановки строк a'ii = 1, благоприятный исход),  то все остальные элементы в этом столбце в цикле преобразуются в нули с использованием в каждой строке только по одной операции умножения и вычитания в целых числах.
Обозначим  a = aki , b = aii (b < a), тогда ik -итерация означает деление a по модулю b:
a = mb + r1 ,						(3)
где  m = [a/b] – наибольшее целое число, не превосходящее a/b,
 r1 – остаток от деления (0  r1  b - 1) [2].
Следующий шаг  ik-итерации соответствует  делению b по модулю r1:
b = m1 r1 +  r2 ,  
и далее
r1 = m2r2 +  r3 ,
r2 = m3r3 +  r4 ,
…	    						(4)
rn-1 = mnrn +  rn+1.
Для взаимно простых чисел a и b процесс заканчивается при rn = 1 (rn+1 = 0).
Таким образом, оценка эффективности целочисленного метода Гаусса связана с оценкой среднего числа ik –итераций, т.е. числа делений предыдущего остатка rj-1 по модулю последующего остатка rj.
Экспериментальная (статистическая) оценка среднего числа ik –итераций может проводиться в двух направлениях – прямом (задавая случайные числа a и b, подсчитывать соответствующее число ik –итераций) и обратном (исходя от rn =1, rn+1=0 и задавая случайные числа mn, mn-1, mn-2, …, m1, получать в результате числа a и b, являющиеся взаимно простыми [2]).
Обе задачи, на наш взгляд, являются интересными и полезными не только в связи с конкретными целями - оценкой эффективности целочисленного метода Гаусса (и возможности применения его для практических вычислений), но и установления некоторых свойств, присущих парам взаимно простых чисел.
1.	Первая задача вычисления для произвольных  a и b последнего отличного от нуля остатка rn  0 (rn+1 = 0) соответствует алгоритму Евклида нахождения наибольшего общего делителя D(a,b) натуральных чисел a и b. С точки зрения приложений для метода ЦМГ, неблагоприятный случай - если a и b имеют общий делитель d0  1, тогда нуль в k-й строке получится “раньше”, но поиск единицы продолжится в следующих i(k+1)–итерациях. Если же числа a и b взаимно простые, то наибольший общий делитель D(a,b) = rn = 1, на этом процесс ik –итераций в этой паре строк заканчивается и, далее, вся лежащая ниже часть i-го столбца обнуляется только двумя наиболее экономичными операциями – умножения и сложения (вычитания) в целых числах.
2.	В обратной задаче, исходя от rn =1, (rn+1=0) и задавая случайные числа mn, mn-1, mn-2, …, m1, можно строить взаимно простые числа a и b. При этом, для данного числа n “обратных” итераций и произвольных совокупностей n чисел mn, mn-1, mn-2, …, m1  можно получать, вообще говоря, бесконечное множество пар взаимно простых чисел.
Если одно из двух взаимно простых чисел (а именно, большее - a) - простое, то при любом b < a пара (a, b) будет взаимно простой, т.е. последний в ik-итерациях отличный от нуля остаток rn = 1, что является благоприятным исходом в методе ЦМГ.  Ниже приведены предварительные результаты оценок числа ik-итераций прямой задачи. Для пяти наибольших до 1000 простых чисел a  A = {997, 991, 983, 977, 971} в таблице приведены числа ik-итераций для всех чисел b от 1 до 1000 (т.е. для всех взаимно простых пар {(ai, bj) ai  A, bj  {1, 2, …, 1000}} и, в том числе, по одной паре, не являющейся взаимно простой при bj = ai и D(ai, bj) = ai  1).  В 6-ом и 7-ом столбцах показано, что большое число итераций (для a = 997) связано только с числами b, находящимися в сравнительно узком интервале: bj (-, +), где    2a/3, а  зависит от b и n. Распределение fb/a(n) числа ik-итераций близко к нормальному с заметно выраженной положительной асимметрией S > 0 и математическим ожиданием Mx  = nmax / 2.  Для всех приведенных ai среднее число ik-итераций Mx  = 6 (средняя строка таблицы).

	997	991	983	977	971	997	997	
n	1-1000	1-1000	1-1000	1-1000	1-1000	10-1010	400-900	
1	2	2	2	2	2	1	0	
2	11	23	3	9	7	7	1	
3	37	51	41	41	49	35	5	
4	113	89	113	94	113	115	26	
5	191	172	184	189	176	192	77	
6	208	211	221	240	212	210	109	
7	192	190	201	195	193	194	109	
8	136	148	131	136	142	136	91	
9	68	76	62	66	78	68	49	
10	30	28	28	18	22	30	23	
11	10	8	12	8	4	10	8	
12	2	2	2	2	2	2	2	

Литература
1.	Хемминг Р.В. Численные методы. М., Наука, 1972 г. 400 с
2.	Калужнин Л.А. Введение в общую алгебру. М., Наука, ФМЛ, 1973 г. 448с.
3.	Родкин А.Ф. Алгоритм метода Гаусса преобразования матриц в кольце целых чисел. 40-я Всероссийская межвузовская научно-техническая конференция "Фундаментальные и прикладные вопросы физики и математики"  .  Сб. докл., т.1, ч. 2,  Владивосток, Изд. ТОВВМУ им. С.О. Макарова, 1997 г., с.163-165.
4.	Родкина Л.Р., Родкин А.Ф. Алгоритм вычислений определителей  целочисленных матриц по методу Гаусса. Всероссийская НТК,  посвященная 150-летию со дня рождения С.О. Макарова. Сб. докл., т.2., Владивосток, изд. ТОВМИ им. С.О. Макарова 1998 г.,   с.190-192.
5.	Родкина Л.Р., Родкин А.Ф. Вычисление определителей целочисленных  матриц по методу Гаусса. Концепции методики преподавания - 2002 в сфере высшего образования. Материалы научно-методической конференции, сентябрь 2002, г. Артем, изд. ДВГУ, Владивосток, 2002 г., с. 49-52. 
6.	Родкина Л.Р., Родкин А.Ф.  О точном методе решения систем линейных уравнений Материалы научно-практической конференции, вып.1, (апр., 2004, г. Артем), изд. ДВГУ, Владивосток, 2004 г., с. 93-96.