# Modular arithmetic problem

I need some hints for this problem from Dummit and Foote. (edit: added the full question verbatim for context)

Let $p$ be an odd prime and let $n$ be a positive integer. Use the binomial theorem to show that $(1+p)^{p^{n-1}} \equiv 1 \pmod{p^n}$ but $(1+p)^{p^{n-2}} \not\equiv 1\pmod{p^n}$. Deduce that $1+p$ is an element of order $p^{n-1}$ in the multiplicative group $(\mathbb{Z}/p^n\mathbb{Z})^{\times}$.

For the first part I just need to show that $$p^n \;\left|\; \sum\limits_{k=1}^{p^{n-1}}\binom{p^{n-1}}{k}p^k\right.$$ and it seems obvious enough that it should, since I think I can factor a $p^n$ out of each term, but Im having trouble actually proving this.

For the second part I am unsure what to do.

For reference it is problem 21. on page 60 of the third edition. (section 2.3).

Edit Ok I have managed to show the first part. From the lemma in the post Bill Dubuque linked to, which I could prove easily, if $z\equiv 1$ mod $p^n$ and $z = p+1$ then $z^p \equiv 1$ mod $p^{n+1}$. Since $z^p-1 = (z-1)(1+z+...+z^{p-1})$ and $(1+z+...+z^{p-1})\equiv 1+1+...+1 = p \equiv 0$ mod $p$.

So it follows by induction that $(p+1)^{p^{n-1}} \equiv 1$ mod $p^n$.

My problem here is that what Ive proven really only shows that $ord_p(z^p-1) \geq ord_p(z-1)+1$ as far as I can tell, so Im still not sure how I can show that $(1+p)^{p^{n-2}} \not\equiv 1\pmod{p^n}$. I think Im missing something here.

Edit II Ok, I snuck a peek at Pete's notes and I see what I was missing. Really the crucial step was writing $z = 1 + xp$, then I could see how to do it.

-
math.stackexchange.com/questions/20737/…, just-posted question and answers, tell you how many powers of $p$ you can factor out of $\binom{p^{n-1}}{k}$, so that would do it. –  Arturo Magidin Feb 6 '11 at 22:05
Yes, thanks Arturo, the first part at least becomes clear from that fact. I posted this problem before I had seen your other answer. –  AnonymousCoward Feb 6 '11 at 22:08
@Gottfried: You can use \pmod{p} in LaTeX to generate $\pmod{p}$; if you prefer not to have parentheses, you can use \bmod{p}. Then you don't jump in and out of LaTeX. –  Arturo Magidin Feb 7 '11 at 1:43
@GottfriedLeibniz: I'm interested in the reference to "Dummit and Foote" because I'm writing a small treatize on cyclic subgroups $b^n -1 (mod p)$ and came to the same problem and that I had to do the same proof myself because I did not see this anywhere. (We had a discussion about/a solution of this in the newsgroup sci.math but already some years ago - however may be found via google) –  Gottfried Helms Feb 7 '11 at 8:09
@helms, yes I had not seen this anywhere else, (at least thus far in the course or my previous undergrad classes). The solution in Pete's notes is very different from what I would have come up with on my own. I will add the full question from dummit for context. –  AnonymousCoward Feb 7 '11 at 17:50

Hint: use the binomial formula to establish the following fact.

Let $p$ be an odd prime number and $z$ an integer which is $1$ mod $p$. Then

$\operatorname{ord}_p(z^p − 1) = \operatorname{ord}_p(z − 1) + 1.$

Here, for a nonzero integer $N$, $\operatorname{ord}_p(N)$ is the largest power of $p$ which divides $N$.

(This is actually taken from a result in some notes of mine from an elementary number theory course, but since the OP asked for a hint only, I wish to obey by not posting the link.)

Note: the hint should serve to solve both parts of the question.

Added: Okay, for more help see Lemma 3 of these notes.

-
See also here math.stackexchange.com/q/6310/242 –  Bill Dubuque Feb 6 '11 at 22:24
Ok I think I have it from here. Thanks. –  AnonymousCoward Feb 6 '11 at 22:29
Im having trouble showing that $ord_p(z^p-1) \leq ord_p(z-1)+1$ whereas the $\geq$ was straight-forward. –  AnonymousCoward Feb 7 '11 at 0:37
Thank you for the help! –  AnonymousCoward Feb 7 '11 at 2:04