## Computing orders mod 23

Hi Sir,

Sorry to disturb you again. I was working out the order of 3 mod 23, which i found to be 11. I did this the following way:

I was wondering if there was a simpler method to find the order instead of doing it using this way?

——————————————————————

Reply:

It’s hard to give a general answer for small moduli, where the improvement over brute force calculation tends to be rather incremental. It might be somewhat helpful to analyze the *possible orders*. In the case at hand, the non-zero elements modulo 23 under multplication form a group of order . Thus, the possible orders of elements are 1,2, 11, and 22. Since 3 clearly doesn’t have order 1 or 2, the possibilities are 11 and 22. But I don’t see an obvious way to rule out the possibility of 22 without calculating as you’ve done. On the other hand, if any element satisfies

then we can immediately conclude that the order is 22.

### Like this:

Like Loading...

*Related*

## One Comment

Not sure if this helps or is even relevant:

You can use a fast powering algorithm (number of operations reduces to logarithmic instead of linear) –

To calculate a^k (mod m):

(1) Form a table with three columns and first row: “k” “a” “1”;

(2) at each stage, form a new row as follows:

(a) the entry in column 1 is half the entry in column 1 of the previous row, ignoring fractions;

(b) the entry in column 2 is the square of the entry in column 2 of the previous row (modulo m);

(c) if the entry in column 1 of the previous row is even, the entry in column 3 is the same as the entry in column 3 of the previous row, otherwise it is the product (modulo m) of the entries oin column 2 and column 3 of the previous row.

—

(3) when the entry in column 1 is 0, the entry in column 3 of that row is the required power.

EXAMPLE: To calculate 2^11 (mod 23):

11 2 1

5 4 2

2 16 8

1 3 8

0 9 1

Therefore, 2^11 = 1 (mod 23).