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!
 A: 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.$$
A: Let $D_a$ be the set of divisors of $a$. Note that $-1, 1 \in D_a$. On the other hand, $D_1 = \{\pm 1\}$.
Thus, $D_a \cap D_1 = \{\pm 1\}$. By definition, the gcd is the largest element in this (finite) set. Since $-1 < 1$, we get $\gcd(a, 1) = 1$.

If your definition works with positive integers, then just remove $-1$ everywhere from the above argument.

Some also define $\gcd(a, b)$ (where at least one of $a$ or $b$ is non-zero) to be the smallest positive element in $$S_{a, b} = \{am + bn : m, n \in \Bbb Z\} \subset \Bbb Z.$$
With this definition, it is clear that $\gcd(a, 1) \ge 1$ (since $1$ is the smallest positive integer).
On the other, $1 \in S_{a, 1}$ since $1 = a\cdot0 + 1\cdot1$ and thus, $1 \ge \gcd(a, 1)$.
Again, we get $\gcd(a, 1) = 1$.

Note that all the above arguments are also valid if $a = 0$.
A: 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 }$
