Integers and common factor

The Bézout's identity states that the Diophantine equation $ax+by=c$ has solutions in integers $x,y$ if and only if $d \vert c$ , where $d=\text{gcd}(a,b)$ . (This finishes of the problem!)

Here is the idea of what is being used in the above lemma.

$24x+42y=2018 \implies 6(4x+7y)=2018 \implies 6\vert 2018$ which is not true. Hence no solutions exists in integers.

$48x+84y=2018 \implies 12(4x+7y)=2018 \implies 12\vert 2018$ which is not true. Hence no solutions exists in integers.

But solutions do exist for the equation $28x+82y=2018$ . The equation can be simplified as $2(14x+41y)=2018 \implies 14x+41y=1009.$ Note that there exist solutions to the equation $14x+41y=1$ , as the Euclidean algorithm can be written backwards to find the solutions. Now you can just scale up by a factor of $1009$ to get solutions to the equation $14x+41y=1009.$ Again scaling up by a factor of 2, we get solutions to the equation $28x+82y=2018$ .

Thus there exist solutions only to the equation $28x+82y=2018$ .

Note : For the sake of verification, one of the solutions is $x=34, y=13$

The 2nd answer (24x + 42y) is divisible by 3. (Both of its parts are divisible by 3). And 2018 is not divisible by 3. The 3rd answer (48x + 84y) is divisible by 4. (Both of its parts are divisible by 4). And 2018 is not divisible by 4. So the 1st answer is the only answer that is possible. Note that (28 x 3 - 82) = 2. The largest multiple of 82 that is less than 2018 is 24.And 24 x 82 = 1968. And of course 2 x 25 = 50. So (24 x 82 + 25 x 2) = 2018. And so 24 x 82 + 25 x (3 x 28 - 82) = 2018. Which gives us 75 x 28 - 82 = 2018. | It would have been nicer to get x and y that were both positive. wouldn't it. So note that (-82) x 28 + (28) x 82 = 0. And the highest common denominator of 28 and 82 is 2. (28 = 2^2 x 7 and 82 = 2 x 41). So (-41) x 28 + (14) x 82 = 0. So adding this once to the original answer of (75) x 28 + (-1) x 82 gives (34) x 28 + (13) x 82 = 2018 which we wanted! Incidentally, this seems to be the only 'couplet' of x and y that are both positive. Because if you were to take another '41 lots of 28' away from the '34 lots of 28' then the value for x would be negative (-7). If you allow for one of x or y to be negative then there will be an infinite number of answers! Regards, David