For all $n \in N, gcd(5n+8,3n+5)=1$
$\frac{5n+8}{3n+5}$
I can multiply $3n+5$ just once, so I would have $2n+3$ as the remainder
$(5n+8)-(3n+5) = 5n+8-3n-5 = 2n+3$
the linear combination would be $1 \cdot (3n+5)+(2n+3)$
for $gcd(3n+5,2n+3)$
$\frac{3n+5}{2n+3}$, I can multiply $2n+3$ once and my remainder would be $n+2$
$(3n+5)-(2n+3) = 3n+5-2n-3 = n+2$
The linear combination is $1 \cdot (2n+3) +(n+2)$
For $gcd(2n+3,n+2)$, I can multiply $n+2$ twice, but I am stuck with a $-1$ remainder. Since $-1 \neq 1, gcd(5n+8,3n+5) \neq 1$
Question: Prove for all $ n \in N,gcd(2n+1,9n+4)=1$
Attempt: I want to use Euclid's Algorithm because it seemed to be easier than what my book was doing which was manually finding the linear combination.
Euclid's Algorithm states that we let $a,b \in N $. By applying the Division Algorithm repe...
