Q:

Number Theoretic Transform (NTT) example not working out

I'm reading up on the NTT, which is a generalisation of the DFT.  I'm working in $\mathbb{F}_5$ with primitive root $w=2 \mod 5$. Suppose I want to compute the NTT of $x=(1,4)$. So far I have obtained:
$$\hat{x}=\mathcal{N}(x)=\left(\sum_{j=0}^1 2^{jk}x_j\mod 5\right)_{k=0}^1=(1+4,1+2\cdot 4)\equiv(0,4)\mod 5.$$
Applying the inverse NTT should recover $x$. But...
$$\mathcal{N}^{-1}(\hat{x})=\left(\frac{1}{2}\sum_{k=0}^1 2^{-jk}\hat{x}_k\mod 5\right)_{j=0}^1=\left(\frac{1}{2}(0+4),\frac{1}{2}(0+2^{-1}\cdot 4)\right)\equiv(2,1).$$
But this is not the same as $x$. What am I doing/thinking wrong?  I'm thinking it could be to do with how I'm working with "inverses", e.g. 1/2, in modular arithmetic? 

A:

You are trying to compute an NTT of length $n = 2$. You chose the modulus $p = 5$ with a primitive root $w = 2$, which are appropriate so far. 
The primitive root $w$ has order $p - 1 = 4$, which means $2^4 \equiv 1 \mod 5$. But what you want is an $n$th root of unity $a$, where $a^n = a^2 \equiv 1 \mod 5$. The easiest way to obtain this is to compute $a = w^{(p - 1) / n} = w^2 \equiv 4 \mod 5$. Now using $a$ instead of $w$, we have:
$$\begin{align}
\hat{x} = \mathcal{N}(x) &= (1a^0 + 4a^0, \: 1a^0 + 4a^1) \\
&= (1\cdot1 + 4\cdot1, \: 1\cdot1 + 4\cdot4) \\
&\equiv (0, \: 2) \mod 5. 
\end{align}$$
We compute the inverse transform using $a^{-1} \equiv 4 \mod 5$:
$$\begin{align}
x = \mathcal{N}^{-1}(\hat{x}) &= (2^{-1})\:(0a^0 + 2a^0, \: 0a^0 + 2a^{-1}) \\
&= (3)\:(0\cdot1 + 2\cdot1, \: 0\cdot1 + 2\cdot4) \\
&\equiv (3)\:(2, \: 3) \\
&\equiv (1, \: 4) \mod 5. 
\end{align}$$
Notes:

In your own answer you said that because you need a 2nd root of unity, you needed to choose $p = 3$. This is not true - you can choose any $p = kn + 1$. Higher primes will have higher order roots, but you can take the power of a primitive root to get the $n$th root that you desire. 
Your approach of padding the vector with zeros may or may not be appropriate depending on the situation.  Padding is okay when the goal is to compute a convolution, but not okay if the goal is to compute the exact frequency spectrum of the input.