Warning: foreach() argument must be of type array|object, bool given in /var/www/html/web/app/themes/studypress-core-theme/template-parts/header/mobile-offcanvas.php on line 20

What is the sum of the nth roots of unity? What is their product if n is odd? If n is even?

Short Answer

Expert verified

Sum of nth root of unity =0

Product of nth root of unity, when number of terms are even =-1

Product of nth root of unity, when number of terms are odd =1

Step by step solution

01

Sum of  n th root of unity

Thenthrootsofunityare1,W,W2,W3,....WN-1Where,W=e2πn=cos2πnθ+isin2πnθ

The sum of nth roots of unity is:

1,W,W2,W3,.....WN-1 …… (1)

As per the geometric series, the sum of n terms of 1,W,W2,W3,.....WN-1is represented as .

So, equation (1) can be represented as follows:

Sum of nth root of unity= 1-wn1-w

=1-cos2πn+isin2πn1-cos2πn+isin2πn=1-cos2π+isin2π1-cos2πn+isin2πn=1-1+01-cos2πn+isin2πn=1-11-cos2πn+isin2πn=0

02

Product of nth root of unity 

The production of th root unity are following: 1,W,W2,W3,....WN-1...3... (3)

As per the arithmetic series, the product of n terms of 1,W,W2,W3,....WN-1is

represented as role="math" localid="1658921404734" Wnn-12

So, calculation (3) is present as follows:

Product of th root of unity =Wnn-12

=cos2n+isin2nnn-12 ... (4)

If is even, then

Product of nth root of unity =-1 … (5)

If n is odd, then

Product of nth root of unity =1 … (6)

Moreover,

  • This summation of such nth component of unity is given by Equation (2), is equal to 0.
  • If "n" is even, this products of both the nth root for unity is obtained from Equation (5), is equal to -1.
  • If "n" is odd, the composite of nth roots of unity may be calculated using Equation (6), is equal to 1.

Unlock Step-by-Step Solutions & Ace Your Exams!

  • Full Textbook Solutions

    Get detailed explanations and key concepts

  • Unlimited Al creation

    Al flashcards, explanations, exams and more...

  • Ads-free access

    To over 500 millions flashcards

  • Money-back guarantee

    We refund you if you fail your exam.

Over 30 million students worldwide already upgrade their learning with Vaia!

One App. One Place for Learning.

All the tools & learning materials you need for study success - in one app.

Get started for free

Most popular questions from this chapter

You are given an array of nelements, and you notice that some of the elements are duplicates; that is, they appear more than once in the array. Show how to remove all duplicates from the array in time O(nlogn) .

A linear, time-invariant system has the following impulse response:


(a) Describe in words the effect of this system.

(b) What is the corresponding polynomial

This problem illustrates how to do the Fourier Transform (FT) in modular arithmetic, for example, modulo .(a) There is a number such that all the powers ω,ω2,...,ω6 are distinct (modulo ). Find this role="math" localid="1659339882657" ω, and show that ω+ω2+...+ω6=0. (Interestingly, for any prime modulus there is such a number.)

(b) Using the matrix form of the FT, produce the transform of the sequence (0,1,1,1,5,2) modulo 7; that is, multiply this vector by the matrix M6(ω), for the value of ωyou found earlier. In the matrix multiplication, all calculations should be performed modulo 7.

(c) Write down the matrix necessary to perform the inverse FT. Show that multiplying by this matrix returns the original sequence. (Again all arithmetic should be performed modulo 7.)

(d) Now show how to multiply the polynomials and using the FT modulo 7.

Question: You are given an infinite array A[·]in which the first n cells contain integers in sorted order and the rest of the cells are filled with . You are not given the value of n. Describe an algorithm that takes an integer x as input and finds a position in the array containing x, if such a position exists, in O(log n) time. (If you are disturbed by the fact that the array A has infinite length, assume instead that it is of length n, but that you don’t know this length, and that the implementation of the array data type in your programming language returns the error message whenever elements A[i]withi>n are accessed.)

Practice with polynomial multiplication by FFT.

(a) Suppose that you want to multiply the two polynomials x + 1 and x2+1using the FFT. Choose an appropriate power of two, find the FFT of the two sequences, multiply the results component wise, and compute the inverse FFT to get the final result.

(b) Repeat for the pair of polynomials 1+x+2x2and 2 + 3x.

See all solutions

Recommended explanations on Computer Science Textbooks

View all explanations

What do you think about this solution?

We value your feedback to improve our textbook solutions.

Study anywhere. Anytime. Across all devices.

Sign-up for free