## Re: [PrimeNumbers] Order of an integer

Expand Messages
• Hello, ... 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
Message 1 of 3 , Jun 1, 2005
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
Your message has been successfully submitted and would be delivered to recipients shortly.