What are the conjectures about the order of an integer modulo prime numbers?

[BenGoodchild]

Two conjectures (or are they?):

1. The order of an integer 'a' modulo P^m = P^(m-1)*(Order of a mod P); where P
is an odd prime .

2. If a, m, and n are elements of Z and (a,mn) = 1, then Order of a mod mn =
QR/(Q,R); where Q = Order of a mod m and R = Order of a mod n and (Q,R) is the
greatest common divisor function.

For example:

Example 1:Let a =2 and P=7. Then the order of 2 mod 7 = 3 and the order of 2
mod 7^3 = 7^2(3)= 147.

Example 2: The Order of 2 mod 11^2 = 11*(Order of 2 mod 11) = 110

Example 3: The Order of 2 mod (3*7) = (Order of 2 mod 3)*(Order of 2 mod
7)/(U,V) = 2*3/1 = 6; where U = Order of 2 mod 3 and V = Order of 2 mod 7.

Are any of these two statements known? If so, could one point me in the
direction? If not can anyone prove or disprove?

 

[matt grime]

Firstly,in 2. the quantity QR/(Q,R) is commonly called the least common multiple of Q and R.

In any case the proof of (the correct version of) statement 1 appears in LeVeque fundmentals of number theory 4.4

Let p be an odd prime, and suppose p does not divide a. Futher suppose that the order of a module p is t, and let s be the largest powe of p dividing a^t-1.

If s=p then the order of a modulo p^n is still t, otherwise it is tp^n/s

The second one is, I think, obvious, isn't it?

If a^t is 1 modulo mn it is 1 modulo m and n thus Q divides t as does R, hence their least common multiple, call that L, divides t. Conversely it suffices to show that a^L=1 modulo mn, but we know a^L=km+1 and jn+1 for some integers k and j, that is km=jn for some choice of integers j and k, hence m divides j and n divides k as n and m are coprime, ie km=nmk' for some integer k' and thus a^L=nmk'+1=1 mod(mn).

Thus the order is divisible by L and divides L, so they must be equal.

 

[shmoe]

...as n and m are coprime...

I just wanted to point out that this assumption wasn't included in Ben's post, but it is needed.

 

[BenGoodchild]

I would just like to clarify this is not for me! And I hadn't really looked at the problem, just somebody on another forum pm'd me with it nad at the time I had no time to spare.

so, anyway thank you a lot guys for doing it for me, and Matt I have LeVeques book - in all its purple and red glory!

-Ben

 

[matt grime]

I just blindly assumed I'd read m and n were coprime otherwise the conjecture would have to be false. Or rather it would be unlikely to be true and I'd instantly start to look for a counter example and find one very quickly I imagine eg a=3, m=n=2.

Sometimes your mind just fills in the blanks.