Math Is Fun Forum

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Fundamental theorem of arithmetic

Everybody is familiar with this result, that every integer greater than 1 can be written uniquely as a product of primes. Here is one way to prove it – using group theory!

Let

and

be the cyclic group of order

. Then

has a composition series

(where

is a maximal normal subgroup of

for

). Now

is cyclic, so each composition factor

is cyclic. Also, each

is a simple group. Since a finite cyclic group is simple if and only if its order is prime,

is prime. It follows that

is a product of primes. Furthermore, the Jordan–Hölder theorem states that the composition series of

is unique up to isomorphism of its composition factors; therefore the prime factorization of

is unique.

I think this is a brilliant proof indeed!

Last edited by JaneFairfax (2009-04-26 11:58:16)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Fundamental theorem of arithmetic

We need to note something here. When we use a big result (like the Jordan–Hölder theorem) to prove a small result (like the fundamental theorem of arithmetic) we must always be on our guard against the possibility of a circular proof. Big results are usually built up from smaller results, and there is the danger that the small result we wish prove may be part of the smaller results used to develop the big result.

This is not a trivial matter. I have actually seen a circular proof of this sort myself. It was in the Wikipedia article on Bézout’s identity, where some smart Alec apparently had a proof of the result using another result. It turned out that the second result could only be proved by using Bézout’s identity, and so the whole proof of Bézout’s identity turned out be a tautology.

So, in this particular case, we have got to ask ourselves: Does the development of the Jordan–Hölder theorem assume the fundamental theorem of arithmetic at any stage?

Well, I have followed the material in John F. Humphreys’s A Course in Group Theory all the way from the beginning, and I can confidently say that the fundamental theorem of arithmetic was not assumed in the development of the results leading up to the Jordan–Hölder theorem. Therefore the proof of the fundamental theorem of arithmetic using composition series and the Jordan–Hölder theorem is not circular.

Last edited by JaneFairfax (2009-04-27 10:26:43)

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Fundamental theorem of arithmetic

The closest Humphreys has come to the fundamental theorem of arithmetic is the following result (tacitly used in the proof of Proposition 16.5 on p.138):

For any integer

, there is a prime which divides

.

Note that this is not the same as the fundamental theorem of arithmetic. The fundamental theorem says that

can be completely split up into primes, which is not what the statement above is asserting. Indeed, the statement above can be proved without assuming unique prime factorization.

Proof:

Suppose that there is an integer greater than 1 which is not divisible by any prime. Let

be the smallest such integer. Then

must be composite (for if it were prime, it would be divisible by a prime, namely itself). Hence

is divisible by some integer

with

. By minimality of

,

is divisible by a prime

. Then it follows that

itself is divisible by

after all. This contradiction means that no such integer

exists; hence every integer greater than 1 is divisible by some prime.

JaneFairfax

Member

Registered: 2007-02-23

Posts: 6,868

Re: Fundamental theorem of arithmetic

Actually, there is another chapter in which Humphreys makes use of the statement in post #2 (even more tacitly) – that’s in the chapter on the Sylow theorems. A (finite) p-group G is defined as a group in which every element has order a power of fixed prime p (including the identity, which has order p[sup]0[/sup]). From this it follows that |G| = p[sup]n[/sup] for some positive integer n. Humphreys does not go into details but the implication is this. By Lagrange, |G| = p[sup]n[/sup]k for some positive integer k coprime with p; if k > 1, then it would be divisible by some prime q ≠ p; hence there would be a Sylow q-subgroup containing nonidentity elements not of order a power of p; therefore k = 1.