About Greatest Common Divisor

Normally, there are two ways to define the greatest common divisor.
Definition A:
$p=gcd(A)$ iff
i. $p|s$ if $s\in A$
ii. $a|p$ if a is a common divisor of $\latex A$
Another equivalent definition B is:
$p=gcd(A)$ iff $p$ is the largest common divisor.
Update:
OK, I think I made a mistake last night. In Definition A that GCD is the common divisor that divides all common divisors, it needs extra effort to prove such common divisor exists. Once this is done, the two definitions are trivially equivalent.

Theorem. $A\Leftrightarrow B$
Proof. $A\Rightarrow B$ : Suppose q is a common divisor of A and $q>p$ , we have $p|q$ , hence $p\geq q$ . Contradiction.
$B\Rightarrow A$ : It is pretty hard. Actually I’m considering using the following theorem:

Theorem. Let $a_1,a_2,\dots,a_k$ be integers, not all zero. Then, there exist integers $x_1,x_2,\dots,x_k$ s.t. $\gcd(a_1,\dots,a_k)=a_1x_1+\dots+a_kx_k$

I’ll update once I found the proof.

There are three ways to establish the GCD theory, according to by Chengdong Pan. They all depend on Long Division algorithm, but via different methods, i.e. least common multiplier of common divisors, Bezout’s identity and Euclidean Algorithm, respectively.

1. Least common multiplier of common divisors.
Lemma If $a_i|S \mbox{ for }i=1,2,\dots,n$ , then $lcm(a_1,a_2,\dots,a_n)|S$
Proof.
Let $L=lcm(a_1,a_2,\dots,a_n)$ , by Long Division, if $s\in S$ , $s=qL+r,0\leq r\leq L-1$ . Since $a_i|s,a_i|L$ , we have $a_i|r$ for all $i=1,2,\dots,n$ . Hence $r=0$

Theorem $gcd(S)=L=lcm(a_1,a_2,\dots,a_n)$ , where $a_n$ are all common divisors of $S$ .
Proof.
By definition, L divides all common divisors of $S$ , so it satisfies Def A(i). By the lemma, it satisfies Def A(ii).

2. Bezout’s identity.
Theorem Suppose $a_1,a_2,\dots,a_n$ are integers s.t. $\sum a_i^2\neq 0$ .
(i) $gcd(a_1,\dots,a_n)=min\{s=\sum_{i=1}^na_ix_i:x_i\in \mathbb{Z}(1\leq i\leq n),s>0\}$
(ii) There exists $x_1,\dots,x_n$ s.t. $gcd(a_1,\dots,a_n)=\sum_{i-1}^na_ix_i$

Proof.
Since $\sum_{i=1}^na_i^2>0$ , $S$ is nonempty. Here $S$ denotes the set $\{s=\sum_{i=1}^na_ix_i:x_i\in \mathbb{Z}(1\leq i\leq n),s>0\}$ . By the minimum number principle, S has minumum, denotes as $s_0$ . Obviously if $d$ is a common divisor of $a_1,\dots,a_n$ , $d|s_0$ . Therefore it satisfies Def A(ii).
If there is $a_j$ s.t. $s_0$ doesn’t divide $a_j$ , by Long Division, $a_j=qs_0+r$ , $r=a_j-qs_0\in S$ , but $r<s$ , contradiction. Hence $s_0$ is a common divisor of $a_1,\dots,a_n$ . Therefore $s_0=gcd(a_1,\dots,a_n)$ .

By the theorem, we can derive the gcd of $a_1,\dots,a_n$ by multiple times of Euclidean algorithm.

By Chengdong Pan, “It is the ideas, conceptions, methods, structures of theory that are the most precious and important part of mathematics”. I’ll update once I have further understanding of the GCD theory.

This entry was posted on Thursday, September 16th, 2010 at 1:00 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

Marine's Math