Finding the minimum of $z+d$?

Question

Suppose that $z, d\in \mathbb{Z}$ are a $3$-digit positive integer with $24\text{gcd}(z, d) = \text{lcm}(z, d)$. How can we find the minimum of $z+d$?

$$\begin{align}\text{gcd}(z, d)\text{lcm}(z, d) = zd&\iff 24\text{gcd}^2(z, d) = zd \\\ &\iff \text{gcd}(z, d) = \sqrt{\frac{zd}{24}}\end{align}$$

and

$$\begin{align}\text{gcd}(z, d)\text{lcm}(z, d) = zd&\iff \frac{\text{lcm}^2(z, d)}{24} = zd \\\ &\iff \text{lcm}(z, d) = \sqrt{24zd}\end{align}$$

If $\text{gcd}(z, d), \text{lcm}(z, d)\in \mathbb{Z}$ are both integers, then the numbers $\displaystyle \frac{zd}{24}, 24zd\in \mathbb{Z}$ both have to be a perfect square. However, I am not sure where this would lead us

Answer 1

You’re off to a great start! You have the equation in a form that’s much easier to work with:

$$ 24gcd(z,d)^2 = zd $$

Here’s an idea when you see a problem like this: play around with the numbers until you find a solution to it, and only then look at minimizing your other expression, $z + m$ in this case.

Try that and see if it gets you anywhere. Otherwise keep reading.

It would be “nice” if the solution was such that $gcd(z,d)$ was 1. It simplifies the equation greatly. It becomes:

$24(1^2)=24=zd$

Now by inspection, 8 and 3 satisfy the conditions. Their product is 24 and their gcd is 1. The only other pair which satisfies that is 24 and 1, but clearly their sum is greater, so we can ignore it. Now the problem lies in proving that this minimizes $z+d=8+3=11$

Notice that if some integers $a$ and $b$ satisfy the equation, then any scalar multiples of them also satisfy the equation. This is easy to show. This means that by dividing by those scalars, you can get a solution with a gcd of 1 whose sum is strictly lesser. Therefore, our guess earlier was correct! 8 and 3 is the only solution with a gcd of 1, therefore 11 is the minimum.

Now to apply the other condition, that they are three digit numbers. We now know that all solutions are scalar multiples of (8,3), so we simply multiply this by the minimum scalar to bring it in the range, 34. So the solution which minimizes in that range is $z+d=34(8+3)=34(11)=374$

Answer 2

As the entire problem is symmetric with respect to $z,d$, we may assume, without loss of generality, that $z\leq d$. Also, to ease up on space, I will define $g := \gcd(z,d)$.

In these terms, your equation $24\text{gcd}^2(z, d) = zd$ can be written $$24 = \left(\frac{z}{g}\right)\left(\frac{d}{g}\right)$$ where we note that $\gcd(z/g, d/g) = \gcd(z,d)/g = 1$, so this is a factorization of $24$ into relatively prime positive integers. There are only two ways for this to happen with $z \leq d$: $$\begin{array}{cccc}(1) & \frac{z}{g} = 1, \frac{d}{g} = 24, & \text{ or equivalently } & z=g, d=24g \\ \\ (2) & \frac{z}{g}=3, \frac{d}{g} = 8, & \text{ or equivalently } & z= 3g, d=8g.\end{array}$$

We can dispose of the first case quickly by noting that if $z,d$ are three-digit numbers, then $g = z \geq 100$ and $2400 \leq 24g = d < 1000,$ which is a contradiction. Therefore we're left with $z=3g$ and $d=8g$.

Once again applying the assumption that $z$ is a three-digit number: $3g = z \geq 100$ gives $g \geq 34$ so $$z+d = 3g + 8g = 11g \geq 374.$$

Now we need to check that our candidate $z,d$ are valid. When $g=34$, we have $$z = 3(34) = 102, \\ d = 8(34) = 272$$ both of which are three-digit numbers, and $$\gcd(z,d) = \gcd(102,272) = 34 \\ 24(\gcd(z,d))^2 = 24(34^2) = 27744 = (102)(272)=zd.$$

Since everything checks out, we can conclude the minimum of all such $z+d$ is $374$.