Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

4 Answers

up vote 3 down vote accepted

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

share|improve this answer
    
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
add comment

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

share|improve this answer
add comment

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.

share|improve this answer
add comment

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.