Given diophantine equation $11x+17y +19z =2561$ , which $x,y,z \geq 1$
Find minimum and maximum value of $x+y+z$
I'm start with reduces equation to $11x+17y +19z =2514$ , which help us guarantee that $x,y,z \geq 1$ then set each variable to $0$ to find bound of $x+y+z$
that comes to this
I'm not sure that the solution I did was correct. So, minimum $x+y+z = 137$ and maximum $x+y+z = 231$ ???. sorry for my english and thank you in advance.
On
Assume $11x+17y+19z=2514,$ with $x,y,z\geq 0.$
Since $$\begin{align}17\cdot 4 &= 11\cdot 1 + 19\cdot 3\\ \end{align}$$ We get that if $y\geq 4,$ then $(x',y',z')=(x+1,y-4,z+3)$ which has $x'+y'+z'=x+y+z.$ So we can restrict our search for both minimum and maximum values to where $y\leq 3.$
Now, minimizing/maximizing $x+y+z$ is the same as minimizing/maximizing:
$$19(x+y+z)-2514=8x+2y$$
which is the same as minimizing/maximizing $y+4x.$ So given a fixed $y\leq 3$ we need a minimum value for $x$ to get the minimum value of $x+y+z$, and maximum value of $x$ to get the maximum value of $x+y+z.$
So we need find any integer solutions $x_i,z_i$ for $i=0,1,2,3:$
$$11x_i + 19z_i = 2514 - 17\cdot i$$
Since $11\cdot 7+19\cdot(-4) = 1$ we can use:
$$x_i=7(2514-17i),z_i=-4(2514-17i)$$
Then the maximum value is gott by finding $y=i,x=x_i$ which maximizes $$i+4\left(x_i+19 \left\lfloor\frac{z_i}{11}\right\rfloor\right)$$ I get the value $y=i=1,x=227,z=0,$ yielding $x+y+z=228.$
The minimum value is given by the value $i$ that minimizes: $$i + 4\left(x_i\bmod 19\right)$$
The minimum value is when $i=1$ so $y=0$ and $(x,y,z)=(4,0,130).$
In general, given positive $a<b<c$ and $\gcd(a,c)=1,$ and we want to find the extrema $x+y+z$ where $ax+by+cz=M$ and integers $x,y,z\geq 0.$
First we must assure that there are any solutions. If not, there are no solutions. If $M>(a-1)(b-1)$ there is always a solution to $ax+by=M.$
As above, we can restrict the answers to:
$$y<\frac{c-a}{\gcd(c-b,b-a)}$$
This is because $$a(c-b)+c(b-a) = b(c-a)$$
Computing $c(x+y+z)-M$ we see that the value of $x+y+z$ is maximized when $(c-a)x+(c-b)y$ is maximized, so for fixed $y$ we want to maximize $x.$
Start with any integer solution $X,Z$ to $aX+cZ=1.$
For $0\leq i<\frac{c-a}{\gcd(c-b,b-a)}$, we take $y_i=i.$ The smallest $x_i$ for this $y_i$ is given by the formula:
$$x_i = (M-bi)X\bmod c$$
Then the minimum value over all $i$ is given by the $i$ which minimizes $(c-a)x_i+(c-b)i.$
You can simplify the calculation by precomputing $M_0=(MX\bmod c)$ and $b_0=(bX\bmod c).$ Then you get $$x_i=(M_0-b_0i)\bmod c,$$ with all with coefficients less than $c.$
The maximum (given $y=i$) occurs when $$x_i=(M-bi)X + c\left\lfloor \frac{(M-bi)Z}{a}\right\rfloor$$ Then take the value $i$ such which maximizes $(c-a)x_i+(c-b)i.$
That might seem like a lot of calculations, but you can pre-calculate $MZ = aM_1+M_2$ and $bZ=ab_1+b_2$ with $0\leq b_2,M_2<a$ then you get:
$$\begin{align}x_i &= (M-bi)X + cM_1-cb_1i + c\left\lfloor \frac{M_2-b_2i}{a}\right\rfloor\\ &=(MX+M_1c)-(bX+cb_1)i + c\left\lfloor \frac{M_2-b_2i}{a}\right\rfloor \end{align}$$
So precompute $U=MX+M_1c$ and $V=bX+cb_1$ and it is relatively easy to find the value of $i$ that maximizes $$(c-b)i + (c-a)(U-Vi +c\lfloor\cdots\rfloor=(c-a)U -\left((c-a)V-(c-b))\right)i +c(c-a)\lfloor\dots\rfloor$$
In the original problem, this yielded:
$$y_i+4x_i = 232-5i+19\cdot 4\cdot\left\lfloor\frac{2i-2}{11}\right\rfloor$$
The floor function is $-1$ when $i=0$ and $0$ when $i=1,2,3.$ The value is decreasing for $i\geq 1$ but the case when $0$ has a big $-4\cdot 19$ added, so $i=1$ is the maximum value.
For the minimum, the original yielded:
$$y_i + 4x_i = i + 4\left((4-5i)\bmod 19\right)$$
This is minimized at $i=0.$ when restricted to $i\leq 3.$
You are gonna need some care if $\gcd(a,c)\not\mid b.$ You'll want to restrict $i$ such that $M-bi$ is divisible by $\gcd(a,c).$
So, for $(a,b,c)=(11,16,19)$ and $M=521$, you get $0\leq y\leq 7.$ You want to minimize/maximize $3y+8x.$ We solve $X=7,y=-4$ as before, because $a,c$ haven't changed.
For $i=0,\dots, 7$ let $y_i=i.$
For the minimum calculation, you get $x_i = 7(521-16i)\bmod 19$ and $7\cdot 16 \bmod 19 = 17$ and $7\cdot 521\bmod 19 = 18$ So $x_i=2i-1\pmod{19}.$
Then $$3i+8x_i=\begin{cases}3+8\cdot 18&i=0\\3i+(2i-1)&0<i<8\end{cases}$$
This gives us $i=1,x=1$ as the minimum, and $z_i=26.$
For the maximum calculation, you get $-4\cdot 521 = -190\cdot 11 + 6$ and $-4\cdot 16 = (-6)*11+2.$
So $$\left\lfloor\frac{-4(521-16i)}{11}\right\rfloor=-190+6i+\left\lfloor \frac{6-2i}{11}\right\rfloor$$
So we get the maximal:
$$\begin{align}x_i&=7(521-16i)+19(-190 +6i)+ 19\left\lfloor \frac{6-2i}{11}\right\rfloor\\ &=37 -2i + 19\left\lfloor \frac{6-2i}{11}\right\rfloor \end{align}$$
Then $$3y_i+8x_i = 111 - 15i + 19\cdot 8 \left\lfloor \frac{6-2i}{11}\right\rfloor$$
That's a decreasing function, so we get the minimum when $i=0$ and $x=37,y=0,z=6.$
From $$11\mid 2561-19z-17y -11(233-2z-2y) = -2+3z+5y$$
we have also $$11 \mid 4(5y+3z-2)-11(z+2y-1)=z-2y+3$$
So $z-2y+3 = 11t$ for some integer $t$. So we have $$z = 2y+11t-3$$ and $$x= 238-5y-19t$$ (from here we get $ 6\leq 238 -19t\implies t\leq 12$ ) so $$x+y+z = 235-2y-8t$$