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.

Which of the following correct?

$\gcd(x,x\times2) = x$

or

$\gcd(x,x\times2) = x/2$

I am a programmer. I am new to mathematics.

share|improve this question
2  
The "g" in $\gcd$ means greatest. –  J. M. Sep 24 '11 at 12:47
    
If $x$ is positive, the gcd is $x$. Definitely not $x/2$. Thus $\gcd(40,80)=40$. –  André Nicolas Sep 24 '11 at 12:48
    
@André, Please make that an answer so I can accept. –  musicwithoutpaper Sep 24 '11 at 13:10
    
If you want to think about gcd's, learn Euclid's algorithm. See the Wikipedia article on it. Notice that, for example, the divisors of $24$ are $1,2,3,4,6,8,12,24$, and the divisors of $60$ are $1,2,3,4,5,6,10,12,15,20,30,60$, so the COMMON DIVISORS of $24$ and $60$---just the numbers that those two lists share in common---are $1,2,3,4,6,12$. "gcd" means "greatest common divisor", so it's the largest one of those. –  Michael Hardy Sep 24 '11 at 15:33

2 Answers 2

up vote 11 down vote accepted

If $a$ and $b$ are positive integers, the greatest common divisor of $a$ and $b$, often called $\gcd(a,b)$, is the largest integer $d$ such that $d$ divides both $a$ and $b$. So for example $\gcd(15,21)=3$, since $3$ is the largest integer that divides both of $15$ and $21$. And $\gcd(50, 21)=1$, for certainly $1$ divides $50$ and $21$, but nothing bigger does.

Let $x$ be a positive integer. Then $\gcd(x,2x)$ is the largest integer $d$ such that $d$ divides both $x$ and $2x$. Certainly $x$ divides both $x$ and $2x$, and nothing bigger than $x$ can be simultaneously a divisor of $x$ and a divisor of $2x$. Thus $\gcd(x,2x)=x$. In the concrete example of the post, $40$ is the largest integer that divides both $40$ and $80$, so $\gcd(40,80)=40$. The number $20$ is a common divisor of $40$ and $80$, but it is not the greatest common divisor of $40$ and $80$.

Comments: (a) Any integer $n$ greater than $1$ has at least two divisors, namely $1$ and $n$. It is all too easy to forget about them, since they are so boring. But they are divisors of $n$. We have for example $\gcd(3,5)=1$, even though sloppily someone might say that "nothing" divides both $3$ and $5$. However, something does, namely $1$.

(b) If $a$ and $b$ are two positive integers, we can in principle find $\gcd(a,b)$ as follows.

(i) List all the positive integers that divide $a$. In the case of $a=40$ these would be $1$, $2$, $4$, $5$, $8$, $10$, $20$, and $40$.

(ii) List all the positive integers that divide $b$.

Search for the largest integer which appears in both lists. That integer is $\gcd(a,b)$.

Obviously the procedure we have just described is hopelessly slow. Finding the greatest common divisor is important in many problems. Luckily, there is a very fast algorithm, the Euclidean Algorithm, for computing the greatest common divisor of two given numbers.

share|improve this answer
    
This is a much longer answer than the one I intended to accept when I asked you to turn the comment into an answer, but I accept anyway. –  musicwithoutpaper Sep 24 '11 at 19:42
4  
I wanted to be reasonably complete, for someone who later looked up stuff on the site. –  André Nicolas Sep 24 '11 at 19:53

I will supplement André's comment with the following remark:

In mathematics, we almost always consider cases which you might consider to be trivial.

I suspect that in the case of gcd(40,80), you were suspicious about the answer of 40 because it was identical to one of the numbers you're taking the divisor of, whereas you might think that a divisor has to be smaller somehow. But of course, it's perfectly fine as a divisor. Because 40 evenly divides itself (40 ÷ 40 = 1), then 40 is certainly a divisor of itself; and it is also a divisor of 80; so 40 is a common divisor of 40 and 80. Because 40 has no larger divisors, it follows that there are no common divisors which are larger than 40; so 40 is the greatest common divisor.

It's similarly true that N is a divisor of itself, for any integer N, even for N = 0. (This is because the divisor relationship is technically defined by many not in terms of division, but in terms of multiples: a | b if and only if b is an integer multiple of a, and zero certainly is a multiple of itself. Similarly, any integer N is an integer multiple of itself — even if a somewhat boring one.)

Similarly, mathematicians talk about sets S being subsets of themselves, vector spaces V being subspaces of themselves, and so forth. We could define things in order to exclude these "trivial", perhaps even "smart-alecy" sorts of answers, but by including them we obtain mathematical theories, structures, and lines of reasoning which are more elegant than we might otherwise, and that almost always makes it worthwhile to include such trivial special cases.

As a programmer, such trivial special cases are ones which you should be careful to do error-checking for, not only when doing math, but in any situation where some boundary case exists, because even if you aren't planning for them in your code, they may naturally arise due to circumstances you don't start off imagining.

share|improve this answer

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.