multiplicative order of an integer modulo mMultiplicativeOrderOfAnIntegerModuloM2006-10-26 13:55:512007-05-30 12:32:01Definition${\mathbb{Z}}_n$% this is the default PlanetMath preamble. as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.
% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}
% there are many more packages, add them here as you need them
% define commands here
\newtheorem{thm}{Theorem}
\newtheorem*{defn}{Definition}
\newtheorem{prop}{Proposition}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\theoremstyle{definition}
\newtheorem{exa}{Example}
\newtheorem*{rem}{Remarks}
% Some sets
\newcommand{\Nats}{\mathbb{N}}
\newcommand{\Ints}{\mathbb{Z}}
\newcommand{\Reals}{\mathbb{R}}
\newcommand{\Complex}{\mathbb{C}}
\newcommand{\Rats}{\mathbb{Q}}
\newcommand{\Gal}{\operatorname{Gal}}
\newcommand{\Cl}{\operatorname{Cl}}\PMlinkescapeword{order}
\begin{defn}
Let $m>1$ be an integer and let $a$ be another integer relatively prime to $m$. The \PMlinkname{order}{OrderGroup} of $a$ modulo $m$ (or the multiplicative order of $a \mod m$) is the smallest positive integer $n$ such that $a^n\equiv 1 \mod m$. The order is sometimes denoted by $\operatorname{ord} a$ or $\operatorname{ord}_m a$.
\end{defn}
\begin{rem} Several remarks are in order:
\begin{enumerate}
\item Notice that if $\gcd(a,m)=1$ then $a$ belong to the units $(\Ints/m\Ints)^\times$ of $\Ints/m\Ints$. The units $(\Ints/m\Ints)^\times$ form a group with respect to multiplication, and the number of elements in the subgroup generated by $a$ (and its powers) is the order of the integer $a$ modulo $m$.
\item By Euler's theorem, $a^{\phi(m)} \equiv 1 \mod m$, therefore the order of $a$ is less or equal to $\phi(m)$ (here $\phi$ is the Euler phi function).
\item The order of $a$ modulo $m$ is precisely $\phi(m)$ if and only if $a$ is a primitive root for the integer $m$.
\end{enumerate}
\end{rem}