## 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:

$3^2 \ \ (23)= 9$
$3^3 \ \ (23)= 4$
$3^4 \ \ (23)= 12$
$3^5 \ \ (23)= 13$
$3^6\ \ (23)= 16$
$3^7 \ \ (23)= 25$
$3^8 \ \ (23)= 6$
$3^9 \ \ (23)= 18$
$3^{10}\ \ (23)= 8$
$3^{11}\ \ (23)= 1$

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 $22=2\times 11$. 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 $a$ satisfies

$a\ \ (23)\neq 1, a^2\ \ (23)\neq 1, a^{11}\ \ (23)\neq 1,$

then we can immediately conclude that the order is 22.

### One Comment

1. Posted September 26, 2009 at 5:47 pm | Permalink | Reply

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