5.0: Prelude to Indices and Discrete Logarithms
- Page ID
- 77430
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)We talked about the cyclic subgroup \(\left<a\right>\) of \((\mathbb{Z}/n\mathbb{Z})^*\) generated by an element \(a\) in the proof of our version of Lagrange’s Theorem 3.3.1, on the way to Euler’s Theorem 3.3.2. Recall it consisted of all powers of \(a\) (well, of \([a]_n\)) in \((\mathbb{Z}/n\mathbb{Z})^*\). Here are some examples:
| \(n\) | \(\phi(n)\) | \((\mathbb{Z}/n\mathbb{Z})^*\) | \(a\) | \(\left<a\right>\) | \(\text{ord}_n(a)\) |
|---|---|---|---|---|---|
| 2 | \)" style="text-align:left;" class="lt-math-77430">\(\{2,\ 2^2\equiv1\}\) | 2 | |||
| 3 | \)" style="text-align:left;" class="lt-math-77430">\(\{3,\ 3^2\equiv1\}\) | 2 | |||
| 2 | \)" style="text-align:left;" class="lt-math-77430">\(\{2,\ 2^2\equiv4,\ 2^3\equiv3,\ 2^4\equiv1\}\) | 4 | |||
| 3 | \)" style="text-align:left;" class="lt-math-77430">\(\{3,\ 3^2\equiv4,\ 3^3\equiv2,\ 3^4\equiv1\}\) | 4 | |||
| 4 | \)" style="text-align:left;" class="lt-math-77430">\(\{4,\ 4^2\equiv1\}\) | 2 | |||
| 5 | \)" style="text-align:left;" class="lt-math-77430">\(\{5,\ 5^2\equiv1\}\) | 2 | |||
| 2 | \)" style="text-align:left;" class="lt-math-77430">\(\{2,\ 2^2\equiv4,\ 2^3\equiv1\}\) | 3 | |||
| 3 | \)" style="text-align:left;" class="lt-math-77430">\(\{3,\ 3^2\equiv2,\ 3^3\equiv6,\ 3^4\equiv4,\ 3^5\equiv5,\ 3^6\equiv1\}\) | 6 | |||
| 4 | \)" style="text-align:left;" class="lt-math-77430">\(\{4,\ 4^2\equiv2,\ 4^3\equiv1\}\) | 3 | |||
| 5 | \)" style="text-align:left;" class="lt-math-77430">\(\{5,\ 5^2\equiv4,\ 5^3\equiv6,\ 5^4\equiv2,\ 5^5\equiv3,\ 5^6\equiv1\}\) | 6 | |||
| 6 | \)" style="text-align:left;" class="lt-math-77430">\(\{6,\ 6^2\equiv1\}\) | 2 | |||
| 3 | \)" style="text-align:left;" class="lt-math-77430">\(\{3,\ 3^2\equiv1\}\) | 2 | |||
| 5 | \)" style="text-align:left;" class="lt-math-77430">\(\{5,\ 5^2\equiv1\}\) | 2 | |||
| 7 | \)" style="text-align:left;" class="lt-math-77430">\(\{7,\ 7^2\equiv1\}\) | 2 | |||
| 2 | 1 | \(\{1\}\) | 1 | \)" style="text-align:left;" class="lt-math-77430">\(\{1\}\) | 1 |
| 3 | 2 | \(\{1,\ 2\}\) | 1 | \)" style="text-align:left;" class="lt-math-77430">\(\{1\}\) | 1 |
| 4 | 2 | \(\{1,\ 3\}\) | 1 | \)" style="text-align:left;" class="lt-math-77430">\(\{1\}\) | 1 |
| 6 | 2 | \(\{1,\ 5\}\) | 1 | \)" style="text-align:left;" class="lt-math-77430">\(\{1\}\) | 1 |
| 5 | 4 | \(\{1,\ 2,\ 3,\ 4\}\) | 1 | \)" style="text-align:left;" class="lt-math-77430">\(\{1\}\) | 1 |
| 8 | 4 | \(\{1,\ 3,\ 5,\ 7\}\) | 1 | \)" style="text-align:left;" class="lt-math-77430">\(\{1\}\) | 1 |
| 7 | 6 | \(\{1,\ 2,\ 3,\ 4,\ 5,\ 6\}\) | 1 | \)" style="text-align:left;" class="lt-math-77430">\(\{1\}\) | 1 |
Each of these cyclic subgroups \(\left<a\right>\) has a size – being the order \(\text{ord}_n(a)\) of its generator – which divides the size of the ambient \((\mathbb{Z}/n\mathbb{Z})^*\), as we know will happen from Euler’s Theorem 3.3.2.
Some random things we also notice, which might or might not hold true in general, given the small amount of evidence in this table, are:
- frequently there is an element \(a\) which generates the biggest possible cyclic subgroup: \(\left<a\right>=(\mathbb{Z}/n\mathbb{Z})^*\);
- there seem always to be those big cyclic subgroups in \(\mathbb{Z}/n\mathbb{Z}\) when \(n\) is a prime;
- even some composite \(n\) give a \(\mathbb{Z}/n\mathbb{Z}\) which contains a big cyclic subgroup, except for the case of the largest power of \(2\), which was \(n=2^3\), that we tried.
Just to see if those possible general statements hold a bit further, let’s compute two more examples. For these we give only the sizes of \((\mathbb{Z}/n\mathbb{Z})^*\) and \(\left<a\right>\), not complete lists of their elements, to conserve space and since the elements of \((\mathbb{Z}/n\mathbb{Z})^*\) can be found in the column labelled “\(a\)”:
| \(n\) | \(\phi(n)\) | \(a\in(\mathbb{Z}/n\mathbb{Z})^*\) | \(\text{ord}_n(a)\) |
|---|---|---|---|
| 16 | 8 | 1 | 1 |
| 3 | 4 | ||
| 5 | 4 | ||
| 7 | 2 | ||
| 9 | 2 | ||
| 11 | 4 | ||
| 13 | 4 | ||
| 15 | 2 | ||
| 17 | 16 | 1 | 1 |
| 2 | 8 | ||
| 3 | 16 | ||
| 4 | 4 | ||
| 5 | 16 | ||
| 6 | 16 | ||
| 7 | 16 | ||
| 8 | 8 | ||
| 9 | 8 | ||
| 10 | 16 | ||
| 11 | 16 | ||
| 12 | 16 | ||
| 13 | 4 | ||
| 14 | 16 | ||
| 15 | 8 | ||
| 16 | 2 |
Our guesses (large powers of \(2\) not so good; other \(n\)’s, particularly prime, are good) still hold true. Of course, any finite amount of evidence for a general mathematical statement is very inconclusive....
Now to the formal analysis