Archive for the ‘Finite groups’ Category

Walter Ledermann – Encounters of a Mathematician

December 8, 2011

For about 20 years from the 1940s the Edinburgh publisher Oliver and Boyd published a series of very high standard pocket-sized texts in mathematics and mathematical physics entitled ‘University Mathematical Texts.’

Among my favourites, purchased as an undergraduate and still referred to forty years later, was ‘Finite Groups’ by Walter Ledermann.

For years Ledermann remained a name on a bookcover for me, until, through the magic of the internet, I chanced upon his reminisces, which begin here, full of warmth and humour.

Ledermann was a German Jew who was lucky enough to emigrate to Britain in the early 1930s, and to be able to follow his chosen career as a mathematician until he was well into his eighties.  The account of his PhD student from Afghanistan is particularly humorous and touching.

Euler’s phi function

August 14, 2009

If k is some positive integer, φ(k) is defined as the number of positive integers less than or equal to k whose greatest common divisor (gcd) with k is one.  Thus φ(1)=1, φ(2)=1, φ(3)=2, φ(4)=2, φ(5)=4, φ(6)=2 and so on.

Let d, n be positive integers and let ‘d|n’ signify ‘d divides n’.  The theorem


is not difficult to prove (for example Hardy and Wright, 5th ed. Theorem 63).  The proof I like best however is not the simplest, but it shows how φ is related to the structure of the abstract finite cyclic groups, of which the additive groups of integers (modulo n) are concrete examples.

By the the latter groups I mean the set of integers 0, 1, … , n-1 and the binary operation ° which is defined such that a°b is the remainder on dividing a+b by n.  We call this addition (modulo n).

We define the order of a as the least positive integer i such that ai is divisible by n, that is, the remainder on dividing ai by n is 0, the identity element. 

Now every element of a group has some order and if N(d) is the number of elements of order d then


where n is the order of the group.  But an element of order d generates a subgroup of order d and so by Lagrange’s theorem, d|n.  Thus


Now the cyclic group of order n (Cn) is known to have exactly one subgroup of order d for each divisor d of n, and each subgroup is necessarily cyclic. An element of Cn has order d iff it is a generator of the subgroup of Cn of order d. Therefore N(d), the number of elements of order d in Cn, is equal to the number of generators in Cd. To complete the proof we need only show that this is φ(d).

We can represent Cd as consisting of the integers 0, 1, … , d-1 with the binary operation being addition modulo d. If gcd(k,d)=1 then none of the integers k, 2k, … ,(d-1)k is divisible by d, and they are all distinct (mod d) and since there are d-1 of them and dk=0 (mod d) then k is a generator. On the other hand, if k is a generator it has order d. But

\displaystyle k\frac{d}{gcd(k,d)}=k'd=0 (mod d)

so the order of k is no greater than d/gcd(k,d) and if gcd(k,d) were not one, we would have a contradiction.  Therefore k is a generator iff gcd(k,d)=1 and so the number of generators in Cd is φ(d).