Re: Order modulo p^n (Number Theory)

On Mon, 15 Sep 2008 11:28:25 -0400, quasi <quasi@xxxxxxxx> wrote:

(Welcome back.)

On Mon, 15 Sep 2008 14:15:37 +0100, Angus Rodgers
<twirlip@xxxxxxxxxxx> wrote:

would someone please explain in gory detail just
how this one is supposed to go?

Here's one version, essentially along the lines described by the OP,
but with more details included ...

proposition:

If p is an odd prime then p+1 has order p^(n-1) mod p^n.

proof:

First, a lemma:

If p is an odd prime and p^r || x, where x in Z and r in N, then

I thought at first that by p^r || x you must mean p^r divides x
and p^{r+1} does not divide x, but it seems from the work below
that you just mean that p^r divides x. Is that right? ... no, I
see below that it isn't! ... OK, I've re-read the proof, and it
all makes sense now, although I'll have to read through it again
more slowly to make quite sure.

p^(r+1) || (x+1)^p - 1.

proof of the lemma:

Using the binomial theorem,

(x+1)^p - 1 = x^p + c_1*x^(p-1) + ... + c_(p-1)*x

where c_k = (p choose k).

Claim each term on the RHS, except the last, is divisible by p^(r+2),
and the last term is divisible by p^(r+1) but not by p^(r+2).

From this we would immediately get

p^(r+1) || (x+1)^p - 1

as required.

It remains to verify the claim.

First consider the leading term.

p^r || x => p^(pr) || x^k

Since p >= 3 and r >= 1,

p^(pr) || x^k => p^(3r) | x^p => p^(r+2) | x^p

Next consider the other terms.

For k = 1,...,(p-1)

p^1 || c_k

and

p^((p-k)*r) || x^(p-k)

hence

p^((p-k)*r+1) || c_k*x^(p-k)

For k = 1,...,(p-2),

(p-k)*r+1 >= 2*r+1 >= r+2

so p^(r+2) | c_k*x^(p-k)

Finally, for k = (p-1),

(p-k)*r+1 = r+1

so p^(r+1) || c_(p-1)*x

which completes the verification of the claim, and completes the proof
of the lemma.

OK, but that was rather more "gory detail" than I needed for such
a simple proof! The reason I asked for details is that everybody
else who has posted to this thread seems to suggest that the entire
proof is just a simple matter of expanding something by the Binomial
Theorem and proving that all or most of the binomial coefficients
are divisible by p, or by some power of p, in a way which is too
obvious to need explaining. Both of my proofs are more complicated
than this outline suggests; and so is yours (although this lemma
isn't - unless I missed something in my quick scan through it -
I'll read it more thoroughly later).

corollary:

If p is an odd prime, and n in N, then

p^n || (p+1)^(p^(n-1)) - 1

proof:

Proceed by induction.

This is quite like my first proof, which was a proof by induction
on n that:

(p + 1)^{p^{n-2}} = 1 + p^{n-1} (mod p^n)

for all odd primes p, and all integers n >= 2. The messy part was
that I used a trinomial expansion; and I still suspect that I made
unnecessarily heavy weather of it. (However, it didn't need any
lemmas! And it was pretty straightforward - just a bit messy.)

As in your proof, I applied this result twice to deduce the order
of p + 1 (mod p^n).

The verification for n=1 is immediate.

Next, suppose the corollary is true for n=m, for some m in N.

Thus, p^m || (p+1)^(p^(m-1)) - 1.

Letting x = (p+1)^(p^(m-1)) - 1, and applying the lemma,

p^(m+1) || (x+1)^p - 1

that is,

p^(m+1) || (p+1)^(p^m) - 1

which completes the induction, and proves the corollary.

That's neat. Definitely neater than my proof, especially if the
proof of the lemma is written out with less "gore"!

Returning to the proof of the proposition, let s be the order of (p+1)
mod p^n.

By the corollary,

p^n | (p+1)^(p^(n-1)) - 1

hence

(p+1)^(p^(n-1)) = 1 (mod p^n)

It follows that s | p^(n-1).

Applying the corollary again,

p^(n-1) || (p+1)^(p^(n-2)) - 1

hence

p^n does not divide (p+1)^(p^(n-2)) - 1

Ah ... so || does have the interpretation I at first imagined.

This is very nice.

Equivalently

(p+1)^(p^(n-2)) /= 1 (mod p^n)

and hence, s does not divide p^(n-2).

It follows that s = p^(n-1), which completes the proof.

Although I like the proof a lot, I have to object that it does
not explain what everybody else had in mind, which is what was
worrying me - making me think that I had missed something that
should be utterly obvious.

For what it's worth, my second proof (attempting to follow the
lines that various hints in this thread seemed to be suggesting)
proved that for m = n - 1 or n - 2, p^{n-k} divides binom{p^m}{k},
for k = 4, ..., n - 1 (the cases k = 2 and k = 3 being easily
disposed of separately, the only minor complication being when
k = p = 3), by using the fact that the highest power of p that
divides k! is p^s, where s = floor(k/p) + floor (k/p^2) + ...
<= k/p + k/p^2 + ... = k/(p - 1) <= k/2 <= k - 2, therefore the
binomial coefficient is divisible by at least p to the power of
m - s >= (n - 2) - (k - 2) = n - k, as required. (One word: ugh!)

So I still don't know if I've been making unnecessarily heavy
weather of this. Your proof, assuming it's valid as it seems
to be, seems to be the way to go, but I still don't know what
everybody else had in mind!

--
Angus Rodgers
(twirlip@ eats spam; reply to angusrod@)
Contains mild peril
.

Relevant Pages

  • Re: Order modulo p^n (Number Theory)
    ... If p is an odd prime then p+1 has order p^mod p^n. ... The verification for n=1 is immediate. ... which completes the induction, and proves the corollary. ... s does not divide p^. ...
    (sci.math)
  • Re: Order modulo p^n (Number Theory)
    ... If p is an odd prime then p+1 has order p^mod p^n. ... The verification for n=1 is immediate. ... which completes the induction, and proves the corollary. ... s does not divide p^. ...
    (sci.math)
  • Re: Fermats last theorem and a counter example
    ... has at least one odd prime factor and all prime factors of ... divide ... has at least one odd prime factor and all prime factors of (z-y) ... has at least one odd prime factor and all prime factors of (z-x) ...
    (sci.math)
  • Re: Fermats last theorem and a counter example
    ... FLM states simply that the following equation: ... All odd prime factors of must be some prime ... factors of z-y divide x. ... If there are no odd prime factors for z-x, ...
    (sci.math)
  • Re: Definition for UFD
    ... Lukas-Fabian Moser schrieb: ... for all p by induction on the number t of all p such that v_p does not ... How can you assert that p_0 must divide one of the irreducibles? ...
    (sci.math.research)
Loading