Is it correct to write gcd(a,b) if a<b?

Question

While creating an algorithm to compute the greatest common divisor of two numbers I saw that — on various websites/books — when you have "gcd(a,b)" a is superior to b ; is it an obligation or am I right if I write gcd(a,b) where a < b ?

Answer 1

Yes $gcd(a, b) = gcd(b, a)$. But if you are writing a function that calculates gcd, ensure that the divider is smaller one, else you will waste more cycles. See the algorithm below.

From Donald Knuth (A popular Computer Scientist and the inventor of Tex):

Euclid's Algorithm:

Given two positive integers $a$ and $b$.

E0: [Ensure $a \geq b$] if $a < b$, exchange $a \leftrightarrow b$

E1: [Find remainder] Divide $a$ by $b$ and let $r$ be the remainder. $0 \leq r < b$.

E2: [Is $r=0$] If $r = 0$, the algorithm terminates; $b$ is the answer.

E3: [Interchange] Set $a \leftarrow b$, $b \leftarrow r$, go back to step E1.

Wasted Cycle example (without E0 step):

Let $a = 3$ and $b = 10$.

$$r \leftarrow a \bmod b$$ Thus, $r = a$

$$a \leftarrow b, b \leftarrow r$$

Now that $a>b$ the algorithm can compute the "real answer", but with the price of wasting cycles.

Answer 2

gcd(a,b) is well-defined whether a < b or a > b. Therefore if you write a function to calculate gcd(a,b) it should work in all cases.

Answer 3

It is correct, you even have $\gcd(a,b)=\gcd(b,a).$

Answer 4

There is no implicit order. One sometimes sees $\gcd\{a,b\}$, much in the spirit of $\min\{a,b\}$ and $\max\{a,b\}$