# Euclidean Algorithm - find $\gcd(172, 20)$ and solve $172a + 20b = 1000$.

I am revising for an exam and have just realised that the euclidean algorithm questions in past exams are much harder than in homeworks! So i need some help please.

I have a question here, i already have the solution to it but i dont understand it that well, so i would like someone to please explain what is going on ect, and dont worry about avoiding giving me the full solution as i already have it so a full solution would be good!

Here is the question:

Use euclids Algorithm to find $gcd(172,20)$. Hence solve $172a + 20b = 1000$ giving all solutions in terms of parameter t. List any solutions for which $a,b>0$.

So it wants the answers in terms of parameter t, which is something i am not familiar with and cannot find in my books.

I have the solution in the solutions paper as

$$172= 8\times20+12$$ $$20=1\times 12 + 8$$ $$12=1 \times 8 +4$$ $$8=2\times 4+0$$

thus $gcd(172,20)=4$

then

$$4= 12-8=12-(20-12)=2\times 12 - 20$$

$$=2\times(172-8\times20)-20$$

$$=2 \times 172 -17 \times20$$

multiplying by 250 we get

$$1000=500 \times 172 -4250 \times 20$$

so one solution is $a=500, b=-4250$

So, I understand everything up until here!!

Now it says,

Generally, $$a=500-t \frac{20}{4}=500-t$$ $$b=-4250+t \frac{172}{4}=-4250+43t$$

To have $a,b>0$, we need $$500-5t>0, (100>t)$$ to have $a>b$ we need $$-4250+43t>0,(t>98.8)$$$Need$t=99$,$a=5$,$b=7$Could someone please help explain what is going on in this last bit of working out? I am pretty good at euclidean algorithm usually but havent seen this type before an am panicking bit as so close to exam! Any help appreciated how to find t and the other positive solutions would be great! Please could you show me exactly how it is done here as my lecturer is quite strict with us using his exact methods. Many thanks • Hint:$20\times\frac{172}{4}t = 172\times\frac{20}{4}t$; so subtracting$\frac{20}{4}t$to$a$is cancelled out by adding$\frac{172}{4}t$to$b$and vice versa. The rest ("To have$a,b>0$...) is just a pair of inequalities. – Peter Košinár Jan 3 '14 at 22:34 • @PeterKošinár I wonder why I nowhere read it, or thought that way! – jiten Jan 12 '18 at 6:37 ## 3 Answers Suppose you are finding all integer solutions of$ma+nb=k$where m and n are given integers (in this case, 172 and 20). After using the Euclidean algorithm to find$d=gcd(m,n)$, and then using this to get a particular solution$(a^{\prime},b^{\prime})$to the equation, all solutions are given by$a=a^{\prime}+t\frac{n}{d}$and$b=b^{\prime}-t\frac{m}{d}$where t is any integer. (This follows from the fact that$ma^{\prime}+nb^{\prime}=k=ma+nb$, so$m(a-a^{\prime})=n(b^{\prime}-b)$and therefore$\frac{m}{d}(a-a^{\prime})=\frac{n}{d}(b^{\prime}-b)$where$\frac{m}{d}$and$\frac{n}{d}$are relatively prime.) • Oh!! wow this is amazing! So i can apply this rule to any question... Thank you!! – Bernard.Mathews Jan 3 '14 at 22:36 • @Bernard.Mathews It is in fact the same we see in linear algebra: the general solution to a non-homogeneous system of lin. equations is given by the general solution to the associated homogeneous system plus a particular solution of the non-homogeneous sytem...:) – DonAntonio Jan 3 '14 at 22:45 • ah so it is.. havent done gaussian elimination or linear algebra for a while! Thanks for that i dont understand why it wasnt written in the solutions or notes like that! :) – Bernard.Mathews Jan 3 '14 at 22:46 • Sorry - it doesn't matter if you use a + sign in the first term and a - sign in the second (or vice versa), but I should have followed the way your lecturer did it to avoid confusion. (With my version of the answer, you would use$t=-99$) – user84413 Jan 3 '14 at 23:55 • You're welcome; I'm glad this helped! – user84413 Jan 4 '14 at 18:32 The important thing here is that $$172\cdot 2+20\cdot(-17)=4\implies 172\cdot 2\cdot 250+20\cdot (-17)\cdot 250=4\cdot 250=1,000\implies$$ $$172\cdot500+20\cdot(-4,250)=1,000$$ What you have written there is $$172a+20b=1,000\implies 172\cdot\left(a-\frac{20}4t\right)+20\left(b+\frac{172}4\right)=$$ $$=172a+20b+\underbrace{\left(\frac{-172\cdot 20+20\cdot 172}4\right)}_{\text{This is zero!}}t=172a+20b=1,000$$ You have $$172a + 20b = 1000$$ and you found one of the solutions,$a = 500, b = -4250$. I will try to explain parametrization and then finding specific solutions. Parametrisation You have two variables$a,b$and one equation so it can by parametrised by one parameter. Let's find$p_1$and$p_2$, s.t. $$172*(500 + p_1*t) + 20*(-4250 + p_2*t) = 1000.$$ We have $$86000 + 172 * p_1 * t - 85000 + 20*p_2*t = 1000.$$ so $$172 * p_1 * t + 20*p_2*t = 0.$$ We can divide by$gcd(20,172)=4$and get $$(43 * p_1 + 5*p_2)*t = 0.$$ Now, either$t$is$0$and we have the same solution or$(43 * p_1 + 5*p_2) = 0$which is true for$p_1 = 5$and$p_2 = -43$. So we have parametrization: a_t = 500 + 5*t b_t = -4250 - 43*t Solution Also, another condition is that : We are looking for such$t$that$a_t,b_t >0$so we simply require $$a_t = 500 + 5*t > 0 \text{ and } b_t = -4250 - 43*t > 0$$ Now $$-100 < t \text{ and } -98.8 > t,$$ so$t = -99$works. We get$a_t = 5$and$b_t = 7\$.

I hope this clarifies the idea in this particular example. In order to get general formulas just try with symbols.