Problem 4

Determine, with proof, the greatest number which is the product of positive integers whose sum is

1976

Step 6 of 6: Use the remainder modulo

3

Previous step Next step

In plain words

The remainder $2$ modulo $3$ selects one $2$ rather than zero or two; all remaining mass is spent on the most efficient factor, $3$ .

1976=3\cdot658+2,\quad f(S)=2\cdot3^{658}

Detailed analysis

Since $1976=3\cdot658+2$ , and the number of $2$ 's is at most two, the number of $2$ 's must be exactly one: two $2$ 's would contribute $4\equiv1\pmod3$ , while one contributes $2\pmod3$ . The remaining sum is $1974=3\cdot658$ , so the maximizing multiset is one $2$ and $658$ copies of $3$ , with product $\boxed{2\cdot3^{658}}$ .