Given two integers n and m, their Greatest Common Divisor or GCD is defined as the largest number that divides into both n and m. So, given 6 and 35, for example, we have that the GCD(6,35) = (2·3,5·7) = 1, and likewise, the GCD of 121 and 44, or GCD(121,44) = GCD(11·11,4·11)= 11 because 11 is the largest number that divides into both 121 and 44.

But there is a very unexpected application of the GCD going on every second inside our own heads, as Manfred Schroder* goes on to say:

“An interesting and most surprising application of the GCD occurs in human perception of pitch: the brain, upon being presented with a set of harmonically related frequencies, will perceive the GCD of these frequencies as the pitch. Thus, the subjective pitch of the two-tone chord (320 Hz and 560 Hz) is (320,560) = 80Hz, and not the difference frequency (240 Hz).

Upon a frequency shift of +5Hz applied to both frequencies, the GCD drops to 5 Hz; and for an irrational frequency shift, the GCD even drops to 0 Hz. But that is not what the ear perceives as the pitch. Rather it tries to find a close match in the range of pitches above 50 Hz. For the frequencies 325 Hz and 565 Hz such a match is given by 81 Hz, which is the GCD of 324 Hz and 567 Hz – close to the two given frequencies.

Note that the concept that pitch is given by the difference frequency or “beat” frequency has been beaten: if both frequencies are shifted by the same amount, their difference remains unchanged. Yet psycho-acoustic experiments clearly show that the perceived pitch is increased, from 80 Hz to about 81 Hz in our example, just as the amplified GCD model predicts.

What this tells us is that the human brain switches on something like a GCD spectral matching computer program when listening to tone complexes. Fascinating? Indeed. Unbelievable? Well, the brain has been caught doing much trickier things than that.”

[ Technical Notes ]

The GCD appears in the solution to many, seemingly unrelated, problems. For example, take n jugs with capacities of L1, L2, . . . , Ln liters. What amounts k of water (or wine) can be dispensed by these n/1 jugs?

Answer: k must be a multiple of the GCD. Now, to better understand the GCD and its counterpart, the LCM, we will need more math.

Fundamental theorem of arithmetic. Each natural number n > 1 is either a prime or can be uniquely factored into primes

$n=p_{1}^{{{e}_{1}}}p_{2}^{{{e}_{2}}}p_{3}^{{{e}_{3}}}...p_{k}^{{{e}_{k}}}...p_{r}^{{{e}_{r}}}=\prod\limits_{i}{p_{i}^{{{e}_{i}}}}$

where the order of the prime factors makes no difference.

Proof. There are only two cases to consider. Either n is prime or n is composite. If n is prime, then the theorem is obviously true, by definition. Therefore, the only case we need to consider is when n is composite.

If n is composite, then there exists an integer p where p divides into n so that and 1 < p < n must be true because n is, by definition, greater than 1, and so if p divides into n, then p must be smaller than n, hence 1 < p < n as just stated. [this proof is still being written, and will be completed by the Jan 25 weekend]

It is extremely relevant to note that because there is no corresponding theorem for the additive decomposition of natural numbers into primes, this lack explains why additive number theory, when dealing with things like partitions, is so difficult.

Now, two integers n and m have a least common multiple (LCM) [n,m], and we need this every time we want to add two fractions, because we then need to find the LCM to combine two fractions with denominators n and m into a single fraction, and that is where the expression least common denominator comes from.

So, the LCM of 6 and 9 is LCM[6,9] = 18 so that:

$\frac{1}{6}+\frac{2}{9}=\frac{3}{18}+\frac{4}{18}=\frac{7}{18}$

So that we have, in general:

Definition. The Lowest Common Multiple or LCM of two integers n and m is defined as:

${}[n,m]=\prod\limits_{i}{p_{i}^{\max ({{e}_{i}},{{f}_{i}})}}$

and likewise, given two integers, we have:

Definition. the Greatest Common Divisor or GDC is defined as:

${}(n,m)=\prod\limits_{i}{p_{i}^{\min ({{e}_{i}},{{f}_{i}})}}$

and there are interesting properties between the GDC and LCM, such as that, for any two numbers n and m, the product of the GCD and the LCM equals the
product of n and m.

$(n,m)[n,m]=nm$

because whenever the GCD picks the exponent e of i for p of i, the LCM picks the exponent f of i, and vice versa and so:

$(n,m)[n,m]=\prod\limits_{i}{p_{i}^{{{e}_{i}}+{{f}_{i}}}=nm}$

and this works for three or more integers as well

$(n,m,k)[n,m,k]=nmk$

$(n,m,k,j)[n,m,k,j]=nmkj$

$(n,m,k,j,l)[n,m,k,j,l]=nmkjl$

Also, the direct result of the Min and Max functions in the definition of the GCD and LCD yields a “distributive law”

$(k[n,m])=[(k,n),(k,m)]$

$[k(n,m)]=([k,n],[k,m])$

And a beautiful “self-duel” relationship

$([k,n],[k,m],[n,m])=[(k,n),(k,m),(n,m)]$

Tuesday 17 January 2012