# Procedure to solve this Number theory question

We are provided with a positive number N which denotes that we have N objects . Each of those N objects hold a value. Now we are provided a task to add non-negative value to the objects in such a way that the resultant values of N objects have a common factor .
Find the minimum sum of all the numbers added.

For example :- Suppose N = 3 and we have objects with values as:-
11 ,21 ,24
The answer to this is 1 as we can add 1 to 11 , and thus resultant values become
12, 21, 24 ,
which have 3 as common factor .

• I understand that you can add a number (same number) to all the objects that you want. In that case, if you have $N$ objects, all even, then sum 0. If this isn't the case, plus 1 to all the odd objects and then the resulting $N$ objects are all even. Could you be more clear? – sinbadh Jan 1 '16 at 12:41
• The thing is not about odd or even . How can your technique work for the example i mentioned above? – user249117 Jan 1 '16 at 12:45
• Is the common factor specified? If not, then the comment of @sinbadh seems to settle the matter. In your example, add $1$ to $11,21$ to get the triple $12,22,24$ which share the factor $2$. On its face, that would seem to pass your requirements... – lulu Jan 1 '16 at 12:48
• @lulu but that would not be the minimum, the question clearly asks for minimum. – Daga Jan 1 '16 at 12:49
• But minimum such value is required . Common factor is required , and min value is 1 , whereas as per the above mentioned procedure , answer is 2 – user249117 Jan 1 '16 at 12:50

Thinking the problem as a programming question will make it easy.

For given $N$ objects $\{x_1,x_2,x_3,\dots,x_n\}$, find all values of primes $p$, such that there exist a value of $i$, such that $x_i \mod p =0$.

For all such values of $p$ find the minimum value to be added to $x_i$, such that $x_i \mod p =0$ if $x_i \mod p \ne 0$. This value is equal to $p - (x_i \mod p)$.

For all values of p, find the sum of all the values added to $x_i$, the minimum among them will be the answer.

• Thanx a lot . This was the exact approach i was looking for – user249117 Jan 1 '16 at 13:21

Don't see a simple closed formula. As a programming method, note that the even/odd calculation gives an upper bound (equal to the number of odd numbers in the list). Then work prime by prime until the least element needs too great a summand.

Example (randomly chosen): $$L=\{12,17,23,31,43,57,91,102\}$$

There are $6$ odd numbers in the list so the upper bound is $6$.

Now try $p=3$ working mod$3$ we get $$L\equiv \{0,2,2,1,1,0,1,0\}$$. Thus we must add $\{0,1,1,2,2,0,2,0\}$ which sums to a value greater than $6$.

Now try $p=5$. working mod$5$ we get $$L\equiv \{2,2,3,1,3,2,1,2\}$$ and again it is no good.

Similarly, we can rule out $p=\{7,11,13,17\}$. No need to look any further as we we'd clearly have to add more than $6$ to $12$. Hence the upper bound was good, and the answer is $6$.

• Thanx a lot . That helped a lot :) – user249117 Jan 1 '16 at 13:21