Re: Order modulo p^n (Number Theory)

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

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.

corollary:

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

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

proof:

Proceed by induction.

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.

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

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.

quasi
.

Relevant Pages

  • Re: Order modulo p^n (Number Theory)
    ... If p is an odd prime then p+1 has order p^mod p^n. ... and p^does not divide x, but it seems from the work below ... Theorem and proving that all or most of the binomial coefficients ... This is quite like my first proof, which was a proof by induction ...
    (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)