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.

  • 1
    $\begingroup$ Well, you don't need to write down "all the multiples". We know that, if $\gcd(a,n)=1$ then the order $a\pmod n$ is a divisor of $\varphi(n)$. All you need to do is to check those divisors. Of course, that can still be quite tedious. $\endgroup$ – lulu Sep 27 '16 at 22:52
  • $\begingroup$ @lulu That's for the multiplicative group, the question is about the additive group. $\endgroup$ – arkeet Sep 27 '16 at 22:57
  • $\begingroup$ @arkeet Really? Never saw anyone compute that before. Just $\frac {m}{\gcd(m,a)}$ I suppose. $\endgroup$ – lulu Sep 27 '16 at 23:01

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.