FOURIER TRANSFORM OF THE SEQUENCES OF THE PRIMITIVE ROOTS OF THE PRIME NUMBERS

Academic Open Internet Journal

ISSN 1311-4360

www.acadjournal.com

Volume 18, 2006

FOURIER TRANSFORM OF THE SEQUENCES OF THE PRIMITIVE ROOTS OF THE PRIME NUMBERS

H. K. Terzidis, P. Tzekis

Technological Educational Institution of Thessaloniki

School of Sciences - Department of Mathematics

P.O. Box 14561, GR-541 01

Thessaloniki ,

Greece

Email:tzekis@math.auth.gr

ABSTRACT

First we study the energy spectra of the sequences corresponding to the primitive roots of the prime numbers. Finally, we study the general case of DFT of the sequences corresponding to the primitive roots of the prime numbers.

KEYWORDS:primitive roots;prime numbers;energy spectra;DFT

1.INTRODUCTION

The periods of the inverses of integers, the spectral analysis of the periods of the inverses of integers and the spectral analysis of the Discrete Fourier Transform are studied in [9],[10],[11] and [12]. Here, we study the energy spectra of the sequences corresponding to the primitive roots of the prime numbers. Finally, we study the general case of DFT of the sequences corresponding to the primitive roots of the prime numbers.

2. THE ENERGY SPECTRA OF THE SEQUENCES THAT CORRESPOND TO THE PRIMITIVE ROOTS OF THE PRIME NUMBERS

Consider the sequence , with , where is a primitive root and a prime number, which elements has unity norm. Because the sequence , is periodical with period , it is implied that the is periodical with the same period. Certainly, the elements of this sequence are the roots of the unity, except for the unity itself. In particular, the elements of this sequence, represent this permutation of the roots of the unity, except for the unity itself, which corresponds to the permutation of the positive integers, less than , with count of permutations . If we symbolize with the conjugate complex of , then the sequence , , which is defined from the relation

(1)

is the autocorrelation sequence of . This Sequence is also periodical with period . Actually, because

(2)

it follows from (1) that

(3)

Moreover, because it is implied from (1) that

and because the sequence is periodical with period , it follows that in general is , for . For , because , it follows that the product is element of the limited residual system . Therefore, as varies from to , gives the roots of the unity, except for the unity itself. Since for the set of the roots of the unity is

it follows that for .

If now is the DFT of the sequence , i.e.

then the sequence is also periodical with period and the energy spectra

of , by the Wiener --Khinchin theorem, constitutes a Fourier pair with its autocorrelation function , i.e.

and

For , and also for , is

But and for .

For , and also for , is

But

implies that for is

Constant energy spectra like the above are called Plane or White.

3. THE DFT OF THE SEQUENCES THAT CORRESPOND TO THE PRIMITIVE ROOTS OF THE PRIME NUMBERS

Let a primitive root , where is a prime number and its inverse. Because of and , we have that

(4)

But in general, because of and , we have

(5)

Let now , the Discrete Fourier Transforms (DFT) of the sequences and respectively, :

(6)

and

(7)

where .

Form (4) and (5), (7) becomes

(8)

Because of , we have that for is . Therefore, from for , is

and then

where is the conjugate of .

So, (8) becomes

(9)

That is the DFT of the sequence coincides with the inverse transform of the sequence .

In the same conclusion of course, we arrive as follows:

Let be the DFT of the DFT of the sequence : Then we have

But

So,

Because is , the inverse of the primitive root , implies that the DFT of the DFT of the sequence , is the sequence , which is symmetrical to the first one. i.e. , or . Obviously,the opposite of this relation is also true i.e. . We can see analogous relations if we consider the sequence , where is a primitive root and , is a primitive root of the unity. We have

and then

As previously mentioned, we have

So,

and then, the DFT of the DFT of the sequence , is the sequence ,which, because and , for , coincides with the sequence

Now, we have that

and then, the relations (6) and (9) can be rewritten as

and therefore we have

Since

it follows

which means that the complex numbers and have the same norm and opposite s, so they are conjugates.

REMARKS

Consider the DFT of the sequence . Then

Then , when , i.e. and when , i.e. . So, the DFT of the sequence is

For its IDFT, , we have

Then , when and when and the IDFT of the sequence is

References

1) T. M. Apostol, Introduction to Analytic Number theorySpringer Verlang, New York, 1976.

2) G. H. Hardy, E. M. Wright, An introduction to the theory of numbers 5th edition Clarendon, Oxford, 1979.

3) M. R. Schroeder, Number theory in Science and CommunicationSpringer Verlag, New York, 1984.

4) J. H. McClellan, C. M. Rader, Number theory in Digital Signal Processing Prentice Hall, Englewood Clifs, N J , 1979.

5) H. Hsu, Fourier AnalysisSimon and Schuster, 1970.

6) A. Papoulis, Signal AnalysisMcGraw Hill, 1977.

7) Hewlett Packard Co, Spectrum AnalysisAN 63 and AN 63A, Palo Alto, CA, 1965.

8) R. Crandall, Mathematica for the SciencesAddisson Wesley, 1995.

9) H. Terzidis and G. Danas, The spectral analysis of the periods of the inverses of integersJour. Inst. Maths. & Comp. Sciences (Comp. Sc. Ser.), Vol. 10, No. 1 , pp. 61-69, 1999.

10) H. Terzidis and G. Danas, The systems of primitive roots. The degree and rank of prime numbersIntern. J. Computer Math., Vol. 73, pp. 469-478, 1999.

11) H. Terzidis and G. Danas, The spectral analysis of the Discrete Fourier TransformHandronic Journal, Vol. 24, pp. 225-240, 2001.

12) H. Terzidis and G. Danas, The periods of the inverses of integers NNTDM, Vol. 8, No. 1, pp. 1-20, 2002.

Technical College - Bourgas,