О построении пары взаимно простых чисел

О ПОСТРОЕНИИ ПАРЫ ВЗАИМНО ПРОСТЫХ ЧИСЕЛ
Л.Р. Родкина, доцент кафедры электроники ИИИБС ВГУЭС

А.Ф. Родкин, к.ф.-м.н., доцент АИ ДВФУ

Владивостокский государственный университет экономики и сервиса, Владивосток
"Задача решения систем линейных алгебраических уравнений возникает очень часто и привлекает внимание многих исследователей ... Имеется множество методов ... и на эту тему можно написать целую книгу."

Р.В. Хемминг [1].

Задача о построении пары взаимно простых чисел возникает в связи с оценкой эффективности целочисленного метода Гаусса. Целочисленный метод Гаусса (ЦМГ) был предложен авторами в работе [3], в основном, как представлялось, для разработки тренажерно-обучающих (компьютерных) программ по линейной алгебре.

Цель заключалась в том, чтобы работа с такой вычислительной программой в точности соответствовала работе с такими же вычислениями в аудитории (на доске, в тетради). Но первой операцией в стандартном методе Гаусса является деление всех коэффициентов при неизвестных в первом уравнении на коэффициент a₁₁ при первой неизвестной x₁[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-й строки с помощью разрешающего элемента a_li l-й строки, введенная в [3].

Под lk - итерацией с разрешающим элементом a_li (a_liki) понимается элементарное преобразование (ЭП) элементов k-й строки, соответствующее делению элемента a_ki по модулю a_li (для простоты считаем a_li и a_ki положительными и a_liki):

a'_ki = a_ki - [a_ki /a_li]* a_li , (2)

где [a_ki /a_li] – наибольшее целое число, не превосходящее a_ki /a_li.

В результате применения одной итерации в рассматриваемом столбце получается элемент a'_ki, по модулю меньший разрешающего элемента a_li. Повторяем lk -итерацию к этой паре строк с разрешающим элементом a'_ki. Результатом проведения двух или более итераций в данной паре строк будет появление нуля на месте одного из преобразуемых элементов i-го столбца (в (2) a'_ki = 0, если a_li = 1 или a_li является делителем a_ki). Если получится 0, то в этой строке неизвестная x_i - исключена (локальная цель достигнута) и дальше процесс продолжается с наименьшим в этом столбце разрешающим элементом a'_ki. Если же a'_ki = 1 (или a'_li = 1), то, переставляя строки так, чтобы диагональным элементом стала полученная единица a'_ii = 1, придем к начальным условиям стандартного метода Гаусса.

Таким образом, вопрос о возможности использования ЦМГ в целях решения практических задач – решения систем линейных уравнений больших размерностей -связан с выяснением следующего обстоятельства: на сколько (или во сколько) затратнее операция вычисления единицы с помощью многократных сложений и умножений в кольце целых чисел К по сравнению с вычислением ее с помощью единственной операции деления в поле рациональных чисел Q?

Рассмотрим детальнее процесс lk -итераций.

Пусть преобразования по ЦМГ доведены до i-го столбца, т.е. во всех предыдущих столбцах ниже главной диагонали все элементы – нулевые, все неизвестные с первой до i-1 – исключены. Следующий шаг - с помощью диагонального элемента a_ii преобразовать все элементы, лежащие ниже, в нулевые.

1). Если a_ii = 1, то, вычитая из k-й строки i-ю, умноженную на a_ki, получим в k-й строке 0 (аналогично (в цикле) и во всех строках, лежащих ниже i-й):

a'_ki = a_ki - a_ii a_ki = a_ki - 1* a_ki = 0.

2). Если a_ii 1, то единица ищется среди элементов, лежащих ниже. Если a_ki =1, то, переставляя i-ю и k-ю строки, получим условие 1).

3). Общий случай - среди элементов, начиная с диагонального, единиц нет. Алгоритм ЦМГ состоит в следующем. Из всех этих элементов выбирается минимальный по величине и (после перестановки строк, если требуется) этот элемент устанавливается диагональным. Так как, после этого a_ii - наименьший по величине, то к любой строке k ниже i-й можно применять lk -итерации (точнее ik –итерации и первой среди них будет k = i+1 строка). В результате первой ik –итерации, соответствующей делению элемента a_ki по модулю a_ii (0 < a_ii ki)), получим:

a'_ki = a_ki - [a_ki /a_ii]* a_ii ,

где a'_ki – остаток от деления: 0 a'_ki a_ii– 1.

Переставляя i-ю и k-ю строки, придем к условию: диагональный элемент a'_ii - наименьший по величине и продолжаем итерации в этих строках. Так как, после каждого шага остаток a'_kiстановится по величинеменьше диагонального (разрешающего) элемента a_ii, то после конечного числа шагов получим остаток a'_ki = 0. Предпоследний (не равный нулю) остаток a'_ki= d при d 1 является наибольшим общим делителем элементов a_ii и a_ki и остаток a'_ki= 1, если a_ii и a_ki – взаимно простые числа. Если a'_ki 1, то ik –итерации применяются к следующей k = i+2 строке с разрешающим элементом a'_ii = d, но этот элемент меньше исходного a_ii и, следовательно, число следующих итераций может быть значительно меньше. Если же a'_ki = 1 (после перестановки строк a'_ii = 1, благоприятный исход), то все остальные элементы в этом столбце в цикле преобразуются в нули с использованием в каждой строке только по одной операции умножения и вычитания в целых числах.

Обозначим a = a_ki, b = a_ii (b < a), тогда ik -итерация означает деление a по модулю b:

a = mb + r₁ , (3)

где m = [a/b] – наибольшее целое число, не превосходящее a/b,

r₁ – остаток от деления (0 r₁ b - 1) [2].

Следующий шаг ik-итерации соответствует делению b по модулю r₁:

b = m₁ r₁ + r₂ ,

и далее

r₁ = m₂r₂ + r₃ ,

r₂ = m₃r₃ + r₄ ,

… (4)

r_n-1 = m_nr_n + r_n+1.

Для взаимно простых чисел a и b процесс заканчивается при r_n= 1 (r_n₊₁ = 0).

Таким образом, оценка эффективности целочисленного метода Гаусса связана с оценкой среднего числа ik –итераций, т.е. числа делений предыдущего остатка r_j_-1 по модулю последующего остатка r_j.

Экспериментальная (статистическая) оценка среднего числа ik –итераций может проводиться в двух направлениях – прямом (задавая случайные числа a и b, подсчитывать соответствующее число ik –итераций) и обратном (исходя от r_n =1, r_n₊₁=0 и задавая случайные числа m_n, m_n_-1, m_n_-2, …, m₁, получать в результате числа a и b, являющиеся взаимно простыми [2]).

Обе задачи, на наш взгляд, являются интересными и полезными не только в связи с конкретными целями - оценкой эффективности целочисленного метода Гаусса (и возможности применения его для практических вычислений), но и установления некоторых свойств, присущих парам взаимно простых чисел.

Первая задача вычисления для произвольных a и b последнего отличного от нуля остатка r_n 0 (r_n₊₁ = 0) соответствует алгоритму Евклида нахождения наибольшего общего делителя D(a,b) натуральных чисел a и b. С точки зрения приложений для метода ЦМГ, неблагоприятный случай - если a и b имеют общий делитель d₀ 1, тогда нуль в k-й строке получится “раньше”, но поиск единицы продолжится в следующих i(k+1)–итерациях. Если же числа a и b взаимно простые, то наибольший общий делитель D(a,b) = r_n = 1, на этом процесс ik –итераций в этой паре строк заканчивается и, далее, вся лежащая ниже часть i-го столбца обнуляется только двумя наиболее экономичными операциями – умножения и сложения (вычитания) в целых числах.
В обратной задаче, исходя от r_n =1, (r_n₊₁=0) и задавая случайные числа m_n, m_n_-1, m_n_-2, …, m₁, можно строить взаимно простые числа a и b. При этом, для данного числа n “обратных” итераций и произвольных совокупностей n чисел m_n, m_n_-1, m_n_-2, …, m₁ можно получать, вообще говоря, бесконечное множество пар взаимно простых чисел.

Если одно из двух взаимно простых чисел (а именно, большее - a) - простое, то при любом b < a пара (a, b) будет взаимно простой, т.е. последний в ik-итерациях отличный от нуля остаток r_n = 1, что является благоприятным исходом в методе ЦМГ. Ниже приведены предварительные результаты оценок числа ik-итераций прямой задачи. Для пяти наибольших до 1000 простых чисел a A = {997, 991, 983, 977, 971} в таблице приведены числа ik-итераций для всех чисел b от 1 до 1000 (т.е. для всех взаимно простых пар {(a_i, b_j) a_i A, b_j {1, 2, …, 1000}} и, в том числе, по одной паре, не являющейся взаимно простой при b_j = a_i и D(a_i, b_j) = a_i 1). В 6-ом и 7-ом столбцах показано, что большое число итераций (для a = 997) связано только с числами b, находящимися в сравнительно узком интервале: b_j(-, +), где 2a/3, а зависит от b и n. Распределение f_b_/_a(n) числа ik-итераций близко к нормальному с заметно выраженной положительной асимметрией S > 0 и математическим ожиданием M_x = n_max/ 2. Для всех приведенных a_i среднее число ik-итераций M_x = 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

Литература

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