3
$\begingroup$

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.

4 Answers 4

3

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

  • 0
    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.2010-10-17
  • 0
    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?2010-10-17
  • 0
    I agree. The condition $d|a$ is already stated in "Then any $d\in Z : d | a, d | b$".2010-10-17
2

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

0

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

0

By definition $$\gcd(a,b)\mid a,b$$

the greatest common divisor. So if $\gcd(a,b)=|a|$ then $ |a|\mid b$.


Alternatively consider $(a),(b)\subseteq\mathbb{Z}$ and notice that $(|a|)=(a)$ as ideals since $-1\in\mathbb{Z}$. Thus, by the Euclidean algorithm, $$(a)+(b)=(a)$$ which means that $(b)\subseteq (a)$. This means in particular that $a\mid b$, and therefore also $|a|\mid b$.