Hello,

--- Peter Kosinar <

goober@...> wrote:

> 1. The order of an integer 'a' modulo P^m =

> P^(m-1)*(Order of a mod P);

> where P is an odd prime .

>

> This conjecture doesn't seem to be valid.

Thankyou for providing counter examples,a special case

of this conjecture is proved to be true as follows:

If p is an odd prime and p(doesnot divide k), then

p^(m-1) is the order of a = 1+kp (mod p^m).

The proof can be found on page 43, A classical

introduction to modern number theory, Kenneth Ireland

and Michael Rosen, Second Edition, Springer

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

The proof of this has been given by Maverick as

follows:

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 modulo p is t,

and let s be the largest power 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

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.

This must be acknowlodged to mattgrime @ physicsforums

Cheers.

__________________________________

Yahoo! Mail

Stay connected, organized, and protected. Take the tour:

http://tour.mail.yahoo.com/mailtour.html