Skip to main content
Contents Index Dark Mode Prev Up Next \(\newcommand{\mylongdiv}[2]{#1\,\enclose{longdiv}{#2}}
\renewcommand{\emptyset}{\{\}}
\newcommand{\blanksp}{\underline{\hspace{.25in}}}
\newcommand{\eridfive}{\mathbf{\forall}}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\cspace}{-}
\newcommand{\Ta}{\mathtt{a}}
\newcommand{\Tb}{\mathtt{b}}
\newcommand{\Tc}{\mathtt{c}}
\newcommand{\Td}{\mathtt{d}}
\newcommand{\Te}{\mathtt{e}}
\newcommand{\Tf}{\mathtt{f}}
\newcommand{\Tg}{\mathtt{g}}
\newcommand{\Th}{\mathtt{h}}
\newcommand{\Ti}{\mathtt{i}}
\newcommand{\Tj}{\mathtt{j}}
\newcommand{\Tk}{\mathtt{k}}
\newcommand{\Tl}{\mathtt{l}}
\newcommand{\Tm}{\mathtt{m}}
\newcommand{\Tn}{\mathtt{n}}
\newcommand{\To}{\mathtt{o}}
\newcommand{\Tp}{\mathtt{p}}
\newcommand{\Tq}{\mathtt{q}}
\newcommand{\Tr}{\mathtt{r}}
\newcommand{\Ts}{\mathtt{s}}
\newcommand{\Tt}{\mathtt{t}}
\newcommand{\Tu}{\mathtt{u}}
\newcommand{\Tv}{\mathtt{v}}
\newcommand{\Tw}{\mathtt{w}}
\newcommand{\Tx}{\mathtt{x}}
\newcommand{\Ty}{\mathtt{y}}
\newcommand{\Tz}{\mathtt{z}}
\newcommand{\So}{\Tf}
\newcommand{\Sno}{\Tg}
\newcommand{\Si}{\Th}
\newcommand{\Sni}{\Tj}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\W}{\mathbb{W}}
\newcommand{\ZZ}{\Z}
\newcommand{\PP}{\mathbb{P}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\RR}{\R}
\newcommand{\F}{\mathbb{F}}
\newcommand{\A}{\mathbb{A}}
\newcommand{\abs}[1]{|#1|}
\newcommand{\fmod}{\bmod}
\newcommand{\fdiv}{\,\mathrm{div}\,}
\newcommand{\lcm}{\mathrm{lcm}}
\newcommand{\id}{\mathrm{id}}
\newcommand{\nr}[1]{\##1}
\newcommand{\gexp}[3]{#1^{#2 #3}}
\newcommand{\gexpp}[3]{\displaystyle\left(#1\right)^{#2 #3}}
\newcommand{\glog}[3]{\log_{#1}^{#3}#2}
\newcommand{\sol}[1]{{\color{blue}\textit{#1}}}
\newcommand{\gro}[1]{{\color{gray}#1}}
\newcommand{\todo}[1]{{\color{purple}TO DO: #1}}
\newcommand{\fixme}[1]{{\color{red}FIX ME: #1}}
\newcommand{\checkme}[1]{{\color{green}CHECK ME: #1}}
\newcommand{\degre}{^\circ}
\newcommand{\vect}[1]{\overrightarrow{#1}}
\newcommand{\nix}{}
\newcommand{\cox}[1]{\fcolorbox[HTML]{000000}{#1}{\phantom{M}}}
\newcommand{\tox}[1]{\texttt{\##1} \amp \cox{#1}}
\newcommand{\ttx}[1]{\texttt{\##1}}
\newcommand{\mox}[1]{\mathtt{\##1}}
\newcommand{\xx}{\mathtt{\#}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 15.1 Exponentiation in Groups
Recall that \(\cdot:\Z \times \Z \to \Z\) (multiplication) is a binary operation on the set \(\Z\) of integers. We defined exponentiation as repeated multiplication. For \(a\in\Z\) and \(n\in\N\text{,}\) we used the notation
\begin{equation*}
a^n := \underbrace{a \cdot a \cdot \ldots \cdot a}_{n \text{ copies of }a }
\end{equation*}
and also defined \(a^0:=1\text{.}\) We now extend this definition from powers of integers to powers of group elements.
Following the definition of powers of integers in
Definition 1.4.1 , we define exponentiation of group elements as repeated use of the group operation. We write the binary operation next to the exponent to show which operation is used.
Definition 15.1.1 .
Let \((G,\star)\) be a group and \(b\in G\text{.}\)
We set
\(\gexp{b}{0}{\star}=e\) where
\(e\in G\) is the identity of the group
\((G,\star)\text{.}\)
For
\(n\in\N\) we set
\(\gexp{b}{n}{\star}=\underbrace{b\star b\star\dots\star b}_{n \text{ copies of }b}\text{.}\)
We read
\(\gexp{b}{n}{\star}\) as “
\(b\) to the
\(n\) by
\(\star\) ”. We call
\(b\) the
base and
\(n\) the
exponent .
It follows from the definition that in a group
\((G,\star)\) we have
\(\gexp{b}{1}{\star}=b\) for all
\(b\in G\text{.}\) For the identity
\(e\) of any group we have
\(\gexp{e}{x}{\star}=e\) for all
\(x\in\W\text{.}\)
Theorem 15.1.2 .
Let \((G,\star)\) be a group and \(b\in G\text{.}\) Let \(m\in\N\) and \(n\in\N\text{.}\) In \((G,\star)\) we have
\(\displaystyle \displaystyle\gexp{b}{m}{\star}\star \gexp{b}{n}{\star} = \gexp{b}{(m+n)}{\star}\)
\(\displaystyle \displaystyle \gexp{(\gexp{b}{m}{\star})}{n}{\star} = \gexp{b}{(m\cdot n)}{\star}\)
Proof.
Both statements are proven by counting the number of copies of the base
\(b\) when rewriting the powers according to
Definition 15.1.1 .
\begin{align*}
\gexp{b}{m}{\star}\star \gexp{b}{n}{\star} \amp =
\underbrace{b\star\dots\star b}_{m \text{ copies of } b } \star \underbrace{b\star\dots\star b}_{n \text{ copies of } b}\\
\amp = \underbrace{b\star\dots\star b}_{m + n \text{ copies of }b} = \gexp{b}{(m+n)}{\star}
\end{align*}
\begin{align*}
\gexp{(\gexp{b}{m}{\star})}{n}{\star} \amp =
\underbrace{\gexp{b}{m}{\star}\star\dots\star \gexp{b}{m}{\star}}_{n \text{ copies of }\gexp{b}{m}{\star}} \\
\amp = \underbrace{\underbrace{b\star\dots\star b}_{m \text{ copies of }b } \star\dots\star \underbrace{b\star\dots\star b}_{m \text{copies of }b}}_{n\text{ copies of } \underbrace{(b\star\dots\star b)}_{m \text{ copies of }b} } \\
\amp = \underbrace{b\star\dots\star b}_{m \cdot n\text{ copies of }b} = \gexp{b}{(m\cdot n)}{\star}
\end{align*}
Note that the notation of inverses for binary operations in
Definition 13.4.4 is chosen such that the properties proven above also work for negative exponents. In a group
\((G,\star)\) with identity
\(e\) for
\(a\in G\) we have
\begin{equation*}
\gexp{a}{1}{\star} \star \gexp{a}{-1}{\star} = \gexp{a}{(1 + (-1))}{\star}=\gexp{a}{0}{\star}=e\text{.}
\end{equation*}
Our definition of exponentiation works in every group. Our examples use only the groups
\((\Z_p^\otimes,\otimes)\text{,}\) where
\(p\) is prime and the operation
\(\otimes:\Z_p^\otimes\times\Z_p^\otimes\to\Z_p^\otimes\) is given by
\(a\otimes b=(a\cdot b)\bmod p\text{.}\)
Specializing
Definition 15.1.1 to the group
\((\Z_p^\otimes,\otimes)\) we have for all
\(b\in\Z_p^\otimes\) that
\begin{equation*}
\gexp{b}{0}{\otimes}=1
\end{equation*}
and for all \(b\in\Z_p^\otimes\) and all \(n\in\N\) that
\begin{equation*}
\gexp{b}{n}{\otimes} =\underbrace{b\otimes b\otimes\dots\otimes b}_{n\text{ copies of }b }= (\underbrace{b\cdot b\cdot\dots\cdot b}_{n\text{ copies of }b })\fmod p= (b^n)\fmod p.
\end{equation*}
Example 15.1.3 . Powers of elements of \((\Z_{11}^\otimes,\otimes)\) .
In \((\Z_{11}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 11\) we have
\(\gexp{2}{3}{\otimes}=2\otimes 2\otimes 2=(2\cdot 2\cdot 2) \bmod 11 = 8 \bmod 11 = 8\) by
Definition 15.1.1 Item 2
\(\gexp{2}{4}{\otimes}=2\otimes 2\otimes 2\otimes 2=(2\cdot 2\cdot 2\cdot 2) \bmod 11=16\bmod 11 = 5\) by
Definition 15.1.1 Item 2
For larger numbers, it is easier to compute
\(\fmod\) after each multiplication.
Example 15.1.4 . Two ways for computing \(\gexp{6}{8}{\otimes}\) .
In the group \((\Z_{11}^\otimes,\otimes)\) where \(a\otimes b=(a\cdot b)\fmod 11\) we compute
\begin{equation*}
\gexp{6}{8}{\otimes}=6\otimes 6\otimes6\otimes6\otimes6\otimes6\otimes6\otimes6\text{.}
\end{equation*}
We use two approaches.
We directly follow the definition, that is, we repeatedly apply \(a \otimes b=(a\cdot b)\fmod 11\text{.}\) We first compute
\begin{equation*}
\gexp{6}{2}{\otimes}=6\otimes 6=(6\cdot 6)\fmod 11=36 \fmod 11= 3
\end{equation*}
We now compute the other powers up to
\(\gexp{6}{8}{\otimes}\) making use of the previous result. In every step we apply
Theorem 15.1.2 Item 1 .
\begin{align*}
\gexp{6}{3}{\otimes}\amp =\gexp{6}{2}{\otimes}\otimes 6=3\otimes 6=(3\cdot 6)\fmod 11=18\fmod 11=7\\
\gexp{6}{4}{\otimes}\amp =\gexp{6}{3}{\otimes}\otimes 6=7\otimes 6=(7\cdot 6)\fmod 11=42\fmod 11=9\\
\gexp{6}{5}{\otimes}\amp =\gexp{6}{4}{\otimes}\otimes 6=9\otimes 6=(9\cdot 6)\fmod 11=54\fmod 11=10\\
\gexp{6}{6}{\otimes}\amp =\gexp{6}{5}{\otimes}\otimes 6=10\otimes 6=(10\cdot 6)\fmod 11=60\fmod 11=5\\
\gexp{6}{7}{\otimes}\amp =\gexp{6}{6}{\otimes}\otimes 6=5\otimes 6=(5\cdot 6)\fmod 11=30\fmod 11=8\\
\gexp{6}{8}{\otimes}\amp =\gexp{6}{7}{\otimes}\otimes 6=8\otimes 6=(8\cdot 6)\fmod 11=48\fmod 11=4
\end{align*}
We have computed \(\gexp{6}{8}{\otimes}=4\text{.}\)
We compute \(6^8\) in the integers and then compute the result \(\fmod 11\text{:}\)
\begin{equation*}
\gexp{6}{2}{\otimes}=6^8\fmod 11=1679616\fmod 11=4
\end{equation*}
We can easily do the computations in
Item 1 by hand, but we would not want to compute
\(6^8\) without a calculator. When the bases and exponents are larger, the second approach is no longer practical because the numbers become too large for most calculators.
The calculations in
Example 15.1.4 and
Item 1 follow
Definition 15.1.1 . This method is called
naive exponentiation . We used the same strategy in
Algorithm 2.6.1 to compute powers of integers. For group elements, we replace integer multiplication with the group operation.
Algorithm 15.1.5 . Naive Exponentiation for Group Elements.
Input:
A group
\((G,\star)\text{,}\) \(b\in G\text{,}\) and a non-negative integer
\(n\)
Output:
\(\displaystyle \gexp{b}{n}{\star}\)
if \(n=0\) then return the identity of
\((G,\star)\)
if \(n=1\) then return \(b\)
The video in
Figure 15.1.6 reviews exponentiation in groups and shows each step of the naive exponentiation algorithm.
Figure 15.1.6. Exponentiation in Groups by Matt Farmer and Stephen Steward
