How to formally prove that $\gcd(a,1) = 1$ when $a \in Z$

Question

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!

Answer 1

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

Answer 2

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

Answer 3

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 }$