Re: [PrimeNumbers] Order of an integer
--- Peter Kosinar <goober@...> wrote:
> 1. The order of an integer 'a' modulo P^m =Thankyou for providing counter examples,a special case
> P^(m-1)*(Order of a mod P);
> where P is an odd prime .
> This conjecture doesn't seem to be valid.
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) =The proof of this has been given by Maverick as
> 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.
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
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
Thus the order is divisible by L and divides L, so
they must be equal.
This must be acknowlodged to mattgrime @ physicsforums
Stay connected, organized, and protected. Take the tour: