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 $\backslash$omega in $\{0,1,2,3,4\}$ such that $\{\backslash$omega

$0$

$,\backslash$omega $1$

$,\backslash$omega $2$

$,\backslash$omega $3\}$ the are $4$th roots of unity

$($modulo $5),$ i$.$e$.,$ solutions to z

$4=1($mod $5).$ When doing the FT in modulo $5,$ this $\backslash$omega

will serve a similar role to the primitive root of unity in our standard FT$.$ Show that

$\{1,2,3,4\}$ are the $4$th roots of unity $($modulo $5),$ with $\backslash$omega $=2$ as the primitive root. Also

show that $1+\backslash$omega $+\backslash$omega

$2+\backslash$omega

$3=0($mod $5)$ for $\backslash$omega $=2.$