what is the smallest positive integer in the set $\{24x+60y+2000z \mid x,y,z \in \mathbb{Z}\}$!

I cant understand how to do it please help me. Thanks in advance my question is what is the smallest positive integer in the set $\{24x+60y+2000z \mid x,y,z \in \mathbb{Z}\}$! its options are given $2,4,6,24$

Solution 1:

As $(24,60)=12,$

$24a+60b=12(2a+5b)$ will be divisible by $12$ for integers $a,b$

Using Bézout's Lemma/identity, we can find integers $x,y$ such that $24x+60y=12$

In fact $60(1)+24(-2)=12$

Now, $(12,2000)=4,$ we can find integers $p,q$ such that $12p+2000q=4$

By actual division $2000=167\cdot12-4\implies 167\cdot12-2000=4$

$$\implies 167\{60(1)+24(-2)\}-2000=4$$

$$\implies 167\cdot60+24(-2\cdot167)+2000(-1)=4$$

This is the smallest as $24x+60y+2000z=4(6x+15y+500z)$ will always be divisible by $4$ for integers $x,y,z$

Solution 2:

The set in question is a subgroup of $\mathbb{Z}$, and hence generated by a single element $c \in \mathbb{N}$, which is also the smallest positive integer in the set. This element must be a common divisor of 24, 60, and 2000 (since each of those elements is in this set). It is not too hard to see that $c$ must be the greatest common divisor of all these three numbers, which is 4.

Solution 3:

$$24x+60y+2000z=4(6x+15y+500z)$$ Now, $$\gcd(6,15,500)=1\Rightarrow 6x+15y+500z=1$$ for some $x,y,z\in \mathbb{Z}$ by using the generalized Bezout's identity. Hence $4$ is the answer.

In general the minimum positive integer value that the set $\displaystyle \left\{\sum_{k=1}^n a_kx_k\big|x_k\in\mathbb{Z},1\le k\le n\right\}$ can give is $\gcd(a_1,a_2,\cdots\ ,a_n)$.