How to formally prove that $\gcd(a,1) = 1$ when $a \in Z$ I was trying to prove that $$\gcd(2a+1,9a+4) = 1 , a\in Z$$
My proof went like this:
$$ (9a+4) = 4(2a+1) + a$$
$$ (2a+1) = 2(a) + 1 $$
$$ \Rightarrow \gcd(9a+4,2a+1) = \gcd(2a+1,a)=\gcd(a,1) = 1$$
The last line of reasoning seems intuitive for me; The greatest common divisor of any integer with 1 is definitely one because the only divisor of 1 is itself. However, the question of how to prove it formally arose.
Thanks for any suggestions!
The formal definition for the greatest common divisor function is:
$$\gcd(n,m)=\max\{d\in\mathbb{N}:d\mid n \,\wedge\,d\mid m\}.$$
Set $m=1$. The only number $d$ that satisfies $d\mid n$ and $d\mid1$ is $1$. So we have
$$\gcd(n,1)=\max\{1\}=1.$$
using Euclid's Lemma, GCD (a,b) = GCD(a,a-b), , You can continue like this ,by subtracting smaller number from larger number.

${(2a+1 , (9a+4-2a-1))=(2a+1,7a+3)...  (a,a-1)=1}$

-|  but there is a faster way to do this.

${ GCD(2a+1,9a+4)= (2a+1, 4(2a+1)+a)= (2a+1,a)= (a,2a+1)=(1,a)=1 }$