Re: Order modulo p^n (Number Theory)

On Sep 15, 2:21 am, Angus Rodgers <twir...@xxxxxxxxxxx> wrote:
On Sun, 14 Sep 2008 08:01:55 -0700 (PDT),
"dark.sorrow.myst...@xxxxxxxxx"





<dark.sorrow.myst...@xxxxxxxxx> wrote:
On Sep 15, 12:37 am, Tonico <Tonic...@xxxxxxxxx> wrote:
On Sep 14, 3:56 pm, "dark.sorrow.myst...@xxxxxxxxx"

<dark.sorrow.myst...@xxxxxxxxx> wrote:
Hello need some help with a question in number theory im attempting

Let p be an odd prime and n > 1 an integer. Find the order of (1 + p)
modulo (p^n).

Cheers

***********************************************************

Hints:

1.- Try with p = 3, 1 + p = 4 and n = 1, 2, 3, 4, and then with p = 5
and 1 + p = 6, and then even with p = 7 and 1 + p = 8...

2.- Now prove your guess or huntch: use Newton's binomial with

(1 + p)^(p^(n-1))...you may want to show that the binomial

coefficient [p^r : r] is divisible by p iff r is a multiple of p...

Regards
Tonio

Cheers, thanks you for your help, I  should of used the examples to
find the order. Then try prove it.  was trying to come up with the
order via theorems and was getting know where. Thanks Tonio on the
binomial, that really helped with the proof ofthe order.

Can you explain your proof?

My original "proof" was a load of dingo's kidneys (as I would have
realised if I had typed it up neatly to post to sci.math). I think
I've fixed it now, but I'm still reluctant to post it until you've
shown your work.

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

- Show quoted text -

Hey,

well first through writing a few examples I saw that the order should
be p^n-1.
After that I used Newtons binomial and showed that p^n divides all the
coeffients apart from when k=0. (lower bound on my sum) which gives a
remainder 1, giving the required (1+p)^(p^n-1)= 1 mod(p^n). So either
that is the order or the order divides p^n-1. Then i showed for any
powers less than n-1 the expansion dosent give the remainder 1 and the
coefients are not divisible by p^n. :)

cheers, sorrow
.

Relevant Pages

  • Re: Bug in expr ?
    ... >> Note however that remainder (aka modulo) is negative, ... Modulo numbers are never negative. ... Remainder can be whatever you ... "Modulo" has multiple meanings, especially accoring to context, e.g. mathematics vs. computing. ...
    (comp.lang.tcl)
  • Re: Representing sets of points
    ... defined in a coordinate system by these ... Given an integer m, we say that "a and b are congruent modulo m", ... This is usually called "division with remainder", ... this is seldom used by mathematicians. ...
    (sci.math)
  • Re: Integer division, surprising results
    ... > A remainder is always positive, ... Remainders are always positive, but modulo can be ... There are pros and cons for doing it either ...
    (comp.lang.python)
  • Re: do something every 1000 records or so
    ... On May 15, 10:36 am, Richard Senior ... I think you need the modulo operator. ... This gives the remainder of an ... it print only the first time? ...
    (comp.lang.java.programmer)
  • Re: % operator incompatibility...
    ... > Try Pascal and Ada as well. ... Fortran defines two functions: ... MODULO - the modulo function ... I think the confusion arises because people assume that the remainder ...
    (comp.lang.tcl)