Критерии первообразности

[latex] U_n[/latex] — циклическая группа корней [latex] n[/latex]-й степени из единицы. Образующий элемент группы [latex] U_n[/latex] называется первообразным корнем [latex] n[/latex]-й степени из единицы.

Теорема 1 (Первый критерий первообразности)

Корень [latex] n[/latex]-й степени из единицы будет первообразным корнем [latex] n[/latex]-й степени из единицы [latex] \Leftrightarrow[/latex] не является корнем из единицы никакой степени [latex] <n[/latex].

Доказательство

Необходимость:
[latex] E[/latex] – первообразный корень степени [latex] n[/latex] из единицы .
[latex] \forall m \in \mathbb{N}[/latex], [latex] m < n[/latex], [latex] E^m \ne 1[/latex];
[latex] U_n=[/latex] [latex]\{1, E, E^2, …, E^{n-1}\}[/latex].
От противного. Пусть [latex] E^m= 1[/latex], [latex] m < n[/latex], тогда [latex] E[/latex] образует группу [latex] {U}'_n[/latex] (или [latex] U_m[/latex]) = [latex]\{1, E, E^2, …, E^{m-1}, E^m\}[/latex] = [latex]\{1, E, E^2, …, E^{m-1}\}[/latex], где [latex] E^m= 1[/latex] и [latex] {U}'_n= m[/latex], но [latex] m < n \Rightarrow [/latex] [latex] {U}'_n \ne U_n \Rightarrow [/latex] [latex] E[/latex]- не образующий элемент [latex] U_n[/latex]. Получаем, что [latex] \forall m \in \mathbb{N}[/latex], [latex] m < n[/latex], [latex] E^m \ne 1[/latex].
Достаточность:
[latex] \forall m \in \mathbb{N}[/latex], [latex] m < n[/latex], [latex] E^m \ne 1 \Rightarrow [/latex]
[latex] E[/latex] — первообразный корень из единицы степени [latex]n[/latex].
От противного. Пусть [latex] E[/latex]-не является первообразным корнем [latex] n[/latex]-й степени из единицы [latex] \Rightarrow E [/latex] не образует группу [latex] U_n \Rightarrow [/latex]
[latex] U^E_n= {E^0, E^1, E^2,…< E^{n-1} } \ne U_n \Rightarrow U^E_n \in U_n \Rightarrow \exists k, 1 \leqslant k \leqslant n-1,[/latex] что [latex] E^{k-1}=1[/latex], но [latex] 0 \leqslant k+1 < n-1 [/latex], [latex] m= k-1 \Rightarrow[/latex] [latex] \exists m \in \mathbb{N}[/latex], [latex] m < n[/latex], [latex] E^m = 1 \Rightarrow [/latex] [latex] E[/latex] – первообразный корень степени [latex] n[/latex] из [latex] 1[/latex].

Лемма

Если [latex] E[/latex] — первообразный корень степени [latex] n[/latex] из единицы, то
[latex] E^m= 1 \Leftrightarrow m \vdots n[/latex].

Доказательство

Необходимость:
Найдём [latex] m= nq+r[/latex], [latex] 0 \leq r \leq n-1[/latex];
[latex] 1= E^m= E^{nq+n}= E^{nr}E^r= (E^n)^qE^r= 1^qE^r= E^r[/latex].
Если [latex] r \in \mathbb{N}[/latex], то получим противоречие с первым критерием [latex] r=0 \Rightarrow m \vdots n[/latex].
Достаточность: [latex] m \vdots n \Rightarrow m=nq[/latex];
[latex] E^m= E^{nq}= (E^n)^q= 1^q=1[/latex].

Теорема 2 (Второй критерий первообразности)

Пусть [latex] E [/latex] — первообразный корень степени [latex] n[/latex] из единицы, тогда [latex] E^k (k \in \mathbb{N})[/latex] является первообразным корнем степени [latex] n[/latex] из единицы [latex] \Leftrightarrow (n,k)=1[/latex].

Доказательство

[latex](n,k)= d[/latex]; [latex] n= n,d[/latex]; [latex] k= k,d[/latex]; [latex](n_1, k_1)=1[/latex].
Необходимость: [latex] E[/latex], [latex] E^n[/latex] — корни степени [latex] n[/latex] из единицы.
[latex] (n,k)=1 [/latex]
От противного. [latex] (n,k)=d > 1 \Rightarrow n_1 < n [/latex];
[latex](E^k)^{n_1} = (E^{k_1d})^{n_1}= E^{k_1dn_1}= E^{k_1(nd_1)}= E^{k_1n}= (E^n)^{k_1}= 1^{k_1}=1 \Rightarrow d=1[/latex] противоречие.
Достаточность: [latex] E [/latex] — первообразный корень степени [latex] n [/latex] из единицы;
[latex] (n,k)=1 [/latex];
[latex] E^k [/latex] — первообразный корень степени [latex] n[/latex] из единицы.
От противного. Пусть [latex] E^k [/latex] – не является первообразным корнем степени [latex] n[/latex] из единицы, тогда по первому критерию первообразности: [latex] \exists m \in N[/latex], [latex] m < n[/latex], [latex](E^k)^m= 1[/latex];
[latex] E^{km}=1 \Rightarrow [/latex] по лемме [latex] km \vdots n \Rightarrow m \vdots n [/latex], но [latex] m < n [/latex] – противоречие.

ПРИМЕРЫ

Найти все первообразные корни группы [latex]U_{12}[/latex], пользуясь вторым критерием первообразности.

Даны корни из единицы [latex]E_1 = i[/latex], [latex] E_3 = -i[/latex]. Построить группу [latex] U_4[/latex].

Лимит времени: 0

Навигация (только номера заданий)

0 из 6 заданий окончено

Вопросы:

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6

Информация

Тест по вышеизложенному материалу

Вы уже проходили тест ранее. Вы не можете запустить его снова.

Тест загружается...

Вы должны войти или зарегистрироваться для того, чтобы начать тест.

Вы должны закончить следующие тесты, чтобы начать этот:

Результаты

Правильных ответов: 0 из 6

Ваше время:

Время вышло

Вы набрали 0 из 0 баллов (0)

Средний результат
Ваш результат

Рубрики

1. Нет рубрики 0%
2. Алгебра 0%

Ваш результат был записан в таблицу лидеров

Загрузка

Имя: E-Mail:

Капча:

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6

1. С ответом
2. С отметкой о просмотре

1. Задание 1 из 6

   1.

   [latex]U_n[/latex] циклическая группа корней [latex]n[/latex]-ой степени из 1. Первообразным корнем [latex]n[/latex]-ой степени из 1 является________элемент группы [latex]U_n[/latex].

   • (образующий)
   Правильно
   

   Неправильно
   
2. Задание 2 из 6

   2.

   Установить соответствие между условиями теорем (критерии первообразности) и леммы:

   Элементы сортировки

   • не является корнем из единицы никакой степени $ < n$
   • $m \vdots n$
   • $(n,k)=1$

   • Корень$ n$-й степени из единицы будет первообразным корнем $n$-й степени из единицы $\Leftrightarrow$

   • Если $E$ - первообразный корень степени $n$ из единицы, то $ E^m= 1 \Leftrightarrow$

   • Пусть $E$ - первообразный корень степени $ n $ из единицы, тогда $ E^k (k \in \mathbb{N})$является первообразным корнем степени $n$ из единицы $\Leftrightarrow$

   Правильно
   

   Неправильно
   
3. Задание 3 из 6

   3.

   Взаимно простыми называются числа, которые не имеют никаких общих делителей, кроме:

   • $i$ и $-i$
   • $1$ и $-1$
   • $1$,$-1$,$i$ и $-i$
   Правильно
   

   Неправильно
   
4. Задание 4 из 6

   4.

   Какое количество первообразных имеет $\sqrt[5]{1}$ ?
   Правильно
   

   Неправильно
   
5. Задание 5 из 6

   5.

   Все первообразные корни группы [latex]U_9[/latex]

   • $ E= \cos\frac{7\pi}{6} + i\sin\frac{7\pi}{6}$
   • $E= \cos\frac{11\pi}{6} + i\sin\frac{11\pi}{6}$
   • $E= \cos\frac{5\pi}{6} + i\sin\frac{5\pi}{6}$
   • $E= \cos\frac{13\pi}{6} + i\sin\frac{13\pi}{6}$
   • $E= \cos\frac{\pi}{6} + i\sin\frac{\pi}{6}$
   Правильно
   

   Неправильно
   
6. Задание 6 из 6

   6.

   Указать особенность первого и второго критерия

   • Оба критерия эквивалентны.
   • С помощью критериев первообразности находятся разные множества первообразных корней.
   • Второй критерий удобнее использовать на практике.
   Правильно
   

   Неправильно
   

Источники

1. Белозеров Г.С. Конспект лекций.
2. Курош А.Г. Курс линейной алгебры. Издание тринадцатое, 2004. Стр.123-128.
3. Фаддеев Д.К. Лекции по алгебре. Наука, 1984. Стр.43-49.

ПРИМЕР

Любой геометрический радиус-вектор плоскости, представим в виде:
[latex] x = ix_1 + jx_2[/latex]

При этом, если [latex] x = ix_1 + jx_2[/latex], [latex] y = iy_1 + jy_2[/latex], то
[latex] x + y = (x_1 + y_1)i +(x_2 + y_2)j[/latex] и [latex] \alpha x = (\alpha x_1)i + (\alpha x_2)j[/latex].
В результате устанавливаем взаимно однозначное соответствие [latex] x \Leftrightarrow (x_1, x_2)[/latex], соответствие между пространствами геометрических радиусов-векторов плоскости и двумерных арифметических векторов. Очевидно, оно будет изоморфизмом данных пространств, так как
если [latex] x \Leftrightarrow (x_1, x_2)[/latex], [latex] y \Leftrightarrow (y_1, y_2)[/latex], то [latex] x + y \Leftrightarrow (x_1 + y_1, x_2 + y_2)[/latex] и [latex] \alpha x \Leftrightarrow ( \alpha x_1, \alpha x_2 )[/latex].

Задача

Даны пространства [latex] A = \mathbb{R}[/latex] и [latex] B = \mathbb{R}[/latex]. Установить между ними соответствие, которое:

1. будет являться изоморфизмом;
2. не будет являться изоморфизмом.

Решение

1. Первое, что мы делаем, это каждому числу [latex] a \in \mathbb{R}[/latex] ставим в соответсвие число [latex] b \in \mathbb{R}[/latex], придерживаясь правила: [latex] b= 2a[/latex]. Каждое [latex] b \in \mathbb{R}[/latex] будет отвечать единственному числу [latex] a= \frac{1}{2}b[/latex]. Отсюда следует, что утверждение [latex] b= 2a[/latex] устанавливает взаимно однозначное соответствие [latex] \mathbb{R} \Leftrightarrow \mathbb{R}[/latex]. Если [latex] a_1 \Leftrightarrow b_1[/latex] и [latex] a_2 \Leftrightarrow b_2[/latex], т.е. [latex] b_1 = 2a_1[/latex] и [latex] b_2= 2a_2[/latex] то [latex] (a_1+a_2) \Leftrightarrow (b_1+b_2)[/latex], так как [latex] b_1+b_2= 2a_1+2a_2 = 2(a_1+a_2)[/latex]. Если [latex] a \Leftrightarrow b[/latex], т.е. [latex] b= 2a[/latex], то [latex] \lambda a \Leftrightarrow \lambda b[/latex] для каждого действительного числа [latex] \lambda [/latex], так как [latex] \lambda b= \lambda 2a= 2 \lambda a[/latex]. Как результат, в данном соответствии [latex] b= 2a[/latex] сохраняются линейные операции, и оно является изоморфизмом.
2. Следующее взаимно однозначное соответствие, которое будем рассматривать [latex] \mathbb{R} \Leftrightarrow \mathbb{R}[/latex], устанавливается формулой [latex] b= a^3[/latex] (число сопоставляемое числу [latex] a= \sqrt[3]{b}[/latex]). Данное соответствие не будет являться изоморфизмом, потому что будет сохранять линейные операции. Как пример, если [latex] a \Leftrightarrow b[/latex], т.е. [latex] b= a^3[/latex], то [latex]{(2a)}^3= 8a^3= 8b[/latex]. Значит, [latex] 2a \Leftrightarrow 8b[/latex], возникает противоречие условию [latex] \lambda a \Leftrightarrow \lambda b[/latex] для [latex] \lambda = 2[/latex] .

Задача

Проверить, являются ли изоморфными пространства:
[latex] X_1= \{ f(x) \in R[x] | f(x) \quad\vdots\quad (x^2+1) \}[/latex] и [latex] X_2[/latex], натянутое на систему векторов [latex] <a_1, a_2, a_3>. a_1=(0,0,1,0,1)[/latex], [latex] a_2=(0,1,0,1,0)[/latex] и [latex] a_3=(1,0,1,0,0)[/latex].

Решение

Найдем базис [latex] X_1[/latex]
[latex] \forall f(x) \in X_1 \Leftrightarrow f(x)= [/latex] [latex](x^2+1)(ax^2+bx+c)=[/latex] [latex]ax^4+bx^3+ax^2+cx^2+bx+c=[/latex] [latex]a(x^4+x^2)+b(x^3+x)+c(x^2+1)[/latex], таким образом [latex]<x^4+x^2,x^3+x,x^2+1>[/latex] — базис.
Очевидно, что система [latex] <a_1,a_2,a_3>[/latex], на которую натянуто [latex] X_2[/latex] ЛНЗ (линейно независимая система), dim [latex] X_1 =[/latex] dim [latex] X_2= 3[/latex]. Следовательно по критерию изоморфности [latex] X_1 \simeq X_2[/latex].

Источники

1. Белозеров Г.С. Конспект лекций
2. Проскуряков И.В. Сборник задач по линейной алгебре. Издание пятое, 1974.Стр. 170

Теоремы о транспозиции

Прежде чем мы будем рассматривать теоремы о транспозиции, попытаемся сформулировать само понятие транспозиции. Транспозицией называется перемена местами двух элементов перестановки .

Теорема 1

Все $ n!$ перестановок длин $ n $ можно расположить одну за другой так, что каждая последующая получается из предыдущей $ 1 $ (одной) транспозицией, начинать можно с любой перестановки.

Доказательство

Доказательство будем проводить индукцией по $ n$ .
База индукции: $ n= 2$ , то получаем перестановки $ (1, 2), (2, 1)$ , тогда расположения будут иметь вид $ (1, 2, 2, 1)$ и $ (2, 1, 1, 2)$ , теорема справедлива.
Предположение индукции: $ n \le m,$ $ m \ge 2$ .
Шаг индукции: $ n= m+1$ $ (i_1, i_2,$ … $, i_{m+1})$ . Рассмотрим все перестановки, где на первом месте стоит $ i_1$ .
$(i_1, {i`}_2,$ …$, {i`}_{m+1})$ ;
$({i`}_2, i_1,$ …$, {i`}_{m+1})$ ;
$({i`}_2, {i`}_1,$ …$, {i«}_{m+1})$ ;
Таких $ m!(m+1)= (m+1)!$ перестановок.
Следствие:
Пусть $ n \ge 2 $ , тогда число $ \frac{n!}{2}$ чётных равно числу $ \frac{n!}{2}$ нечётных перестановок.

Для следующей теоремы нам понадобятся знания таких понятий, как “инверсия”, “чётность перестановок”.

Теорема 2

Любая транспозиция меняет чётность перестановки.

Доказательство

Рассмотрим перестановку …,$ i, j$ , …, где $ i$ и $ j$ транспонируемые символы, стоящие рядом. В результате транспозиции получим новую перестановку …, $j, i $ , …, при этом в данных перестановках каждый из символов $ i$ и $ j$ составит одинаковые инверсии с символами, остающимися на месте, количество таких инверсий $ n$ . В случае, если до этого $ i$ и $ j$ не составляли инверсий, то с новой перестановкой появится и новая инверсия (число инверсий будет равным $ n+1 $ ), в противном случае, число инверсий на $ 1 $ уменьшиться. И в том и в другом случаях чётность перестановки меняется.
Теперь рассмотрим вариант, когда между $ i$ , $ j$ расположено$ s$ символов $ (s>0) $ , т.е. перестановка имеет вид …$ i, k_1, k_2$ , …, $ k_s, j$ ,…. Транспозицию символов $ i$ , $ j$ получим последовательным выполнением $ 2s+1$ транспозиции элементов, стоящих рядом. В итоге, мы меняем четность перестановки нечетное число раз, и по-этому перестановки
…, $ i, k_1, k_2$ , …, $ k_s, j$ ,… и …, $ j, k_1, k_2$ , …, $ k_s, i$ ,… будут противоположной чётности.

Пример

$ (2,5,4,1,3)$ $ \Rightarrow$ $ (1,5,4,2,3)$ $ \Rightarrow$ $ (1,2,4,5,3)$ $ \Rightarrow$
$ (1,2,3,5,4)$ $ \Rightarrow$ $ (1,2,3,4,5)$ .
Здесь, перестановка $(2,5,4,1,3)$ приведена к начальной за $ 4 $ транспозиции и она четная, т.к. $ \tau(2,5,4,1,3)= 6$

Тест о теоремах о транспозиции

Лимит времени: 0

Навигация (только номера заданий)

0 из 6 заданий окончено

Вопросы:

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6

Информация

Данный тест поможет проверить, как вы усвоили материал данной статьи

Вы уже проходили тест ранее. Вы не можете запустить его снова.

Тест загружается...

Вы должны войти или зарегистрироваться для того, чтобы начать тест.

Вы должны закончить следующие тесты, чтобы начать этот:

Результаты

Правильных ответов: 0 из 6

Ваше время:

Время вышло

Вы набрали 0 из 0 баллов (0)

Средний результат
Ваш результат

Рубрики

1. Нет рубрики 0%
2. Алгебра 0%

Ваш результат был записан в таблицу лидеров

Загрузка

Имя: E-Mail:

Капча:

максимум из 11 баллов

Место	Имя	Записано	Баллы	Результат
Таблица загружается
Нет данных

1. 1
2. 2
3. 3
4. 4
5. 5
6. 6

1. С ответом
2. С отметкой о просмотре

1. Задание 1 из 6

   1.

   За какое количество транспозиций перестановка (4, 2, 5, 1, 3) будет приведена к начальной?
   Правильно
   

   Неправильно
   
2. Задание 2 из 6

   2.

   По теореме о транспозиции

   • Любая транспозиция меняет (чётность перестановки)
   Правильно
   

   Неправильно
   
3. Задание 3 из 6

   3.

   Являются ли такое преобразования перестановок транспозицией ?
   2679035418[latex]\Rightarrow[/latex]2479305618

   • Да
   • Нет
   • Невозможно определить
   Правильно
   

   Неправильно
   
4. Задание 4 из 6

   4.

   Перестановка 38524671 является:

   • четной
   • нечетной
   Правильно
   

   Неправильно
   
5. Задание 5 из 6

   5.

   Сопоставить перестановки с числом содержащихся в них инверсий:

   Элементы сортировки

   • 7
   • 10
   • 4

   • ( 1, 5, 8, 3, 2, 4)

   • ( 6, 9, 5, 8, 7, 1)

   • (4, 1, 3, 2, 5, 6)

   Правильно
   

   Неправильно
   
6. Задание 6 из 6

   6.

   Этапы доказательства теоремы 1 (Все [latex] n![/latex] перестановок длин [latex] n[/latex] можно расположить одну за другой так, что каждая последующая получается из предыдущей [latex] 1 [/latex](одной) транспозицией, начинать можно с любой перестановки):

   • $n= 2$, то получаем перестановки $ (1, 2), (2, 1)$, тогда расположения будут иметь вид $ (1, 2, 2, 1)$ и $(2, 1, 1, 2)$, теорема справедлива;
   • $ n \in m,$ $m \ge 2$;
   • Рассмотрим все перестановки, где на первом месте стоит $i_1$.
   • $(i_1, {i`}_2 $, …,$ {i`}_{m+1})$; $({i`}_2, i_1 $, …,$ {i`}_{m+1})$; $({i`}_2, {i`}_1 $, …,$ {i``}_{m+1})$. Таких $ m!(m+1)= (m+1)!$ перестановок.
   Правильно
   

   Неправильно
   

Источники

1. Г.С.Белозеров.Конспект лекций
2. В.В.Воеводин. Линейная алгебра. Второе издание, физико-математическая литература, 1980. Стр. 122-124.
3. А.Г.Курош. Курс линейной алгебры. Издание тринадцатое, 2004. Стр.28-37.