Finding the order of an element in the group of integers modulo n with addition

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.

2 Answers

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$.

Let's think $a \in G$ we want to find

$a*m \equiv 0 \mod n$ where $m$ is the smallest such natural number.

$am \equiv 0 \mod n$ means

$am = kn$ for some $k$

So $m = kn/a$

Case 1: $\gcd(a,n) = 1$.

.. $a|k$.

So $m = n(k/a)$ so the order is a multiple of $n$. As the order is the minimum such value,

the order $m = n$.

Case 2: $\gcd(n,a) = d$

$m = kn/a = \frac{k*(n/d)}{a/d}$

but as $a/d$ and $n/d$ are relatively prime this is exactly as it was in case 1:

$(a/d)|k$ so order is a multiple of $n/d$. And we want the order to be minimum so...

$m = (\frac k{a/d})(n/d)$ so the order $m = \frac{n}{\gcd(a,n)}$.

So that's the order of $a$: $\text{ord}(a) = \frac{n}{\gcd(n,a)}$.