Abstract Algebra – Finding Order of an Element in Modular Arithmetic

abstract-algebramodular arithmetic

I'm a bit new to abstract algebra and while learning it, I've come across a somewhat tedious problem.

I'm curious as to whether or not there is some modular congruency trick/number theory that lets you immediately find the order of an element in the group integers $n$ modulo $n$ without having to write out all its multiples.

The group integers $n$ modulo $n$ is a group with addition $mod$ $n$.

So far, I have been checking at which $i \geq 1$ for some $a \in G$ such that $ia$ mod $n = 0$ and, least to say, it has been quite cumbersome without a quick computer script.

Best Answer

The (additive) order of $a$ modulo $n$ is the smallest positive integer $k$ such that $ka$ is a multiple of $n$. By definition this is the l.c.m. of $a$ and $n$, so $$k=\frac n d,\quad\text{where}\enspace d=\gcd(a,n).$$

You can find it with the extended Euclidean algorithm, which yields integers $u, v$ such that $$\; ua+vn=\gcd(a,n) \qquad(\textit{Bézout's identity}).$$ Proceeding one step further yields a relation $xa+yn=0$, i.e. $\lvert xa\rvert$ is the l.c.m. of $a$ and $n$, so the positive integer $k$ sought for is $\lvert x\rvert$.