I have to prove the following statement 2 ways, one by dividers and the other by the Euclidean Algorithm.
Show that for all positive integers $a$,
$hcf(6a + 8, 4a + 5) = 1$
The first way was easy enough. Let $x = hcf(6a + 8, 4a + 5)$. By definition of $hcf$ (or $gcd$), $x$ divides both $6a + 8$ and $ 4a + 5$. It must also divide $m(6a + 8) - n(4a + 5)$ for any integers $m$ and $n$. So suppose $m=2$ and $n=-3$, we get $x|(2(6a + 8) - 3(4a + 5))$ or $x|1$, so $x$ must be $1$ (Feel free to correct if I'm wrong or missing something).
The Euclidean Algorithm was a bit more confusing at the end.
I'm just going to write out all the steps to make it clear where I'm confused:
$6a + 8= 1(4a + 5) +(2a+3)$
$4a + 5= 1(2a+3) +(2a+2)$
$2a+3= 1(2a+2) +(0a+1)$
$2a+2= 2(0a+1) +(2a+0)$
$0a+1= 0(2a+0) +(0a+1)$
So would it be enough to say that the Euclidean Algorithm never finds a $hcf$ or $gcd$ as it never reaches a remainder $0$, so it must not have any common factors greater than 1? Or would I have to use some other additional property to complete the proof after this step?
Thank you