Definition:Root of Unity Modulo m

This page has been identified as a candidate for refactoring of medium complexity. In particular: Extract the tables into separate pages, and extract the supplementary statements in the Definition section into their own pages. Until this has been finished, please leave {{Refactor}} in the code. New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Refactor}} from the code.

Definition

Let $n \in \Z_{>0}$ be a positive integer.

Let $m \in \Z_{>1}$ be a positive integer greater than one.

Then $a$ is an $n^{th}$ root of unity modulo $m$ if and only if:

$a^n \equiv 1 \pmod m$

Solving the following equation over the smallest integers modulo $m$:

$\ds \paren {a^n - 1} = \paren {a - 1} \paren {\sum_{k \mathop = 0}^{n - 1} a^k} \equiv 0 \pmod m$

will produce the roots.

Any root found will also have $a + k m$ as a solution, where $k \in \Z$ is any integer.

Euler's Function $\map \phi m$ root of unity modulo $m$ is the set of all positive integers less than $m$.

This article, or a section of it, needs explaining. In particular: The above statement needs tightening: what has been described "$\map \phi m$ root of unity modulo $m$" is not clearly defined and (while it possibly may be used to define a set by predicate, is does not appear itself actually to be a set. Difficult to tell. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Table of Roots of Unity Modulo $m$

Prime numbers are in bold font.

$\begin{array}{|c|c|}

\hline n & a \\ \hline 1 & 1 \\ \mathbf 2 & \pm 1, \pm a_2 \\ \mathbf 3 & 1, a_3, -a_3 - 1, b_3 \\ 4 & \pm 1,\pm a_4, b_4 \\ \vdots \\ \map \phi m & 1, 2, 3, \ldots, m \\ \hline \end{array}$

This article, or a section of it, needs explaining. In particular: The contents of the right hand column need to be explained and defined. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by explaining it. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Explain}} from the code.

Table of Non-trivial Square Roots of Unity Modulo $m$

Solutions for $1 < a < m$ of:

$\paren {a^2 - 1} = \paren {a - 1} \paren {a + 1} \equiv 0 \pmod m$

$\begin{array}{|c|l|}

\hline m & a_2 \\ \hline 8 & \mathbf 3 \\ 12 & \mathbf 5 \\ 15 & 4 \\ 16 & \mathbf 7 \\ 20 & 9 \\ 21 & 8 \\ 24 & \mathbf{5},\mathbf{7},\mathbf{11} \\ 28 & \mathbf{13} \\ 30 & \mathbf{11} \\ 32 & 15 \\ 33 & 10 \\ 35 & 6 \\ 36 & \mathbf{17} \\ 39 & 14 \\ 40 & 9,\mathbf{11},\mathbf{19} \\ 42 & \mathbf{13} \\ 44 & 21 \\ 45 & \mathbf{19} \\ 48 & \mathbf{7},\mathbf{17},\mathbf{23} \\ 51 & 16 \\ 52 & 25 \\ 55 & 21 \\ 56 & \mathbf{13},15,27 \\ 57 & 20 \\ 60 & \mathbf{11},\mathbf{19},\mathbf{29} \\ 63 & 8 \\ 64 & \mathbf{31} \\ 65 & 14 \\ 66 & \mathbf{23} \\ 68 & 33 \\ 69 & 22 \\ 70 & \mathbf{29} \\ 72 & \mathbf{17},\mathbf{19},35 \\ 75 & 26 \\ 76 & \mathbf{37} \\ 77 & 34 \\ 78 & 25 \\ 80 & 9,\mathbf{31},39 \\ 84 & \mathbf{13},\mathbf{29},\mathbf{41} \\ 85 & 16 \\ 87 & 28 \\ 88 & 21,\mathbf{23},\mathbf{43} \\ 90 & \mathbf{19} \\ 91 & 27 \\ 92 & 45 \\ 93 & 32 \\ 95 & 39 \\ 96 & \mathbf{17},\mathbf{31},\mathbf{47} \\ 99 & 10 \\ 100 & 49 \\ \vdots \\ \hline \end{array}$

Table of Non-trivial Cubic Roots of Unity Modulo $m$

Solutions for $1 < a < m$ of:

$\paren {a^3 - 1} = \paren {a - 1} \paren {a^2 + a + 1} \equiv 0 \pmod m$

$\begin{array}{|c|l|l|} \hline

m & a_3 & b_3 \\ \hline \mathbf{7} & \mathbf{2} & \\ 9 & 4,\mathbf{7} & \\ \mathbf{13} & \mathbf{3} & \\ 14 & & 9,\mathbf{11} \\ 18 & & \mathbf{7},\mathbf{13} \\ \mathbf{19} & \mathbf{7} \\ 21 & 4 \\ 26 & & \mathbf{3},9 \\ 27 & & 10,\mathbf{19} \\ 28 & & 9,25 \\ \mathbf{31} & \mathbf{5} \\ 35 & & \mathbf{11},16 \\ 36 & & \mathbf{13},25 \\ \mathbf{37} & 10 \\ 38 & & \mathbf{7},\mathbf{11} \\ 39 & 16 \\ 42 & & 25,\mathbf{37} \\ \mathbf{43} & 6 \\ 45 & & 16,\mathbf{31} \\ 49 & 18 \\ 52 & & 9,\mathbf{29} \\ 54 & & \mathbf{19},\mathbf{37} \\ 56 & & 9,25 \\ \mathbf{57} & \mathbf{7} \\ \mathbf{61} & \mathbf{13} \\ 62 & & \mathbf{5},25 \\ 63 & 4,16,25 & 22,43\\ 65 & & 16,61 \\ \mathbf{67} & \mathbf{29} \\ 70 & & \mathbf{11},51 \\ 72 & & 25,49 \\ \mathbf{73} & 8 \\ 74 & & \mathbf{47},63 \\ 76 & & 45,49 \\ 77 & & \mathbf{23},\mathbf{67} \\ 78 & & 55,\mathbf{61} \\ \mathbf{79} & \mathbf{23},55 \\ 81 & & 28,55 \\ 84 & & 25,\mathbf{37} \\ 86 & & 49,79 \\ 90 & & \mathbf{31},\mathbf{61} \\ 91 & 9,16 & 22,\mathbf{29},\mathbf{53},\mathbf{79} \\ 93 & 25 \\ 95 & & \mathbf{11},26 \\ \mathbf{97} & 35 \\ 98 & & \mathbf{67},\mathbf{79} \\ 99 & & 34,\mathbf{67} \\ \vdots \\ \hline \end{array}$

Table of Non-trivial Quartic Roots of Unity Modulo $m$

Solutions for $1 < a < m$ of:

$\paren {a^4 - 1} = \paren {a - 1} \paren {a + 1} \paren {a^2 + 1} \equiv 0 \pmod m$

$\begin{array}{|c|l|l|} \hline

m & a_4 & b_4 \\ \hline \mathbf{5} & \mathbf{2} \\ 8 & \mathbf{3} \\ 10 & \mathbf{3} \\ 12 & \mathbf{5} \\ \mathbf{13} & \mathbf{5} \\ 15 & \mathbf{2},4,\mathbf{7} \\ 16 & \mathbf{3},\mathbf{5},\mathbf{7} \\ \mathbf{17} & 4 \\ 20 & \mathbf{3},\mathbf{7},9 \\ 21 & 8 \\ 24 & \mathbf{5},\mathbf{7},\mathbf{11} \\ 25 & \mathbf{7} \\ 26 & \mathbf{5} \\ 28 & \mathbf{13} \\ \mathbf{29} & 12 \\ 30 & \mathbf{7},\mathbf{11},\mathbf{13} \\ 32 & \mathbf{7},9,15 \\ 33 & 10 \\ 34 & \mathbf{13} \\ 35 & 6,8,\mathbf{13} \\ 36 & \mathbf{17} \\ \mathbf{37} & 6 \\ 39 & \mathbf{5},8,14 \\ 40 & \mathbf{3},\mathbf{7},9,\mathbf{11},\mathbf{13},\mathbf{17},\mathbf{19} \\ \mathbf{41} & 9 \\ 42 & \mathbf{13} \\ 44 & 21 \\ 45 & 8,\mathbf{17},\mathbf{19} \\ 48 & \mathbf{5},\mathbf{7},\mathbf{11},\mathbf{13},\mathbf{17},\mathbf{19},\mathbf{23} \\ 50 & \mathbf{7} \\ 51 & 4,\mathbf{13},16 \\ 52 & \mathbf{5},21,25 \\ \mathbf{53} & \mathbf{23} \\ 55 & 12,21,\mathbf{23} \\ 56 & \mathbf{13},15,27 \\ \mathbf{57} & 20 \\ 58 & \mathbf{17} \\ 60 & \mathbf{7},\mathbf{11},\mathbf{13},\mathbf{17},\mathbf{19},\mathbf{23},\mathbf{29} \\ \mathbf{61} & \mathbf{11} \\ 63 & 8 \\ 64 & 15,\mathbf{17},\mathbf{31} \\ 65 & 8,12,14,18,21,27,\mathbf{31} \\ 66 & \mathbf{23} \\ 68 & \mathbf{13},21,33 \\ 69 & 22 \\ 70 & \mathbf{13},27,\mathbf{29} \\ 72 & \mathbf{17},\mathbf{19},35 & 66 \\ \mathbf{73} & 27 \\ 74 & \mathbf{31} \\ 75 & \mathbf{7},26,32 \\ 76 & \mathbf{37} \\ 77 & 34 \\ 78 & 25,\mathbf{31} \\ 80 & \mathbf{3},\mathbf{7},9,\mathbf{11},\mathbf{13},\mathbf{17},\mathbf{19},21,\mathbf{23},27,\mathbf{29},\mathbf{31},33,\mathbf{37},39 & 70 \\ 81 & & 66,69,72,75,78 \\ 82 & 9 \\ 84 & \mathbf{13},\mathbf{29},\mathbf{41} \\ 85 & 4,\mathbf{13},16,18,21,33,38 \\ 86 & & 82 \\ \mathbf{87} & \mathbf{17},28,\mathbf{41} \\ 88 & 21,\mathbf{23},43 & 66 \\ 89 & 34 & 81,84 \\ 90 & \mathbf{17},\mathbf{19},\mathbf{37} \\ 91 & 8,27,34 \\ 92 & 45 \\ 93 & 32 \\ 95 & 18,\mathbf{37},39 \\ 96 & \mathbf{7},\mathbf{17},\mathbf{23},25,\mathbf{31},\mathbf{41},\mathbf{47} & 72,84 \\ \mathbf{97} & 22 \\ 98 & & 70,84 \\ 99 & 10 & 66 \\ 100 & \mathbf{7},43,49 & 70,80,90 \\ \vdots \\ \hline \end{array}$