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.

Advertisements

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: