Reverse addition

Question

I have a number 46 which is the result of addition of 12+17+17. Is there a way, given the result 46 and 12 , 17 as the numbers used to get the result, to find out in what combination 12 and 17 was used to get the result 46

Answer 1

You could try using modulo algebra: $$n=\alpha 12 + \beta 17\implies [n]_{17}=[12]_{17}[\alpha]_{17} \implies [\alpha]_{17}=[n]_{17}([12]_{17})^{-1}=[n]_{17}[5]_{17}$$

You get $([12]_{17})^{-1}=[5]_{17}$ with the extended euclidean algorithm

This only works well because 17 is prime (or more specifically gcd(12,17)=1). So then you know $\alpha=5n + m\cdot 17$. That is already an improvement over brute force trying all whole numbers for alpha. Since 5 is a whole number (and this generalizes) $5n>n>\alpha$ so you know that m is negative and basically walk down the negative integers.

You can try playing with that approach a bit.

So pseudo algorithm:

extended euclidean algoritm yields: x,y, gcd(12,17) with 12x+12y=gcd(12,17)
if(gcd(12,17)=1)
    loop m=0,1,2... 
        try alpha=x*n-m*17 (calculate beta - is int?)

Answer 2

If "the number is 169 and 12s and 17s are the numbers used." then you have the Diophantine equation 12x+ 17y= 169. 12 divides into 17 once with remainder 5: 17- 12= 5. 5 divides into 12 twice with remainder 2: 12- 2(5)= 2. Finally, 2 divides into 5 once with remainder 1: 5- 2(2)= 1. Replace that (2) by 12- 2(5): 5- 2(12- 2(5))= 5(5)- 2(12)= 1. Replace that (5) by 17- 12: 5(17- 12)- 2(12)= 5(17)- 7(12)= 1. Multiply by 169: 845(17)- 1183(12)= 169. So one solution is x= -1183, y= 845. But adding any multiple of 17 to x and subtracting that same multiple of 12 from y gives another solution: 12(-1183+ 17k)+ 17(845- 12k)= -14196+ 12(17)k+ 14365- 17(12)k= 169. In particular, taking k= 70 gives positive values for both x and y: x= -1183+ 17(70)= 7 and y= 845- 12(70)= 5. 169= 7(12)+ 5(17).

Answer 3

Plot the line $12x+17y=46$. A point on the line with both coordinates being non-negative integers is the solution. In this case there is one such point. In general there may be none, one or many.

---

And this solves the example from your comment:

Here the solution was not obvious. With less precision we might be led to conclusion that $(10,3)$ or $(4,7)$ was the solution. Therefore we should verify each suspected point by calculation. Still the method ruled out many values of $x$ (e.g. $12$) and many values of $y$ (e.g. $6$).

---

In general a problem $ax+by=c$ generates a line. You are interested in a segment from $(0, \frac c b )$ to $(\frac c a ,0)$. The larger $\frac c b$ and $\frac c a$ are, the more precise you need to be and the more points you'll find close enough to the line so you need to check them by calculation. As $\frac c b$ and $\frac c a$ grow, the method becomes unpractical.

If there are more than two solutions, they occur on the line at regular distances (exercise: why?). This observation will help you to find additional solutions (if they exist) after you find at least two.