Find integers $a$, $b$, $c$, $d$ such that $30a + 42b + 70c + 105d = 11$, or prove that no such integers exist

Question

Find integers $a$, $b$, $c$, $d$ such that $30a + 42b + 70c + 105d = 11$, or prove that no such integers exist

I seem to be struggling greatly with this problem. I am unsure where to begin. There are so many variables I do not know how to prove whether this problem has integers that exist or not. Please help if you are able! Thanks so much!

Answer 1

For a systematic way to solve this we can use the result that, given two integers $x$ and $y$, there exist integers $a$ and $b$ such that $$ax+by=gcd(x,y)$$

where $gcd(x,y)$ is the greatest common divisor of $x$ and $y$.

Now, $gcd(42,30)=6$, $gcd(105,70)=35$ and $35-4*6=11$ so we should be able to use these.

1. $3*30-2*42=6$
2. $105-70=35$

Combining these we get $105-70 -4*(3*30-2*42)= 105- 70 - 12(30) + 8(42)=11$

Answer 2

We have $gcd(30,42,70,105)=gcd(30,42)\cdot gcd(70,105)=gcd(6,35)=1$, so we can find such numbers, by using the Euclidean algorithm successively.

Answer 3

This is sort of a multi variable Bizout's Lemma. $\gcd(30,42,70,105) = 1$ so there must be some $30a + 42b + 70c + 105d = 11 \gcd(30,42,70,105)$

Okay... so $30a + 42b + 70c + 105d = 5(6a+ 14c + 21d) + 42b$.

$5$ and $42$ are relatively prime so we can solve $5E + 42b = 11$

By Euclids Algorithm.

$2 = 42*1 - 8*5$

$1 = 5 - 2*2 = 5-2(42*1 - 5*8) = 17*5 - 2*42$.

So $11 = 17*11 + 42*(-22)$.

So let $b = -22$ and we need to solve for $6a + 14c +21d = E = 187$

Now $14c + 21d = 7(2c + 3d)$ so we need to solve $6a + 7F = 187$

Well, $1 = 7 - 6$ so $187 = 7*187 - 6*187$.

So let $a = -187$ and $F = 187 = 2c + 3d$

Okay this is kind of like throw hammers at flies but.

$1 = 3-2$ so $187 = 3*187-2*187$.

So let $c = -187$ and $d = 187$.

So we have $a = -187; b=-22; c=-187$ and $d = 187$ so

$30a + 42b + 70c + 105d = -30*187 -42*22 -70*187 + 105*187=$

$187(-30 -70 + 105) - 22*42 = $

$187*5 - 22*42 = $

$11*17*5 - 11*2*42 = $

$11(17*5 - 2*42) = $

$11(85 - 84) = 11$.

Ta-da!

====

just because I am obsessive:

$\gcd(105,42) = 31$ and $105 - 2*42 = 21$

So if we let $b = -2d$ the $42b + 105d = -2*42d + 105d = 21d$.

So if $b=-2d$ we need to solve for $30a +70c + 21d=11$

$\gcd(70,30) = 10$ and $70 - 3*30 = 10$

so if we let $a = -2c$ we get $30a + 70cc = -2*30c + 70c =10c$

So if $a=-2d$ we need to solve $10c + 21d = 11$.

Well $c = -1$ and $d=1$ is an obvious answer.

So $a = -2c = 2; b=-2d = -2; c=-1; d= 1$ yields:

$30*2 + 42*(-2) + 70*(-1) + 105*1= 60-84 -70 + 105 = 11$.

Answer 4

There are several ways to solve this problem in general. In this particular case, there is a simple systematic method. The coefficients are all divisors of $210$, so we can write the equation as:

$$ 0 = \frac{30a+42b+70c+105d-11}{210}=\frac{a}7+\frac{b}5+\frac{c}3+\frac{d}2-\frac{11}{210} \tag{1}$$

We find $\;d\;$ must be odd to remove the factor of $2$ in the denominator of $11/210$. Thus we have:

$$ 0 = \frac{30 a + 42 b + 70 c + 105 (1 + 2 d_0) - 11}{210}=\frac{a}7+\frac{b}5+\frac{c}3+d_0+\frac{47}{105} \tag{2}$$

We find $\;c\;$ must be of the form $2+3c_0$ to remove the factor of $3$ in the denominator of $47/105$.

$$ 0 = \frac{30 a + 42 b + 70 (2 + 3 c_0) + 105 (1 + 2 d_0) - 11}{210} =\frac{a}7+\frac{b}5+c_0+d_0+\frac{39}{35} \tag{3} $$

We find $\;b\;$ must be $3+5b_0$ to remove the factor of $5$ in the denominator of $39/35$. We now have:

$$ 0 = \frac{30 a + 42 (3 + 5 b_0) + 70 (2 + 3 c_0) + 105 (1 + 2 d_0) - 11} {210} = \frac{a}7\! + \!b_0\! + \!c_0\! + \!d_0\! + \frac{12}7 \tag{4}$$

We find $\;a\;$ must be $2+7a_0$ to remove the factor of $7$ in the denominator of $12/7$. We now have:

$$ 0 = \frac{30 (2 + 7 a_0) + 42 (3 + 5 b_0) + 70 (2 + 3 c_0) + 105 (1 + 2 d_0) - 11}{210} = a_0\! + \!b_0\! + \!c_0\! + \!d_0\! + \!2 $$

Finally, we have to find solutions to $-2 =a_0 + b_0 + c_0 + d_0$ in integers which is very easy to do.

Answer 5

First things first:
$30 = 2\cdot 3\cdot 5$
$42 = 2\cdot 3\cdot 7$
$70 = 2\cdot 5\cdot 7$
$105 = 3\cdot 5\cdot 7$

So although the complete set do not have a factor that is common to all of them - meaning there will be a solution - any $3$ of them willl have a common factor. So we're going to need all four to get below any common factor and down to a linear combination giving $1$.

So what I would do is use the numbers in two pairs (eg. $(30,70)$ and $(42,105)$) to find the linear combinations in each case to give the respective $\gcd$s:

$70-2\cdot 30 =10\quad(=\gcd(30,70))$
$105-2\cdot 42 =21\quad(=\gcd(42,105))$

Then it's easy to combine these $\gcd$s for the result needed:

$21-2\cdot 10 =1$

giving

$1\cdot 105 - 2\cdot 42 -2\cdot70 + 4\cdot 30 = 1$