From: Robin Chapman <rjc@maths.ex.ac.uk>
Newsgroups: sci.math
Subject: Re: Primality Test Using Chebyshev Polynomials!
Date: Fri, 20 Feb 1998 04:35:18 -0600

In article <6cfkq8$maa@info.mcs.kent.edu>,
  rayes@goat.mcs.kent.edu ( Mohamed Omar Rayes) wrote:
>
> An odd integer n > 0 is prime if and only if the Chebyshev
> polynomial of the first kind T(n,x), divided by x, is
> irreducible over the integers.

Its roots are the non-zero numbers of the form cos(pi/2n + 2j pi)
where j is an integer. They include cos(pi/2n) whic generates the
real subfield of the cyclotomic field Q(exp(2 pi i/4n)). This cyclotomic
field has degree phi(4n) = 2 phi(n) (where phi is the Euler function)
and its real subfield has degree phi(n) [this is due to the
irreducibility of the cyclotomic polynomials]. So the minimal polynomial of
cos(pi/2n) has degree phi(n), and so equals the Chebyshev divided by x
iff phi(n) = n-1 iff n is prime.

A related but simpler "primality test" is that p is prime iff
X^{p-1} + X^{p-2} + ... + X + 1 is irreducible over Q.
Of course both of these "tests" are useless in practical terms.

Robin Chapman                           "256 256 256.
Department of Mathematics                O hel, ol rite; 256; whot's
University of Exeter, EX4 4QE, UK        12 tyms 256? Bugird if I no.
rjc@maths.exeter.ac.uk                   2 dificult 2 work out."
http://www.maths.ex.ac.uk/~rjc/rjc.html  Iain M. Banks - Feersum Endjinn

-----== Posted via Deja News, The Leader in Internet Discussion ==-----
http://www.dejanews.com/   Now offering spam-free web-based newsreading