
Common Divisor’s computing > NonLinear Programming task
Posted:
Jun 5, 2009 12:14 PM


Author: Yuly Shipilevsky
Algorithms for finding the Common Divisors and Greatest Common Divisor . (Reducing of the Common Divisor?s computing to the solution of a Quadratic and NonLinear Programming/Optimization problem).
First algorithm.
Let N be a set of positive integers, N = {1, 2, ? } Let D be a Common Divisor of X1, ? , XM. There exists an unique Mtucle m0=(m01 , . . . , m0M) that corresponds to the Mtucle X=( X1, ? , XM) so that:
(1) Xi = Dm0i ,
(2) 1 <= m0i <= Xi , 1<= i <= M
Let gcd(X1, ? , XM) denotes the Greatest Common Divisor of X1, ? , XM.
Let N^M denotes a Cartesian product of M sets N, Let m denotes an arbitrary Mtucle (m1 , . . . , mM) contained in N^M.
Let S_ N^M = {m : 1 <= mi <= Xi , 1<= i <= M }
Let's define the following function:
(3) S1(m,X) = SUM_i,j=1...M,i>j [Xi/mi ? Xj/mj]^2 ,
where m=(m1 , . . . , mM) is contained in S_N^M
Proposition 1 (Minimum Principle).
for any Mtucle m contained in S_N^M the following is true:
min_m { S1(m,X)  S_N^M } = S1(m0,X) = 0,
(the minimum is being searched amongst all the ?m?s contained in S_N^M),
S1(m,X) > = S1(m0,X) = 0,
If and only if m0 contained in S_N^M corresponds to the Mtucle X=( X1, ? , XM) and satisfies
(1) and (2)
Proof.
It follows from X?s Common Divisors? existence (1 is considered as a Common Divisor as well) and (1) , (2) , (3) .
On the base of Proposition 1 we can suggest a
Theorem 1 (Reducing of Common Divisor?s computing to the solution of a Quadratic Integer Programming/Optimization problem).
To compute the Greatest Common Divisor of X1, ? , XM do the following steps:
(a) Find Mtucles m contained in S_N^M and minimizing S1 (S1 > min  S_N^M) (b) For each and every Mtucle, determined at step (a) find the corresponding Common Divisor of X using (1) and then (c) Find the Greatest amongst Common Divisors determined at the step (b)
(the minimum is being searched amongst all the ?m?s contained in S_N^M).
Proof.
It follows from the Proposition 1.
Lemma 1.
If S_R_ N^M = {m: 1<= mi <= Xi, mi  real numbers, 1<= i <=M } ,
then
min_m { S1(m,X)  S_N^M } = min_m { S1(m,X)  S_R_ N^M} = 0
Proof.
It follows from the Proposition 1 and (1) , (2), (3).
On the base of Lemma 1 and Theorem 1 we can suggest a
Theorem 2 (Reducing of Common Divisor?s computing to the solution of a Quadratic Programming /Optimization problem).
To compute the Greatest Common Divisor of X1, ? , XM do the following steps:
(a) Find Mtucles m contained in S_R_N^M and minimizing S1 (S1 > min  S_R_N^M) (b) For each and every Mtucle, determined at step (a) find the corresponding Common Divisor of X using (1) and then (c) Find the Greatest amongst Common Divisors determined at the step (b)
(the minimum is being searched amongst all the ?m?s contained in S_R_N^M).
Second algorithm.
Let?s define the following function:
(4) S2(m,X) = SUM_i,j=1...M,i>j [Xi/mi ? Xj/mj]^2 ?  Xk/mk ,
where m=(m1 , . . . , mM) is contained in S_N^M, 1 <= k <= M.
Proposition 2 (Minimum Principle).
The following is true:
gcd(X1, ? , XM) =  min_m { S2(m,X)  S_N^M } = =  S2(m0,X)
(the minimum is being searched amongst all the ?m?s contained in S_N^M).
If and only if m0 corresponds to the Mtucle X=( X1, ? , XM) , satisfies
(1) and (2) and corresponds to the Greatest Common Devisor gcd(X1, ? , XM).
Proof.
It follows from X?s Common Divisors? existence (1 is considered as a Common Divisor as well) and (1) , (2) , (4) .
On the base of Proposition 2 we can suggest a
Theorem 3. (Reducing of gcd?s computing to the solution of a Integer Programming /Optimization problem).
To compute the Greatest Common Divisor of X1, ? , XM do:
(a) Find an Mtucle m0 contained in S_N^M and minimizing S2 (S2 > min  S_N^M) (b) Find the Greatest Common Divisor corresponding to the Mtucle m0 determined at step (b) as follows:
gcd(X1, ? , XM) =  min_m { S2(m,X)  S_N^M } =  S2(m0,X).
(the minimum is being searched amongst all the ?m?s contained in S_N^M).
Lemma 2.
If S_R_ N^M = {m: 1<= mi <= Xi, mi  real numbers, 1<= i <=M } ,
then
min_m { S2(m,X)  S_N^M } = min_m { S2(m,X)  S_R_ N^M}
Proof.
It follows from Proposition 2, the fact that
SUM_i,j=1...M,i>j [Xi/mi ? Xj/mj]^2 >= 0 and
continuosity and monotonicity of S21(mk) = Xk/mk function.
On the base of Lemma 2 and Theorem 3 we can suggest a
Theorem 4. (Reducing of gcd?s computing to the solution of a NonLinear Programming /Optimization problem).
To compute the Greatest Common Divisor of X1, ? , XM do:
(a) Find an Mtucle m0 contained in S_R_N^M and minimizing S2 (S2 > min  S_R_N^M) (b) Find the Greatest Common Divisor corresponding to the Mtucle m0 determined at step (b) as follows:
gcd(X1, ? , XM) =  min_m { S2(m,X)  S_R_N^M } =  S2(m0,X).
(the minimum is being searched amongst all the ?m?s contained in S_R_N^M).
Example.
Finding the Greatest Common Divisor of 9636, 1456 and 2098 is being reduced to the following NonLinear Programming task:
S2(m , X) = ( 9636 / m1  1456 / m2 )^2 + ( 1456 / m2  2098/ m3 )^2  9636 / m1 > min
m =(m1, m2, m3) ,
X=(9636, 1456, 2098),
m1, m2, m3  real numbers,
satisfying the following constraints:
1 <= m1 <= 9636 , 1 <= m2 <= 1456,
1 <= m3 <= 2098
gcd(9636, 1456, 2098) =  min_m { S2(m , X)  1 <= m1 <= 9636 , 1 <= m2 <= 1456, 1 <= m3 <= 2098 }.

