Associated Topics || Dr. Math Home || Search Dr. Math

Number Theory and Modular Arithmetic

```Date: 01/27/2006 at 15:55:05
From: ali
Subject: number theory

Suppose the order of an element mod(p) = n.  Is it true that the order
of this element mod(p^k) = n * p^{k-1}, where p is odd prime and
k > 1?  If yes, how would I prove that?

```

```
Date: 01/28/2006 at 14:56:43
From: Doctor Vogler
Subject: Re: number theory

Hi Ali,

Thanks for writing to Dr. Math.  That's a very good question.  The
statement that you made is almost true, but it is not quite true.  For
example, 3 has order 10 mod 11, but it also has order 10 mod 121.
Indeed, you could just take m = 1 + s * p^n, and then m has order 1
mod p, and order 1 mod p^n.  This provides a counterexample to the
conjecture, albeit a rather cheap one.  Nevertheless, it illustrates
the need for care in stating the theorem.  You might be tempted to
require m < p, but this is rather an artificial requirement, since it
has nothing to do with modular arithmetic.  In any case, that's why I
chose the example with m = 3 and p = 11.

So here is a better idea (although still not quite true):  Let k be
the largest integer with p^k divides m^n - 1.  Then the order of m mod
p^i is n if i <= k, and it is n*p^(i-k) if i >= k.

This is better, but you can still find a counterexample.  Try m=3 and
p=2.  And yet we can *almost* prove the above theorem.  So let's look
at what we can get.

Lemma 1:  If the order of m mod p^i is N, then the order of m mod
p^(i+1) is either N or pN.

Proof:  If we let

M = m^N,

(which is congruent to 1 mod p^i), then

m^(pN) - 1 = M^p - 1 = (M - 1)(M^(p-1) + ... + M + 1).

The first factor, M - 1, is divisible by p^i, and each term M^j in the
second factor is congruent to 1 mod p^i.  There are p such terms, so
the sum is congruent to p mod p^i.  That means that the product is
divisible by p^(i+1), and therefore the order of m mod p^(i+1) divides
the number pN.  But if p^(i+1) divides m^k, then so does p^i, which
means that the order (N) of m mod p^i must divide the order of m mod
p^(i+1).  The only choices are N and pN.

But we can get even more from this:  If the number i is at least 2,
then that means that the second factor is divisible by p and *not* by
p^2, which means that we can prove

Lemma 2:  If n^(pk) = 1 mod p^(i+1), and n^k = 1 mod p^2, then n^k = 1
mod p^i.

Proof:  n^(pk) - 1 = (n^k - 1)*(n^((p-1)k) + ... + n^k + 1) is
divisible by p^(i+1), and the second factor (the sum) is divisible by
p but not by p^2.  That means that the first factor must be divisible
by p^i.

So now we'd like to be able to put all of this together.  The idea is
that we need to know the order of m mod p, and the order of m mod p^2,
and we need to know the smallest power of p (past 2) where the order
of m mod p^i changes.  So we have

Theorem:  Given a prime number p, and an integer m not divisible by p,
of order n mod p, let k be the largest integer with p^k divides

m^n - 1.

(By the definition of n, k >= 1.)  If k >= 2, then the order of m mod
p^i is n when i <= k, and it is n*p^(i-k) when i >= k.  If k = 1, then
the order of m mod p^2 is pn, and let k' be the largest integer with
p^k' divides

m^(pn) - 1.

Then k' >= 2, and the order of m mod p^i is pn when 1 < i <= k', and
it is n*p^(i+1-k') when i >= k'.

Proof:  In the first case, where k >= 2, the order for i <= k is
easily seen to be n (by the definition of k).  For i = k + 1, we know
that the order is either n or pn by lemma 1, but it can't be n or else
k would have been larger.  So the order of m mod p^(k+1) is pn.  For
i > k, we prove by induction on i, with the initial case i = k + 1
already established.  Consider what the order of m mod p^(i+1) could
be.  It must be divisible by pn, so call it pns.  Since m^n = 1 mod
p^2, so too m^(ns) = 1 mod p^2, and so lemma 2 tells us that m^(ns) =
1 mod p^i.  That means that the order of m mod p^i must divide ns, and
since the order of m mod p^(i+1) is pns, that means that the order of
m mod p^i must be ns.  So you multiply by p at each step.

In the second case, where k = 1, the order of m mod p^2 is pn by lemma
1, and the order for 1 < i <= k' is easily seen to be pn (by the
definition of k').  The rest of the argument is much like that of the
above paragraph, so I won't repeat it all.

In conclusion, if you look at the order of m mod p, mod p^2, mod p^3,
mod p^4, and so on, there are two things that could happen.

Case 1:  You could start with order n, stay at n for possibly several
steps, and then start multiplying by p at every step, as in

n, n, n, n, n, n, np, np^2, np^3, np^4, np^5, ....

Case 2:  Or you could start with order n, then have order pn, and then
stay at pn for possibly several steps, before multiplying by p at
every step, as in

n, np, np, np, np, np^2, np^3, np^4, np^5, ....

Of course, the most common thing that happens is that you don't stay
for more than one step:

n, np, np^2, np^3, np^4, np^5, ....

So you might ask yourself if there are only a few cases where you stay
for longer.  It turns out that it is easy to construct examples where
you stay longer in the first case.  Pick any prime p, and choose m = a
mod p, and find the order n of a mod p.  Then if you write

m = a + b*p + c*p^2 + d*p^3 + ...,

and you multiply out

m^n = a^n + n*a^(n-1)*b*p (mod p^2),

you can solve for what b has to be in order to get k >= 2.  Then you
can multiply out

m^n mod p^3

and solve for what c has to be in order to get k >= 3, and so on.

Staying for several steps in the second case is harder, as you'll see
if you try to apply the above method to the second case.  You can
choose a prime p, and a residue a (mod p), and then compute the order
n of a mod p.  Then you solve the above equation to find out what b
should *not* be, and then you multiply out

m^(pn) = a^(pn) + pn*a^(pn-1)*b*p +
(1/2)pn(pn-1)*a^(pn-2)*b^2*p^2 (mod p^3)

and you solve this for b to see what it *should* be.  It turns out
that if p is an odd prime, then the last term is 0 mod p^3, and then
those two values will always be the same!  That means that case 2 can
only happen when p = 2.  So we can state this in a simpler theorem by
excluding the case p = 2:

Theorem:  Given an odd prime p, and an integer m not divisible by p,
of order n mod p, let k be the largest integer with p^k divides

m^n - 1,

and then the order of m mod p^i is n when i <= k, and it is n*p^(i-k)
when i >= k.

In the special case p = 2, however, you can have both cases happen.
In the case p = 2, if m is not divisible by p (m is odd), then it must
have order 1 mod 2.  If it is, in fact, 1 mod 4, then we get k >= 2,
and we have case 1, with

m = 1 + s*2^k

for some odd number s.  The other possibility is that it is 3 mod 4,
and then it has order 2 mod 4, and we compute k', the number of powers
of 2 that divide m^2 - 1, which must be at least 3.  It turns out
that, in this case,

m = -1 + s*2^(k'-1)

for some odd number s.

back and show me what you have been able to do, and I will try to
offer further suggestions.

- Doctor Vogler, The Math Forum
http://mathforum.org/dr.math/

```

```
Date: 01/30/2006 at 15:21:13
From: ali
Subject: Thank you (number theory)

Hello Doctor Vogler,

Thank you very much for helping me with my question.  Your answer was
very helpful.  I am really happy to find someone like you to deal with!
```
Associated Topics:
College Number Theory

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search