Первообразный корень из единицы

Первообра́зный ко́рень из едини́цы (первообразный корень из ${\displaystyle 1}$) степени ${\displaystyle n}$ (${\displaystyle n}$ – натуральное число) в ассоциативном коммутативном кольце с единицей ${\displaystyle R}$, элемент ${\displaystyle w\in R}$, удовлетворяющий условиям:

сумма ${\displaystyle n}$ единиц кольца ${\displaystyle R}$ обратима в ${\displaystyle R,\quad (1)}$

${\displaystyle w^{n}=1}$ и для ${\displaystyle k=1,2,\ldots ,n-1}$ разность ${\displaystyle (1-w^{k})}$ не является делителем нуля в ${\displaystyle R.\quad (2)}$

При этом ${\displaystyle 0}$ считается делителем нуля в ${\displaystyle R}$. Условие ${\displaystyle (1)}$ часто формулируют, допуская некоторую вольность речи и говоря, что число ${\displaystyle n}$ обратимо в ${\displaystyle R}$.

Если ${\displaystyle R}$ является полем, то данное определение может быть упрощено. Вместо условий ${\displaystyle (1)}$ и ${\displaystyle (2)}$ может быть взято эквивалентное им условие ${\displaystyle (3)}$. И тогда элемент ${\displaystyle w\in R}$ называется первообразным корнем из ${\displaystyle 1}$ степени ${\displaystyle n}$ в поле ${\displaystyle R}$, если ${\displaystyle w^{n}=1}$ и ${\displaystyle w}$ не является корнем из единицы никакой положительной степени ${\displaystyle k}$, меньшей ${\displaystyle n}$, т. е. если для ${\displaystyle w}$ выполнены условия

${\displaystyle w^{n}=1}$ и для ${\displaystyle k=1,2,\ldots ,n-1}$ разность ${\displaystyle (1-w^{k})}$ не равна ${\displaystyle 0.\quad (3)}$

Теорема. Если ${\displaystyle w}$ – первообразный корень из ${\displaystyle 1}$ степени ${\displaystyle n}$ в кольце ${\displaystyle R}$, то:

• элементы ${\displaystyle w^{0},w^{1},w^{2},\ldots ,w^{n-1}}$ попарно различны,${\displaystyle \quad (4)}$
• для любого ${\displaystyle i=1,2,\ldots ,n-1}$ сумма ${\displaystyle \sum _{j=0}^{n-1}w^{ij}}$ равна ${\displaystyle 0,\quad (5)}$
• теоретико-числовое ${\displaystyle {\text{ДПФ}}_{R,n,w}}$ обратимо.${\displaystyle \quad (6)}$

Доказательство утверждения ${\displaystyle (4)}$. Предположим, что существуют целые ${\displaystyle a}$ и ${\displaystyle b}$ такие, что ${\displaystyle 0\leq a<b\leq n-1}$ и ${\displaystyle w^{a}=w^{b}}$, тогда для ${\displaystyle i=b-a}$ выполняется ${\displaystyle w^{a}(1-w^{i})=0}$. Так как первый сомножитель ${\displaystyle w^{a}}$ произведения ${\displaystyle w^{a}(1-w^{i})}$ отличен от нуля, то второй сомножитель оказывается делителем нуля, что противоречит ${\displaystyle (2)}$.

Доказательство утверждения ${\displaystyle (5)}$. В кольце многочленов ${\displaystyle Z[c]}$ от одной переменной с целыми коэффициентами для любого целого ${\displaystyle n\geq 1}$ выполняется тождество

${\displaystyle (1-c)(1+c+c^{2}+\ldots +c^{n-1})=1-c^{n}}$.

Подставляя в это тождество ${\displaystyle {\text{с}}=w^{i}}$, где ${\displaystyle 1\leq i<n}$, получаем

${\displaystyle (1-w^{i})\sum _{j=0}^{n-1}w^{ij}=1-(w^{i})^{n}}$

,}}

где правая часть равна нулю, т. к. ${\displaystyle 1-(w^{i})^{n}=1-(w^{n})^{i}=1-1=0}$.</n<></math>

Первый сомножитель произведения ${\displaystyle (1-w^{i})\sum _{j=0}^{n-1}w^{ij}}$ согласно ${\displaystyle (2)}$ не является делителем нуля, значит второй сомножитель ${\displaystyle \sum _{j=0}^{n-1}w^{ij}}$ равен нулю.

Доказательство утверждения ${\displaystyle (6)}$ см. в статье Теоретико-числовое дискретное преобразование Фурье.

Пример 1. В поле комплексных чисел число ${\displaystyle w=e^{-2\pi i/n}=\cos(-2\pi /n)+i\sin(-2\pi /n)}$ является корнем из ${\displaystyle 1}$ степени ${\displaystyle n}$ и не является корнем из ${\displaystyle 1}$ меньшей степени, поэтому является первообразным корнем из ${\displaystyle 1}$ степени ${\displaystyle n}$. Cтепени этого корня ${\displaystyle w^{0},w^{1},w^{2},\ldots ,w^{n-1}}$ попарно различны, исчерпывают всё ${\displaystyle n}$-элементное множество комплексных корней из ${\displaystyle 1}$ степени ${\displaystyle n}$ и их сумма равна нулю.

Замечание. Для любого поля ${\displaystyle R}$ из ${\displaystyle (3)}$ следуют ${\displaystyle (1)}$ и ${\displaystyle (2)}$. Существуют кольца, для которых это не так.

Пример 2. Обозначим через ${\displaystyle w}$ вычет числа ${\displaystyle 3}$ в кольце с единицей ${\displaystyle R=\mathbb {Z} /8\mathbb {Z} }$. Этот вычет является корнем из ${\displaystyle 1}$ степени ${\displaystyle 2}$ и не равен ${\displaystyle 1}$. Поэтому ${\displaystyle 1-w\neq \;0}$, т. е. выполнено условие ${\displaystyle (3)}$ для ${\displaystyle n=2}$. Однако сумма ${\displaystyle 1+1}$ в кольце ${\displaystyle R}$ не равна нулю и ${\displaystyle 1-w}$ является делителем нуля, т. е. ${\displaystyle (1)}$ и ${\displaystyle (2)}$ не выполняются.