I need a formula to calculate the maximum sum of products of variable and constant and the whole sum will be then performed a modulus by some number.
X = (C1*x1 + C2*x2 + C3*x3..... )%M, we have to maximise 'X' here, the values of Ci and M is given, all xi are variables (any integer, zero included), in short I can say we have to vary the xi's such that we get maximum possible X, for example
X = (10*i + 3*j)%18 (here i and j are variables)
answer :- X = 17 (take j = 1 and i = 5)
Does any formula exists to find the maximum possible value of X ?
sorry if you didn't understand the question (my English is not good), if you have any doubts ask in the comments section
The minimum positive value attainable with integers $x_1,x_2,\dots,x_i$ and positive integers $C_1,C_2,\dots,C_i$ is $k=\min{(\{z:z=\gcd{(C_j,C_k)}\land j,k\in\{1,2,\dots,i\}\})}$, and the maximum value of $X$ in this case is $\max{(\{k,2k,3k,\dots,(M−1)k\})}\mod{M}$. In other words, the maximum positive value of $$C_1x_1+C_2x_2+\dots+C_ix_i\mod{M}$$ with positive integers $C_1,C_2,\dots$ and $M$ is $$X\equiv\max{(\{k,2k,3k,\dots,(M−1)k\})} \mod{M}$$ where $k$ is the lowest possible greatest common denominator of a pair of integers from $C_1,C_2,\dots,C_i$ i.e $$k=\min{(\{z:z=\gcd{(C_j,C_k)}\land j,k\in\{1,2,\dots,i\}\})}$$