For example:

• #\max(3,8)=8# and #\max(-3,-8)=-3#, while
• #\min(3,8)=3# and #\min(-3,-8)=-8#.

Examples:

\[ \begin{array}{rclcrcl}\gcd(2,3)&=&1&\phantom{xxxxx}&{\rm lcm}(2,3) &=&6\\ \gcd(4,6)&=&2&\phantom{xxxxx}&{\rm lcm}(4,6) &=&12\\ \gcd(4,4)&=&4&\phantom{xxxxx}&{\rm lcm}(4,4) &=&4\end {array}\]

Let #a# and #b# be natural numbers. There are always numbers that divide both #a# and #b#, because #1# is such a number.

Any number that divides #a# and #b#, is less than or equal to #\min(a,b)#. Therefore, there is a greatest common divisor, and \[1\le \gcd(a,b)\le\min(a,b)\tiny.\]

There is always a number that is a multiple of both of #a# and #b#, being #a\times b#. On the other hand such a common multiple is greater than or equal to #\max(a,b)#. Therefore, there is a least common multiple and \[\max(a,b)\le {\rm lcm}(a,b)\le a\times b\tiny.\]

There is also a greatest common divisor and a least common multiple of more than two numbers. For example, \[ \begin{array}{rclcrcl}\gcd(2,3,6)&=&1&\phantom{xxxxx}&{\rm lcm}(2,3,6) &=&6\\ \gcd(2,4,6)&=&2&\phantom{xxxxx}&{\rm lcm}(2,4,6) &=&12\\ \gcd(4,6,8)&=&2&\phantom{xxxxx}&{\rm lcm}(4,6,8) &=&24\end {array}\] In general, we have, for three natural numbers #a#, #b#, #c#:

\[ \gcd(a,b,c)=\gcd\left(\gcd(a,b),c\right)\tiny.\]

The definition #\gcd(a,0)=0# satisfies the definition, because #a# divides both #0# and itself and is the largest natural number having that property.

All equalities in the last two lines of the definition indicate that for the definition of #\gcd# and #\rm lcm# the sign does not matter.

The values of #\gcd# and #\rm lcm# are never negative.

Example: #\gcd(15,-20)=\gcd(15,20)=5#.

The proof will be omitted, but we note that all the statements follow from rules 3 and 4.

Some examples:

1. #\gcd(42,28)=\gcd(7\times 6,7\times4) =7\times\gcd(6,4)= 14#.
2. The number #14# is the remainder of the division of #42# on #28#, so #\gcd(42,28) = \gcd(14,28)#.
3. #\gcd(42,28)=\gcd(2\times3\times7,2^2\times7)=2\times7=14#, as #2# is the highest power of #2# dividing both #42# and #28#, similarly for #7#, and #1# is the highest power of #3# dividing both #42# and #28#.
4. #{\rm lcm}(42,28)={\rm lcm}(2\times3\times7,2^2\times7)=2^2\times3\times7=84#, as #2^2# is the highest power of #2# dividing #42# or #28#, and similarly for #3# and #7#.
5. #{\rm lcm}(42,28) = 84=42\times 2=\frac{42\times 28}{14}=\frac{42\times 28}{\gcd(42,28)}#.

For the remainder #t# in step 2, the formula #t=r-\left\lfloor \frac{r}{s}\right\rfloor\times s# applies.

Each instance of the pair #\rv{r,s}# satisfies #\gcd(r,s)=\gcd(a,b)#:

1. In the beginning because #\rv{r,s}# is equal to #\rv{a,b}# or #\rv{b,a}#,

2. At the end of each step w, because of gcd-rule 2.

When we are done with step 2, then #s=0# holds and #\gcd(a,b)=\gcd(r,0)=r# follows from this. Hence, the output indeed provides #\gcd(a,b)#.