Saturday 13 September 2008

Totients, Eulers Phi Function


The totient of an integer, N, is the number of integers Less than N which are relatively prime to N, that is, they share no common factors. The symbol for the Totient (by the way, the word is pronounced to rhyme with "quotient"... I didn't know that for a long time) of N is usually the greek letter Φ. We would write Φ(10)=4, to indicate there are four numbers less than 10 which have no factor in common with the number ten. The four numbers 1,3,7, and 9 are called the totitives of 10. The image at top shows a graph of Φ(n) for each n.

Euler showed that if a number n had prime factors p, q, and r; then the totient would equal N(1-1/p)(1-1/q)(1-1/r). It doesn't matter if it has some prime factors more than once, you only use each factor once in the calculation. As an example, 20 factors to 2x2x5, but the number of prime factors is found by 20 (1-1/2)(1-1/5) = 8; with totatives of 1, 3, 7, 9, 11, 13, 17, and 19. The word totient is drawn from the Latin root tot for "so much", and probably to the Greek tosos, "so great". The word tot is still used occasionally for a mark made beside a list to acknowledge receipt, and is sometimes called a "tot mark"(pronounced with a long o, like tote). Euler defined the rule for the number of totients around 1761 in proving what we now call the "Euler-Fermat" theorem. Euler didn't use the word totient. That term was introduced by J J Sylvester, (According to Graham, Knuth and Patashnik, "Concrete Mathematics") who had a habit of making up new words for math terms. "The reference they give is to a paper from 1883: "On the number of fractions contained in any 'Farey series' of which the limiting number is given".

The name "PHI" for the function was created by Gauss in his Disquitiones arithmeticae .

Here is a list of the first few integers, their totients, and their totitives...

N_____Φ(N)______ totitives

1_____ 1 ____ 1

2_____ 1 ____ 1

3_____ 2 _____ 1,2

4_____ 2 _____ 1,3

5_____ 4 _____ 1,2,3,4

6_____ 2 ______1, 5

7_____ 6 ______1.2.3.4.5.6

8_____ 4 ______ 1,3,5,7

There is actually an interesting unproven math theorem about totients. It seems that any number that appears in the sequence of Φ(N) must appear at least twice. It has been proven that if there is an exception, it must have more than 10,000 digits. This is sometimes called the Carmichael Conjecture after R. D. Carmichael.

No comments: