Fourier transforms (FT) have to deal with computations involving irrational numbers which can be tricky to implement in practice. Motivated by this, in this problem you will demon- strate how to do a Fourier transform in modular arithmetic, using modulo 5 as an example. (a) There exists we {0, 1, 2, 3, 4} such that w are 4th roots of unity (modulo 5), i.e., solutions to 24 = 1. When doing the FT in modulo 5, this w will serve a similar role to the primitive root of unity in our standard FT. Show that {1,2,3,4} are the 4th roots of unity (modulo 5). Also show that 1+w+wa+w3 = 0 (mod 5) for w= 2. (b) Using the matrix form of the FT, produce the transform of the sequence (0,1,0, 2) modulo 5; that is, multiply this vector by the matrix M4W), for the value w = 2. Be sure to explicitly write out the FT matrix you will be using (with specific values, not just powers of w). In the matrix multiplication, all calculations should be performed modulo 5. (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 5.) (d) Now show how to multiply the polynomials 2x2 + 3 and -x +3 using the FT modulo 5. Fourier transforms (FT) have to deal with computations involving irrational numbers which can be tricky to implement in practice. Motivated by this, in this problem you will demon- strate how to do a Fourier transform in modular arithmetic, using modulo 5 as an example. (a) There exists we {0, 1, 2, 3, 4} such that w are 4th roots of unity (modulo 5), i.e., solutions to 24 = 1. When doing the FT in modulo 5, this w will serve a similar role to the primitive root of unity in our standard FT. Show that {1,2,3,4} are the 4th roots of unity (modulo 5). Also show that 1+w+wa+w3 = 0 (mod 5) for w= 2. (b) Using the matrix form of the FT, produce the transform of the sequence (0,1,0, 2) modulo 5; that is, multiply this vector by the matrix M4W), for the value w = 2. Be sure to explicitly write out the FT matrix you will be using (with specific values, not just powers of w). In the matrix multiplication, all calculations should be performed modulo 5. (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 5.) (d) Now show how to multiply the polynomials 2x2 + 3 and -x +3 using the FT modulo 5