elementary number theory - 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

Answer

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