Thursday, December 5, 2019

elementary number theory - Prove that $(1+p)^{p^{n-1}} equiv 1 pmod{p^n}$ but $(1+p)^{p^{n-2}} notequiv 1pmod{p^n}$, deduce $text{ord}_{p^n}(p+1)=p^{n-1}$



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.


Answer



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.


No comments:

Post a Comment

analysis - Injection, making bijection

I have injection $f \colon A \rightarrow B$ and I want to get bijection. Can I just resting codomain to $f(A)$? I know that every function i...