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

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!

closed as off-topic by Namaste, Leucippus, Xander Henderson, user99914, user284331Apr 20 '18 at 1:07

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Namaste, Leucippus, Xander Henderson, Community, user284331
If this question can be reworded to fit the rules in the help center, please edit the question.

• 30*2 + 42*3 + 70*2 - 105*3=11 – kvantour Apr 19 '18 at 18:21
• thirty and seventy will force a 10, 105 will force a 5, and 42 will force a 2, all but the 105 are dividable by 2. This help? – bukwyrm Apr 19 '18 at 18:22
• Have a look at this, it might be a starting point mathworld.wolfram.com/DiophantineEquation.html – kvantour Apr 19 '18 at 18:23

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$

• That's probably the gentlest way. – fleablood Apr 19 '18 at 19:27

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.

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$.

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$

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.