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
 A: 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$$
A: 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.
A: 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.)
