Content deleted Content added
mNo edit summary |
|||
Line 15:
k = 0,\dots,N-1. </math>
If ''N'' is a prime number, then the set of non-zero indices ''n'' = 1,...,''N''–1 forms a [[group (mathematics)|group]] under multiplication [[modular arithmetic|modulo]] ''N''. One consequence of the [[number theory]] of such groups is that there exists a [[generating set of a group|generator]] of the group (sometimes called a [[primitive root]]), an integer ''g'' such that ''n'' = ''g''<sup>''q''</sup> (mod ''N'') for any non-zero index ''n'' and for a unique ''q'' in 0,...,''N''–2 (forming a [[bijection]] from ''q'' to non-zero ''n''). Similarly ''k'' = ''g''<sup>–''p''</sup> (mod ''N'') for any non-zero index ''k'' and for a unique ''p'' in 0,...,''N''–2, where the negative exponent denotes the [[modular multiplicative inverse|multiplicative inverse]] of ''g''<sup>''p''</sup> modulo ''N''. That means that we can rewrite the DFT using these new indices ''p'' and ''q'' as:
:<math> X_0 = \sum_{n=0}^{N-1} x_n,</math>
| |||