How do I solve this problem on maximizing sum modulo a given number?

Question

I am stuck in solving this math problem. I need to maximize $$ (a_1\cdot x_1 + a_2\cdot x_2 + a_3\cdot x_3 + \dots + a_n\cdot x_n) \mathbin{\mathrm \%} b. $$ Here $a_i$ and $b$ are given and $x_i$ can be any nonnegative integer.

Answer 1

Tl;dr: The maximum value is $$ b- \gcd(a_1,\dots,a_n,b). $$ When all $a_1,\dots,a_n$ are $0$ modulo $b$, this value is $0$, and any coefficients can be used (eg. $x_i = 0$). Otherwise the coefficients are $$ x_i = \left( y_i\cdot \frac {b- \gcd(a_1,\dots,a_n,b)}{\gcd(a_1,\dots,a_n) \mathbin{\mathrm\%} b} \right) \mathbin{\mathrm\%} b, $$ where $y_i$ are such that $$ \gcd(a_1,\dots,a_n) = a_1 y_1 + a_2 y_2 + a_3 y_3 + .... + a_n y_n. $$

Now the explanation.

---

1. First, observe that, modulo $b$, integral linear combinations of $a_1, \dots, a_n$ are exactly multiples of the greatest common divisor of those numbers, so we'll need to find the maximum multiple modulo $b$ of that. Denote for brevity: $$ g := \gcd (a_1, a_2, \dots, a_n). $$ Of course every linear combination is a multiple of $g$. On the other hand, by the extended Euclidean algorithm/Bézout's identity, $g$ is actually the value of some combination: $$ g = a_1 y_1 + a_2 y_2 + a_3 y_3 + .... + a_n y_n $$ (see a clarification in a note at the end). Here some of $y_i$ are negative, however, if considered modulo $b$, we can use modulos of $y_i$, which are nonnegative: $$ g \stackrel{\mathbin{\mathrm\%} b}= g \mathbin{\mathrm\%} b \stackrel{\mathbin{\mathrm\%} b}= a_1 (y_1\mathbin{\mathrm\%} b) + a_2 (y_2\mathbin{\mathrm\%} b) + .... + a_n (y_n\mathbin{\mathrm\%} b) $$ or in other notation $$ g \stackrel{\bmod b}\equiv g\bmod b \stackrel{\bmod b}\equiv a_1 (y_1\bmod b) + a_2 (y_2\bmod b) + .... + a_n (y_n\bmod b). $$

2. Now, the multiples of $g$ considered modulo $b$ are exactly the same as the multiples of $\gcd(g,b)$ modulo $b$, so exactly the same as integral linear combinations of $a_1, \dots, a_n$ modulo $b$. This is because for some $k$, $l$, $m$:

   • $\gcd(g,b) = kg + lb$, so for any $r$: $r\cdot\gcd(g,b) = rkg + rlb$, hence $$r\cdot\gcd(g,b) \stackrel{\mathbin{\mathrm\%} b}= (rk)g,$$
   • $g = m\gcd(g,b)$, so for any $r$ $$r\cdot g = (rm)\gcd(g,b).$$

Note that $$ \gcd(g,b) = \gcd (a_1, a_2, \dots a_n, b), \gcd(g,b) = \gcd(g \mathbin{\mathrm\%} b, b) $$

3. The maximum multiple of $\gcd(g,b)$ modulo $b$ (and hence the maximum linear combination of $a_1, \dots, a_n$) is $$ b - \gcd(g,b) , $$ (see also the answers to this question). Now, if $g \mathbin{\mathrm\%} b = 0$, this means that all $a_i$ are $0$ modulo $b$, that is divisible by $b$ -- then the formula for the maximum value is correct and we can take any linear combination. If $g \mathbin{\mathrm\%} b \neq 0$, we can rewrite $$ b - \gcd(g,b) = \left(\frac {b- \gcd(g,b)}{g \mathbin{\mathrm\%} b} \right) \cdot (g \mathbin{\mathrm\%} b). $$ so we multiply the linear combination with $y_i$ by this fraction: \begin{align*} b - \gcd(g,b) &\stackrel{\mathbin{\%}b}=\left(\frac {b- \gcd(g,b)}{g \mathbin{\mathrm\%} b} \right) \cdot \bigg( a_1 (y_1\mathbin{\mathrm\%}b) + a_2 (y_2\mathbin{\mathrm\%}b) + .... + a_n (y_n\mathbin{\mathrm\%} b)\bigg) \\ &\stackrel{\mathbin{\%}b}=\sum _{i=1}^n a_i\cdot \left(\frac {b- h}{g \mathbin{\mathrm\%} b} \right)\cdot (y_i\mathbin{\mathrm\%}b) \end{align*} where $$ h = \gcd(g,b) = \gcd (a_1, a_2, \dots a_n, b). $$ Your desired linear combination is considered modulo $b$, so we can modulo the coefficients as well. In other words, as the coefficients we can take $$ x_i = \left[ y_i\left(\frac {b- h}{g \mathbin{\mathrm\%} b} \right) \right] \mathbin{\mathrm\%} b. $$

---

Edit: The greatest common divisor of more than three numbers may be calculated recursively: $$ \gcd(p,q,r) = \gcd\left(\,\gcd(p,q),\,r\right)\\ \gcd (a_1, a_2, \dots, a_n) = \gcd( \dots \gcd(\gcd (a_1, a_2),a_3), \dots, a_n) $$ Similarly, we calculate the coefficients $y_1, \dots y_n$ recursively: first $$ \gcd (a_1, a_2) = s^{(1)} a_1 + t^{(1)} a_2, $$ then \begin{align} \gcd (a_1, a_2, a_3) &= \gcd(\gcd (a_1, a_2),a_3)\\ &= s^{(2)} \cdot \gcd (a_1, a_2) + t^{(2)} a_3\\ &= s^{(2)} \cdot (s^{(1)} a_1 + t^{(1)} a_2) + t^{(2)} a_3\\ &= (s^{(2)} s^{(1)}) a_1 + (s^{(2)} t^{(1)}) a_2 + t^{(2)} a_3, \end{align} and so on.