# Show that $\gcd(a,b)=|a| \iff a | b$

I'm reading A Computational Introduction to Number Theory and Algebra, which can be found here as a free download. From the book's exercises, I'm stuck with a proof to show that $\gcd(a,b)=|a| \iff a | b$.

My current reasoning goes as follows: since $\gcd(a,b) = |a|$, we see that $a\mathbb{Z} + b\mathbb{Z}= |a|\mathbb{Z}$.

Since $a|b \iff az = b$, for some $z \in \mathbb{Z}$, we see that both $az, b \in |a|\mathbb{Z}$.

So there exist $s, t \in \mathbb{Z}$ such that $as + bt = az = b$, which is true for $s = 0$ and $t = 1$.

Q.E.D.?

I guess that in the end my reasoning is wrong, but I can't explain it.

-

Assume that $a,b\in\mathbb{N}$. I use the following definition of $D=\gcd (a,b)$:

(i) $D$ is a common divisor of $a$ and $b$;

(ii) Every integer $d\in\mathbb{N}$ which is a common divisor of $a$ and $b$ divides $D$.

Proposition 1: If $\gcd (a,b)=a$, then $a|b$.

Proposition 2: If $a|b$, then $\gcd (a,b)=a$.

Proof: Since $a|a$ and $a|b$, then any integer $d$ such that $d|a$ and $d|b$ satisfies also the condition $d|a$.

From $a|a$, $a|b$ and $d|a$ we conclude that $\gcd (a,b)=a$.

-
Thanks! The solution was simpler than I thought. It seems that I took a wrong turn in my proof early on. Trying to prove both sides of the biconditional in one equation makes the proof a mess. Your approach to split the statement into two propositions makes the problem easy to understand. –  Rutherford Oct 17 '10 at 9:11
You are welcome! –  Américo Tavares Oct 17 '10 at 10:14
After some consideration I made a slight modification to your proof: By the definition of $gcd$, we know that $a | a$ and $a | b$. Then any $d \in Z : d | a, d | b$, must satisfy $d \le a$. From $a|b$, $a|b$, and $d|a$ we conclude that $gcd(a,b) = a$. I thought that saying $d \le a$ would make the argument more clear. What do you think? –  Rutherford Oct 17 '10 at 10:29
I agree. The condition $d|a$ is already stated in "Then any $d\in Z : d | a, d | b$". –  Américo Tavares Oct 17 '10 at 11:03

It is true that the final assertion holds if $s=0$ and $t=1$, but it is not true that that $as+bt = az = b$ can only hold if $s=0$ and $t=1$ is false. Take, for example, $a=2$ and $b=4$. Then $(-5)a + 3(b) = b$.

Remember that, by definition, gcd$(x,y)|x$ and gcd$(x,y)|y$. That gives one implication.

For the converse, remember that $d|x$ and $d|y$ implies $d|$gcd$(x,y)$.

-

HINT $\rm\ \$ If $\rm\ a\:|\:b\$ then $\rm\ c\:|\:a,b\ \iff\ c\:|\:a\ \ \$ [and conversely via $\rm\ c = a\:$]

Thus $\rm\ a,\:b\$ and $\rm\:a\:$ have the same common divisors $\rm\:c\:$, hence the same greatest$\$ common divisor.

-

Theorems to be used:

1. If $n \in \mathbb{Z}$, then the largest positive integer that divides $n$ is $|n|$.
2. If $a|b$, then the set of positive divisors of $a$ is contained within the set of the positive divisors of $b$; but the vice-versa is not possible.

Using Theorem 2, we know that $\gcd(a,b)$ will be the highest positive divisor of $a$ (why does that happen?). Theorem 1 suggests that the highest positive divisor of $a$ shall be $|a|$. In other words, $\ \ \gcd(a,b) = |a|$.

-