general form of the multiplicative order

[juergen]

Hi,

are there any proofs about how the multiplicative order of numbers
is calculated which include powers of primes?
I put them in three categories:

1. Numbers of the Form p^n where p is a prime and n a natural number >
1

2. Numbers in general of the from a^m where a and m are natural
numbers > 1 and both can be composite

3. Numbers of the form b*a^m where all three can be natural numbers.

I know the following two rules:

Ord(x,m) divides Phi(m) (Ord(x,m) means Order x (mod m))
and
Ord(x,a*b) = least common multiple of [Ord(x,a) ; Ord(x,b)] if a and b
share no common divisor.

By this it is almost clear, that the Order of Numbers of category 1.
should look like

(Ord(x,p) * p^(n-1)

but I don't have a proof for this. If you have one, It would be really
nice if you could post it here, or post the address of it :o)

****

For 2. I did some computation, because at first I thought that I could
also apply the fromula above to this numbers, but it seems that this
is not true.
For example if you look at the orders of the powers of 6, 10 or 21:

6^1 => 2 6^2 => 6 6^3 => 18 (base 5)
10^1 => 4 10^2 => 20 10^3 => 100 (base 3)
21^1 => 6 21^2 => 42 21^3 => 882 (base 2)

The first line means, that Ord(5,6^1) = 2 and Ord(5,6^2)=6.
The second line means, that Ord(3,10^1)=4 and so on...

The most interesting thing about this is, that the orders of composite
powers doesn't follow the rule mentioned for prime powers. I guess the
rule here is something like:

Ord(x,a))*(a / gcd(Ord(x,a);a))^(m-1)

But please note that this is just a guess. I didn't check enough
numbers nor do I have a proof. But maybe there is already a proof
about the acual form of the order for such numbers?!

****

For 3

I think that depending on the actual form of the order of composite
powers (numbers of the second form) the form of this numbers can most
likely be derived using the rule:

Ord(x,a*b) = least common multiple of [Ord(x,a) ; Ord(x,b)]

Here I have some examples (Ord(2,7*...)):

7 => 3
7*3 => 6 => lcm [Ord(2,7) ; Ord(2,3)]
7*3*3 => 6 => lcm [Ord(2,7) ; Ord(2,3*3)]
7*3*3*3 => 18
7*3*3*3*3 => 54

3*7 => 6 (see above)
3*7*7 => 42
3*7*7*7 => 294

It again gets more interesting if the base is composite (here 10):


10 => 4 => Ord(3,10)=4
5 => 4 => Ord(3,5)=4
2 => 1 => Ord(3,2)=1
7 => 6 => Ord(3,7)=6

7*10 => 12 => lcm [Ord(2,7) ; Ord(2, 10)]
7*10*10 => 60 => lcm [Ord(2,7) ; Ord(2, 10*10)]
7*10*10*10 => 300 => lcm [Ord(2,7) ; Ord(2, 10*10*10)]
7*10*10*10 => 1500 => lcm [Ord(2,7) ; Ord(2, 10*10*10*10)]

Note that the orders don't increase by factor 10 but only by factor
5.

This behaviour could be explained by a rule like the one stated above
{ Ord(x,a))*(a / gcd(Ord(x,a);a))^(m-1) }.



You could write each natural number in this form:

n = p1^a1 * p2^a2 * p3^a3 * .... * pn^an

where py (for each y in {1,2,3,...n}) >0 and no two ay are equal and all of them are primes.

Using this notation I guess you could compute the order of a composite number with the following fromula:

(lcm [Ord(x,p1);Ord(x,p2);Ord(x,p3);....;Ord(x,pn)]) * A

where

A := B / gcd(B;C)
B := p1^(a1-1) * p2^(a2-1) * p3^(a3-1) * .... * p1^(an-1)
C := Ord(x , p1)^(a1-1) * Ord(x , p2)^(a2-1) * Ord(x , p3)^(a3-1)* ... Ord(x , pn)^(an-1)

This formula, if it is really right could also handle the special case where all the factors of the number are relative prime to each other (for this case I know that the form of the order has already been proved to be lcm [Ord(x;p1); Ord(x;p2) ; ... Ord(x;p3)]. In other words the prooved case is the simplified case of the form above where all elements a1 to an are equal to 1.
The second hint that it could be right is, that numbers of this form always divide Phi, because all the factors of the number are divisors of Phi.

It would really be nice if you could forward me to sources about this topic.
I would appreciate any and all help, since I don't even know a proof of the first form, but I guess that this has already been proofed :o)

Thank you in advance

[juergen]

Hello all,

I think to proof the first is easy. I think I could do this, but the others seem to be much more complicated. I try to figure out a rule here, but it seems not to be obvious to me.
I wonder if there was really no research on that, or if my question makes no sense, since maybe I miss some important point?!

Please note that this questions are also related to mersenne numbers or mersenne like numbers, because if you consider the order 2 of a number n it means that you are searching for the smallest mersenne number for which

n is divisor of 2^x-1

if you have found this mersenne number (x>0) than the exponent x is the order of this number n.

To be honest in my opinion the mersenne numbers with composite exponents are much more interesting than the ones with prime exponents, but of course the ones with composite exponents are never Primes. I think that they are much more important for number theory in general!

The formula for composite numbers which I wrote in my last posting is not correct. I tried to figure out a rule, how the formula for the order is built, but there seems to be no obvious rule.

For example look at the orders (3) of the powers of 10.

Ord 10^1 = 4 (mod 3)
Ord 10^2 = 20 (mod 3)
Ord 10^3 = 100 (mod 3)
Ord 10^4 = 500 (mod 3)
Ord 10^5 = 5000 (mod 3)
Ord 10^6 = 50000 (mod 3)

From 1 to 4 the order always increases by factor 5, after 4 it increases by 10. What is the rule about this? Isn't it strange that there is a formula which works for all orders except for the ones which have prime factors with exponents > 1?

If you know anything about this, or you know where I could search for further informations about this, please help

Kind regards

Juergen

Originally Posted by juergen

Hi,

are there any proofs about how the multiplicative order of numbers
is calculated which include powers of primes?
I put them in three categories:

1. Numbers of the Form p^n where p is a prime and n a natural number >
1

2. Numbers in general of the from a^m where a and m are natural
numbers > 1 and both can be composite

3. Numbers of the form b*a^m where all three can be natural numbers.

I know the following two rules:

Ord(x,m) divides Phi(m) (Ord(x,m) means Order x (mod m))
and
Ord(x,a*b) = least common multiple of [Ord(x,a) ; Ord(x,b)] if a and b
share no common divisor.

By this it is almost clear, that the Order of Numbers of category 1.
should look like

(Ord(x,p) * p^(n-1)

but I don't have a proof for this. If you have one, It would be really
nice if you could post it here, or post the address of it :o)