From: Ray Subject: Re: P-gon constructibility Date: Sat, 13 Nov 1999 21:10:03 -0500 Newsgroups: sci.math > An n-gon is constructible iff cos(2*pi/n) is constructible. In the case > where n = some prime p, why must p be of the form p = 2^r + 1, for r in > the naturals? Short answer: because phi(p) must be a power of 2, where phi(n) = the number of numbers less than or equal to n that are relatively prime to n. Somewhat longer answer: Well, suppose we want to construct some number x. Now, it turns out that to construct x, its degree must be a power of 2. What this means is that if we consider all the polynomials with integer coefficients which have x as a root, then the minimal polynomial (something like that) is the one with the smallest degree. The degree of x's minimal polynomial is the degree of x. This is because, when constructing, all we can do is take intersections of a line and a circle. And since a circle gives a relation between squares of numbers, and a line is linear, then you can see that all you can do is double the degree of a number, etc., or something like that. Now, to construct an n-gon, we need to construct the n n-th roots of unity. These are related by the equation z^n - 1 = 0. Now, some of these are not "primitive" n-th roots (something like that), for example, the 2nd 6th root of unity is also a 3rd root of unity, and as such, is a solution to z^3 - 1 = 0. Now, when we look at primitive 6th roots of unity, we don't consider the 0-th (or 6th = 1), the 2nd, 3rd, or 4th roots because they have different minimal polynomials. Since all the 6th roots satisfy z^6 - 1 = 0, then we can divide by the minimal polynomials of the non-primitive 6th roots of unity, i.e., (z - 1), (z + 1), and (z^2 + z + 1), and get (z^2 - z + 1). This is called the 6th cyclotomic polynomial (or something like that). Thus, any primitive 6th root of unity z satisfies z^2 - z + 1 = 0. Here, z-1 is the minimal polynomial of the 1st root of unity (1), z+1 is the minimal polynomial for the primitive 2nd root of unity (-1), and z^2+z+1 is the minimal polynomial for the primitive 3rd roots of unity (-1/2 +/- i*sqrt(3)/2). The first couple are: x Psi_x (i think that's the notation) 1 z-1=0 2 z+1=0 3 z^2+z+1=0 4 z^2+1=0 5 z^4+z^3+z^2+z^1+1=0 6 z^2-z+1=0 Psi_n is just the minimal monic polynomial of a primitive n-th root of unity (i think). Now, the m-th n-th root of unity is not primitive if gcd(m,n)<>1. Therefore, there are Phi(n) primitive n-th roots of unity. (Phi(n) = the number of numbers less than or equal to n which are relatively prime of n.) In general, Psi_n = (z^n-1)/prod(Psi_d)), where the product is taken over all d which divide n. Now, the degree of Psi_n = Phi(n). There are two ways to see this: 1) we take a polynomial of degree n, and divide it by (z-z_i) whenever i is not relatively prime to n, where z_i is the i-th n-th root of unity 2) from the recursive definition, degree(Psi_n) = n - sum(degree(Psi_d)). Noting that n = sum(Phi(d)), where the sum is taken over all divisors d of n, we see that Psi_n has degree Phi(n), and can prove it inductively if we wanted. Anyway, the minimal polynomial of a primitive n-th root of unity has degree Phi(n), which we wish to be a power of 2. In the case of n= a prime, Phi(n) = n - 1, so n must be 1 more than a power of 2, i.e., n = 2^r + 1. But note that if r has any prime factors, then n could be factored. Since n is prime, we must have r = 2^k for some k. Therefore, if a regular p-gon is constructable, p a prime, we must have p = 2^2^k + 1, i.e., p is a fermat prime. Now, if n = p^a*q^b*r^c. . ., then phi(n) = n*(1-1/p)*(1-1/q)&(1-1/r). . . = (p^a-p^(a-1))*(q^b-q^(b-1))*(r^c-r^(c-1)). . . So if a regular n-gon is constructable, phi(n)=2^k, so the only primes which divide n are 2 and any number of fermat primes, and each fermat prime can occur no more than once in the prime factorization of n. This also implies that you can't trisect an angle, since if you could, you could construct a regular 9-gon, but phi(9) = 6. Hope this helps. -Ray "I'm not really sure what I'm talking about" Cassella