\documentclass{article}
\usepackage{amsmath,amssymb,geometry}
\geometry{margin=0.55in}

\title{Exercise 1 Cheat Sheet\\Multiplicative Groups of $(\mathbb Z/n\mathbb Z)^*$}
\date{}
\author{}

\begin{document}
\maketitle

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Recognition}

Use this algorithm when asked to:
\begin{itemize}
\item Find the order of an element.
\item Count elements of order $k$.
\item Find all elements of order $k$.
\end{itemize}

If

\[
n=pq,
\]

then

\[
\boxed{
(\mathbb Z/n\mathbb Z)^*
\cong
(\mathbb Z/p\mathbb Z)^*
\times
(\mathbb Z/q\mathbb Z)^*
}
\]

Always split with the Chinese Remainder Theorem (CRT).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Facts}

\[
|(\mathbb Z/p\mathbb Z)^*|=p-1,
\qquad
|(\mathbb Z/n\mathbb Z)^*|=(p-1)(q-1).
\]

Each $(\mathbb Z/p\mathbb Z)^*$ is cyclic.

\[
\boxed{
\operatorname{ord}(x)
=
\operatorname{lcm}
(\operatorname{ord}(x_p),\operatorname{ord}(x_q))
}
\]

A cyclic group has exactly

\[
\boxed{
\phi(d)
}
\]

elements of order $d$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{(a) Find the Order of $a$}

\textbf{1. Factor $n$.}

\[
n=pq
\]

GAP:

\[
\texttt{FactorsInt(n);}
\]

\vspace{1mm}

\textbf{2. Compute orders modulo each prime.}

Since

\[
a^{p-1}\equiv1\pmod p,
\]

the order divides $p-1$.

Start with

\[
t=p-1.
\]

Factor $t$.

For every prime divisor $r$:

\[
\boxed{
\text{while }
a^{t/r}\equiv1\pmod p,
\quad
t\leftarrow t/r
}
\]

Idea: repeatedly shrink the exponent until it cannot be reduced.

Then

\[
t=t_p=\operatorname{ord}(a\bmod p).
\]

Repeat for $q$ to obtain $t_q$.

Useful GAP:

\[
\texttt{FactorsInt(p-1);}
\]

\[
\texttt{PowerMod(a,e,p);}
\]

\[
\texttt{OrderMod(a,p);} \qquad \text{(verification)}
\]

\vspace{1mm}

\textbf{3. Combine}

\[
\boxed{
\operatorname{ord}(a)
=
\operatorname{lcm}(t_p,t_q)
}
\]

GAP:

\[
\texttt{Lcm(tp,tq);}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{(b) Count Elements of Order $k$}

\textbf{1. List divisors}

\[
d_1\mid(p-1),
\qquad
d_2\mid(q-1).
\]

GAP:

\[
\texttt{DivisorsInt(p-1);}
\]

\[
\texttt{DivisorsInt(q-1);}
\]

\vspace{1mm}

\textbf{2. Keep only}

\[
\boxed{
\operatorname{lcm}(d_1,d_2)=k.
}
\]

\vspace{1mm}

\textbf{3. Count}

A cyclic group contributes

\[
\phi(d)
\]

elements of order $d$.

Therefore

\[
\boxed{
\sum_{\operatorname{lcm}(d_1,d_2)=k}
\phi(d_1)\phi(d_2)
}
\]

GAP:

\[
\texttt{Phi(d);}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{(c) Find All Elements of Order $k$}

\textbf{1. Find valid sub-orders}

List

\[
d_1\mid(p-1),
\qquad
d_2\mid(q-1),
\]

and keep only

\[
\boxed{
\operatorname{lcm}(d_1,d_2)=k.
}
\]

\vspace{2mm}

\textbf{2. Find generators}

Test small integers ($2,3,5,\ldots$) until one passes:

\[
g^{(p-1)/r}\not\equiv1\pmod p
\]

for every prime divisor $r$ of $p-1$.

Repeat for $q$.

GAP:

\[
\texttt{GeneratorsPrimeResidues(p);}
\]

\vspace{2mm}

\textbf{3. Build all subgroup elements}

For each valid pair $(d_1,d_2)$:

\[
a=g_p^{(p-1)/d_1},
\qquad
b=g_q^{(q-1)/d_2}.
\]

These produce one element of orders $d_1$ and $d_2$.

To obtain \emph{all} elements:

\[
a^m,
\qquad
1\le m<d_1,
\qquad
\gcd(m,d_1)=1,
\]

\[
b^n,
\qquad
1\le n<d_2,
\qquad
\gcd(n,d_2)=1.
\]

There are exactly

\[
\phi(d_1),
\qquad
\phi(d_2)
\]

such elements.

Manual shortcut:

\begin{itemize}
\item List $1,\ldots,d-1$.
\item Cross out multiples of every prime factor of $d$.
\item Remaining exponents are exactly the coprime ones.
\end{itemize}

\vspace{2mm}

\textbf{4. Combine with CRT}

For every pair $(a^m,b^n)$ solve

\[
x\equiv a^m\pmod p,
\qquad
x\equiv b^n\pmod q.
\]

Each CRT solution has order $k$.

GAP:

\[
\texttt{ChineseRem(a,p,b,q);}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Workflow}

\[
\boxed{
\begin{array}{c}
\text{Factor }n\\
\downarrow\\
\text{CRT}\\
\downarrow\\
\begin{cases}
(a)\ \text{Find }t_p,t_q\rightarrow\operatorname{LCM}\\
(b)\ \text{Divisors}\rightarrow\phi(d_1)\phi(d_2)\\
(c)\ \text{Generators}\rightarrow g^{(p-1)/d}\rightarrow\text{CRT}
\end{cases}
\end{array}
}
\]

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section*{Common Mistakes}

\begin{itemize}
\item Never compute the order directly modulo $n$; split with CRT first.
\item Orders combine by \textbf{LCM}, never multiplication.
\item $\phi(d)$ counts elements of order $d$ only because each $(\mathbb Z/p\mathbb Z)^*$ is cyclic.
\item To obtain \emph{all} elements of order $d$, use every exponent coprime to $d$.
\item Before counting or constructing elements of order $k$, verify there exist
\[
d_1\mid(p-1),\qquad d_2\mid(q-1)
\]
such that
\[
\operatorname{lcm}(d_1,d_2)=k.
\]
\end{itemize}

\end{document}